链表操作总结

电玩女神 2022-05-28 10:51 209阅读 0赞

## 链表操作总结(创建,遍历,就地逆置,删除偶数结点…) ##

1、随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。  
2、遍历单向链表（显示）。  
3、把单向链表中元素逆置（不允许申请新的结点空间）。  
4、在单向链表中删除所有的偶数元素（值为偶数）结点。  
5、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。  
6、利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。  
7、利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。  
8、编写一个主函数，调试上述算法。  
所用函数::  
1.创建带头节点的单向链表，输入一组元素  
2.显示单向链表  
3.逆置元素（不申请新节点）  
4.删除所有值为偶数的节点  
5.递增数列中插入元素仍有序  
6.建立两个递增的有序单向链表，合并成一个递增  
7.建立两个递减的有序单向链表，合并成一个递减

//
    // main.cpp
    // Listlist
    //
    // Created by 王子谖on 2018/4/2.
    // Copyright © 2018 王子谖. All rights reserved.
    //
    /```
    #include <iostream>
    #include <stdlib.h>
    #include <stdio.h>
    using namespace std;
    
    /* 实验内容： 1、随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 2、遍历单向链表（显示）。 3、把单向链表中元素逆置（不允许申请新的结点空间）。 4、在单向链表中删除所有的偶数元素（值为偶数）结点。 5、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。 6、利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。 7、利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。 8、编写一个主函数，调试上述算法。 所用函数:: 1.创建带头节点的单向链表，输入一组元素 2.显示单向链表 3.逆置元素（不申请新节点） 4.删除所有值为偶数的节点 5.递增数列中插入元素仍有序 6.建立两个递增的有序单向链表，合并成一个递减 7.建立两个递减的有序单向链表，合并成一个递增 */
    
    
    typedef struct node
    {
        int data;
        struct node *next;
    }LNode,*LinkList;
    
    //1.创建带头节点的单向链表
    void init(LinkList &L)
    {
        L=(LinkList)malloc(sizeof(LNode));
        L->next=NULL;
    }
    //1.输入一组数,头插法
    void insert1(LinkList &L,int m)
    {
        LinkList p;
        p=(LinkList)malloc(sizeof(LNode));
        p->data=m;
        p->next=L->next;
        L->next=p;
    }
    //1.输入一组数,尾插法
    void insert2(LinkList &L,int m)
    {
        LinkList p,q;
        p=(LinkList)malloc(sizeof(LNode));
        p->data=m;
        p->next=NULL;
        q=L;
        if(L==NULL) //首节点为空
        {   L=p;  //L指向p
            p->next=NULL;
        }
        else{
            while (q->next!=NULL)
            {
                q=q->next;//到尾巴时
            }
            q->next=p; //插入结点
        }
    
    }
    //2.显示单向链表
    void print(LinkList &L)
    {
        LinkList p;
        p=(LinkList)malloc(sizeof(LNode));
        p=L->next;
        while(p)
        {   printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    //3.逆置元素（不申请新节点）
    void contrary(LinkList &L){
        LinkList p,q;
        p=(LinkList)malloc(sizeof(LNode));
        q=(LinkList)malloc(sizeof(LNode));
        p=L->next;
        L->next=NULL;//将链断开
        while (p) {
            q=p->next;//q永远在p的后一个
            p->next=L->next;//将p连在L的后面,先把尾巴连上
            L->next=p;//将p连在L的后面,再把前面接上
            p=q;//p指向下一个,即q所在的位置
        }
    }
    //4.删除所有值为偶数的节点
    void delet(LinkList &L)
    {
        LinkList p,q;
        p=(LinkList)malloc(sizeof(LNode));
        q=(LinkList)malloc(sizeof(LNode));
        p=L->next;
        q=L;
        while(p)
        {
               if((p->data)%2!=0)
                {
                     p=p->next;
                     q=q->next;
                }
               else{
                   q->next=p->next;//删除节点
                   p=p->next;
               }
        }
    }
    //5.递增数列中插入元素仍有序
    void insert3(LinkList &L,int c)
    {
        LinkList p,q,s;
        s=(LinkList)malloc(sizeof(LNode));
        p=(LinkList)malloc(sizeof(LNode));
        q=(LinkList)malloc(sizeof(LNode));
        p=L->next;
        q=L;
        s->data=c;
        while((p->data<=c)&&(p->next!=NULL))//条件是p->next!=null
        {   p=p->next;
            q=q->next;
        }
        if(p->next==NULL)//特殊考虑p指向结尾
        {
            p->next=s;
            s->next=NULL;
        }
        else{
            s->next=p;
            q->next=s;
        }
    
    }
    //6.建立两个递增的有序单向链表，合并成一个递减(建立两个递增的有序单向链表，合并成一个递增,再就地逆置元素)
    LinkList inde(LinkList &L,LinkList &J)
    {
    
        LinkList Q;
        init(Q);
        LinkList pa,pb,pc;
        pa=(LinkList)malloc(sizeof(LNode));
        pb=(LinkList)malloc(sizeof(LNode));
        pc=(LinkList)malloc(sizeof(LNode));
        pa=L->next;
        pb=J->next;
        pc=Q;
        pc->next=NULL;
        while(pa&&pb)
        {
            if(pa->data<=pb->data)
            {
                pc->next=pa;
                pc=pa;
                pa=pa->next;
            }
            else {
                pc->next=pb;
                pc=pb;
                pb=pb->next;
            }
        }
        if(pa)
        {
            pc->next=pa;
        }
        else
        {
            pc->next=pb;
        }
        free(L);
        free(J);
    
        return Q;
    }
    //7.建立两个递减的有序单向链表，合并成一个递增(建立两个递减的有序单向链表，合并成一个递减,再就地逆置元素)
    LinkList dein(LinkList &L,LinkList &J)
    {
    
        LinkList Q;
        init(Q);
        LinkList pa,pb,pc;
        pa=(LinkList)malloc(sizeof(LNode));
        pb=(LinkList)malloc(sizeof(LNode));
        pc=(LinkList)malloc(sizeof(LNode));
        pa=L->next;
        pb=J->next;
        pc=Q;
        pc->next=NULL;
        while(pa&&pb)
        {
            if(pa->data>=pb->data)
            {
                pc->next=pa;
                pc=pa;
                pa=pa->next;
            }
            else {
                pc->next=pb;
                pc=pb;
                pb=pb->next;
            }
        }
        if(pa)
        {
            pc->next=pa;
        }
        else
        {
            pc->next=pb;
        }
        free(L);
        free(J);
    
        return Q;
    }
    
    
    
    
    int main()
    {
        LinkList S;
    int number,data;
        init(S);//创建带头节点的链表
        printf("创建带头节点的链表\n");
        printf("输入插入元素的个数\n");
        scanf("%d",&number);//输入插入元素的个数
        for(int i=0;i<number;i++)
        {
            printf("尾插法,依次输入元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(S,data);//1.头插法,输入元素
            insert2(S,data);//1.尾插法,输入元素
        }
        printf("\n显示带头节点的链表\n");
        print(S);// 2.显示单向链表
        printf("显示逆置的链表\n");
        contrary(S);//3.逆置元素（不申请新节点）
        print(S);// 2.显示单向链表
        printf("删除所有值为偶数的节点\n");
        delet(S); // 4.删除所有值为偶数的节点
        print(S);// 2.显示单向链表
    
        LinkList U;
        init(U);//创建带头节点的链表
        printf("输入插入元素的个数\n");
        scanf("%d",&number);//输入插入元素的个数
        for(int i=0;i<number;i++)
        {
            printf("尾插法,依次输入有序递增元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(U,data);//1.尾插法,输入元素
        }
        printf("输入要插入的元素\n");
        int k;
        scanf("%d",&k);//要插入递增数列的k
        insert3(U,k);//5.递增数列中插入元素仍有序
        print(U);// 2.显示单向链表
    
    
        LinkList V,W,Res;
        int m,n;
        init(V);//创建带头节点的链表
        init(W);//创建带头节点的链表
        printf("输入两个链表的元素个数分别为m,n\n");
        scanf("%d%d",&m,&n);//输入插入元素的个数
        printf("请输入第一个链表的元素\n");
        for(int i=0;i<m;i++)
        {
            printf("尾插法,依次输入有序递增元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(V,data);//1.尾插法,输入元素
        }
        printf("请输入第二个链表的元素\n");
        for(int i=0;i<n;i++)
        {
            printf("尾插法,依次输入有序递增元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(W,data);//1.尾插法,输入元素
        }
            Res=inde(V,W);//6.建立两个递增的有序单向链表，合并成一个递减
            contrary(Res);//3.逆置元素（不申请新节点）
            print(Res);// 2.显示单向链表
    
        LinkList E,F,Re;
        int a,b;
        init(E);//创建带头节点的链表
        init(F);//创建带头节点的链表
        printf("输入两个链表的元素个数分别为m,n\n");
        scanf("%d%d",&a,&b);//输入插入元素的个数
        printf("请输入第一个链表的元素\n");
        for(int i=0;i<a;i++)
        {
            printf("尾插法,依次输入有序递减元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(E,data);//1.尾插法,输入元素
        }
        printf("请输入第二个链表的元素\n");
        for(int i=0;i<b;i++)
        {
            printf("尾插法,依次输入有序递减元素,以回车分隔,输入元素第%d个\n",i+1);
            scanf("%d",&data);
            //insert1(U,data);//1.头插法,输入元素
            insert2(F,data);//1.尾插法,输入元素
        }
        Re=dein(E,F);//7.建立两个递减的有序单向链表，合并成一个递增
        contrary(Re);//3.逆置元素（不申请新节点）
        print(Re);// 2.显示单向链表
    
    
    
        return 0;
    }