/ * ================================================ Author : RERLI Time: 2003-12-05 Purpose: To learn, delete, insert (disorderly, orderly), output, order (selection, insertion, bubbling), output, 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. ================================== =============== * /
/ * Of the one-way linked list: ----> [null] Head
Figure 1: Empty link table ----> [p1] ----> [p2] ...----> [pn] ----> [null] Head P1-> Next P2-> Next Pn -> Next
Figure 2: Link list with n nodes * /
#include
Struct student {long Num; / * Learn * / float score; / * score, other information can continue to add field * / struct student * next; / * points to the pointer of the next node * /};
INT N; / * Number total * /
/ * ========================== function: Create a node Returns: Pointer to the chain table header ========== ================= * / Struct student * create () {strunt * {/ * header null * / struct student * p1 = null; / * P1 Save the created new Node's address * / struct student * p2 = null; / * p2 Save the address of the last node of the original list * / n = 0; / * Creating the total number of nodes in the frontlin table is 0: empty list * / p1 = (Struct Student * ) malloc (len); / * Open a new node * / p2 = p1; / * If the node is successful, P2 will save its pointer to use * /
If (p1 == null) / * node opens up unsuccessful * / {Printf ("/ ncann't create ketf (" / ncann't create! / n "); return null;} else / * node opened success * / {Head = null; / * Start Head pointing null * /
Printf ("" "", score: ", n 1); scanf ("% ld,% f ", & (p1-> num), & (p1-> score); / * Enter data * /} while (p1-> num! = 0) / * As long as the school number is not 0, continue to enter the next node * / {n = 1; / * Node total number increase 1 * /
If (n == 1) / * If the total number of nodes is 1, head points to the node p1 * / {head = p1; / * that is just created: Note: P2 at this time is P1, that is, P1-> Next point null. This way to keep consistent with ELSE below. * / P2-> next = null;} else {p2-> next = p1; / * Points to the next node that is just opened below * /}
P2 = p1; / * Reserved the address of P1 to P2, then P1 to generate new nodes * / p1 = (Struct Student *) Malloc (LEN); Printf ("please input% d node - num, score:", N 1); scanf ("% ld,% f", & (p1-> num), & (p1-> score));} P2-> next = null; / * This sentence is based on one-way linked list The last node wants to point to NULL * / FREE (P1); / * Release P1. With malloc (), both variables must be free () * / p1 = null; / * Special Don't forget to empty the released variable is NULL, otherwise it becomes a "wild pointer", that is, the address uncertain pointer . * / Return head; / * Return to the head pointer to create a list * /}
/ * =========================== function: output node returns: void =============== ============= * / void print (strunt student * head) {struct student * p; printf ("/ nnow, there% d Records are: / n", n); p = Head; if (head! = null) / * As long as it is not a empty list, output all nodes in the list * / {Printf ("Head IS% O / N", Head); / * Output Head Pointer Pointer Address * / DO {/ * Output the corresponding value: the current node address, each field value, the next node address of the current node. This allows the reader to see the storage structure of a one-way linker in the computer, and the illustration of our design is exactly the same. * / Printf ("% O% LD% 5.1F% O / N", P, P-> Num, P-> Score, P-> Next); P = P-> Next; / * Move to the next node * /} While (p! = Null);}}
/ * ========================== function: Delete the specified node (this example is a node that deletes the specified student number) Returns: Point to the Link list Head pointer =================================== * /
/ * Delete illustration of one-way linked list: ----> [null] Head
Figure 3: Empty chain table
As can be seen from Figure 3, the empty chain table obviously cannot delete
----> [1] ----> [2] ...----> [n] ----> [null] (original list) HEAD 1-> Next 2-> Next N- > Next
----> [2] ...----> [N] ----> [NULL] (Delete Rear List) HEAD 2-> Next N-> Next
Figure 4: Link list with n nodes, deleting the first node combines the original list and deleted linked list, it is easy to write the corresponding code. The operation method is as follows: 1, you have to understand the first node, head-> next is the second node; 2. After deleting, Head points points to the second node, that is, let Head = Head-> Next, OK this will .
----> [1] ----> [2] ----> [3] ...----> [n] ----> [null] (original list) HEAD 1- > Next 2-> Next 3-> Next N-> Next
----> [1] ----> [3] ...----> [n] ----> [null] (deleted rear chain table) HEAD 1-> Next 3-> Next N -> Next Figure 5: Link list with n nodes, delete one (hereby deleted the second) combined with the original list and deleted linked list, it is easy to write the corresponding code. The operation method is as follows: 1, you have to understand the first node, 1-> Next is the 2nd node, 2-> Next is the 3rd node; 2. After deleting 2, 1 point to the third node, that is Let 1-> next = 2-> next. * / struct student * del (strunt news * head, long Num) {strunt news * p1; / * P1 Save the address of the node that needs to be checked * / struct student * p2; / * P2 Save the address of the currently checked node * / If (head == null) / * is an empty list (in conjunction with Figure 3) * / {Printf ("/ nlist is null! / N"); return head;}
/ * Location to delete the node * / p1 = head; while (p1-> num! = NUM && P1-> next! = Null) / * P1 pointing node is not what you want to find, and it is not the last node, Continue to find * / {p2 = p1; / * Save the address of the current node * / p1 = p1-> next; / * After one node * /}
IF (NUM == P1-> Num) / * found. (Combined in connection with Figure 4, 5) * / {if (p1 == HEAD) / * If the node to be deleted is the first node * / {head = p1-> next; / * head pointer points to the first node The latter node is the second node. Such the first node is not in the chain list, that is, deleted. * /} Else / * If it is another node, let the original node point to the current node, point to its next node, complete deletion * / {p2-> next = p1-> next;
}
Free (p1); / * Release the current node * / p1 = null; Printf ("/ ndelete% ld success! / n", num); n - = 1; / * Node total number 1 * /} else / * Did not find * / {printf ("/ n% ld not been all! / N", num);
Return head;
/ * ========================== Function: Insert the back of the specified node (this example is the node of the specified student number) Returns: Point to Lin Lab The pointer of the header ==================================== * /
/ * Insert illustration of one-way linked list: ----> [null] Head
----> [1] ----> [NULL] (After inserting the list) Head 1-> Next Figure 7 Vacuum list Insert a node combined with the original list and the linked list, it is easy to write Code. The method of operation is as follows: 1, you have to understand the empty list Head point to null is Head = null; 2, after inserting the Head point to the first node, it is to let Head = 1, 1-> next = null, OK is like this.
----> [1] ----> [2] ----> [3] ...----> [n] ----> [null] (original list) HEAD 1- > Next 2-> Next 3-> Next N-> Next
----> [1] ----> [2] ----> [x] ----> [3] ...----> [n] ----> [Null ] (Link table after insert) Head 1-> Next 2-> Next X-> Next 3-> Next N-> Next
Figure 8: Link list with n nodes, insert a node (hereinafter inserted) combined with the original list and the inserted list, it is easy to write the corresponding code. The method of operation is as follows: 1, you have to understand the original 1-> Next is the node 2, 2-> Next is the node 3; 2, the X point to the third node, 2 points X, is let X-> next = 2- > next, 1-> next = x. * / struct student * INSERT (Struct Student * Head, Long Num, Struct Student * Node) {struct student * p1; / * P1 Save the address of the node that needs to be checked * /
IF (Head == NULL) / * (Combined with Illustration 7) * / {Head = Node; Node-> Next = NULL; N = 1; Return Head;}
P1 = head; while (p1-> NUM! = NUM && P1-> Next! = NULL) / * P1 The node points to the node is not to look up, and it is not the last node, continue to find * / {p1 = p1 -> next; / * After one node * /} if (num == p1-> num) / * found (combined with illustration 8 understand) * / {node-> next = p1-> next; / * obvious Node's next node is the original P1's next * / p1-> next = node; / * After insertion, the next node of the original P1 is the Node * / n = 1 to be inserted; / * The total number of nodes adds 1 * /} Else {printf ("/ n% ld not been found! / N", num);} return head;
/ * ========================== function: the reverse sequence node (the head of the linked list turns into the end of the chain list, the tail of the list) Returns: Pointer to the chain table header ================================================================================================================================================================================================================== -> [1] ----> [2] ----> [3] ...----> [N] ----> [Null] (original list) HEAD 1-> Next 2 -> Next 3-> Next N-> Next
[NULL] <---- [1] <---- [2] <---- [3] <------... [n] <---- (Link list after the reverse 1-> Next 2-> Next 3-> Next N-> Next HEAD
Figure 9: Links with n nodes are easily written in the original chain table and the linked list after insertion. The operation method is as follows: 1, we need a pointer P2 of the original chain table P2, the P1 = NULL of the contrast chain table (the next NEXT is null), and there is a temporary storage variable P; 2, P2 read in the original list Out of a node, let's put it in P1, p is the problem for handling node placement order; 3, for example, now we get a 2, in order to continue the node, we must save its NEXT value, P = 2-> next; 4, then the chain table is then known from the rear sequence, and after the reagent, 2-> next to point 1, then 2-> next = 1; 5, ok, now it has been reversed One node, then deal with the next node, it needs to be saved at this time: P1 becomes 2, ie p1 = 2; P2 is to become the next node, that is, the P2 = P . * / struct student * Reverse (strunt news * p; / * temporary storage * / struct student * p1; / * Storage return result * / struct student * p2; / * Source results node one one 1 / P1 = null; / * Start upside down, the reversed portion is empty * / p2 = head; / * p2 pointing to the head node of the linked list * / while (p2! = Null) {p = p2-> next; p2- > next = p1; p1 = p2; p2 = p;} Head = p1; return;}
/ * Test procedure for the above function: Tip: This is also a test method according to the corresponding block according to the different annotations of the test function. * / main () {structure * head; struct student * stu; long kilnumber;
/ * Test Create (), Print () * / head = create (); print (head); / * Test Del (): Please compile to remove the release block * / / * printf ("/ NWHICH One delete:") Scanf ("% ld", & teller); Head = del (Head, teller); Print (Head); * // * Test INSERT (): Please compile to remove the release block * /
/ * STU = (Struct Student *) Malloc (LEN); Printf ("/ NPLEase:"); Scanf ("% ld,% f", & stu-> num, & stu-> score PRINTF ("/ Ninsert Behind Num:"); Scanf ("% LD", & Thenumber); Head = INSERT (Head, Thenumber, STU); Free (STU); Stu = NULL; Print (Head); * / / * Test Reverse (): Please compile to the release block * /
/ * Head = Reverse (HEAD); Print (Head); * / printf ("/ n"); system ("pause");}
/ * Next, sort (selection, insert, bubble) Insert (orderly), hope interested friends pay attention * /
