Experiment 3: design and verify all operations represented by linear table sequence on the computer

This blog is from teacher YanWeiMin's book 《 data structure 》 Today, you need to verify the single linked list in the book , I have nothing to do to help them directly .

Topic reproduction

1、 The main basic operations of the current single linked list , And write a main program to verify ;
2、 In a single linked list L Two data elements of a and b Insert between x, Write insert x Algorithm implementation of , And write a program to verify

Idea of problem solving

1. subject 1 The code on the book is mainly typed once
2. The second question is given directly O(n) To insert

subject 1：

Status GetElem_L(LinkList L,int i,ElemType &e){
    
    LinkList  p = L->next;
    int j = 1;
    while(p && j<i){
    
        p = p->next;
        ++j;
    }
    if(!p || j>i) return ERROR;
    e = p->data;
    return OK;
}

Status ListInsert_L(LinkList &L,int i,ElemType e){
    
    LinkList  p = L;
    int j = 0;
    while(p && j<i-1){
    
        p = p->next;
        ++j;
    }
    if(!p || j>i-1) return ERROR;
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status ListDelete_L(LinkList &L,int i,ElemType &e){
    
    LinkList p = L;
    int j = 0;
    while(p->next && j<i-1){
    
        p = p->next ;
        ++j;
    }
    if(!(p->next)||j>i-1) return ERROR;
    LinkList q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}

void CreateList_L(LinkList&L,int n ){
    
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    for(int i=n;i>0;i--){
    
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d",&p->data);
        p->next = L->next;
        L->next = p;
    }
}

subject 2

Status LinkList_ab(LinkList&L,ElemType a,ElemType b,ElemType x){
    
    LinkList p = L;
    p = p->next;
    while(p){
    
        if(p->data == a) break;
        p = p->next;
    }
    LinkList q = p->next;
    if(p==NULL || q==NULL) return ERROR;
    else{
    
        LinkList tmp = (LinkList)malloc(sizeof(LNode));
        tmp->data = x;
        p->next = tmp;
        tmp->next = q;
    }
    return OK;


}

summary

No difficulty. , Just follow the book .

Complete code

#include<iostream>
#define ERROR -1
#define OK 1
using namespace std;
typedef int ElemType;
typedef int Status;
typedef struct LNode{
    
    ElemType data;
    struct LNode*next;
}LNode,*LinkList;

Status GetElem_L(LinkList L,int i,ElemType &e){
    
    LinkList  p = L->next;
    int j = 1;
    while(p && j<i){
    
        p = p->next;
        ++j;
    }
    if(!p || j>i) return ERROR;
    e = p->data;
    return OK;
}

Status ListInsert_L(LinkList &L,int i,ElemType e){
    
    LinkList  p = L;
    int j = 0;
    while(p && j<i-1){
    
        p = p->next;
        ++j;
    }
    if(!p || j>i-1) return ERROR;
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status ListDelete_L(LinkList &L,int i,ElemType &e){
    
    LinkList p = L;
    int j = 0;
    while(p->next && j<i-1){
    
        p = p->next ;
        ++j;
    }
    if(!(p->next)||j>i-1) return ERROR;
    LinkList q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}

void CreateList_L(LinkList&L,int n ){
    
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    for(int i=n;i>0;i--){
    
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d",&p->data);
        p->next = L->next;
        L->next = p;
    }
}
// In a single linked list L Two data elements of a and b Insert between x, Write insert x Algorithm implementation of 
// Assume adjacency 
Status LinkList_ab(LinkList&L,ElemType a,ElemType b,ElemType x){
    
    LinkList p = L;
    p = p->next;
    while(p){
    
        if(p->data == a) break;
        p = p->next;
    }
    LinkList q = p->next;
    if(p==NULL || q==NULL) return ERROR;
    else{
    
        LinkList tmp = (LinkList)malloc(sizeof(LNode));
        tmp->data = x;
        p->next = tmp;
        tmp->next = q;
    }
    return OK;


}
Status Print(LinkList L){
    
    if(L==NULL) return ERROR;
    LinkList p = L;
    p=p->next;
    while(p){
    
        cout << " " << p->data;
        p=p->next;
    }
    cout << endl;
}
int main(){
    
    LinkList L;
    cout << "test1:createList:" << endl;
    CreateList_L(L,5);
    Print(L);
    //Delete L

    //1 2 3 4 5
    int x;
    int flag = ListDelete_L(L,1,x);
    cout << "test2: deleted: "  << x << endl;
    Print(L);
    cout << "test3: geted:" ;
    GetElem_L(L,2,x);
    cout << x << endl;
    cout << "test4:ListInsert_L:5" << endl;
    ListInsert_L(L,2,5);
    Print(L);
    cout << "test5:insert [5,3] into 4"<< endl;
    LinkList_ab(L,5,3,4);
    Print(L);
    return 0;
}