实验1 链表的插入和删除

偏执的太偏执、 2022-06-05 09:43 113阅读 0赞

【实验内容】

设有两个无头结点的单链表，分别为ha，hb，其链中有数据域data，链域next，两链表的数据都按递增序存放。现要求将hb表归到ha表中，且归并后ha仍按递增排序，归并中ha表中已有的数据若与hb相同，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。

【实验目的】

1、 了解单链表、循环链表和双链表的基本知识；

2、 掌握算法思想和数据结构的描述；

3、 掌握链表的插入、删除的相关语句及基本方法。

【实验步骤与要求】

1、 实验前的准备

（1） 了解C语言的基本概念；

（2） 了解C语言的基本段落。

2、 上机操作

（1） 了解链表的基本知识；

（2） 掌握算法思想和数据结构的描述；

（3） 掌握链表的插入、删除的相关语句及基本方法。

代码：

#include<stdio.h>
    #include<stdlib.h>//malloc函数要用的库
    /*
    这题的要求是要生成两个链，输入的数据无序但是输出的时候要有序，所以在插入节点的时候就类似于选择排序的写法，
    在合适的位置插入就好了。由于要求是无头结点的写法，之前有头结点的做法是生成一个空的节点，然后就可以直接在
    该节点的next指针处插入节点就好，无头结点的做法就相当于抓取第一个节点作为头结点，接下来就和有头结点的做法
    一样在尾部插入数据就好了，至于在寻找插入位置是为什么要特判第一个，因为链表是(当前节点的->next)->v小于待
    插入节点的v的时候往该节点的next插入，也就是从第二个的v值开始判断的，所以要特判一下第一个，如果小于第一个
    就特殊处理一波
    */
    typedef struct node
    {
        int v;//数据域
        struct node* next;//指针域
    }list;
    list* build(int v)//特殊处理头结点
    {
        list*head=malloc(sizeof(list));
        head->next=NULL;
        head->v=v;
        return head;
    }
    list* insert(list* head,int v)//有序插入
    {
        if(head->v>=v)//特殊处理头结点
        {
            list* t=malloc(sizeof(list));
            t->next=head;
            t->v=v;
            return t;
        }
        list* t=head;
        while(t->next&&(t->next)->v<v)//找到当前节点下一个节点的数据正好大于待插入节点的值的位置
        {
            t=t->next;
        }
        list* aft=malloc(sizeof(list));//生成节点
        aft->next=t->next;
        aft->v=v;
        t->next=aft;//断开一个小口子将结点插入
        return head;
    }
    void bianli(list* head)//遍历链表
    {
        list*t=head;
        while(t)
        {
            printf("%d ",t->v);
            t=t->next;
        }
        printf("\n");
    }
    list* merge(list* heada,list* headb)//有序合并链表并去重
    {
        list *head,*t,*ta=heada,*tb=headb;
        if(ta->v<=tb->v)//特殊处理第一个节点
        {
            head=ta;
            head->next=NULL;
            ta=ta->next;
        }
        else
        {
            head=malloc(sizeof(list));
            head->v=tb->v;
            head->next=NULL;
            tb=tb->next;
        }
        t=head;
        while(ta&&tb)//当链表都还有剩余
        {
            while(ta&&ta->v==t->v)//处理旧的a表与新的a表数据重复，跳到下一个
            {
                ta=ta->next;
            }
            if(ta==NULL)//如果到了a表表尾退出
                break;
            while(tb&&tb->v==t->v)
            {
                tb=tb->next;
            }
            if(tb==NULL)//同理
                break;
            if(ta->v<tb->v)//值不重复，当a链的值较小的时候，将该节点加入a链
            {
                t->next=ta;
                t=ta;
                ta=ta->next;
                t->next=NULL;
            }
            else//因为b链不能破坏，所以就新生成一个节点复制下b链节点的信息并加入a链
            {
                list* temp=malloc(sizeof(list));
                temp->v=tb->v;
                temp->next=NULL;
                t->next=temp;
                t=t->next;
                tb=tb->next;
            }
        }
        while(ta)//如果上面退出循环是因为b链到了尾部，而a链没有，直接连接剩下的a链
        {
            while(ta&&ta->v==t->v)//同样去重
            {
                ta=ta->next;
            }
            if(ta==NULL)
                break;
            t->next=ta;
            ta=ta->next;
            t=t->next;
            t->next=NULL;
        }
        while(tb)//和上文同理，上面循环退出原因是a链到了尾部，处理剩下的b链
        {
             while(tb&&tb->v==t->v)
            {
                tb=tb->next;
            }
            if(tb==NULL)
                break;
            list* temp=malloc(sizeof(list));//和上面相同复制节点信息加入
            temp->v=tb->v;
            temp->next=NULL;
            t->next=temp;
            t=t->next;
            tb=tb->next;
        }
        return head;//返回头结点位置
    }
    int main()
    {
        int i,j,n,m;
        printf("input the size of a list:");//输入a链大小
        scanf("%d",&n);
        printf("input the a list:\n");
        list* head_a;
        int v;
        for(i=0;i<n;i++)
        {
            scanf("%d",&v);
            if(i==0)//如果是第一个就将该值作为头结点生成一个链表
                head_a=build(v);
            else
                head_a=insert(head_a,v);//否则就插入该节点
        }
        printf("the a list is:");
        bianli(head_a);//遍历a链
        list* head_b;
        printf("input the size of b list:");
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d",&v);
            if(i==0)
                head_b=build(v);
            else
                head_b=insert(head_b,v);
        }
        printf("the b list is:");
        bianli(head_b);
        printf("after merging the a list is:");
        head_a=merge(head_a,head_b);//更新a的头结点,因为合并后a链头结点地址可能改变
        bianli(head_a);
        return 0;
    }