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

avatar 2016年12月5日12:02:27 评论 1,057 views

 

  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. }
  25. int main()
  26. {   datatype x;
  27.     linklist head;
  28.     head=creatbyqueue();        /*尾插入法建立带头结点的单链表*/
  29.     print(head);
  30.     printf("请输入要删除的值:");
  31.     scanf("%d",&x);
  32.     head=delx(head,x);            /*删除单链表的第一个值为x的结点*/
  33.     print(head);
  34.     delList(head);                /*释放单链表空间*/
  35.     return 0;
  36. }

 

  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.          {
  19.              if(pre->info>p->info) //交换 
  20.              {
  21.                  temp=p->info;
  22.                  p->info=pre->info;
  23.                  pre->info=temp;
  24.              }
  25.              p=p->next;
  26.          }
  27.          pre=pre->next;
  28.      }
  29.      return head;
  30. }
  31. int main()
  32. {        linklist head;
  33.          head=creatbyqueue();           /*尾插法建立带头结点的单链表*/
  34.          print(head);                    /*输出单链表head*/
  35.          sort(head);                     /*排序*/
  36.          print(head);
  37.          delList(head);
  38.          return 0;
  39. }

 

  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. */
  6. /**********************************/
  7. /*文件名称:lab3_08.c             */
  8. /**********************************/
  9. #include "slnklist.h"
  10. /*请将本函数补充完整,并进行测试*/
  11. void partion(linklist head)
  12. {
  13.     linklist p,s,pre;
  14.     pre=head;
  15.     p=head->next;
  16.     while(p)
  17.     {
  18.         if(p->info%2==0//偶数 
  19.         {
  20.             pre=p;
  21.             p=p->next;
  22.         }
  23.         else
  24.         {
  25.             s=p;
  26.             pre->next=p->next;
  27.             p=pre->next;
  28.             s->next=NULL;
  29.             s->next=head->next;
  30.             head->next=s;
  31.         }
  32.     }
  33. }
  34. int main()
  35. {        linklist head;
  36.          head=creatbyqueue();           /*尾插法建立带头结点的单链表*/
  37.          print(head);                   /*输出单链表head*/
  38.          partion(head);
  39.          print(head);
  40.          delList(head);
  41.          return 0;
  42. }

 

  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. {
  18.     linklist  head,s;
  19.     datatype x;
  20.     head=(linklist)malloc(sizeof(node));
  21.     head->next=NULL;
  22.     printf("请输入整数序列(空格分开,以0结束):\n");
  23.     scanf("%d",&x);
  24.     while (x!=0)
  25.     {
  26.         s=(linklist)malloc(sizeof(node));
  27.         s->info=x;
  28.         s->next=head->next;
  29.         head->next=s;
  30.         scanf("%d",&x);
  31.     }
  32.     return head;
  33. }
  34. /***************************************/
  35. /*函数名称:creatbyqueue()                */
  36. /*函数功能:尾插法建立带头结点的单链表 */
  37. /***************************************/
  38. linklist creatbyqueue()
  39. {
  40.     linklist head,r,s;
  41.     datatype x;
  42.     head=r=(linklist)malloc(sizeof(node));
  43.     head->next=NULL;
  44.     printf("请输入整数序列(空格分开,以0结束):\n");
  45.     scanf("%d",&x);
  46.     while (x!=0)
  47.     {
  48.          s=(linklist)malloc(sizeof(node));
  49.          s->info=x;
  50.          r->next=s; //把新元素放到当前元素后面 
  51.          r=s;    //把当前指针指向新元素 
  52.          scanf("%d",&x);
  53.    }
  54.     r->next=NULL;
  55.     return head;
  56. }
  57. /**********************************/
  58. /*函数名称:print()                      */
  59. /*函数功能:输出带头结点的单链表      */
  60. /**********************************/
  61. void print(linklist head)
  62. {
  63.     linklist p;
  64.     int i=0;
  65.     p=head->next;
  66.     printf("List is:\n");
  67.     while(p)
  68.     {
  69.         printf("%7d",p->info);
  70.         i++;
  71.         if (i%10==0)    printf("\n");
  72.         p=p->next;
  73.     }
  74.     printf("\n");
  75. }
  76. /******************************************/
  77. /*函数名称:creatLink()                   */
  78. /*函数功能:从文件中读入n个数据构成单链表 */
  79. /******************************************/
  80. linklist creatLink(char *f, int n)
  81. {
  82.     FILE *fp;
  83.     int i;
  84.     linklist s,head,r;
  85.     head=r=(linklist)malloc(sizeof(node));
  86.     head->next=NULL;
  87.     fp=fopen(f,"r");
  88.     if (fp==NULL)
  89.         return head;
  90.     else
  91.     {
  92.          for (i=0;i<n;i++)
  93.             {
  94.                 s=(linklist)malloc(sizeof(node));
  95.                 fscanf(fp,"%d",&(s->info));
  96.                 r->next=s;
  97.                 r=s;
  98.             }
  99.         r->next=NULL;
  100.         fclose(fp);
  101.         return head;
  102.     }
  103. }
  104. /*
  105.     函数名称:writetofile
  106.     函数功能:将链表内容存入文件f
  107. */
  108. void writetofile(linklist head, char *f)
  109. {
  110.     FILE *fp;
  111.     linklist p;
  112.     int i=0;
  113.     fp=fopen(f,"w");
  114.     if (fp!=NULL)
  115.     {
  116.         p=head->next;
  117.         fprintf(fp,"%s","List is:\n");
  118.         while(p)
  119.         {
  120.             fprintf(fp,"%7d",p->info);
  121.             i++;
  122.             if (i%10==0)    fprintf(fp,"%c",'\n');
  123.             p=p->next;
  124.         }
  125.         fprintf(fp,"%c",'\n');
  126.         fclose(fp);
  127.     }
  128.     else    printf("创建文件失败!");
  129. }
  130. /**********************************/
  131. /*函数名称:delList()                  */
  132. /*函数功能:释放带头结点的单链表      */
  133. /**********************************/
  134. void delList(linklist head)
  135. { linklist p=head;
  136.   while (p)
  137.   { head=p->next;
  138.     free(p);
  139.     p=head;
  140.   }
  141. }

本文地址:http://liuyanzhao.com/3596.html

转载请注明

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: