数据结构 - 2顺序表及链表基本运算实现

太过爱你忘了你带给我的痛 2022-07-26 12:27 162阅读 0赞

# 实验目的 #

深入掌握线性表的两种存储方法，即顺序表和链表。体会这两种存储结构之间的差异。

# 实验内容 #

## 1. 编写一个程序exp2-1.cpp，实现顺序表的各种运算（假设顺序表的元素类型为char） ##

并在此基础上完成如下功能：

（1）初始化顺序表L；  
（2）采用尾插法依次插入元素a，b，c，d，e；  
（3）输出顺序表L；  
（4）输出顺序表L的长度；  
（5）判断顺序表L是否为空；  
（6）输出顺序表L的第3个元素；  
（7）输出元素a的位置；  
（8）在第4个元素位置上插入元素f；  
（9）输出顺序表L；  
（10）删除L的第3个元素；  
（11）输出顺序表L；  
（12）释放顺序表L

#include <iostream>
    #include <malloc.h>
    using namespace std;
    typedef char
    ElemType;
    typedef class Sqlist{
        public:
        ElemType data[100];
        int length;
    };
    void CreateList(Sqlist *&L,ElemType a[],int n);
    void InitList(Sqlist *&L);
    void DisList(Sqlist *L);//输出元素
    void ListLength(Sqlist *L);//输出长度
    bool judge(Sqlist *L);   //判断线性表是否为空
    bool getElem(Sqlist *L,int i);     //输出线性表第e个元素
    int LocatElem(Sqlist *L,ElemType e);         //8.输出指定元素位置
    bool ListInsert(Sqlist *L,int i,ElemType e);    //9.在第i个元素位置上插入元素e
    bool ListDle(Sqlist *L,int i,ElemType e);      //删除元素
    void DestroyList(Sqlist *&L);                //销毁线性表
    int main()
    {
        Sqlist *L;
        char a[]={'a','b','c','d','e'};
        cout<<"(1)初始化线性表"<<endl;
        InitList(L);
        cout<<"(2)采用尾插法依次插入元素a，b，c，d，e"<<endl;
        CreateList(L,a,5);
        cout<<"(3)输出顺序表L:";
        DisList(L);
        cout<<"(4)顺序表L的长度=";
        ListLength(L);
        cout<<"(5)顺序表L为";
        if(judge(L))
            cout<<"空！"<<endl;
        else
            cout<<"非空！"<<endl;
        cout<<"(6)顺序表的第三个元素=";
        if(getElem(L,3));
        cout<<"(7)元素a的位置:"<<LocatElem(L,'a');
        cout<<"(8)在第四个位置插入元素f";
        if(ListInsert(L,4,'f'))
            cout<<endl;
        cout<<"(9)输出顺序表：";
        DisList(L);
        cout<<"(10)删除线性表L第三个元素";
        if(ListDle(L,3,'e'));
            cout<<endl;
        cout<<"(11)输出顺序表：";
        DisList(L);
        cout<<"(12)释放线性表"<<endl;
        DestroyList(L);
        return 0;
    }
    void CreateList(Sqlist *&L,ElemType a[],int n)
    {
        int i;
        L=(Sqlist * )malloc(sizeof(Sqlist));
        for(int i=0;i<n;++i)
        {
            L->data[i]=a[i];
        }
        L->length=n;
    }
    void InitList(Sqlist *&L)
    {
        L=(Sqlist * )malloc(sizeof(Sqlist));
        L->length=0;
    }
    void DisList(Sqlist *L)   //输出元素
    {
        for(int i=0;i<L->length;++i)
        {
            cout<<L->data[i]<<" ";
        }
        cout<<endl;
    }
    void ListLength(Sqlist *L)   //输出长度
    {
        cout<<L->length<<endl;
    }
    bool judge(Sqlist *L)   //判断线性表是否为空
    {
        return(L->length==0);
    }
    bool getElem(Sqlist *L,int i)     //7.输出线性表第e个元素
    {
        if(i<1||i>L->length)
            return false;
        cout<<L->data[i-1]<<endl;
        return true;
    }
    int LocatElem(Sqlist *L,ElemType e)        //8.输出指定元素位置
    {
        int i=0;
        while(i<L->length&&L->data[i]!=e)
            i++;
        if(i>=L->length)
            return 0;
        else
            return i+1;
    }
    bool ListInsert(Sqlist *L,int i,ElemType e)    //9.在第i个元素位置上插入元素e
    {
        int j;
        if(i<1||i>L->length+1)
            return false;
        i--;
        for(j=L->length;j>i;--j)
            L->data[j]=L->data[j-1];
        L->data[i]=e;
        L->length++;
        return true;
    }
    bool ListDle(Sqlist *L,int i,ElemType e)    //9.在第i个元素位置上插入元素e
    {
        int j;
        if(i<1||i>L->length+1)
            return false;
        i--;
        e=L->data[i];
        for(j=i;j<L->length;++j)
            L->data[j]=L->data[j+1];
        L->length--;
        return true;
    }
    void DestroyList(Sqlist *&L)                //销毁线性表
    {
        free(L);
    }

## 2. 编写一个程序exp2-2.cpp，实现单链表的各种基本运算（假设单链表的元素类型为char） ##

并在此基础上完成如下功能：

（1）初始化单链表h；  
（2）采用尾插法依次插入元素a，b，c，d，e；  
（3）输出单链表h；  
（4）输出单链表h长度；  
（5）判断单链表h是否为空；  
（6）输出单链表h的第3个元素；  
（7）输出元素a的位置；  
（8）在第4个元素位置上插入元素f；  
（9）输出单链表h；  
（10）删除h的第3个元素；  
（11）输出单链表h；  
（12）释放单链表h

#include <iostream>
    #include <malloc.h>
    using namespace std;
    typedef char ElemType;
    typedef class Linklist{
        public:
        ElemType data;
        Linklist *next;
    };
    void CreateList(Linklist *&L,ElemType a[],int n);
    void InitList(Linklist *&L);
    void DisList(Linklist *L);//输出元素
    void ListLength(Linklist *L);//输出长度
    bool judge(Linklist *L);   //判断线性表是否为空
    bool getElem(Linklist *L,int i);     //输出线性表第e个元素
    int LocatElem(Linklist *L,ElemType e);         //8.输出指定元素位置
    bool ListInsert(Linklist *L,int i,ElemType e);    //9.在第i个元素位置上插入元素e
    bool ListDle(Linklist *L,int i,ElemType e);      //删除元素
    void DestroyList(Linklist *&L);                //销毁线性表
    int main()
    {
        Linklist *L;
        char a[]={'a','b','c','d','e'};
        cout<<"(1)初始化单链表"<<endl;
        InitList(L);
        cout<<"(2)采用尾插法依次插入元素a，b，c，d，e"<<endl;
        //if(L->data=='x')
       //     cout<<'Y'<<endl;
        CreateList(L,a,5);
        cout<<"(3)输出单链表h:";
        DisList(L);
        cout<<"(4)单链表h的长度=";
        ListLength(L);
        cout<<"(5)单链表h为";
        if(judge(L))
            cout<<"空！"<<endl;
        else
            cout<<"非空！"<<endl;
        cout<<"(6)单链表的第三个元素=";
        if(getElem(L,3));
        cout<<"(7)元素a的位置:"<<LocatElem(L,'a')<<endl;
        cout<<"(8)在第四个位置插入元素f";
        if(ListInsert(L,4,'f'))
            cout<<endl;
        cout<<"(9)输出单链表h：";
        DisList(L);
        cout<<"(10)删除单链表h第三个元素";
        if(ListDle(L,3,'e'));
            cout<<endl;
        cout<<"(11)输出单链表：";
        DisList(L);
        cout<<"(12)释放单链表"<<endl;
        DestroyList(L);
        return 0;
    }
    void CreateList(Linklist *&L,ElemType a[],int n)
    {
        Linklist *s,*r;
        int i;
        L=(Linklist * )malloc(sizeof(Linklist));
        r=L;
        for(int i=0;i<n;++i)
        {
            s=(Linklist *)malloc(sizeof(Linklist));
            s->data=a[i];
            cout<<s->data<<endl;
            r->next=s;
            r=s;
        }
        r->next=NULL;
    }
    void InitList(Linklist *&L)
    {
        L=(Linklist * )malloc(sizeof(Linklist));
        L->next=NULL;
    }
    void DisList(Linklist *L)   //输出元素
    {
        Linklist *p=L;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    void ListLength(Linklist *L)   //输出长度
    {
        int n=0;
        Linklist *p=L;
        while(p->next!=NULL)
        {
            n++;
            p=p->next;
        }
        cout<<n<<endl;
    }
    bool judge(Linklist *L)   //判断线性表是否为空
    {
        return(L->next==NULL);
    }
    bool getElem(Linklist *L,int i)     //7.输出线性表第e个元素
    {
        int j=0;
        Linklist *p=L;
        while(j<i&&p!=NULL)
        {
            j++;
            p=p->next;
        }
        if(p==NULL)
            return false;
        else
        {
            cout<<p->data<<endl;
            return true;
        }
    }
    int LocatElem(Linklist *L,ElemType e)        //8.输出指定元素位置
    {
        int i=1;
        Linklist *p=L->next;
        while(p!=NULL&&p->data!=e)
        {
            p=p->next;
            i++;
        }
        if(p==NULL)
            return 0;
        else
            return i;
    }
    bool ListInsert(Linklist *L,int i,ElemType e)    //9.在第i个元素位置上插入元素e
    {
        int j=0;
        Linklist *p=L,*s;
        while(j<i-1&&p!=NULL)
        {
            j++;
            p=p->next;
        }
        if(p==NULL)
           return false;
        else
        {
            s=(Linklist *)malloc(sizeof(Linklist));
            s->data=e;
            s->next=p->next;
            p->next=s;
            return true;
        }
    }
    bool ListDle(Linklist *L,int i,ElemType e)    //9.在第i个元素位置上s删除元素e
    {
        int j=0;
        Linklist *p=L,*q;
        while(j<i-1&&p!=NULL)
        {
            j++;
            p=p->next;
        }
        if(p==NULL)
           return false;
        else
        {
            q=p->next;
            if(q==NULL)
                return false;
            e=q->data;
            p->next=q->next;
            free(q);
            return true;
        }
    }
    void DestroyList(Linklist *&L)                //销毁线性表
    {
        free(L);
    }

# 运行结果： #

![Center][]

![Center 1][]

[Center]: /images/20220724/d0650f666948401799295681a534b2b0.png
[Center 1]: /images/20220724/570907c7ffe64158b03665217e44b7b0.png