Curriculum design assignment

Design topic and content

There are six design topics. You can choose one of them.

(1)Binary balanced sort tree

[problem description]

Starting from an empty tree, in the process of creating, we should ensure the order of the tree and make some adjustments to the balance of the tree. Finally, the binary sort tree should be transformed into binary balanced sort tree.

[basic requirements]

1) create (insert, adjust);2) Output.

(2)Design and implementation of hash table

[problem description]

The hash table is designed to realize the telephone number searching system.

[basic requirements]

1) Suppose that each record has the following data items: telephone number, user name and address;

2) Input each record from the keyboard, and set up hash table with telephone number and user name as keywords respectively;

3) Adopt certain methods to solve the conflict;

4) Search and display the record of given telephone number;

5) Find and display records for a given user name.

(3)The making of address book

[problem description]

Using the bidirectional linked list in data structure as the data structure, combined with the basic knowledge of C language. Write an address book management system. In order to apply the data structure knowledge to the actual software development.

[basic requirements]

The system should complete the following functions:

1) Enter information - enter ():

2) Display information - display ():

3) Search (), with name as the key word;

4) Delete ();

5) Save ():

6)load ();

(4)Conversion of number system

[problem description]

Any given M-ary number x, please achieve the following requirements

[basic requirements]

1) Find the decimal value of this number x (expressed in HD)

2) Realize the conversion of X to any non-m-ary number.

3) stack or array is used to achieve the above requirements .

DFS traversal of Graphs

[problem description]

Starting from any given vertex (called initial point) in a given graph, all vertices in the graph are accessed along the edge of the graph according to some search method, so that each vertex is accessed only once.Please use DFS depth first search process to realize traversal.

[basic requirements]

1) First, create any graph;

2) Implementation of recursive and non recursive algorithms for DFS of graph

3) It is required to use adjacency matrix or adjacency table to store.

(6)Ranking synthesis

[problem description]

Use random function to generate N random integers, and sort these numbers in various ways.

[basic requirements]

1) At least three methods are used to solve the above problems (prompt, quick sort must be done o other available methods are insert sort, Hill sort, bubble sort, select sort, heap sort and merge sort). The sorted results are saved in different files.

2) Count the performance of each sorting method (based on the time it takes to run the program on the computer), and find out two faster methods.

3) If four or more methods are used, additional points can be given.

Submission

1) Submit the curriculum design report; 2) Submit the source program.

Final Report

1.Problem Analysis (15 points)

2.Algorithm Design (30 points)

3.Source Code (30 points)

4.Program Output (10 points)

5.Conclusion (15 points)