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.