Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to realize linear dynamic one-way linked list in C language". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "C language how to achieve linear dynamic one-way linked list" bar!

What is a linked list

Linked list is a kind of data structure, linear linked list is a kind of linked list, the extension of linear linked list is two-way linked list and circular linked list. Optimizing data structure in programming language can greatly reduce the space complexity and time complexity of the program when dealing with big data. Here I will only use a simple example-linear one-way linked list as an example to illustrate how the C language implements this structure.

The elements of the linked list are implemented by the structure struct table * p. One member of the structure is the structure pointer struct table * next, and the structure pointer is of the same type as this structure. Except for the last element of the linked list, the pointer of each structure points to the structure of the next element in the linked list, and the structure pointer of the last element is NULL. When you save a linked list, you only need to record the head pointer of the linked list, that is, the address of the first structure in the linked list. When you add a linked list element, you need to apply for a separate section of memory; when you delete it, you free it. When looking up a linked list, you only need to look down one by one in the order of the structure pointers to the member pointers in the structure you are looking for. The following is an illustration of a linked list structure:

Struct Student {int ID;// student number char [20]; / / name int marks [5]; / / 5 exam scores struct Student * next;// points to the structure pointer of the next structure} Why not use the structure array

Some people may ask why not just replace the linked list with a struct array. The memory space occupied by the struct array is continuous and can be stored dynamically if you use malloc instructions, and continuous memory space is definitely better than uncertain memory space. But if you insert or delete elements to a dynamic array, all the elements that follow it need to be repositioned, so it is much more difficult to modify the array than the linked list. But its advantage is that the search method is very flexible, and each element has an offset I relative to the address of the first element of the array, so it can be looked up either forward or reverse or dichotomy for the array.

Because each element of the linked list has a section of memory, the memory is not necessarily contiguous, and the linked list itself has one more structural pointer to the next element than the structured array, so the linked list is not as good as the array from a memory-saving point of view. But when the linked list deletes an element (assuming that the element is a [k]), it only needs the next pointer of a [k-1] to point to a [k + 1], and then releases the memory of a [k], which is very convenient. When inserting an element (assuming that the element is a [n]), you only need the next pointer of a [n-1] to a [n] and then the pointer of a [n] to a [n + 1]. Compared to the array, only two elements have been modified, which is fast and very convenient.

Operation of linked list

The operation of linked list is divided into creating table, inserting element, deleting element, emptying table, looking up table, and printing table. The inserted / deleted elements can be one or more. In terms of storage type, linked list can be divided into static linked list and dynamic linked list. Static linked list is a linked list written in advance, and the memory occupied is the memory of static storage area. When in use, the elements in it can not be deleted, but can only be found. Dynamic linked list is a linked list generated according to the requirements of the program, which is stored in the dynamic storage area, and the structure is more flexible. Each element occupies part of the storage space. If you want to delete the element, release the memory of that location; if you want to add the element, then apply for the memory in the memory area of a structure.

Create a tabl

Creating a linked list requires two pointers, one as a leading pointer (* p1) to open up memory and save the value of the structure, and one as a cache pointer (* p2), which retains all the values of the leading pointer and points its next to the leading pointer. When building a linked list, the first pointer assigns a value, the second pointer holds a value, and the next of the latter pointer points to the leading pointer. When the assignment terminates, the next of the leading pointer points to NULL, and the leading pointer is assigned to the latter pointer, and the linked list is built.

The code window can be viewed through the keyboard's "←" and "→".

Struct Student * input () {struct Student * p1Magneol / p2journal headspace null; printf ("* dynamic linked list experiment *\ n [input dynamic linked list]\ n") Printf ("Please enter your student ID (cm), height, weight (kg) (end with a space, enter 0):\ n"); p2roomp1 = (struct Student *) malloc (LEN); / / open up memory scanf ("% d% s% f% f", & p1-> ID,&p1- > name,&p1- > height,&p1- > weight); if (p1-> ID==0) return (head); While (p1-> height/100) {p2-> next=p1; p2roomp1; p2-> BMI= (float) p2-> weight/ (p2-> height/100) / (p2-> height/100); / / BMI index p1 = (struct Student *) malloc (LEN) / / Open memory scanf ("% d% s% f", & p1-> ID,&p1- > name,&p1- > height,&p1- > weight);} p2-> next=NULL; return (head); / / return chain header pointer} delete element

To delete the nth element of the element linked list, you only need to point the next pointer of the n-1 element to the n + 1 element, and then release the memory of the nth element. Here is one of the examples written here, delete an element in the table according to the keyword number (int stdID) and return the deleted list header address (if the first element is deleted, the chain header address will change)

The code window can be viewed through the keyboard's "←" and "→".

Struct Student * delate (struct Student * head,int stdID) {struct Student * p1); if (head- > ID==stdID) {p1mm head-> next; free (head); return p1 } / / if the first element is deleted, it is special and the header pointer needs to be modified. The rest of the cases are to modify the next structure pointer for. The p2 pointer points to the current student, and p2 points to the previous student {if (p1-> ID==stdID) {p2-> next=p1- > next. / / suppose the student number of the student to be deleted is found, then let the pointer of the previous student point to the free (p1) that skips his next student; return head;}} return NULL;// returns NULL indicates that the insertion element is not found

The principle of inserting an element is to assume that you want to insert an element before the nth element. First determine whether it is the first element, and if so, modify the header pointer to point to the element and point the element's next to the original header pointer. If it is not the first element, but inserts an element before the k-th element, point the next pointer of the k-1 element to the address (or header pointer) of the inserted element (or child table), and point the next pointer (or tail pointer) of the inserted element to the k-th element. This sample code is a function that inserts an element (or subtable) based on a student number (primary keyword) and returns the first address of the linked list (because the first address of the linked list may be changed if inserted before the first element).

The code window can be viewed through the keyboard's "←" and "→".

Struct Student * insert (struct Student * head,int stdID,struct Student * insertstd) {struct Student * p1journal p2journal; for (padded insertstablep> next); / / find the last element of the insert linked list, if (head- > ID==stdID) {p-> next=head; return insertstd;} for (p1headscape p1mm null). Next) {if (p1-> ID==stdID) {p2-> next=insertstd; p-> next=p1; return head;}} return NULL;} code and running results

The complete code and comments are as follows:

The code window can be viewed through the keyboard's "←" and "→".

# include # define LEN sizeof (struct Student) / / defines the size of the structural body variable as the symbolic constant LEN struct Student {int ID;// student number char name [20]; / / the name float height;// height float weight;// weight float BMI;//BMI index, which does not need to be calculated when entering struct Student * next;// points to the next structure}; struct Student * input () / / input function void output (struct Student * head); / / output function struct Student * delate (struct Student * head,int stdID); / / Delete an element and return the header pointer struct Student * insert (struct Student * head,int stdID,struct Student * insertstd) of the deleted table; / / return the header pointer int append (struct Student * head) after inserting the element (child table); / / insert a linked list and enter struct Student * isexist (struct Student * head,int stdID) from the input function Int main () {struct Student * present;// header pointer int choice; bool next; int stdID of the current linked list / * 1: insert an element 2: delete an element 3: continue table 4: look up table * / printf ("* dynamic linked list experiment *\ ninitialize a linked list:\ n"); present=input () / / current linked list pointer do {printf ("Please select:\ n | 1: insert element (child table)\ n | 2: delete element\ n | 3: continue table\ n | 4: look up table\ n"); scanf ("% d", & choice) Switch (choice) {case 1: printf ("Please enter the student number of the last classmate in the insertion place:"); scanf ("% d", & stdID) If (isexist (present,stdID) = = NULL) {printf ("this student does not exist!\ n"); break / / exit switch statement} present=insert (present,stdID,input ()); printf ("the linked list after inserting elements is:\ n"); output (present); break Case 2: printf ("Please enter the student number to delete the element:"); scanf ("% d", & stdID) If (isexist (present,stdID) = = NULL) {printf ("this student does not exist!\ n"); break / / exit switch statement} present=delate (present,stdID); printf ("deleted linked list is:\ n"); output (present); break Case 3: append (present); printf ("list after continuation:\ n"); output (present); break Case 4: printf ("current linked list is:\ n"); output (present); break;} printf ("whether to continue (Yes:1,No:0):") Scanf ("% d", & next); fflush (stdin);} while (next); return 0;} struct Student * input () {struct Student * p1 Printf ("* dynamic linked list experiment *\ n [enter dynamic linked list]\ n"); printf ("Please enter your student number, name, height (cm), weight (kg) (spaced by spaces, end with 0):\ n") P2memory p1 = (struct Student *) malloc (LEN); / / Open up memory scanf ("% d% s% f% f", & p1-> ID,&p1- > name,&p1- > height,&p1- > weight); if (p1-> ID==0) return (head); else head=p1; while (p1-> IDC / 0) {p2-> next=p1; p2=p1 P2-> BMI= (float) p2-> weight/ (p2-> height/100) / (p2-> height/100); / / find the BMI index p1 = (struct Student *) malloc (LEN); / / open up memory scanf ("% d% s% f% f", & p1-> ID,&p1- > name,&p1- > height,&p1- > weight);} p2-> next=NULL; return (head) / / return chain header pointer} void output (struct Student * head) {struct Student * p; int num=1; padded headheading / transfer the header pointer address to p printf ("[output dynamic linked list]\ n"); printf ("| Student ID\ t\ t | name\ t | height\ t | weight\ t | BMI\ n") While (paired null) {printf ("% 3D | d\ t |% s\ t |% 5.2f\ t |% 5.2f\ t |% lf\ n", num++,p- > ID,p- > name,p- > height,p- > weight,p- > BMI); pumped-> next;}} struct Student * delate (struct Student * head,int stdID) {struct Student * p1coverp2 If (head- > ID==stdID) {p1headhead> next; free (head); return p1;} / / if the first element is deleted, it is special and the header pointer needs to be modified. The rest of the cases are to modify the next structure pointer for. The p2 pointer points to the current student, and p2 points to the previous student {if (p1-> ID==stdID) {p2-> next=p1- > next. / / if the student number of the student to be deleted is found, let the pointer of the previous student point to his next student free (p1); return head;}} return NULL / / return NULL indicates that} struct Student * insert (struct Student * head,int stdID,struct Student * insertstd) {struct Student * p1grad is not found; for (paired insertstdentpoun > nextstdentnulls / next); / / find the last element of the insert linked list if (head- > ID==stdID) {p-> next=head; return insertstd;} for (p1=head) Next) {if (p1-> ID==stdID) {p2-> next=insertstd; p-> next=p1; return head;} return NULL } int append (struct Student * head) / / insert a linked list and enter {struct Student * p from the input function; for (pendant headposition p-> nextsteps null); / / find the last element of the head linked list, p-> next=input (); / / enter the element to be added from input, which can be one or more return 0 } struct Student * isexist (struct Student * head,int stdID) {struct Student * p; for (pairing headboard, pairing, nulling, next) {if (p-> ID==stdID) {return p;}} return NULL;}

The output effect is as follows:

At this point, I believe that the "C language how to achieve linear dynamic one-way linked list" have a deeper understanding, might as well to practical operation it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.