数据结构实验1 线性表的有关操作

系统管理员 2022-07-27 10:58 169阅读 0赞

数据结构试验1 线性表的有关操作：

操作要求：

1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。

2．遍历单向链表。

3．把单向链表中元素逆置（不允许申请新的结点空间）。

4．在单向链表中删除所有的偶数元素结点。

5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。

6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。

7．利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。

8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

10．在主函数中设计一个简单的菜单，分别调试上述算法。

按照要求去逐个实现算法

具体代码实现如下：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <windows.h>
    #include <time.h>
    
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct LNode
    {
        ElemType data;
        struct LNode *next;
    } LNode,*LinkList;
    
    void Menu()
    {
        cout<<"0.break."<<endl;
        cout<<"1.Create The List:"<<endl;
        cout<<"2.Display The List:"<<endl;
        cout<<"3.NiZhi The List:"<<endl;
        cout<<"4.Delete OuShu:"<<endl;
        cout<<"5.Create The Sort DiZeng List:"<<endl;
        cout<<"6.Hebing Two Lists into DiZeng List:"<<endl;
        cout<<"7.Hebing Two Lists into DiJian List:"<<endl;
        cout<<"8.Fenjie Odd & Fodd:"<<endl;
    }
    
    LinkList Creat()
    {
        LinkList head,p,q;
        ElemType x;
        head=new LNode;  //head=(LinkList )malloc(sizeof(LNode));
        p=head;
        cin>>x;
        while(x!=0)
        {
            q=new LNode;
            q->data=x;
            p->next=q;
            p=p->next; //p=q;
            cin>>x;
        }
        p->next=NULL;
        return head;
    }
    
    LinkList CreateRandom()
    {
        //srand(time(0)); //随机数种子
        //int a=rand()%150; //产生150以内的随机数
        LinkList head,p,q;
        ElemType x;
        head=new LNode;  //head=(LinkList )malloc(sizeof(LNode));
        p=head;
        srand(time(0));
        x=rand()%10;
        while(x!=0)
        {
            q=new LNode;
            q->data=x;
            p->next=q;
            p=p->next; //p=q;
            x=rand()%10;//产生10以内的随机数，遇到0结束
        }
        p->next=NULL;
        return head;
    }
    
    void Display(LinkList head)
    {
        LinkList p;
        p=head->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    
    void Nizhi(LinkList &L)
    {
        LinkList p,q;
        p=L->next;
        L->next=NULL;
        while(p!=NULL)
        {
            q=p;
            p=p->next;
            q->next=L->next;
            L->next=q;
        }
    }
    
    void Deletoushu(LinkList &L)
    {
        LinkList p,q;
        p=L;
        q=p->next;
        while(q)
        {
            if(q->data%2==0)
            {
                p->next=q->next;
                free(q);
                q=p->next;
            }
            else
            {
                p=p->next;
                q=q->next;
            }
        }
    }
    
    void Insert(LinkList &L,ElemType x)
    {
        LinkList p,q;
        p=L;
        q=p->next;
        while(q!=NULL&&x>q->data)
        {
            p=p->next;
            q=q->next;
        }
        if(q==NULL)
        {
            q=new LNode;
            q->data=x;
            q->next=NULL;
            p->next=q;
        }
        else
        {
            LinkList s;
            s=new LNode;
            s->data=x;
            p->next=s;
            s->next=q;
        }
    }
    
    LinkList Creath()
    {
        LinkList Lhead1;
        Lhead1=(LinkList)malloc(sizeof(LNode));
        if(Lhead1!=NULL)
        {
            Lhead1->next=NULL;
        }
        return Lhead1;
    }
    
    void Hebing1(LinkList &head1,LinkList &head2,LinkList &head)
    {
        LinkList p1,p2,p,p11,p22;
        p=head;
        p1=head1->next;
        p2=head2->next;
        while(p1!=NULL && p2!=NULL)
        {
            if(p1->data>p2->data)
            {
                p11=p1;
                p1=p1->next;
                p->next=p11;
                p=p->next;
                p->next=NULL;
            }
            else
            {
                p22=p2;
                p2=p2->next;
                p->next=p22;
                p=p->next;
                p->next=NULL;
            }
        }
        if(p1!=NULL)
        {
            p->next=p1;
        }
        else
        {
            p->next=p2;
        }
    }
    
    void Hebing2(LinkList &head1,LinkList &head2,LinkList &head)
    {
        LinkList p1,p2,p,p11,p22;
        p=head;
        p1=head1->next;
        p2=head2->next;
        while(p1!=NULL && p2!=NULL)
        {
            if(p1->data<p2->data)
            {
                p11=p1;
                p1=p1->next;
                p->next=p11;
                p=p->next;
                p->next=NULL;
            }
            else
            {
                p22=p2;
                p2=p2->next;
                p->next=p22;
                p=p->next;
                p->next=NULL;
            }
        }
        if(p1!=NULL)
        {
            p->next=p1;
        }
        else
        {
            p->next=p2;
        }
    }
    
    void Freeh(LinkList &head)
    {
        LinkList p,q;
        p=head;
        q=NULL;
        while(p!=NULL)
        {
            q=p;
            p=p->next;
            free(q);
        }
    }
    
    void Fenjie(LinkList &Lhead,LinkList &headodd,LinkList &headfodd)
    {
        LinkList p,p1,p2,q;
        p=Lhead->next;
        p1=headodd;
        p2=headfodd;
        while(p!=NULL)
        {
            if(p->data%2==0)
            {
                q=p;
                p=p->next;
                p2->next=q;
                p2=p2->next;
                p2->next=NULL;
            }
            else
            {
                q=p;
                p=p->next;
                p1->next=q;
                p1=p1->next;
                p1->next=NULL;
            }
        }
    }
    
    
    int main()
    {
        LinkList Lhead;
        LinkList Lhead1;
        LinkList head,head1,head2;
        LinkList headodd,headfodd;
    
        int choosecase;
        cout<<"WELCOME !"<<endl<<endl;
        Menu();
        cout<<"Please Input Your Choice:"<<endl;
        cin>>choosecase;
        while(choosecase!=0)
        {
            switch (choosecase)
            {
            case 1 :
                cout<<"Create The LinkList ...ing"<<endl;
                //cout<<"Please Input The Datas:"<<endl;
                Lhead=CreateRandom();
                cout<<"Create Over!"<<endl;
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
                break;
    
            case 2 :
                cout<<"Display The List:"<<endl;
                Display(Lhead);
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
                break;
    
            case 3 :
                cout<<"NiZhi The List...ing"<<endl;
                Nizhi(Lhead);
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
                break;
    
            case 4 :
                Deletoushu(Lhead);
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
                break;
    
            case 5 :
                LinkList Lhead1;
                Lhead1=Creath();
                int x;
                cin>>x;
                while(x!=0)
                {
                    Insert(Lhead1,x);
                    cin>>x;
                }
                Display(Lhead1);
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
                break;
    
            case 6 :
                head=Creath();
                head1=Creath();
                head2=Creath();
                int x1,x2;
                cout<<"Please Input The First List:"<<endl;
                cin>>x1;
                while(x1!=0)
                {
                    Insert(head1,x1);
                    cin>>x1;
                }
                cout<<"Please Input The Second List:"<<endl;
                cin>>x2;
                while(x2!=0)
                {
                    Insert(head2,x2);
                    cin>>x2;
                }
                //Display(head1);
                //Display(head2);
                Nizhi(head1);
                Nizhi(head2);
                //Display(head1);
                //Display(head2);
                Hebing1(head1,head2,head);
                cout<<"After Hebing, The List is:"<<endl;
                Display(head);
                cout<<"Free ...ing"<<endl;
                Freeh(head);
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
                break;
    
            case 7 :
                head=Creath();
                head1=Creath();
                head2=Creath();
                int xx1,xx2;
                cout<<"Please Input The First List:"<<endl;
                cin>>xx1;
                while(xx1!=0)
                {
                    Insert(head1,xx1);
                    cin>>xx1;
                }
                cout<<"Please Input The Second List:"<<endl;
                cin>>xx2;
                while(xx2!=0)
                {
                    Insert(head2,xx2);
                    cin>>xx2;
                }
                //Display(head1);
                //Display(head2);
                //Display(head1);
                //Display(head2);
                Hebing2(head1,head2,head);
                cout<<"After Hebing1, The List is:"<<endl;
                Display(head);
                cout<<"Free ...ing"<<endl;
                Freeh(head);
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
                break;
    
            case 8 :
                headodd=Creath();
                headfodd=Creath();
                Fenjie(Lhead,headodd,headfodd);
                cout<<"The odd List is:"<<endl;
                Display(headodd);
                cout<<"The fodd List is:"<<endl;
                Display(headfodd);
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
                break;
    
            default:
                cout<<"Input Error!"<<endl;
                Menu();
                cout<<"Please Input Your Choice:"<<endl;
                cin>>choosecase;
            }
        }
        return 0;
    }

注：提示性语句采用中拼结合大法，敬请谅解！