[final examination of data structure experiment] - delete the first largest element and its duplicate node in the single linked list
subject
- Known single linked list A, write an algorithm to delete the first largest element in the single linked list.
- Given the single linked list L, write an algorithm to delete its duplicate nodes (only one is retained).
Programming
1) Outline design
Several functions are designed to implement initialization, trailing method to build tables, delete the first largest element, delete duplicate nodes, and then call the function in the main function to achieve operation.
2) Detailed design
Import related libraries
#include<stdio.h> #include<stdlib.h> #include<malloc.h>
Storage structure of single linked list.
Note: LinkList and Node * are both structure pointer types, which are equivalent.
Usually, LinkList is used to describe pointer variables, emphasizing that it is the head pointer variable of a single linked list.
Use such as to define LinkList L, and l is the header pointer of the single linked list, so as to improve the readability of the program.
Use Node * to define the pointer to the Node in the single linked list. For example, Node *p, then p is the pointer variable to the Node in the single linked list.
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node * next;
}Node,* LinkList;
/*LinkList And Node * are structure pointer types, and the two types are equivalent.
Usually, LinkList is used to describe pointer variables, emphasizing that it is the head pointer variable of a single linked list.
such as If LinkList L is defined, l is the header pointer of the single linked list, so as to improve the readability of the program.
Use Node * to define the pointer to the Node in the single linked list. For example, Node *p, then p is the pointer variable to the Node in the single linked list.*/
Initialize single linked list
//Initialize single linked list
void Init_LinkList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));//Create header node
(*L)->next=NULL;//Create an empty single linked list
//Note: L is the pointer to the single chain header node, which is used to receive the address of the header pointer variable with initialization of the single chain table in the main program,
//*L is equivalent to the header pointer variable with initialized single linked list in the main program.
}
Tail interpolation table
Algorithm idea: insert the new node into the tail of the previous single linked list. Therefore, you need to add a tail pointer r to make it only want the tail of the current single linked list.
//Tail interpolation table
void CreateFromTail(LinkList L)
{
Node *r,*s;//A dynamic tail pointer r
int flag=1;
r=L;
char c;
while(flag)
{
c=getchar();
// printf(" ");
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=(int)c;
r->next=s;
r=s;//r is always at the end
}
else
{
flag=0;
r->next=NULL;//Set the next chain field of the last node to empty, indicating the end of the linked list
}
}
}
Displays a single linked list.
Algorithm idea: print one by one along the pointer.
//display single linked list
void Display_LinkList(LinkList L)
{
//printf("display call start \ n");
Node *p;
ElemType s;
p=L;
while(p->next)
{
//p=p->next;
printf("%c ",p->next->data);//% c because getchar() is in front of it
//printf(" ");
p=p->next;
}
//Printf ("end of display call \ n");
}
Delete the first largest element in the single linked list
//Delete the first largest element in the single linked list
void delmaxnode(LinkList L)
{
Node *p=L->next,*pre=L,*maxp=p,*maxpre=pre;
while (p!=NULL)
{
if (maxp->data<p->data) //If a larger node is found
{
maxp=p; //Change maxp
maxpre=pre; //Change maxpre s
}
pre=p; //p. Move one node after pre synchronization
p=p->next;
}
maxpre->next=maxp->next; //Delete * maxp node
free(maxp); //Release * maxp node
}
Delete duplicate nodes
//Delete duplicate nodes
void del_repeated_node(LinkList L)
{
Node *k = L->next;
Node *pre_p=k;
Node *p=pre_p->next;
//Traverse each node of the single linked list
while(k && k->next != NULL)
{ //Judge whether the node behind k is repeated with the value field of k. if it is repeated, delete it.
while(p)
{
if(k->data == p->data)
{
//Delete duplicate p nodes
Node* temp = p;
pre_p ->next= p->next;
p = pre_p->next;
free(temp);
}
else
{
pre_p = pre_p->next;
p = pre_p->next;
}
}
k = k->next;
pre_p=k;
p = pre_p->next;
}
}
Main function
Use a form of "menu" to make the operation of single linked list more clearly displayed.
int main()
{
LinkList L;
ElemType e,x;
int i=1,k,j;
Init_LinkList(&L);
printf("The single chain table established by tail interpolation is as follows:\n(Input rule: input a number one by one without adding space and carriage return. Space and carriage return will also be regarded as one character. Please enter at the end'$')\n");
CreateFromTail(&L);
//system("cls");
while(i)//Keep it going
{
printf("\n Current linked list: ");
Display_LinkList(&L);
printf("\n-------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 Delete the first largest element \n");
printf(" 2 Delete duplicate nodes \n");
printf(" 3 Clear screen \n");
printf(" 0 End program \n");
printf("--------------------------------------\n");
printf("Please enter the menu number you selected<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
delmaxnode(&L);
break;
case 2:
del_repeated_node(&L);
break;
case 3:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("Incorrect input~");
}
}
return 0;
}
experimental result
The two largest numbers are in different positions, the first one is deleted, and the deletion of duplicate nodes is also successfully realized.
Finally, the complete code is attached
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//Use typedef to define a name for int as ElemType, which means the type of the element in the table
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node * next;
}Node,* LinkList;
//Initialize single linked list
void Init_LinkList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));//Create header node
(*L)->next=NULL;//Create an empty single linked list
}
//Delete the first largest element in the single linked list
void delmaxnode(LinkList L)
{
Node *p=L->next,*pre=L,*maxp=p,*maxpre=pre;
while (p!=NULL)
{
if (maxp->data<p->data) //If a larger node is found
{
maxp=p; //Change maxp
maxpre=pre; //Change maxpre s
}
pre=p; //p. Move one node after pre synchronization
p=p->next;
}
maxpre->next=maxp->next; //Delete * maxp node
free(maxp); //Release * maxp node
}
//Delete duplicate nodes
void del_repeated_node(LinkList L)
{
Node *k = L->next;
Node *pre_p=k;
Node *p=pre_p->next;
//Traverse each node of the single linked list
while(k && k->next != NULL)
{ //Judge whether the node behind k is repeated with the value field of k. if it is repeated, delete it.
while(p)
{
if(k->data == p->data)
{
//Delete duplicate p nodes
Node* temp = p;
pre_p ->next= p->next;
p = pre_p->next;
free(temp);
}
else
{
pre_p = pre_p->next;
p = pre_p->next;
}
}
k = k->next;
pre_p=k;
p = pre_p->next;
}
}
//Tail interpolation table
void CreateFromTail(LinkList L)
{
Node *r,*s;//A dynamic tail pointer r
int flag=1;
r=L;
char c;
while(flag)
{
c=getchar();
// printf(" ");
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=(int)c;
r->next=s;
r=s;//r is always at the end
}
else
{
flag=0;
r->next=NULL;//Set the next chain field of the last node to empty, indicating the end of the linked list
}
}
}
//display single linked list
void Display_LinkList(LinkList L)
{
//printf("display call start \ n");
Node *p;
ElemType s;
p=L;
while(p->next)
{
//p=p->next;
printf("%c ",p->next->data);
//printf(" ");
p=p->next;
}
//Printf ("end of display call \ n");
}
int main()
{
LinkList L;
ElemType e,x;
int i=1,k,j;
Init_LinkList(&L);
printf("The single chain table established by tail interpolation is as follows:\n(Input rule: input a number one by one without adding space and carriage return. Space and carriage return will also be regarded as one character. Please enter at the end'$')\n");
CreateFromTail(&L);
//system("cls");
while(i)//Keep it going
{
printf("\n Current linked list: ");
Display_LinkList(&L);
printf("\n-------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 Delete the first largest element \n");
printf(" 2 Delete duplicate nodes \n");
printf(" 3 Clear screen \n");
printf(" 0 End program \n");
printf("--------------------------------------\n");
printf("Please enter the menu number you selected<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
delmaxnode(&L);
break;
case 2:
del_repeated_node(&L);
break;
case 3:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("Incorrect input~");
}
}
return 0;
}