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.