This article uses .c files to call functions, and .h files to define the layout of functional functions.
Because no other space is occupied when doing merge and intersection difference, after executing a function, the values of the two linked lists have changed and are no longer the original values, so after each function is executed, the program exits and then runs and executes the corresponding Just function
There is a complete code display at the end of the article
1. Calling function functions in the main function of .c file
<1>main.c main function code display
#include"Module.h"
int main()
{
int Choice = 0;
struct STU* List1 = CreaterList();
printf("Please enter the data of the second linked list: \\
");
struct STU* List2 = CreaterList();
while (1)
{
printf("Select the next operation: 1: Linked list merging 2: Incremental linked list merging 3: Linked list intersection 4: Linked list difference 5: Exit\\
");
scanf_s("%d", & amp;Choice);
if((Choice>=6)||(Choice<=0))//If you don’t want to change it after writing it, it will be easier to use default:break;
{
printf("Illegal input, please enter an option within 1-5\\
");
}
else
{
switch (Choice)
{
case 1:
Merge(List1, List2);
break;
case 2:
Contrast(List1, List2);
break;
case 3:
Intersection(List1, List2);
break;
case 4:
Differ_set(List1, List2);
break;
case 5:
exit(0);
break;
}
}
}
}
<2>Running result display
The input boundary is processed here, and there will be an illegal input reminder when it exceeds the range.
2. Definition of structure in .h file and reference to standard library
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
typedef struct STU
{
int data;//data field of the structure
struct STU* next; //Pointer field of structure
};
3. Definition of linked list creation function CreaterList
struct STU* CreaterList()
{
struct STU* head = (struct STU*)malloc(sizeof(struct STU));
head->next = NULL;//Create the head node
struct STU* p = head;
printf("Please enter the number of elements in the linked list you want to create: \\
");
int amount = 0;
scanf_s("%d", & amp;amount);
for (int i = 0; i < amount; i + + )
{
struct STU* knot = (struct STU*)malloc(sizeof(struct STU));//Create a new node
//printf("Please enter the data of the %dth element, and the input is an increasing sequence: \\
", i + 1);
scanf_s("%d", & amp;knot->data);//Save the input data into the data field of the node
p->next = knot;
p = p->next;
knot->next = NULL;//Point the last node of the linked list to null, otherwise it will be an uncertain value
p->next = NULL;
}
return head;
}
Four: The simplest merge of linked lists (end to end connected)
<1>Merge function definition code display
//Linked list merge
int Merge(struct STU* List1, struct STU* List2)
{
struct STU* p1 = List1;
while (p1->next != NULL)
{
p1 = p1->next;
}//The pointer field of the last element of List1 points to null, just make it point to the second node of List2
p1->next = List2->next;//List2 contains the head node, so the node pointed to by List2->next saves the required data
for (struct STU* p = List1->next; p != NULL; p = p->next)//Print the merged linked list
{
printf("%d\t", p->data);
}
printf("\\
");
return List1;
}
<2>Run results
In this function, if the elements of the two linked lists have duplicate values, they will also be spliced together. This function only implements a simple function of connecting the tails of the two linked lists.
5. (Increasing linked list merging) Example requirement: Merge two increasing ordered linked lists into one increasing ordered linked list. It is required that the resulting linked list still uses the storage space of the original two linked lists and does not occupy other storage space. Duplicate data is not allowed in the table
<1>Contrast function definition code display
// //Increasing linked lists are merged into increasing linked lists
int Contrast(struct STU* List1, struct STU* List2)
{
struct STU* head = List1;
struct STU* p1 = List1->next; //Double pointer
struct STU* p2 = List2->next;
while((p1!=NULL) & amp; & amp; (p2 != NULL))
{
if((p1->data < p2->data))
{
head->next = p1;
p1 = p1->next;
}
else if ((p1->data == p2->data))
{
head->next = p1;//When there are the same elements in the two linked list elements, point head->next to any one of p1 or p2
p1 = p1->next;//When pointing to p1, move the p1 pointer back one bit
p2 = p2->next;//At the same time, move p2 back one bit to skip repeated values and prevent repeated sorting.
}
else
{
head->next = p2;
p2 = p2->next;
}
head = head->next;
}
head->next = p1 == NULL ? p2 : p1;//Because it is an increasing sequence, when all the elements of one are arranged, just add the elements that are not left in the linked list to the back.
for (struct STU* p = List1->next; p != NULL; p = p->next)//Use List->next to skip the head node
{
printf("%d\t", p->data);
}
printf("\\
");
return List1;
}
<2>Running result display
When there are duplicate elements, only one of the duplicate elements will be displayed after sorting and merging.
Of course, if duplicate elements are allowed to appear in the merged linked list, you only need to delete the equality statement in the function (the statement corresponding to the else if condition)
6. It is known that two linked lists A and B represent two sets respectively, and their elements are arranged in ascending order. Please design an algorithm to find the intersection of A and B, and store the result in the A linked list
<1>Intersection function definition code display
//Find intersection of linked lists
int Intersection(struct STU* List1, struct STU* List2)
{
int flag = 0;
struct STU* p1 = List1;
struct STU* p2 = List2;
while(p1->next!=NULL)
{
flag = 0;//When the same element as the element in List1 is found in List2, the flag will be assigned a value of 1 otherwise it will be 0
for (p2 = List2; p2->next != NULL; p2 = p2->next)
{
if (p2->next->data == p1->next->data)//Similar to the commonly used assignment of two-dimensional array rows and columns in C language, the outer periphery is the row and the inner loop is the column.
{//Here it is fixed that the elements in List1 are compared one by one with the elements in List2. When the first data in List1 is compared with all the elements in List2,
flag = 1;//Reuse the second element in List1 for comparison until reaching the last element in List1
}
}
if (flag != 1)//If the element at this position in List1 is the same as an element in List2
{
struct STU* delect = p1->next;//Delete the node and point the previous pointer to the node to the next node
p1->next = delect->next;
free(delect);//Release the space of deleted nodes
}
else
{
p1 = p1->next;
}
}
if (List1->next == NULL)
{
printf("The intersection of the two linked lists is empty!!!\\
");
}
else{
for (struct STU* p = List1->next; p != NULL; p = p->next)//Traverse the intersection list and print
{
printf("%d\t", p->data);
}
printf("\\
");
}
return 1;
}
<2>Running result display
1. The intersection operation result of the intersection linked list is displayed 
2. Display of intersection operation results of non-intersection linked lists
7. It is known that the two linked lists A and B represent two sets respectively, and their elements are arranged in ascending order. Please design an algorithm to find the difference between two sets A and B (a set consisting only of elements that appear in A but not in B), store the result in the same form, and return the individual elements of the set. number.
After completing the six examples of finding intersections, we can think about it briefly and find that in the process of finding intersections, we have already found the common elements in the sets A and B. For the rest, we only need to use A as the complete set and put Just delete the elements in the intersection part.
<1>Differ_set function definition code display
There is only a slight difference between this and the code for finding the intersection of linked lists in 6.
//Linked list difference set
int Differ_set(struct STU* List1, struct STU* List2)
{
int flag = 0;
struct STU* p1 = List1;
struct STU* p2 = List2;
while (p1->next != NULL)
{
flag = 0;
for (p2 = List2; p2->next != NULL; p2 = p2->next)
{
if (p2->next->data == p1->next->data)
{
flag = 1;
break;//Jump out of the loop directly after finding it, you can add it or not, and the code running time complexity is smaller
}
}
if (flag == 1)
{
struct STU* delect = p1->next;//Delete the node corresponding to the intersection element
p1->next = delect->next;
free(delect);//Release space
}
else
{
p1 = p1->next;
}
}
int count = 0;
for (struct STU* p = List1->next; p != NULL; p = p->next)
{
count + = 1;
printf("%d\t", p->data);
}
printf("There are %d elements that exist in List1 but not in List2\\
", count);
printf("\\
");
return 1;
}
<2>Running result display
8. Exit function display, invincible exit()!
9. Complete code
<1>.c
#include"Module.h"
int main()
{
int Choice = 0;
struct STU* List1 = CreaterList();
printf("Please enter the data of the second linked list: \\
");
struct STU* List2 = CreaterList();
while (1)
{
printf("Select the next operation: 1: Linked list merging 2: Incremental linked list merging 3: Linked list intersection 4: Linked list difference 5: Exit\\
");
scanf_s("%d", & amp;Choice);
if((Choice>=6)||(Choice<=0))
{
printf("Illegal input, please enter an option within 1-5\\
");
}
else
{
switch (Choice)
{
case 1:
Merge(List1, List2);
break;
case 2:
Contrast(List1, List2);
break;
case 3:
Intersection(List1, List2);
break;
case 4:
Differ_set(List1, List2);
break;
case 5:
exit(0);
break;
}
}
}
}
<2>.h
#include#include #include #include typedef struct STU { int data; struct STU* next; }; struct STU* CreaterList() { struct STU* head = (struct STU*)malloc(sizeof(struct STU)); head->next = NULL; struct STU* p = head; printf("Please enter the number of elements in the linked list you want to create: \\ "); int amount = 0; scanf_s("%d", & amp;amount); for (int i = 0; i < amount; i + + ) { struct STU* knot = (struct STU*)malloc(sizeof(struct STU)); //printf("Please enter the data of the %dth element, and the input is an increasing sequence: \\ ", i + 1); scanf_s("%d", & amp;knot->data); p->next = knot; p = p->next; knot->next = NULL; p->next = NULL; } return head; } //Linked list merge int Merge(struct STU* List1, struct STU* List2) { struct STU* p1 = List1; while (p1->next != NULL) { p1 = p1->next; } p1->next = List2->next; for (struct STU* p = List1->next; p != NULL; p = p->next) { printf("%d\t", p->data); } printf("\\ "); return List1; } // // Increasing linked lists are merged into increasing linked lists int Contrast(struct STU* List1, struct STU* List2) { struct STU* head = List1; struct STU* p1 = List1->next; //Double pointer struct STU* p2 = List2->next; while((p1!=NULL) & amp; & amp; (p2 != NULL)) { if((p1->data < p2->data)) { head->next = p1; p1 = p1->next; } else if ((p1->data == p2->data)) { head->next = p1;//When there are the same elements in the two linked list elements, point head->next to any one of p1 or p2 p1 = p1->next;//When pointing to p1, move the p1 pointer back one bit p2 = p2->next;//At the same time, move p2 back one bit to skip repeated values and prevent repeated sorting. } else { head->next = p2; p2 = p2->next; } head = head->next; } head->next = p1 == NULL ? p2 : p1;//Because it is an increasing sequence, when all the elements in one are arranged, just add the elements that are not left in the linked list to the back. for (struct STU* p = List1->next; p != NULL; p = p->next)//Use List->next to skip the head node { printf("%d\t", p->data); } printf("\\ "); return List1; } //Find intersection of linked lists int Intersection(struct STU* List1, struct STU* List2) { int flag = 0; struct STU* p1 = List1; struct STU* p2 = List2; while(p1->next!=NULL) { flag = 0;//When the same element as the element in List1 is found in List2, the flag will be assigned a value of 1 otherwise it will be 0 for (p2 = List2; p2->next != NULL; p2 = p2->next) { if (p2->next->data == p1->next->data)//Similar to the commonly used assignment of two-dimensional array rows and columns in C language, the outer periphery is the row and the inner loop is the column. {//Here it is fixed that the elements in List1 are compared one by one with the elements in List2. When the first data in List1 is compared with all the elements in List2, flag = 1;//Reuse the second element in List1 for comparison until reaching the last element in List1 } } if (flag != 1)//If the element at this position in List1 is the same as an element in List2 { struct STU* delect = p1->next;//Delete the node and point the previous pointer to the node to the next node p1->next = delect->next; free(delect);//Release the space of deleted nodes } else { p1 = p1->next; } } if (List1->next == NULL) { printf("The intersection of the two linked lists is empty!!!\\ "); } else{ for (struct STU* p = List1->next; p != NULL; p = p->next)//Traverse the intersection list and print { printf("%d\t", p->data); } printf("\\ "); } return 1; } // Find the difference set of linked lists int Differ_set(struct STU* List1, struct STU* List2) { int flag = 0; struct STU* p1 = List1; struct STU* p2 = List2; while (p1->next != NULL) { flag = 0; for (p2 = List2; p2->next != NULL; p2 = p2->next) { if (p2->next->data == p1->next->data) { flag = 1; break; } } if (flag == 1) { struct STU* delect = p1->next; p1->next = delect->next; free(delect); } else { p1 = p1->next; } } int count = 0; for (struct STU* p = List1->next; p != NULL; p = p->next) { count + = 1; printf("%d\t", p->data); } printf("There are %d elements that exist in List1 but not in List2\\ ", count); printf("\\ "); return 1; }
The example title comes from “Data Structure (C Language Edition 2nd Edition)”