Link list

xiaoxiao2021-03-06  53

Link list is the basis of the data structure. Using the list, we can achieve data management. But we often see a variety of questions about the linked list online, here I give a relatively simple but functional program to show you the programming of the list. If you know deeply understand the working principle of the following procedures, you will make a closer for your understanding of the list. If you can't, please read the following procedure, pay special attention to the modification of the program pointer. Especially the inverter of the list, no more than 10 lines will be fixed, there is no additional application space, why not? The program is debugged in VC6.

#include

#include

#include

#include

/ * Constant definition in the book * /

#define ok 1

#define error 0

#define overflow (-1)

Typedef int stat;

/ * Define a student structure * /

Typedef struct {

Int sn; / * Learn * /

Char name [32]; / * Name * /

int score; / * grade * /

} DATA_T;

/ * Define the node form of the linked list is a single-link table * /

Typedef struct lnot {

DATA_T DATA;

Struct Lnode * Next;

} Node_T, * LINK_T;

/ * Create a chain list with head nodes * /

LINK_T CREATE_LINK ();

/ * Destroy the chain table, release node space * /

Void Destroy_Link (Link_t Head);

/ * Insert a node in the iDX location of the linked list, and the value of the node is given by D * /

/ * Note that idx is the position after inserting nodes, and calculates from 0 * /

Status INSERT_NODE (LINK_T Head, Int IDX, DATA_T E);

/ * Delete the iDX node of the list and fill the deleted content to the space pointed to by * /

/ * IDX is also calculated from 0 * /

Status delete_node (link_t head, int idx, data_t * e);

/ * Judging whether the linked list is empty * /

Status Empty_Link (Link_t Head);

/ * Get the length of the linked list * /

INT Length_Link (Link_t Head);

/ * The position of the i-th element of the linked list is obtained, and the pointer to performing the element is returned. NULL is invalid * /

Node_t * locate_link (link_t head, int idx);

/ * Print the contents of the list * /

Void Print_Link (Link_t Head);

/ * Invert a list * /

Void Reverse_link (Link_t Head);

/ * Keyboard command mapping table * /

Const char * help [] =

{

"?, h - this help / n",

"A, A, I, I - Add A Node, EX: A 10 / N",

"D, D - Del a Node, EX: D 10 / N",

"p, p - print this link / n",

"G, G - get link Num / N",

"R, R - Reverse the link / n",

"x, x, q, q - exit this program / n",

}

/ * Program entry * /

INT Main (int Argc, char * argv []) {

CHAR CMD;

INT I, IDX;

DATA_T TMP;

LINK_T Head = CREATE_LINK ();

For (i = 0; i <10; i ) {/ * pre-inserted 10 nodes * /

TMP.SN = I; tmp.score = 100-i; strcpy (tmp.name, "ttttt");

INSERT_NODE (HEAD, I, TMP);

}

Print_Link (Head);

Printf ("INPUT Command:");

While (cmd = getCH ())

{

Printf ("% C / N", CMD);

Switch (cmd)

{

Case '?': Case 'h': Case 'h': / * Print Help Information * /

For (i = 0; I

Printf ("/ T% S", HELP [I]);

Printf ("/ n");

Break;

Case 'a': Case 'a': Case 'I': Case 'I': / * Insert a node * /

PRINTF ("" "" ");

Scanf ("% d", & idx);

IF (IDX <0 || IDX> Length_Link (Head)) {

Printf ("INSERT POS ERROR! / N");

Break;

}

PRINTF ("" please input the Sn, name and score: ");

Scanf ("% D% S% D", & tmp.sn, tmp.name, & tmp.score);

IF (Insert_Node (Head, Idx, TMP) == Error) {

Printf ("INSERT ERROR! / N");

Break;

}

Printf ("INSERT OK! / N");

Print_Link (Head);

Break;

Case 'D': Case 'D': / * Deletes a node * /

Printf ("Please Input Which Do You Want To Delete:");

Scanf ("% d", & idx);

IF (IDX <0 || IDX> = Length_Link (Head) {

Printf ("Delete Pos Error! / N");

Break;

}

IF (DELETE_NODE (Head, IDX, & TMP) == NULL) {

Printf ("INPUT Error! / N");

Break;

}

Printf ("delete ok / n");

Print_Link (Head);

Break;

Case 'P': Case 'P': / * Print Next * /

Print_Link (Head);

Break;

Case 'x': Case 'x': Case 'Q': Case 'q': / * Exit Program * /

DESTROY_LINK (HEAD); RETURN 0;

Case 'R': Case 'R': / * Inverted Links * /

Reverse_link (head);

Printf ("This Link Have Been Reverse! / N");

Print_Link (Head);

Break;

DEFAULT:

Printf ("Input Error !, for Help, Please Input? / N");

}

Printf ("/ N / Ninput Command:");

}

Return 0;

}

LINK_T CREATE_LINK ()

{

LINK_T HEAD;

Head = (link_t) Malloc (SIZEOF (Node_t));

HEAD-> next = NULL;

HEAD-> DATA.SN = 0;

Return head;

}

Void Destroy_Link (Link_t Head)

{

Node_t * p = head;

While (Head! = null) {

P = head-> next;

Free (Head);

HEAD = P;

}

}

Void Print_Link (Link_t Head)

{

Node_t * p = head-> next; / * Skip head node * /

INT CNT = 0;

Printf ("POS: SN% 20S Score / N", "Name");

While (p! = null) {

Printf ("% 04D:% 4D% 20S% 4D / N",

CNT , P-> Data.sn, P-> Data.Name, P-> Data.score;

P = P-> next;

}

}

Status Empty_Link (Link_t Head)

{

IF (head == null || head-> next == null)

Return OK;

Else

Return Error;

}

INT Length_Link (Link_t Head)

{

INT LEN = 0;

Node_t * p = head-> next;

For (; p! = null; p = p-> Next)

Len ;

Return Len;

}

Node_t * locate_link (link_t head, int idx)

{

INT POS = -1;

Node_t * p = head;

While (p! = null && pOS

P = P-> Next; POS ;

}

Return P;

}

Status INSERT_NODE (Link_t Head, Int IDX, DATA_T E)

{

Node_t * add = NULL; / * Node pointer to be added * /

Node_t * p = locate_link (head, idx-1); / * Note Query IDX-1 * /

IF (p == null) return error;

Add = (node_t *) malloc (sizeof (node_t));

Add-> DATA = E;

Add-> Next = P-> next;

P-> next = add;

Return OK;

}

Status delete_node (link_t head, int idx, data_t * e) {

Node_t * p = locate_link (head, idx-1); / * Note Query IDX-1 * /

Node_t * q = null; / * P For node pointer to be deleted * /

IF (p == null || p-> next == null) return error;

Q = P-> next;

* E = Q-> Data;

P-> next = Q-> next;

Free (q);

Return OK;

}

Void Reverse_Link (Link_t Head)

{

Node_t * p1, * p2;

P1 = head-> next;

HEAD-> next = NULL;

While (p1! = null) {

P2 = p1-> next;

P1-> Next = head-> next;

HEAD-> Next = P1;

P1 = p2;

}

}

Everyone saw it, and every subunies above are simple, no more than 10 lines. The only MAIN function is relatively long. The main function has implemented an example of a common menu operation, including the corresponding command and functionality of the function of the help, the insertion of the list, delete, etc., and the implementation of the functional combinations of each function function is implemented.

- Pediatrics, don't throw bricks, eggs!

转载请注明原文地址:https://www.9cbs.com/read-117596.html

New Post(0)