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

avatar 2016年12月05日12:11:53 1 7384 views
博主分享免费Java教学视频，B站账号：Java刘哥 ，长期提供技术问题解决、项目定制：本站商品点此
 
  1. /*编写函数slnklist delx(linklist head, datatype x)，删除不带头结点单链表head中第一个值为x 的结点。
  2. 并构造测试用例进行测试。
  3. */
  4. /**********************************/
  5. /*文件名称：lab2_01.c             */
  6. /**********************************/
  8. #include "slnklist.h"
  9. /*请将本函数补充完整，并进行测试*/
  10. linklist delx(linklist head,datatype x)
  11. {
  12.     linklist p = head,pre=NULL;//一定要初始化pre=NULL 
  13.     while(p&&p->info!=x)
  14.     {
  15.         pre = p;
  16.         p = p->next;
  17.     }
  18.     if(p)
  19.     {
  20.         if(!pre)
  21.         {
  22.             head = head->next;
  23.         }
  24.         else
  25.         {
  26.             pre->next = p->next;
  27.             free(p);
  28.         }
  29.     }
  30.     return head;
  32. }
  34. int main()
  35. {   datatype x;
  36.     linklist head;
  37.     head=creatbyqueue();        /*尾插入法建立单链表*/
  38.     print(head);
  39.     printf("请输入要删除的值：");
  40.     scanf("%d",&x);
  41.     head=delx(head,x);            /*删除单链表的第一个值为x的结点*/
  42.     print(head);
  43.     delList(head);                /*释放单链表空间*/
  44.     return 0;
  45. }

  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. }
  40. int main()
  41. {   datatype x;
  42.     linklist head;
  43.     head=creatbystack();        /*头插入法建立单链表*/
  44.     print(head);                /*输出原链表*/
  45.     head= reverse1(head);        /*倒置单链表*/
  46.     print(head);                /*输出倒置后的链表*/
  47.     reverse2(&head);            /*倒置单链表*/
  48.     print(head);
  49.     delList(head);
  50.     return 0;
  51. }

  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.     }
  29.     return head;
  31. }
  32. int main()
  33. {   datatype x;
  34.     linklist head;
  35.     printf("输入一组升序排列的整数：\n");
  36.     head=creatbyqueue();                /*尾插入法建立单链表*/
  37.     print(head);
  38.     printf("请输入要插入的值：");
  39.     scanf("%d",&x);
  40.     head=insert(head,x);                /*将输入的值插入到单链表适当位置*/
  41.     print(head);
  42.     delList(head);
  43.     return 0;
  44. }

  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;
  12. /**********************************/
  13. /*函数名称：creatbystack()              */
  14. /*函数功能：头插法建立单链表            */
  15. /**********************************/
  16. linklist creatbystack()
  17. {  linklist  head,s;
  18.     datatype x;
  19.     head=NULL;
  20.     printf("请输入若干整数序列:\n");
  21.     scanf("%d",&x);
  22.     while (x!=0)        /*以0结束输入*/
  23.     {   s=(linklist)malloc(sizeof(node));  /*生成待插入结点*/
  24.         s->info=x;
  25.         s->next=head;            /*将新结点插入到链表最前面*/
  26.         head=s;
  27.         scanf("%d",&x);
  28.     }
  29.     return head;                /*返回建立的单链表*/
  30. }
  31. /**********************************/
  32. /*函数名称：creatbyqueue()              */
  33. /*函数功能：尾插法建立单链表            */
  34. /**********************************/
  35. linklist creatbyqueue()
  36. {
  37.     linklist head,r,s;
  38.     datatype x;
  39.     head=r=NULL;
  40.     printf("请输入若干整数序列:\n");
  41.     scanf("%d",&x);
  42.     while (x!=0) /*以0结束输入*/
  43.     {    s=(linklist)malloc(sizeof(node));
  44.          s->info=x;
  45.          if (head==NULL)        /*将新结点插入到链表最后面*/
  46.             head=s;
  47.          else
  48.             r->next=s;
  49.         r=s;
  50.         scanf("%d",&x);
  51.    }
  52.     if (r)  r->next=NULL;
  53.     return head;                    /*返回建立的单链表*/
  54. }
  55. /**********************************/
  56. /*函数名称：print()                      */
  57. /*函数功能：输出不带头结点的单链表      */
  58. /**********************************/
  59. void print(linklist head)
  60. {   linklist p;
  61.     int i=0;
  62.     p=head;
  63.     printf("List is:\n");
  64.     while(p)
  65.     {
  66.         printf("%5d",p->info);
  67.         p=p->next;
  68.          i++;
  69.          if (i%10==0) printf("\n");
  70.     }
  71.     printf("\n");
  72. }
  73. /**********************************/
  74. /*函数名称：delList()                  */
  75. /*函数功能：释放不带头结点的单链表      */
  76. /**********************************/
  77. void delList(linklist head)
  78. { linklist p=head;
  79.   while (p)
  80.   { head=p->next;
  81.     free(p);
  82.     p=head;
  83.   }
  84. }

本文地址：http://liuyanzhao.com/3600.html

转载请注明

历史上的今天
十二月
05日
  • 微信
  • 交流学习，资料分享
  • weinxin
  • 个人淘宝
  • 店铺名：言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

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

  

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