数据结构：用C语言实现非递减有序表的合并

忘是亡心i 2022-12-13 12:57 118阅读 0赞

## 实验要求 ##

（1）实验目的

通过该实验，深入理解顺序表的逻辑结构、物理结构等概念，掌握顺序表基本操作的编程实现，注意顺序表插入、删除等操作过程中数据元素的移动现象，培养学生编写程序时，要考虑程序的健壮性，全面考虑问题，熟练掌握通过函数参数返回函数结果的办法。

（2）实验内容

编程实现顺序表下教材第二章定义的线性表的基本操作，并根据已经实现的基本操作，实现两个非递减有序的线性表的合并，注意，合并时，如果有重复的元素，请保留一个。

（3）实验要求

（a）求前驱是指，输入一个元素值（而不是位置），求该元素在顺序表中的直接前驱元素值。求后继是指：输入一个元素值（而不是位置），求该元素在顺序表中的直接后继元素值；（b）为了方便修改数据元素的类型，请使用类型重定义，可以方便修改线性表中的数据元素的类型；（c）大部分函数的返回结果应是函数执行是否成功的一种状态，执行成功了，才返回具体的结果值；（d）对每个功能进行测试时，要求把不合法的情况也测试一下。具体见下面的测试用例；（e）采用菜单形式对应各个操作，使其编成一个完整的小软件，参考界面如下。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70_pic_center]

注：销毁是指free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; return TRUE。清空是指：L.length=0 ;return TRUE。

（3）验收/测试用例

通过菜单调用各个操作，测试点：

l 没有初始化前进行其他操作，程序是否能控制住；即，如果没有初始化线性表，其他的功能是无法正常进行的，如果选择进行其他操作，要提示先进行初始化；

l 初始化一个顺序表（初始化顺序表，是指初始化一个空的线性表，里面的元素个数是0）；

l 插入数据(位置， 数据)，要测插入位置不合法的情况（0,1）、（2,1），正确插入3个数据（1，20）、（1，10）、（3,30）；

l 显示顺序表中的数据，屏幕输出10， 20， 30；

l 判空，屏幕输出顺序表非空；

l 输出顺序表长度，屏幕输出3；

l 获取指定位置元素，要测指定位置在【1，3】范围之外的情况和之内的情况；

l 定位，输入：40， 输出：不存在，输入20，输出位置为2；

l 求直接前驱，要测求第一个元素的前驱、不存在顺序表中的元素的直接前驱，其他元素的直接前驱；输入10，输出：第一个元素没有前驱，输入20，输出前驱是10，输入40，输出该元素不存在；

l 求直接后继，要测最后一个元素的后继、不存在顺序表中的元素的直接后继，其他元素的直接后继；同上求前驱；

l 删除，要测位置在【1，3】范围之外的情况和之内的情况；

l 清空操作后再测长度，判断是否为空；

l 销毁顺序表，销毁线性表之后还能不能做插入，删除等操作，如果选其他操作，就要提示线性表已经销毁不存在；

l 测试合并操作，第一个线性表中的元素是（2,3,4，5），第二个线性表中的内容是（1,4,5，6,7），合并后的结果，请输出。

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node{ 
     int data;
     struct Node *next;
    }Node,*Link; 
    
    void show(){ 
     printf("\t\t\t 1---初始化一个线性表\n");
     printf("\t\t\t 2---销毁线性表\n");
     printf("\t\t\t 3---清空线性表\n");
     printf("\t\t\t 4---判断线性表是否为空\n");
     printf("\t\t\t 5---求线性表长度\n");
     printf("\t\t\t 6---获取线性表中指定位置的元素\n");
     printf("\t\t\t 7---获取线性表元素的位置\n");
     printf("\t\t\t 8---求前驱\n");
     printf("\t\t\t 9---求后继\n");
     printf("\t\t\t 10--在线性表指定位置插入元素\n");
     printf("\t\t\t 11--删除线性表指定位置的元素\n");
     printf("\t\t\t 12--显示线性表\n");
     printf("\t\t\t 13--合并两个非递减有序的线性表\n"); 
     printf("\t\t\t 退出，输入一个负数！");
     printf("\n");
     printf("\t\t----------------------------------------------\n");
     printf("\n");
    }
    
    //初始化线性表
    Link list(Link head){ 
     head = (Link)malloc(sizeof(Node));
     if(head == NULL){ 
      return 0;
     }
     head->next=NULL; 
     Link p,r,s,t;
     int i,sum,num;
     r = head;
     printf("请输入元素总个数：\n");
     scanf("%d",&sum); 
     printf("请输入元素：\n");
     for(i=0;i<sum;i++){ 
      p=(Link)malloc(sizeof(Node));
      if(p){ 
       scanf("%d",&p->data);
       r->next=p;
       r=p;
      }
     }
     /* 这个地方出过错，以为下面排序是基于s！=NULL和 t！=NULL为循环条件的，所以这个把尾节点置空必不可少。 */
     r->next=NULL;
     //把乱的链表排序，类似冒泡排序。 
     s=head->next;
     while(s){ 
      num=s->data; 
      t=s->next;
      while(t){ 
       if(num > t->data){ 
        int tamp=t->data;
        t->data=num;
        num=tamp;
       }
       t=t->next;
      }
      s->data=num;
      s=s->next;
     }
     printf("集合输入完成\n");
     return head;
    }
    
    /* //为线性表赋值 void a(Link head){ Link p,r; int i; r=head; for (i=1;i<=14;i+=2){ p=(Link)malloc(sizeof(Node)); p->data=i; r->next=p; r=p; } r->next=NULL; printf("集合输入完成\n"); } */
    
    /* 个人总结，销毁链表与清空链表的区别在与对头指针的处理。 销毁链表是指将链表全部释放（free ）掉，连同头指针一起释放，故 销毁后链表不再存在，也无法进行任何操作。 清空链表则是将链表除了头节点以外的节点释放掉，因为头节点被保留 所以该链表还存在，可以进行其他操作。 */
    
    //销毁线性表 
    void destroy(Link head){ 
     Link p,q;
     //p=head->next;
     p=head;
     if(!p->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return;
     }
     while(p){ 
      q=p;
      p=p->next;
      free(q);
     }
     head->next=NULL;
    // printf("This part is over\n");
    }
    
    //清空线性表
    void clean(Link head){ 
     Link p,q;
     p=head->next;
     //p=head;
     if(!p){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return;
     }
     while(p){ 
      q=p;
      p=p->next;
      free(q);
     }
     head->next=NULL;
    // printf("clean is over\n");
    } 
    
    //判断线性表是否为空
    void judge(Link head){ 
     if(head->next==NULL){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
     }else{ 
      printf("该链表不是空链表\n"); 
     }
    }
    
    //求线性表的长度
    void length(Link head){ 
     Link p;
     int i=0;
     p=head->next;
     if(!p){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     while(p){ 
      i++;
      p=p->next;
     }
     printf("该线性表长度为：%d\n",i);
    }
    
    //获取线性表指定位置的元素
    void gainElement(Link head){ 
     Link p;
     if(!head->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     p=head->next;
     int location,i;
     printf("请输入所指定元素的位置：\n");
     scanf("%d",&location);
     for(i=1;i<location;i++){ 
      p=p->next;
     }
     printf("该位置的元素是：%d\n",p->data);
    } 
    
    //获取线性表元素的位置
    void gainLocation(Link head){ 
     Link p;
     int element,location=0;
     if(!head->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     p=head->next;
     printf("请输入所指定位置的元素：\n");
     scanf("%d",&element);
     while(p){ 
      location++;
      if(p->data == element){ 
       break;
      }
      p=p->next;
     }
     printf("该元素的位置是：%d\n",location);
    }
    
    //求前驱
    void before(Link head){ 
     Link p,q;
     int element;
     if(!head->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     p=head;
     printf("请输入所指定的元素：\n");
     scanf("%d",&element); 
     while(p){ 
      p=p->next;   
      if(p->data==element){     //第一轮循环时，p->data为第一个元素，则此时无前驱 
       printf("该元素为第一个元素，无直接前驱。\n");
       return ;
      }  
      q=p->next;   
      if(q->data == element){   //判断p下一个元素是否是该元素，若是这输出p->data 
       printf("该元素的直接前驱是%d\n",p->data);
       break;
      }
     } 
    } 
    
    //求后继
     void after(Link head) { 
        Link p;
        int element;
        if(!head->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
        p=head->next;
        printf("请输入所指定的元素：\n");
        scanf("%d",&element);
        while(p){ 
         if(p->next==NULL){ 
          printf("该元素为最后一个元素，无直接后继。\n");
          return ; 
      }
      if(p->data==element){ 
       p=p->next;
       printf("该元素的直接后继是%d\n",p->data);
       break;
      }
      p=p->next;
     }
    }
    
    //在线性表指定位置插入元素
    void insert(Link head){ 
     Link p,q,r;
     int element,location,i;
     if(!head->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     while(1){ 
      p=head->next;
      printf("请输入要插入的位置：\n");
      scanf("%d",&location);
      if(location<0){ 
       printf("输入位置错误，请重新输入\n");
       continue;
      }
      printf("请输入要插入的元素：\n");
      scanf("%d",&element);
      for(i=0;i<location-1;i++){ 
       p=p->next;
       if(!p && i<location-2)   //判断所插入位置是否超出长度，则插入不合理 
        break;
      } 
      if(!p && i<location-2){    
       printf("输入位置错误，请重新输入\n");
       continue;
      }
      q=p->next;
      if(element<=q->data && element>=p->data){ 
       r=(Link)malloc(sizeof(Node));
       r->data=element;
       r->next=p->next;
       p->next=r;
       printf("插入成功\n");
       break;
      }else{ 
       printf("插入位置不合法，请重新输入：\n");
      }
     }
    } 
    
    //删除线性表指定位置的元素
    void reLocation(Link head){ 
     Link p,q;
     int location,i;
     if(!head->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     while(1){ 
      p=head->next;
      printf("请输入要删除的位置：\n");
      scanf("%d",&location);
      if(location<0){ 
       printf("输入位置错误，请重新输入\n");
       continue;
      }
      for(i=0;i<location-2;i++){ 
       if(p){ 
        p=p->next;
       }else{ 
        printf("输入位置错误，请重新输入\n");
        break;
       }
      }
      if(!p) continue;
      i++; 
      q=p->next;
      if(!q) continue ;
      if(p){ 
       p->next=q->next;
       free(q);
       break;
      }
      
     } 
    }
    
    //显示线性表 
    void output(Link head){ 
     Link p;
     if(!head->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     printf("结果为：\n");
     for(p=head->next;p;p=p->next){ 
      printf("%d\t",p->data);
     }
    // printf("All of the element is out\n");
    }
    
    //合并两个非递减有序的线性表
    void merge(Link head,Link second){ 
     Link p,q,r,s;
     int element,i;
     if(!head->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     if(!second->next){ 
      printf("该链表是空链表，请先对链表进行初始化！\n");
      return ;
     }
     q=head->next;
     while(q){ 
      p=second->next;
      while(p){      //遍历head链表，查重 
       if(p->data==q->data){ 
        break;
       }
       p=p->next;
      }
      if(p->data==q->data){    //如果有，跳过 
          q=q->next;
       continue;
      }
      p=head->next;
         
         if(p->data>=q->data){   // 如果该元素比head链表里每一个元素都小 
          r=(Link)malloc(sizeof(Node));
          r->data=q->data;
          r->next=p;
          second->next=r;
          q=q->next;
          continue;
         }
      while(s){  
          s=p->next;
       if(s->data>=q->data){ 
        r=(Link)malloc(sizeof(Node));
        r->data=q->data;
        r->next=s;
        p->next=r;
        break;
       }
       p=p->next;
      }
      q=q->next;  
     }
    } 
    
    int main(){ 
     int choice;
     Link head;
     Link second;
     show(); 
     //菜单 
     while(1){ 
      printf("请输出要选择的功能：\n");
      scanf("%d",&choice);
      if(choice<0){ 
       if(head->next!=NULL){ 
        printf("链表未销毁，请先销毁链表，释放空间后再退出\n");
        continue;
       }
       printf("已退出\n");
       return 0;
      }
      switch(choice){ 
       case 1:
        head=list(head);
        break;
       case 2:
        destroy(head);
        break;
       case 3:
        clean(head);
        break;
       case 4:
        judge(head);
        break;
       case 5:
        length(head);
        break;
       case 6:
        gainElement(head);
        break;
       case 7:
        gainLocation(head);
        break;
       case 8:
        before(head);
        break;
       case 9:
        after(head);
        break;
       case 10:
        insert(head);
        break;
       case 11:
        reLocation(head);
        break;
       case 12:
        output(head);
        break;
       case 13:
        second=list(second);
        merge(head,second);
        output(second);
        break;
       default:
        printf("输入有误！\n");
        printf("请按回车继续！\n");
        break;
      }
     }
     return 0;
    }

代码已完，其中部分注释是写代码时测试用的。  
欢迎大佬前来纠错！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0a59fcd1a24d4380814a01b1c1285b8a.png