链表的插入和删除

叁歲伎倆 2022-07-14 04:12 175阅读 0赞

【实验内容】：

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

【实验源码】：

#include<stdio.h>
    
    #include<stdlib.h>
    
    //定义链表的一个节点数据类型
    
    typedef struct node{
    
    int data;
    
    struct node *next;
    
    }*LinerList;
    
    
    
    //冒泡排序链表
    
    void SortChain(LinerList head,int n)
    
    {      int i,j,temp;
    
    LinerList p1,p2;
    
    for(p1=head,i=0;i<n-1;i++,p1=p1->next)
    
    for(p2=p1->next,j=0;j<n-i-1;j++,p2=p2->next)
    
    if(p1->data>p2->data)
    
    {
    
    temp=p2->data;
    
    p2->data=p1->data;
    
    p1->data=temp;
    
    }
    
    }
    
    //构造递增链表
    
    void CreateLinerList(LinerList *head,int n)
    
    {
    
    int data;
    
        LinerList p,tail;//tail为指向链尾的指针
    
    printf("请输入链表对应的数据元素:\n");
    
    scanf("%d",&data);
    
    //建立链表的第一个节点
    
        p=(LinerList)malloc(sizeof(struct node));
    
    p->data=data;
    
    p->next=*head;
    
        *head=p;
    
    tail=p;//使链尾指针指向新建的结点
    
    //建立其余节点
    
    while(n>1)
    
    {
    
         scanf("%d",&data);
    
         p=(LinerList)malloc(sizeof(struct node));
    
    p->data=data;
    
    p->next=NULL;
    
    tail->next=p;
    
    tail=p;
    
    n--;//每建立一个节点，个数减1
    
    }
    
    }
    
    //显示所创建的链表，遍历链表
    
    void ShowLinerList(LinerList p)
    
    {
    
    while(p!=NULL)
    
    {
    
    printf("%-6d",p->data);
    
    p=p->next;
    
    }
    
    printf("\n");
    
    }
    
    //合并相关链表
    
    
    
    void Combine(LinerList *ha,LinerList hb)
    
    {
    
    LinerList current,last,other;
    
    //变量申明，current指向当前结点，last指向当前结点的前一节点
    
    //other用来保存hb中待插入的值
    
    while(hb!=NULL)
    
    {
    
    //建立新的结点
    
    other=(LinerList)malloc(sizeof(struct node));
    
    other->data=hb->data;
    
    //需寻找插入点
    
    current=*ha;//指向ha的头结点
    
    while(other->data > current->data && current->next!=NULL)
    
    {
    
    //确定插入的位置
    
    last=current;
    
    current=current->next;
    
    }
    
       if(other->data <= current->data)
    
    if(current==*ha&&(other->data != current->data))//在第一个结点之前插入
    
    {
    
    other->next=*ha;
    
    *ha=other;
    
    hb=hb->next;
    
    }
    
    else
    
    if(other->data == current->data)
    
    {
    
    hb=hb->next;//归并中两元素相同，则hb元素不归并到ha中
    
    }
    
    else{
    
    //在ha的中间插入
    
    other->next=current;
    
    last->next=other;
    
    hb=hb->next;
    
    }
    
    else{
    
    //在ha的末尾插入，此时只需把当前剩下未并入的hb元素头结点连入ha即可
    
    other=hb;
    
    current->next=other;
    
    return;//此种情况直接结束函数调用
    
    }
    
    }
    
    }
    
    
    
    //主函数，测试程序
    
    void main()
    
    {
    
    //创建两个链表
    
    LinerList ha=NULL,hb=NULL;
    
    int Na,Nb;
    
    printf("请输入ha的数据个数Na:\n");
    
    scanf("%d",&Na);
    
    //创建链表ha
    
        CreateLinerList(&ha,Na);
    
    //ha排序
    
    SortChain(ha,Na);
    
    
    
    printf("请输入hb的数据个数Nb:\n");
    
    scanf("%d",&Nb);
    
    //创建链表hb
    
        CreateLinerList(&hb,Nb);
    
    //hb递增排序
    
    SortChain(hb,Nb);
    
    
    
        //显示创建的链表
    
    printf("创建的链表ha为:");
    
    ShowLinerList(ha);
    
    printf("创建的链表hb为:");
    
    ShowLinerList(hb);
    
    
    
    //合并两个链表并且显示合并后的结果
    
    printf("\n");
    
    printf("*---------------------------------------------*\n");
    
    Combine(&ha,hb);
    
        printf("合并后的链表ha为:");
    
    ShowLinerList(ha);
    
    printf("合并后的链表hb为:");
    
    ShowLinerList(hb);
    
    }