Section 7.3 of algorithm notes - Special Topic on data structure (1) - > linked list processing

# Problem A: algorithm 2-8 ~ 2-11: basic operation of linked list

### Title Description

Linked list is one of the most basic data structures. It is a linear list realized by linked storage structure. Compared with the sequential table, it does not have to move the subsequent elements during insertion and deletion. Now give you some integers, and then you will frequently insert and delete some elements. At some time, you will find an element or output all the elements in the current linked list.

Here is the basic algorithm description:

### input

There is only one set of input data. The first line has n+1 integers. The first integer is the number of remaining integers in this line, N, followed by N integers. This line of integers is used to initialize the list, and the input order is opposite to that in the list, that is, if there are 1, 2 and 3 in the list, the input order is 3, 2 and 1.

The second line has an integer m, which means there are m lines below. Each line has a string. The string is one of "get", "insert", "delete" and "show". If it is "get" or "delete", it will be followed by an integer a, which means to obtain or delete the a-th element; If it is "insert", it will be followed by two integers a and E, representing the insertion of e before the a position; There is no integer after "show".

### output

If the acquisition is successful, the element is output; If the deletion is successful, "delete OK" is output; If the acquisition or deletion fails, "get fail" and "delete fail" are output. If the insertion is successful, "insert OK" is output; otherwise, "insert fail" is output. If it is "show", all elements in the list will be output. If the list is empty, "Link list is empty" will be output. Note: all double quotation marks are not output.

### sample input

3 3 2 1

21

show

delete 1

show

delete 2

show

delete 1

show

delete 2

insert 2 5

show

insert 1 5

show

insert 1 7

show

insert 2 5

show

insert 3 6

show

insert 1 8

show

get 2

### sample output

1 2 3

delete OK

2 3

delete OK

2

delete OK

Link list is empty

delete fail

insert fail

Link list is empty

insert OK

5

insert OK

7 5

insert OK

7 5 5

insert OK

7 5 6 5

insert OK

8 7 5 6 5

7

### code

#include<cstdlib>//malloc func #include<cstdio>//stdio func #include<cstring>//strcmp func #define OK 1 #define ERROR 0 typedef int Status;//function type typedef int ElemType;//LNode data type typedef struct LNode{ ElemType data;//data element definition struct LNode *next;//next node address definition }LNode, *LinkList;//node type & list type definition Status GetElem_L(LinkList &L,int i, ElemType &e){ //L is head node LinkList p; p=L->next; int j=1;//p is the 1st node(next to L), j is a counter while (p&&j<i){//find the node i(L is node 0) p=p->next; ++j; } if (!p||j>i)//node i is not exist return ERROR; e=p->data;//e is data of node i return OK; } Status ListInsert_L(LinkList &L, int i,ElemType e){ //insert new data before node i LinkList p,s;//definition of new node(s),node i-1(p) p=L; int j=0; while(p&&j<i-1){//find node i-1 p=p->next; ++j; } if(!p||j>i-1)//if i<1 or i>length of list, return ERROR return ERROR; s=(LinkList)malloc(sizeof(LNode));//insert new node as node i-1 s->data=e; s->next=p->next; p->next=s; return OK; } Status ListDelete_L(LinkList &L,int i,ElemType &e){ //delete node i,and return the data by e(by address transmission) LinkList p,q; p=L; int j=0; while(p->next&&j<i-1){//find the node i-1 p=p->next; ++j; } if(!(p->next)||j>i-1)//delete isn't exist return ERROR; q=p->next; p->next=q->next;//delete and free node e=q->data; free(q); return OK; } void CreateList_L(LinkList &L,int n){ //input a list from rear to start LinkList p; int i;//the length of list L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;//head node allocate for(i=n;i>0;--i){ p=(LinkList)malloc(sizeof(LNode));//new node between head node(L) and L->next scanf("%d",&p->data); p->next=L->next; L->next=p; } } void ShowList_L(LinkList &L){ //show data of L LinkList p=L->next;//p is a node to show L if(p==NULL) { printf("Link list is empty\n"); return; } while(p!=NULL){ if(p->next==NULL) printf("%d",p->data); else printf("%d ",p->data); p=p->next; } printf("\n"); } int main(){ int n=0,m=0,num=0; ElemType e; char str_Instruction[10]; LinkList List; scanf("%d",&n); CreateList_L(List,n); scanf("%d",&m); while(m--){ scanf("%s",str_Instruction); if(!strcmp(str_Instruction,"get")){ scanf("%d",&num); if(GetElem_L(List,num,e)){ printf("%d\n",e); } else{ printf("get fail\n"); } } else if(!strcmp(str_Instruction,"delete")){ scanf("%d",&num); if(ListDelete_L(List,num,e)){ printf("delete OK\n"); } else{ printf("delete fail\n"); } } else if(!strcmp(str_Instruction,"insert")){ scanf("%d %d",&num,&e); if(ListInsert_L(List,num,e)){ printf("insert OK\n"); } else{ printf("insert fail\n"); } } else if(!strcmp(str_Instruction,"show")){ ShowList_L(List); } } return 0; }

# Question B: C language - linked list sorting

### Title Description

There are two linked lists a and b, and the nodes in each linked list include student number and grade. It is required to merge the two linked lists and arrange them in ascending order by student number.

### input

In the first row, the number N and M of a and b linked list elements are separated by spaces. Next, row n is the data of a, and then row M is the data of b. each row of data is composed of student number and grade

### output

Data in ascending order of student number

### sample input

2 3

5 100

6 89

3 82

4 95

2 10

### sample output

2 10

3 82

4 95

5 100

6 89

### Code submission

#include <cstdio> struct node { int num; int score; node *next; }; void insert(node *ans, node *q) { //ans is the final printed linked list, and q is the node of a person's student number and score inserted node *pre, *p; //Create two new nodes pre = ans, p = ans->next; while (p != NULL && p->num < q->num) { //Find the first node whose student number is greater than q pre = p; p = p->next; } pre->next = q; // pre-q-p connection q->next = p; } int main() { node *ans, *p; int n, m; scanf("%d %d", &n, &m); ans = new node; ans->next = NULL; for (int i = 0; i < n + m; i++) { p = new node; p->next = NULL; scanf("%d %d", &p->num, &p->score); insert(ans, p); //Connect the new node into the linked list } for (p = ans->next; p != NULL; p = p->next) { printf("%d %d\n", p->num, p->score); } return 0; }

I never thought of this before. In fact, after each new node is created, the sorting can be realized by traversing to find the location where it should be inserted.