数据结构实验3-带头结点的单链表

avatar 2016年12月05日12:02:27 1 7178 views
博主分享免费Java教学视频，B站账号：Java刘哥
 
  1. /*编写函数void delx(linklist head, datatype x)，删除带头结点单链表head中第一个值为x 的结点。
  2. 并构造测试用例进行测试。
  3. */
  4. /**********************************/
  5. /*文件名称：lab3_01.c                 */
  6. /**********************************/
  7. #include "slnklist.h"
  8. /*请将本函数补充完整，并进行测试*/
  9. linklist delx(linklist head,datatype x)
  10. {
  11.     linklist p,pre=head; //别忘了pre=head 
  12.     p = head->next;
  13.     while(p->info!=x)
  14.     {
  15.         pre = p;
  16.         p = p->next;
  17.     }
  18.     if(p)
  19.     {
  20.         pre->next = p->next;
  21.         free(p);
  22.     }
  23.     return head;
  24. }
  26. int main()
  27. {   datatype x;
  28.     linklist head;
  29.     head=creatbyqueue();        /*尾插入法建立带头结点的单链表*/
  30.     print(head);
  31.     printf("请输入要删除的值：");
  32.     scanf("%d",&x);
  33.     head=delx(head,x);            /*删除单链表的第一个值为x的结点*/
  34.     print(head);
  35.     delList(head);                /*释放单链表空间*/
  36.     return 0;
  37. }
 
  1. /**********************************/
  2. /*文件名称：lab3_02.c                 */
  3. /**********************************/
  4. /*
  5. 假设线性表（a1,a2,a3,…an）采用带头结点的单链表存储，请设计算法函数linklist reverse(linklist  head)，
  6. 将带头结点的单链表head就地倒置，使表变成（an,an-1,…a3.a2,a1）。并构造测试用例进行测试。
  7. */
  8. #include "slnklist.h"
  9. /*请将本函数补充完整，并进行测试*/
  10. linklist reverse(linklist head)
  11. {
  12.     //不带头节点是head，带头节点是head->next 
  13.     linklist p,q;
  14.     p = head->next;
  15.     head->next = NULL;
  16.     while(p)
  17.     {
  18.         q = p->next;
  19.         p->next = head->next;
  20.         head->next = p;
  21.         p = q;
  22.     }
  23.     return head;
  24. }
  25. int main()
  26. {   datatype x;
  27.     linklist head;
  28.     head=creatbystack();            /*头插入法建立带头结点的单链表*/
  29.     print(head);                    /*输出原链表*/
  30.     head= reverse(head);            /*倒置单链表*/
  31.     print(head);                    /*输出倒置后的链表*/
  32.     delList(head);
  33.     return 0;
  34. }
 
  1. /*
  2. 假设带头结点的单链表head是升序排列的，设计算法函数linklist insert(linklist head,datatype x)，
  3. 将值为x的结点插入到链表head中，并保持链表有序性。
  4. 分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。
  5. */
  6. /**********************************/
  7. /*文件名称：lab3_03.c                 */
  8. /**********************************/
  9. #include "slnklist.h"
  10. /*请将本函数补充完整，并进行测试*/
  11. linklist insert(linklist head ,datatype x)
  12. {
  13.     //要插入的数据s，位于pre和 p之间 
  14.     linklist pre,p,s;
  15.     s = (linklist)malloc(sizeof(node));
  16.     s->info = x;
  17.     p = head->next;
  18.     pre = head;
  19.     while(p&&p->info<x)
  20.     {
  21.         pre = p;
  22.         p = p->next;
  23.     }
  24.     pre->next = s;
  25.     s->next = p;
  26.     return head;
  27. }
  28. int main()
  29. {   datatype x;
  30.     linklist head;
  31.     printf("输入一组升序排列的整数：\n");
  32.     head=creatbyqueue();                /*尾插入法建立带头结点的单链表*/
  33.     print(head);
  34.     printf("请输入要插入的值：");
  35.     scanf("%d",&x);
  36.     head=insert(head,x);                /*将输入的值插入到带头结点的单链表适当位置*/
  37.     print(head);
  38.     delList(head);
  39.     return 0;
  40. }
 
  1. /*
  2. 编写算法函数linklist delallx(linklist head, int x)，删除带头结点单链表head中所有值为x的结点。
  3. */
  4. /**********************************/
  5. /*文件名称：lab3_04.c                 */
  6. /**********************************/
  7. #include "slnklist.h"
  8. /*请将本函数补充完整，并进行测试*/
  9. linklist delallx(linklist head,int x)
  10. {
  11.     //不带头节点是head，带头节点是head->next 
  12.     linklist p,t;
  13.     while(head->next)//如果要删除的是第一个 
  14.     {
  15.         if(head->next->info==x)//如果第一个数=x 
  16.         {
  17.             p=head->next;//删除操作 
  18.             head->next=head->next->next;
  19.             free(p);//回收p 
  20.         } else {
  21.             break;
  22.         }
  23.     }
  24.     if(head->next)//如果删除的不是第一个 
  25.     {
  26.         p=head->next;
  27.         while(p->next)
  28.         {
  29.             if(p->next->info==x)
  30.             {
  31.                 t=p->next;
  32.                 p->next=p->next->next;
  33.                 free(t);
  34.             } else {
  35.                 p=p->next;
  36.             }
  37.         }
  38.     }
  39.     return head;
  40. }
  41. int main()
  42. {   datatype x;
  43.     linklist head;
  44.     head=creatbyqueue();                /*尾插入法建立带头结点的单链表*/
  45.     print(head);
  46.     printf("请输入要删除的值：");
  47.     scanf("%d",&x);
  48.     head=delallx(head,x);
  49.     print(head);
  50.     delList(head);
  51.     return 0;
  52. }
 
  1. /*
  2. 已知线性表存储在带头结点的单链表head中，请设计算法函数void sort(linklist head)，将head中的结点按结点值升序排列。
  3. */
  4. /**********************************/
  5. /*文件名称：lab3_05.c                 */
  6. /**********************************/
  7. #include "slnklist.h"
  8. /*请将本函数补充完整，并进行测试*/
  9. void  sort(linklist head)
  10. {
  11.      int temp; //temp是int类型，notice 
  12.      linklist p,pre;
  13.      pre=p=head->next;
  14.      while(pre) //pre是前面那个数，p是后面那个数 
  15.      {
  16.          p=pre;//notice，p是从pre后面数里走 
  17.          while(p)
  18.          {
  20.              if(pre->info>p->info) //交换 
  21.              {
  22.                  temp=p->info;
  23.                  p->info=pre->info;
  24.                  pre->info=temp;
  25.              }
  26.              p=p->next;
  27.          }
  28.          pre=pre->next;
  29.      }
  30.      return head;
  31. }
  32. int main()
  33. {        linklist head;
  34.          head=creatbyqueue();           /*尾插法建立带头结点的单链表*/
  35.          print(head);                    /*输出单链表head*/
  36.          sort(head);                     /*排序*/
  37.          print(head);
  38.          delList(head);
  39.          return 0;
  40. }
 
  1. /*
  2. 已知两个带头结点的单链表L1和L2中的结点值均已按升序排序，设计算法函数
  3. linklist mergeAscend (linklist L1,linklist L2)将L1和L2合并成一个升序的
  4. 带头结单链表作为函数的返回结果；
  5. 设计算法函数linklist mergeDescend (linklist L1,linklist L2)
  6. 将L1和L2合并成一个降序的带头结单链表作为函数的返回结果；
  7. 并设计main()函数进行测试。
  8. */
  9. /**********************************/
  10. /*文件名称：lab3_06.c                 */
  11. /**********************************/
  12. #include "slnklist.h"
  13. /*请将本函数补充完整，并进行测试*/
  14. linklist mergeAscend(linklist L1,linklist L2)//升序 
  15. {
  16.     linklist head,x,y,p;
  17.     head=(linklist)malloc(sizeof(node));
  18.     head->next=NULL;
  19.     p=head;
  20.     x=L1->next;
  21.     y=L2->next;
  22.     while(x&&y)
  23.     {
  24.         //当比到最好一个元素的时候，会出现x->next=NULL或者是y->next=NULL
  25.         if(x->info<=y->info)//L1里的数<L2的数 
  26.         {
  27.             //这两句是尾插法的核心 
  28.             p->next=x; //把新元素插到当前元素后面去 
  29.             p=x;  //吧当前指针指向新元素 
  30.             x=x->next;
  31.         }
  32.         else
  33.         {
  34.             //这两句是尾插法的核心 
  35.             p->next=y; //把新元素插到当前元素后面去 
  36.             p=y;  //吧当前指针指向新元素 
  37.             y=y->next;
  38.         }
  39.     }
  40.     p->next=x?x:y; //把最后一个数加进去 
  41.     return head;
  42. }
  43. linklist mergeDescend(linklist L1,linklist L2)//降序 
  44. {
  45. }
  46. int main()
  47. {       linklist h1,h2,h3;
  48.          h1=creatbyqueue();     /*尾插法建立单链表,请输入升序序列*/
  49.          h2=creatbyqueue();
  50.          print(h1);
  51.          print(h2);
  52.          //升序合并请调用 
  53.          h3=mergeAscend(h1,h2);
  54.          //降序合并请调用
  55. //         h3=mergeDescend(h1,h2); 
  56.          print(h3);
  57.          delList(h3);
  58.          return 0;
  59. }
 
  1. /*
  2. /*
  3. 设计一个算法linklist interSection(linklist L1,linklist L2)，
  4. 求两个单链表表示的集合L1和L2的交集，并将结果用一个新的带头
  5. 结点的单链表保存并返回表头地址。
  6. */
  7. /**********************************/
  8. /*文件名称：lab3_07.c                 */
  9. /**********************************/
  10. #include "slnklist.h"
  11. /*请将本函数补充完整，并进行测试*/
  12. linklist   interSection(linklist L1, linklist L2)
  13. {
  14.     linklist head,p,s,x,y; //s是临时存储的结点 
  15.     head=(linklist)malloc(sizeof(node));
  16.     head->next=NULL;
  17.     p = head;
  18.     x = L1->next;
  19.     y = L2->next;
  20.     while(x)
  21.     {
  22.         while(y)
  23.         {
  24.             if(x->info==y->info)
  25.             {
  26.                 s = (linklist)malloc(sizeof(node));
  27.                 s->info = x->info;
  28.                 p->next = s;  //这两句不能互换，因为是添加数据 
  29.                 p = s;
  30.                 break; //notice，不可省略 ，跳出本层循环 ，不执行y=y->next 
  31.             }
  32.             y = y->next;
  33.         }
  34.         x = x->next;
  35.     }
  36.     p->next = NULL;
  37.     return head;
  38. }
  39. int main()
  40. {
  41.  linklist h1,h2,h3;
  42.  h1=creatbyqueue();           /*尾插法建立单链表,输入时请勿输入重复数据*/
  43.  h2=creatbyqueue();
  44.  print(h1);                   /*输出单链表h1*/
  45.  print(h2);
  46.  h3=interSection(h1,h2);      /* 求h1和h2的交集*/
  47.  print(h3);
  48.  delList(h1);
  49.  delList(h2);
  50.  delList(h3);
  51.  return 0;
  52. }
 
  1. /*
  2. 请编写一个算法函数void partion(linklist head)，
  3. 将带头结点的单链表head中的所有值为奇数的结点调整
  4. 到链表的前面，所有值为偶数的结点调整到链表的后面。
  5. */
  7. /**********************************/
  8. /*文件名称：lab3_08.c             */
  9. /**********************************/
  10. #include "slnklist.h"
  11. /*请将本函数补充完整，并进行测试*/
  12. void partion(linklist head)
  13. {
  14.     linklist p,s,pre;
  15.     pre=head;
  16.     p=head->next;
  17.     while(p)
  18.     {
  19.         if(p->info%2==0) //偶数 
  20.         {
  21.             pre=p;
  22.             p=p->next;
  23.         }
  24.         else
  25.         {
  26.             s=p;
  27.             pre->next=p->next;
  28.             p=pre->next;
  29.             s->next=NULL;
  30.             s->next=head->next;
  31.             head->next=s;
  32.         }
  33.     }
  35. }
  36. int main()
  37. {        linklist head;
  38.          head=creatbyqueue();           /*尾插法建立带头结点的单链表*/
  39.          print(head);                   /*输出单链表head*/
  40.          partion(head);
  41.          print(head);
  42.          delList(head);
  43.          return 0;
  44. }
 
  1. /*
  2. 编写一个程序，用尽可能快的方法返回带头结点单链表中倒数第k个结点的地址，如果不存在，则返回NULL。
  3. */
  4. /**********************************/
  5. /*文件名称：lab3_09.c             */
  6. /**********************************/
  7. #include "slnklist.h"
  8. /*请将本函数补充完整，并进行测试*/
  9. linklist   search(linklist head,int k)
  10. {
  11.     linklist p = head->next,x;
  12.     int count = 0,i;
  13.     x = p;
  14.     while(x) //求链表长度 
  15.     {
  16.         count++;
  17.         x=x->next;
  18.     }        //获得倒数第k的值 
  19.     for(i=0;i<count-k;i++)
  20.     {
  21.         p = p->next;
  22.     }
  23.     return p;
  24. }
  25. int main()
  26. {
  27.      int k;
  28.      linklist head,p;
  29.      head=creatbyqueue();        /*尾插法建立带头结点的单链表*/
  30.      print(head);                  /*输出单链表head*/
  31.      printf("k=");
  32.      scanf("%d",&k);
  33.      p=search(head,k);
  34.      if (p) printf("%d\n",p->info);
  35.      else
  36.          printf("Not Found!\n");
  37.      delList(head);
  38.      return 0;
  39. }
slnklist.h
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. /**************************************/
  4. /* 链表实现的头文件，文件名slnklist.h */
  5. /**************************************/
  6.  typedef int datatype;
  7.  typedef struct link_node{
  8.    datatype info;
  9.    struct link_node *next;
  10.  }node;
  11. typedef node *linklist;
  12. /******************************************/
  13. /*函数名称：creatbystack()                      */
  14. /*函数功能：头插法建立带头结点的单链表    */
  15. /******************************************/
  16. linklist creatbystack()
  17. {
  19.     linklist  head,s;
  20.     datatype x;
  21.     head=(linklist)malloc(sizeof(node));
  22.     head->next=NULL;
  24.     printf("请输入整数序列（空格分开，以0结束）:\n");
  25.     scanf("%d",&x);
  26.     while (x!=0)
  27.     {
  28.         s=(linklist)malloc(sizeof(node));
  29.         s->info=x;
  31.         s->next=head->next;
  32.         head->next=s;
  34.         scanf("%d",&x);
  35.     }
  36.     return head;
  37. }
  38. /***************************************/
  39. /*函数名称：creatbyqueue()                */
  40. /*函数功能：尾插法建立带头结点的单链表 */
  41. /***************************************/
  42. linklist creatbyqueue()
  43. {
  44.     linklist head,r,s;
  45.     datatype x;
  46.     head=r=(linklist)malloc(sizeof(node));
  47.     head->next=NULL;
  48.     printf("请输入整数序列（空格分开，以0结束）:\n");
  49.     scanf("%d",&x);
  50.     while (x!=0)
  51.     {
  52.          s=(linklist)malloc(sizeof(node));
  53.          s->info=x;
  54.          r->next=s; //把新元素放到当前元素后面 
  55.          r=s;    //把当前指针指向新元素 
  56.          scanf("%d",&x);
  57.    }
  58.     r->next=NULL;
  59.     return head;
  60. }
  61. /**********************************/
  62. /*函数名称：print()                      */
  63. /*函数功能：输出带头结点的单链表      */
  64. /**********************************/
  65. void print(linklist head)
  66. {
  67.     linklist p;
  68.     int i=0;
  69.     p=head->next;
  70.     printf("List is:\n");
  71.     while(p)
  72.     {
  73.         printf("%7d",p->info);
  74.         i++;
  75.         if (i%10==0)    printf("\n");
  76.         p=p->next;
  77.     }
  78.     printf("\n");
  80. }
  82. /******************************************/
  83. /*函数名称：creatLink()                   */
  84. /*函数功能：从文件中读入n个数据构成单链表 */
  85. /******************************************/
  86. linklist creatLink(char *f, int n)
  87. {
  88.     FILE *fp;
  89.     int i;
  90.     linklist s,head,r;
  91.     head=r=(linklist)malloc(sizeof(node));
  92.     head->next=NULL;
  93.     fp=fopen(f,"r");
  94.     if (fp==NULL)
  95.         return head;
  96.     else
  97.     {
  98.          for (i=0;i<n;i++)
  99.             {
  100.                 s=(linklist)malloc(sizeof(node));
  101.                 fscanf(fp,"%d",&(s->info));
  102.                 r->next=s;
  103.                 r=s;
  104.             }
  105.         r->next=NULL;
  106.         fclose(fp);
  107.         return head;
  108.     }
  109. }
  111. /*
  112.     函数名称：writetofile
  113.     函数功能：将链表内容存入文件f
  114. */
  115. void writetofile(linklist head, char *f)
  116. {
  117.     FILE *fp;
  118.     linklist p;
  119.     int i=0;
  120.     fp=fopen(f,"w");
  121.     if (fp!=NULL)
  122.     {
  123.         p=head->next;
  124.         fprintf(fp,"%s","List is:\n");
  125.         while(p)
  126.         {
  127.             fprintf(fp,"%7d",p->info);
  128.             i++;
  129.             if (i%10==0)    fprintf(fp,"%c",'\n');
  130.             p=p->next;
  131.         }
  132.         fprintf(fp,"%c",'\n');
  133.         fclose(fp);
  134.     }
  135.     else    printf("创建文件失败!");
  137. }
  140. /**********************************/
  141. /*函数名称：delList()                  */
  142. /*函数功能：释放带头结点的单链表      */
  143. /**********************************/
  144. void delList(linklist head)
  145. { linklist p=head;
  146.   while (p)
  147.   { head=p->next;
  148.     free(p);
  149.     p=head;
  150.   }
  151. }
本文地址：http://liuyanzhao.com/3596.html 转载请注明  
历史上的今天
十二月
05日
  • 微信
  • 交流学习，有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享，问题解决，技术交流。群号：590480292
  • weinxin
avatar

发表评论

avatar 登录者：匿名
匿名评论，评论回复后会有邮件通知

  

已通过评论：0   待审核评论数：0