Detailed unidirectional linked table operation (2) [the end]

/ *

Then, when the test is compiled, please put the corresponding function and test code in the relevant place of the previous speech code):

Sort (selection, insert, bubbling)

Insert (orderly)

* /

/ * ================================================ Author : RERLI Time: 2003-12-08 Purpose: To learn, modify, delete, insert (disorderly, order), output, order (selection, insertion, bubbling), order (selection, insertion, bubbling)

Explanation: Compilation does not have any errors to generate an EXE file. This program TC2.0 compiles the generated EXE file, the following error occurs when running the input node (there is no error in TC2.01): Scanf: floating point formats not link Abnormal Program Termination, namely: Struct Student float score field in the input When it doesn't recognize the FLOAT, it can be changed to Long Score. But in TC2.01, Float Score recompiles, links, and runs very normal. So I think this is bug in TC2.0 in the structure type. ================================== =============== * /

/ * ========================== function: Select sort (from small to large) return: Pointer to the chain table header ==== ======================= * /

/ * Selecting the basic idea of ​​sorting is to repeat the node value (which is the field that is sorted by the field, our value of Num is the key value), and recombine into one Link list.

I think the list of writings, the key is to understand: HEAD stores the address of the first node, head-> next stores the address of the second node; any node P's address, only the previous one The NEXT of the node is obtained.

Select order of one-way linked list: ----> [1] ----> [3] ----> [2] ...----> [n] ----> [ NULL] (original list) Head 1-> Next 3-> Next 2-> Next n-> Next ----> [NULL] FIRSTTAIL

----> [1] ----> [2] ----> [3] ...----> [n] ----> [NULL] (sorted back chain) FIRST 1 -> Next 2-> Next 3-> Next Tail-> Next

Figure 10: Link list with n nodes Select sort

1, first look at the minimum in the original list, put it in another empty list; 2. Place the first node in the empty list, generate a sequence linked list, and let it in the original list Separate (at this time, pay attention to the first node or the middle other node); Then it becomes its tail pointer; * / struct student * selectsort (strunt student * head) {structure * first; / * Straighten a sequential sheet head pointer * / struct student * tail; / * Order order Chain tail pointer * / struct student * p_min; / * Reserved key value smaller node pointer * / struct student * min; / * Store minimum node * / struct student * p; / * Current comparison Node * / first = null; while (head! = Null) / * Node that is the smallest value value in the list. * / {/ * Note: Here the for statement is to reflect the place of selecting the sorting idea * / for (p = head, min = head; p-> next! = Null; p = p-> next) / * cycle over the list The node finds the smallest node at this time. * / {If (p-> next-> num num) / * Find a node that is smaller than the current MIN. * / {P_min = p; / * Save the front drive node of the node: Obviously P-> NEXT is P. * / Min = p-> next; / * Save the key value smaller node. * /}} / * After the above For statement, you have to do two things; one is to put it in an ordered chain table; second, according to the corresponding conditions, arrange it to leave the original list. * / / * The first thing * / if (first == null) / * If the ordered chain list is still an empty list * / {first = min; / * The first time the key value is minimized. * / Tail = min; / * Note: The tail pointer makes it point to the last node. * /} Else / * There is already a node * / {tail-> next = min; / * to put the minimum node found to the end, that is, let the NEXT of the tail pointer points to it. * / Tail = min; / * The tail pointer also points to it. * /}

/ * Second thing * / if (min == head) / * If the minimum node found is the first node * / {head = head-> next; / * obviously let Head point to the original Head-> next, ie The second node, OK * /} else / * If it is not the first node * / {p_min-> next = min-> next; / * NEXT of the front minimum node point to the NEXT of the current min, so let MIN Leave the original list. * /}} If (first! = NULL) / * The loop ends to get an orderly linked table first * / {tail-> next = null; / * Next node of the one-way linked list should point to null * /} head = first Return head;

/ * ========================== function: Direct insertion sort (by small to large) return: Pointer to the chain table header === =============================== * /

/ * The basic idea of ​​direct insertion sorting is to assume that the front N-1 node of the linked list is already the key value (which is the field that is sorted, and we take the scholar Num as the key value), for the node N in this sequence Look for insertion positions, so that the new sequence after n is inserted is still orderly. According to this kind of thought, the linked list can be executed from the head until the end of the head, and the unordered linked table can be changed to an ordered list. Direct insertion sort illustration of one-way linked list: ----> [1] ----> [3] ----> [2] ...----> [n] ----> [Null] (original list) HEAD 1-> Next 3-> Next 2-> Next N-> Next

----> [1] ----> [NULL] (From the original list, take the first node as only one node's ordered list) HEAD Figure 11

----> [3] ----> [2] ...----> [n] ----> [NULL] (Original listing of nodes for direct insertion) First 3 -> Next 2-> Next N-> Next Figure 12

----> [1] ----> [2] ----> [3] ...----> [n] ----> [Null] (Sort Back List) HEAD 1 -> Next 2-> Next 3-> Next N-> Next

Figure 13: Direct insertion of N nodes

1. First in the original list with the first node as a ordered list, the remaining nodes are the pending node. 2. Take the node from the linked list of Figure 12 to locate inserts in the linked list of Figure 11. 3, the above figure, although two linked lists are drawn, there is only one linked list. In sorting, the substance only has only increased the head pointer first for pointing to the sorting node. At this point, readers must make it clear, or it may think that it is the same as the selection method above. * / struct student * insertsort (strunt news * head) {structure * first; / * For the original list of nodes * / struct student * t; / * Temporary pointer variable: Insert node * / Struct student * p; / * Temporary pointer variable * / struct student * q; / * Temporary pointer variable * / first = head-> next; / * Original list remaining node link table for direct insertion sort: can be based 12 is understood. * / Head-> next = NULL; / * Ordered chain table containing only one node: It can be understood according to Figure 11. * / while (first! = null) / * Traversed the remaining unordered linked list * / {/ * Note: Here the for statement is to reflect the place of direct insertion of sorting ideas * / for (t = first, q = head; Q! = null) && (Q-> Num num)); P = q, q = q-> next); / * Disorder node finds inserted positions in an ordered list * / / * exits For loop, it is to find the inserted position * / / * Note: According to the reason, this sentence can be placed in the position that is noted below, but it is not possible. Reason: If you understand the third article above, you will know. * / First = first-> next; / * The node in the unordered linked table is leaving so that it is inserted into the ordered list. * / If (q == hEAD) / * before plugging before the first node * / {head = T;} else / * p is Q's pre-drive * / {p-> next = t;} t-> Next = Q; / * Complete the insertion action * / / * first = first-> next; * /} return head;}

/ * ========================== function: bubble sort (by small to large) returns: Pointer to the chain table header === =============================== * /

/ * The basic idea of ​​direct insertion sorting is to compare and adjust the two nodes of the neighboring two nodes in the currently not row, and to make the key value (which is sequenced by it. Field, we take the school number Num as the key value) The larger node is down, and the key value is smaller. That is, each time the two adjacent nodes are discovered, they interchange them when they are sorted and sorted.

Sprinkler order of one-way linked list: ----> [1] ----> [3] ----> [2] ...----> [n] ----> [NULL] (original list) HEAD 1-> Next 3-> Next 2-> Next n-> Next ----> [1] ----> [2] ----> [3].. . ----> [N] ----> [Null] (Sort Back List) HEAD 1-> Next 2-> Next 3-> Next N-> Next N-> NEXT

Figure 14: Link table with n nodes bubble

Any two adjacent nodes p, q position interchange graphic: Suppose P1-> Next point P, then obviously p1-> next-> next, point q, p1-> next-> next-> next, point to Q After the subsequent node, we save P1-> Next-> Next pointers with P2. That is: P2 = P1-> Next-> Next, there is: [] ----> [p] ----------> [q] ----> [] (before sort) P1-> Next P1-> Next-> Next P2-> Next Figure 15

[] ----> [q] ----------> [P] ----> [] (after ordering)

Figure 16

1. After sorting, the Q node points to the P node. Before adjusting points, we want to save the original P point to the pointing node address, namely: p2 = p1-> next-> next; 2, step down next step, sort Figure 16 P1-> Next-> Next 指 P2-> Next, so p1-> next-> next = p2-> next; 3, in Figure 15 P2-> Next, the pointing pointing After sorting, the point to the q in Fig. 16 becomes pointed to P, and the original P1-> next is pointing P, so p2-> next = p1-> next; 4, in Figure 15 P1-> Next Pointing P, sorting FIG. 16 P1-> Next-> NEXT (ie p2) is P1-> next-> next (ie, p2) means Q. So, to this, we have completed Sequential exchange of neighboring two nodes. 6. The following program describes that a little bit is to record the position of each last node sinking so that we don't have to scan from head to tail every time, you only need to scan to record points. Because the following is already in sequence. * / struct student * bubblesort (strunt news * endpt; / * Control loop comparison * / struct student * p; / * Temporary pointer variable * / struct student * p1; struct student * p2;

P1 = (STRUCT Student *) Malloc (LEN); P1-> Next = Head; / * Tour: We add a node, placed in front of the first node, mainly for easy comparison. Because the first node does not have a pre-drive, we cannot exchange the address. * / Head = p1; / * Let Head point to P1 nodes, after ordering, let's release the P1 node * /

For (EndPt = NULL; ENDPT! = Head; EndPt = P) / * Combined with the 6th point to understand * / {for (p = p1 = head; p1-> next-> next! = endpt; p1 = p1-> next ) {If (p1-> next-> NUM> P1-> Next-> Next-> Num) / * If the front node key value is larger than the key value of the back node, exchange * / {p2 = p1-> Next -> Next; / * Combined with 1 point understanding * / p1-> next-> next = p2-> next; / * Combined with the 2nd point of understanding * / p2-> next = p1-> next; / * Combined with the third Point understanding * / p1-> next = p2; / * Combined with the 4th point of understanding * / p = p1-> next-> next; / * Combined with the 6th point of understanding * /}}} p1 = head; / * P1 Remove * / head = head-> next; / * Let Head point to the first node * / free (p1); / * Release P1 * / p1 = null; / * P1 is set to NULL, guarantee Generate a "wild pointer", ie, the address uncertain pointer variable * /

Return head;

/ * ========================== function: insert a node of an ordered chain table (from a small to large) return: Point to the Link table table Head pointer =================================== * /

/ * Order Lin List Insert Node Schematic:

----> [NULL] (empty preface table) HEAD

Figure 18: Empty sequential chain table (empty order chain table is solved, directly let Head point to it.)

The following discussion is an ordered chain table that is not empty. ----> [1] ----> [2] ----> [3] ...----> [n] ----> [NULL] HEAD 1 -> Next 2-> Next 3-> Next N-> Next

Figure 18: Ordered chain table with n nodes

There are two situations where the location of the Node node is inserted: First, the second is before or after another node.

----> [Node] ----> [1] ----> [2] ----> [3] ...----> [n] ----> [Null ] Head node-> Next 1-> Next 2-> Next 3-> Next N-> Next

Figure 19: Node node inserted before the first node

----> [1] ----> [2] ----> [3] ...----> [node] ...----> [n] ---- > [Null] Head 1-> Next 2-> Next 3-> Next Node-> Next N-> Next

Figure 20: Node node After inserting other nodes * / struct student * sortinsert (strunt news * head, struct student * node) {struct student * p; / * p Save the address of the node that needs to be checked * / Structs * T ; / * Temporary pointer variable * / if (Head == null) / * Processing empty ordered chain table * / {head = node; node-> next = null; n = 1; / * After the insertion, the total number of nodes plus 1 * / return head;}

P = head; / * Ordered chain table is not empty * / while (p-> num num "= null) / * p The number of nodes pointed to the node is small than the student number inserted into the node, and it Not equal to NULL * / {T = P; / * Save the forefront of the current node so that the post-process processing * / p = p-> next; / * is moved after one node * /} if (p == head) / * Just insert the first node before * / {node-> next = p; head = node;} else / * After inserting other nodes * / {t-> next = node; / * Add the Node node * / node- > next = p;} n = 1; / * After the insertion, the total number of nodes plus 1 * / return head;

/ *

The test code is as follows:

* /

/ * Test selectsort (): Please compile to remove the release block * /

/ * Head = selectsort (Head); Print (Head); * / / * Test INSERTSORT (): Please compile to remove the release block * /

/ * Head = Insertsort (Head); Print (HEAD); * /

/ * Test bubblesort (): Please compile time to remove the release block * /

/ * Head = bubblesort (Head); Print (Head); * /

/ * Test SortInsert (): Create a linked list above, please pay attention to the number of NUMs from small to large when entering the node. Please compile to the release block * /

/ * STU = (Struct Student *) Malloc (LEN); Printf ("/ NPLEase:"); Scanf ("% ld,% f", & stu-> num, & stu-> score HEAD = SortInsert (HEAD, STU); Free (STU); Stu = NULL; Print (Head); * /

(Full text)