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

avatar 2016年12月05日12:11:53 1 6655 views
博主分享免费Java教学视频,B站账号:Java刘哥
 
  1. /*编写函数slnklist delx(linklist head, datatype x),删除不带头结点单链表head中第一个值为x 的结点。
  2. 并构造测试用例进行测试。
  3. */
  4. /**********************************/
  5. /*文件名称:lab2_01.c             */
  6. /**********************************/
  7. #include "slnklist.h"
  8. /*请将本函数补充完整,并进行测试*/
  9. linklist delx(linklist head,datatype x)
  10. {
  11.     linklist p = head,pre=NULL;//一定要初始化pre=NULL 
  12.     while(p&&p->info!=x)
  13.     {
  14.         pre = p;
  15.         p = p->next;
  16.     }
  17.     if(p)
  18.     {
  19.         if(!pre)
  20.         {
  21.             head = head->next;
  22.         }
  23.         else
  24.         {
  25.             pre->next = p->next;
  26.             free(p);
  27.         }
  28.     }
  29.     return head;
  30. }
  31. int main()
  32. {   datatype x;
  33.     linklist head;
  34.     head=creatbyqueue();        /*尾插入法建立单链表*/
  35.     print(head);
  36.     printf("请输入要删除的值:");
  37.     scanf("%d",&x);
  38.     head=delx(head,x);            /*删除单链表的第一个值为x的结点*/
  39.     print(head);
  40.     delList(head);                /*释放单链表空间*/
  41.     return 0;
  42. }
 
  1. /**********************************/
  2. /*文件名称:lab2_02.c                 */
  3. /**********************************/
  4. /*
  5. 假设线性表(a1,a2,a3,…an)采用不带头结点的单链表存储,
  6. 请设计算法函数linklist reverse1(linklist  head)和
  7. void reverse2(linklist *head)将不带头结点的单链表head就地倒置,
  8. 使表变成(an,an-1,…a3.a2,a1)。并构造测试用例进行测试。
  9. */
  10. #include "slnklist.h"
  11. /*请将本函数补充完整,并进行测试*/
  12. linklist reverse1(linklist head)
  13. {
  14.     linklist p,q;
  15.     p=head;
  16.     head = NULL;
  17.     while(p)  //核心
  18.     {
  19.         q = p->next;
  20.         p->next = head;
  21.         head=p;
  22.         p=q;
  23.     }
  24.     return head;
  25. }
  26. void reverse2(linklist *head) //不返回值,那就从指针上下手 
  27. {
  28.     linklist p,q;
  29.     p=*head;
  30.     *head = NULL;
  31.     while(p)
  32.     {
  33.         q = p->next;
  34.         p->next = *head;
  35.         *head=p;
  36.         p=q;
  37.     }
  38. }
  39. int main()
  40. {   datatype x;
  41.     linklist head;
  42.     head=creatbystack();        /*头插入法建立单链表*/
  43.     print(head);                /*输出原链表*/
  44.     head= reverse1(head);        /*倒置单链表*/
  45.     print(head);                /*输出倒置后的链表*/
  46.     reverse2(&head);            /*倒置单链表*/
  47.     print(head);
  48.     delList(head);
  49.     return 0;
  50. }
 
  1. /*
  2. 假设不带头结点的单链表head是升序排列的,设计算法函数linklist insert(linklist head,datatype x),
  3. 将值为x的结点插入到链表head中,并保持链表有序性。
  4. 分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。
  5. */
  6. /**********************************/
  7. /*文件名称:lab2_03.c                 */
  8. /**********************************/
  9. #include "slnklist.h"
  10. /*请将本函数补充完整,并进行测试*/
  11. linklist insert(linklist head ,datatype x)
  12. {
  13.     linklist pre,p,s;
  14.     s = (linklist)malloc(sizeof(node));
  15.     s->info = x;
  16.     p = head;
  17.     pre=NULL;
  18.     while(p&&p->infonext;
  19.     }
  20.     if(!pre)  //插在表头 
  21.     {
  22.         s->next = head;
  23.         head = s;
  24.     }else{    //插在中间或者末尾 
  25.         pre->next = s;
  26.         s->next = p;
  27.     }
  28.     return head;
  29. }
  30. int main()
  31. {   datatype x;
  32.     linklist head;
  33.     printf("输入一组升序排列的整数:\n");
  34.     head=creatbyqueue();                /*尾插入法建立单链表*/
  35.     print(head);
  36.     printf("请输入要插入的值:");
  37.     scanf("%d",&x);
  38.     head=insert(head,x);                /*将输入的值插入到单链表适当位置*/
  39.     print(head);
  40.     delList(head);
  41.     return 0;
  42. }
 
  1. /*
  2. 编写算法函数linklist delallx(linklist head, int x),删除不带头结点单链表head中所有值为x的结点。
  3. */
  4. /**********************************/
  5. /*文件名称:lab2_04.c                 */
  6. /**********************************/
  7. #include "slnklist.h"
  8. /*请将本函数补充完整,并进行测试*/
  9. linklist delallx(linklist head,int x)
  10. {
  11.     linklist p,t;
  12.     while(head)//如果要删除的是第一个 
  13.     {
  14.         if(head->info==x)
  15.         {
  16.             p=head;
  17.             head=head->next;
  18.             free(p);//回收p 
  19.         } else {
  20.             break;
  21.         }
  22.     }
  23.     if(head)//如果删除的不是第一个 
  24.     {
  25.         p=head;
  26.         while(p->next)
  27.         {
  28.             if(p->next->info==x)
  29.             {
  30.                 t=p->next;
  31.                 p->next=p->next->next;
  32.                 free(t);
  33.             } else {
  34.                 p=p->next;
  35.             }
  36.         }
  37.     }
  38.     return head;
  39. }
  40. int main()
  41. {   datatype x;
  42.     linklist head;
  43.     head=creatbyqueue();                /*尾插入法建立单链表*/
  44.     print(head);
  45.     printf("请输入要删除的值:");
  46.     scanf("%d",&x);
  47.     head=delallx(head,x);
  48.     print(head);
  49.     delList(head);
  50.     return 0;
  51. }
  slnklist.h
  1. #include <stdio.h>
  2.  /**************************************/
  3. /* 链表实现的头文件,文件名slnklist.h */
  4. /**************************************/
  5.  typedef int datatype;
  6.  typedef struct link_node{
  7.    datatype info;
  8.    struct link_node *next;
  9.  }node;
  10. typedef node *linklist;
  11. /**********************************/
  12. /*函数名称:creatbystack()              */
  13. /*函数功能:头插法建立单链表            */
  14. /**********************************/
  15. linklist creatbystack()
  16. {  linklist  head,s;
  17.     datatype x;
  18.     head=NULL;
  19.     printf("请输入若干整数序列:\n");
  20.     scanf("%d",&x);
  21.     while (x!=0)        /*以0结束输入*/
  22.     {   s=(linklist)malloc(sizeof(node));  /*生成待插入结点*/
  23.         s->info=x;
  24.         s->next=head;            /*将新结点插入到链表最前面*/
  25.         head=s;
  26.         scanf("%d",&x);
  27.     }
  28.     return head;                /*返回建立的单链表*/
  29. }
  30. /**********************************/
  31. /*函数名称:creatbyqueue()              */
  32. /*函数功能:尾插法建立单链表            */
  33. /**********************************/
  34. linklist creatbyqueue()
  35. {
  36.     linklist head,r,s;
  37.     datatype x;
  38.     head=r=NULL;
  39.     printf("请输入若干整数序列:\n");
  40.     scanf("%d",&x);
  41.     while (x!=0/*以0结束输入*/
  42.     {    s=(linklist)malloc(sizeof(node));
  43.          s->info=x;
  44.          if (head==NULL)        /*将新结点插入到链表最后面*/
  45.             head=s;
  46.          else
  47.             r->next=s;
  48.         r=s;
  49.         scanf("%d",&x);
  50.    }
  51.     if (r)  r->next=NULL;
  52.     return head;                    /*返回建立的单链表*/
  53. }
  54. /**********************************/
  55. /*函数名称:print()                      */
  56. /*函数功能:输出不带头结点的单链表      */
  57. /**********************************/
  58. void print(linklist head)
  59. {   linklist p;
  60.     int i=0;
  61.     p=head;
  62.     printf("List is:\n");
  63.     while(p)
  64.     {
  65.         printf("%5d",p->info);
  66.         p=p->next;
  67.          i++;
  68.          if (i%10==0) printf("\n");
  69.     }
  70.     printf("\n");
  71. }
  72. /**********************************/
  73. /*函数名称:delList()                  */
  74. /*函数功能:释放不带头结点的单链表      */
  75. /**********************************/
  76. void delList(linklist head)
  77. { linklist p=head;
  78.   while (p)
  79.   { head=p->next;
  80.     free(p);
  81.     p=head;
  82.   }
  83. }
本文地址:http://liuyanzhao.com/3600.html 转载请注明  
  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
avatar

发表评论

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

  

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