实验一 单链表

#include<bits/stdc++.h>

using namespace std;

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;


//初始化
bool InitList(LinkList &L){
    L=new LNode;
    if(!L){
        return false;
    }
    L->next=NULL;
    return true;
}

//头插法
void ListInsert_F(LinkList &L,int fv){
    LinkList s;
    s=new LNode;
    s->data=fv;
    s->next=L->next;
    L->next=s;
}

//尾插法
void ListInsert_B(LinkList &L,int bv){
    LinkList s,r;
    r=L;
    while(r->next!=NULL){
        r=r->next;
    }
    s=new LNode;
    s->data=bv;
    s->next=NULL;
    r->next=s;
    r=s;
}

//位置插入
bool ListInsert_P(LinkList &L,int i,int e){
    int j;
    LinkList p,s;
    p = L;
    j = 0;
    while(p && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if(!p || j > i - 1)
        return false ;
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

//删除元素（位置删除）
bool ListDelete_P(LinkList &L,int i){
    LinkList p,q;
    int j = 0;
    p = L;
    while((p->next)&&(j<i-1))  //p的下一个结点存在才能删除
    {
        p=p->next;
        j++;
    }
    if(!(p->next)||(j>i-1)){  //当i > n 或i < 1时删除位置不合理
        return false;
    }
    q=p->next;;
    p->next=q->next;
    delete q;
    return true;
}

//删除元素（值删除）
bool ListDelete_V(LinkList &L,int vd){
    if(L->next==NULL){
        cout<<"当前表为空表，没有值可供删除"<<endl;
        return false;
    }
    LNode *cur,*pre;
    pre=L;
    cur=L->next;
    while(cur!=NULL){
        if(cur->data==vd){
            pre->next=cur->next;
            free(cur);
            return true;
        }
        pre=cur;
        cur=cur->next;
    }
    return false;
}
//输出
void ListOutput(LinkList L){
    LinkList p;
    p=L->next;
    if(p==NULL){
        cout<<"当前为空表"<<endl;
    }else{
        cout<<"当前单链表元素为";
        while(p!=NULL){
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
}

//查找
bool ListSearch(LinkList &L,int sv){
    if(L->next==NULL){
        cout<<"表中没有此元素"<<endl;
        return false;
    }
    int cnt=1;
    LNode *cur,*pre;
    pre=L;
    cur=L->next;
    while(cur!=NULL){
        if(cur->data==sv){
            cout<<"此元素在表中第"<<cnt<<"位"<<endl;
            return true;
        }
        pre=cur;
        cur=cur->next;
        cnt++;
    }
    return false;
}

//求前驱
bool ListFr(LinkList &L,int efr){
    if(L->next==NULL){
        cout<<"表中没有此元素"<<endl;
        return false;
    }
    LNode *cur,*pre;
    pre=L;
    cur=L->next;
    while(cur!=NULL){
        if(cur->data==efr){
            cout<<"此元素的前驱为"<<pre->data<<endl;
            return true;
        }
        pre=cur;
        cur=cur->next;
    }
    return false;
}
//求后继
bool ListAf(LinkList &L,int eaf){
    if(L->next==NULL){
        cout<<"表中没有此元素"<<endl;
        return false;
    }
    LNode *cur,*pre;
    pre=L;
    cur=L->next;
    while(cur!=NULL){
        if(cur->data==eaf){
            cout<<"此元素的后继为"<<cur->next->data<<endl;
            return true;
        }
        pre=cur;
        cur=cur->next;
    }
    return false;
}
//销毁单链表
bool ListDestory(LinkList &L){
    LinkList p=L;
    while(p){
        L=L->next;
        delete(p);
        p=L;
    }
    cout<<"链表已销毁"<<endl;
    return true;
}

//置空表
bool ListEmpty(LinkList &L){
    LinkList p;
    while(L->next){
        p=L->next;
        L->next=p->next;
        delete(p);
    }
    return true;
}

//求单链表长度
bool ListLength(LinkList &L){
    int len=0;
    if(L==NULL){
        cout<<"当前为空表，表长为：0"<<endl;
    }else{
        while(L->next){
            len++;
            L=L->next;
        }
        cout<<"当前表长为："<<len<<endl;
    }
    return true;
}

//获取特定位置结点内容
void ListGetData(LinkList &L,int pos){
    LinkList p=L;
    while(pos--){
        p=p->next;
    }
    cout<<"此位置的数据为："<<p->data<<endl;
}

int main(){

    LinkList List;
    cout<<"1.建立链表"<<endl;
    cout<<"2.插入元素(头插入)"<<endl;
    cout<<"3.插入元素(尾插入)"<<endl;
    cout<<"4.插入元素(位置插入)"<<endl;
    cout<<"5.删除元素(位置删除)"<<endl;
    cout<<"6.删除元素(值删除)(第一个)"<<endl;
    cout<<"7.查找元素是否在链表中"<<endl;
    cout<<"8.查找元素的前驱"<<endl;
    cout<<"9.查找元素的后继"<<endl;
    cout<<"10.销毁"<<endl;
    cout<<"11.置空表"<<endl;
    cout<<"12.求表长"<<endl;
    cout<<"13.获取特定位置结点的内容"<<endl;
    cout<<"请输入将要进行的操作编号："<<endl;
    int option;
    cin>>option;
    while(option!=15){
        switch(option){
            case 1:
                InitList(List);
                ListOutput(List);
                break;
            case 2:
                int f;
                cout<<"头插入的值为：";
                cin>>f;
                ListInsert_F(List,f);
                ListOutput(List);
                break;
            case 3:
                int b;
                cout<<"尾插入的值为：";
                cin>>b;
                ListInsert_B(List,b);
                ListOutput(List);
                break;
            case 4:
                int ips,val;
                cout<<"要插入的位置是："<<endl;
                cin>>ips;
                cout<<"要插入的值是："<<endl;
                cin>>val;
                ListInsert_P(List,ips,val);
                ListOutput(List);
                break;
            case 5:
                int dps;
                cout<<"要删除的位置是："<<endl;
                cin>>dps;
                ListDelete_P(List,dps);
                ListOutput(List);
                break;
            case 6:
                int dv;
                cout<<"要删除的值是：";
                cin>>dv;
                ListDelete_V(List,dv);
                ListOutput(List);
                break;
            case 7:
                int vs;
                cout<<"要查找的元素是：";
                cin>>vs;
                ListOutput(List);
                ListSearch(List,vs);
                break;
            case 8:
                int px;
                cout<<"要查找前驱的元素是：";
                cin>>px;
                ListOutput(List);
                ListFr(List,px);
                break;
            case 9:
                int bx;
                cout<<"要查找后继的元素是：";
                cin>>bx;
                ListOutput(List);
                ListAf(List,bx);
                break;
            case 10:
                ListDestory(List);
                break;
            case 11:
                ListEmpty(List);
                ListOutput(List);
                break;
            case 12:
                ListOutput(List);
                ListLength(List);
                break;
            case 13:
                int posi;
                cout<<"结点的位置为：";
                cin>>posi;
                ListOutput(List);
                ListGetData(List,posi);
                break;
        }
        cin>>option;
    }
    return 0;
}