devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言单向不循环链表_链表输入如何停止

作者：我家小花儿 | 2024-07-17 02:14:46

赞

踩

链表输入如何停止

目录

链表的概念

 1、设计节点类型

2、创建链表 

3、头插法 

 4、尾插法

​ 5、打印链表节点数据

6、头删法 

 7、尾删法

 8、链表节点数据个数

9、指定位置插入

10、指定位置删除

11、链表冒泡排序

12、菜单 

整体代码显示

测试

链表的概念

链表的两种结构

物理结构和逻辑结构

物理 存储单元 上非连续、非顺序的 存储结构，

逻辑上是连续的，他们之间用指针连续起来

链表中每一个元素称为节点，由一系列的节点组成。

每个节点包括两部分，存储数据元素的数据域（data）和存储下一个节点地址的指针域（next）。

如图所示：下图有四个节点，头节点一般不存数据，head为头节点，next为指向下一个节点的

指针（存储下一个节点的地址），单向不循环链表最后一个节点的指针域，指向空（NULL）。

 1、设计节点类型

  1.  
  2. /**************设计节点类型**************/
  3. typedef struct ListNode
  4. {
  5.     int data;              //数据域
  6.     struct ListNode *next; //地址域
  7. } node_t;

2、创建链表 

申请头节点空间

  1. /********创建链表********/
  2. node_t *CreateList()
  3. {
  4.     node_t *head = (node_t *)malloc(sizeof(node_t)); //申请头节点空间
  5.     if (head == NULL)
  6.     {
  7.         perror("head is null\n"); //如果空间申请失败报错
  8.         return NULL;
  9.     }
  10.     head->data = 0; //头节点数据域不放数据，初始化
  11.     head->next = NULL;
  12.  
  13.     return head;
  14. }

3、头插法 

  1. /************头插法************/
  2. int InsertHListNode(node_t *head, int newdata)
  3. {
  4.     // 1、判断
  5.     if (head == NULL)
  6.     {
  7.         perror("head is null\n");
  8.         return -1;
  9.     }
  10.     // 2、申请新节点空间
  11.     node_t *newnode = (node_t *)malloc(sizeof(node_t));
  12.     if (newnode == NULL)
  13.     {
  14.         perror("newnode is null\n");
  15.         return -1;
  16.     }
  17.     // 3、填写数据
  18.     newnode->data = newdata;
  19.     // 4、修改指针
  20.     newnode->next = head->next;
  21.     head->next = newnode; //头节点指向新节点
  22.     return 0;
  23. }

头插法就是在头节点后插入新节点（头节点不放数据所以从头节点后一个位置插入），核心就是 将新节点两条线连接起来

 

 4、尾插法

  1. /************尾插法************/
  2. int InserttListNode(node_t *head, int newdata)
  3. {
  4.     // 1、判断
  5.     if (head == NULL)
  6.     {
  7.         perror("head is null\n");
  8.         return -1;
  9.     }
  10.     // 2、申请新节点空间
  11.     node_t *newnode = (node_t *)malloc(sizeof(node_t));
  12.     if (newnode == NULL)
  13.     {
  14.         perror("malloc error\n");
  15.         return -1;
  16.     }
  17.     // 3、填写数据
  18.     newnode->data = newdata;
  19.     // 4、找尾
  20.     node_t *temp = head;       //因为头节点不能动所以申请一个中间变量
  21.     while (temp->next != NULL) //当temp->next = NULL时跳出循环
  22.     {
  23.         temp = temp->next;
  24.     }
  25.  
  26.     // 5、修改指针
  27.     newnode->next = temp->next; //新节点指向最后
  28.     temp->next = newnode;       //新节点接到最后一个节点后
  29.     return 0;
  30. }

尾插法 核心就是找尾，找到尾后修改指针的指向，代码中的指针指向跟图中的指针指向是同一个意思，只是写法不同。

 5、打印链表节点数据

遍历， 循环打印，将链表中的所有的节点数据打印到终端

  1. /*************打印链表***************/
  2. void PrintList(node_t *head)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         perror("There is no data in the linked list, please input it first\n");
  7.         return;
  8.     }
  9.  
  10.     node_t *temp = head;
  11.     while (temp->next != NULL)
  12.     {
  13.         temp = temp->next; //因为头节点不放数据所以从第二个节点开始
  14.         printf("%d\t", temp->data);
  15.     }
  16.     printf("\n");
  17. }

6、头删法 

  1. /***************头删法*******************/
  2. int DeleteHList(node_t *head)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         perror("head is null\n");
  7.         return -1;
  8.     }
  9.     //设置一个临时变量
  10.     node_t *temp = head->next;
  11.     head->next = temp->next;
  12.     free(temp); //删除成功释放空间
  13.     temp = NULL;
  14.     return 0;
  15. }

头删法：相对来说是比较简单的，只需要改变一个指针指向。

 7、尾删法

  1. /***************尾删法*******************/
  2. int DeleteTList(node_t *head)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         perror("head is null\n");
  7.         return -1;
  8.     }
  9.     //设置一个临时变量
  10.     node_t *prev = NULL; //指向尾的前一个节点
  11.     node_t *temp = head;
  12.     //找尾
  13.     while (temp->next->next != NULL)
  14.     {
  15.         temp = temp->next;
  16.     }
  17.     prev = temp;
  18.     temp = temp->next;
  19.     prev->next = NULL;
  20.     free(temp);
  21.     temp = NULL;
  22.     return 0;
  23. }

尾删法：找两个节点先找倒是第二个，在通过倒数第二个找到最后一个，找最后一个是为了释放节点空间。

 8、链表节点数据个数

遍历整个链表，然后返回节点数据个数（因为头节点不放数据所以不包括头节点）

  1. /****************链表的节点元素个数**********************/
  2. int ListLength(node_t *head)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         perror("head is null\n");
  7.         return -1;
  8.     }
  9.     node_t *temp = head;
  10.     int i = 0;
  11.     while (temp->next != NULL)
  12.     {
  13.         temp = temp->next;
  14.         i++;
  15.     }
  16.     return i;
  17. }

9、指定位置插入

  1. /***************指定位置插入***************/
  2. int InsertLocaList(node_t *head, int newdata, int loca)
  3. {
  4.     //判错
  5.     int len = ListLength(head);
  6.     if (head == NULL || loca <= 0 || loca > len + 1) //插入的位置超范围
  7.     {
  8.         perror("head is null or out of scope\n");
  9.         return -1;
  10.     }
  11.     //申请新节点空间
  12.     node_t *newnode = (node_t *)malloc(sizeof(node_t));
  13.     if (newnode == NULL)
  14.     {
  15.         perror("malloc error\n");
  16.         return -1;
  17.     }
  18.     //填写数据，建立联系
  19.     newnode->data = newdata;
  20.     node_t *temp = head;
  21.     int i = 1;
  22.     while (loca != i)
  23.     {
  24.         temp = temp->next;
  25.         i++;
  26.     }
  27.     newnode->next = temp->next;
  28.     temp->next = newnode;
  29.     return 0;
  30. }

在写之前一定要判断该链表和该位置是否为空，如果都不存在链表和该位置，要插入的节点就接不上了。 

10、指定位置删除

  1. /***************指定位置删除***************/
  2. int DeleteLocaList(node_t *head, int loca)
  3. {
  4.     //判错
  5.     int len = ListLength(head);
  6.     if (head == NULL || loca <= 0 || loca > len) //删除的位置超范围
  7.     {
  8.         perror("head is null or out of scope\n");
  9.         return -1;
  10.     }
  11.  
  12.     node_t *prev = NULL; //指向尾的前一个节点
  13.     node_t *temp = head;
  14.     int i = 1;
  15.     //找要删除节点的前一个位置
  16.     while (loca != i)
  17.     {
  18.         temp = temp->next;
  19.         i++;
  20.     }
  21.     prev = temp;
  22.     temp = temp->next;
  23.     prev->next = temp->next;
  24.     return 0;
  25. }

11、链表冒泡排序

  1. /************链表冒泡排序*************/
  2. node_t *SortList(node_t *head)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         perror("head is null\n");
  7.         return NULL;
  8.     }
  9.     int len = ListLength(head);
  10.     if (len < 2)
  11.     {
  12.         return head;
  13.     }
  14.     node_t *r, *p, *q; //表示前中后三个节点位置
  15.     r = head;
  16.     for (int i = 0; i < len - 1; i++)
  17.     {
  18.         r = head;
  19.         for (int j = 0; j < len - i - 1; j++)
  20.         {
  21.             p = r->next;
  22.             q = p->next;
  23.             if (q->data < p->data)
  24.             {
  25.                 p->next = q->next;
  26.                 q->next = p;
  27.                 r->next = q;
  28.             }
  29.             r = r->next;
  30.         }
  31.     }
  32.     return head;
  33. }

12、菜单 

  1. void menu(node_t *head)
  2. {
  3.     char ch;
  4.     while (1)
  5.     {
  6.         printf("***************************************\n");
  7.         printf("*****      1.头插                 *****\n");
  8.         printf("*****      2.尾插                 *****\n");
  9.         printf("*****      3.头删                 *****\n");
  10.         printf("*****      4.尾删                 *****\n");
  11.         printf("*****      5.在指定位置插入       *****\n");
  12.         printf("*****      6.在指定位置删除       *****\n");
  13.         printf("*****      7.打印单链表           *****\n");
  14.         printf("*****      8.查看链表中有多少元素 *****\n");
  15.         printf("*****      9.排序                 *****\n");
  16.         printf("*****      0.退出                 *****\n");
  17.         printf("***************************************\n");
  18.  
  19.         int option = 0, loca = 0, newdata = 0;
  20.         printf("请输入选项:> ");
  21.         scanf("%d", &option);
  22.         switch (option)
  23.         {
  24.         case 9:
  25.             head = SortList(head);
  26.             break;
  27.         case 8:
  28.             printf("链表中有%d个元素\n", ListLength(head));
  29.             break;
  30.         case 7:
  31.             PrintList(head);
  32.             break;
  33.         case 6:
  34.             printf("请输入你要删除的位置:");
  35.             scanf("%d", &loca);
  36.             DeleteLocaList(head, loca);
  37.             break;
  38.         case 5:
  39.             printf("请输入你要插入的位置:");
  40.             scanf("%d", &loca);
  41.             printf("请输入你要插入的元素:");
  42.             scanf("%d", &newdata);
  43.             InsertLocaList(head, newdata, loca);
  44.             break;
  45.         case 4:
  46.             DeleteTList(head);
  47.             break;
  48.         case 3:
  49.             DeleteHList(head);
  50.             break;
  51.         case 2:
  52.             printf("请输入你要插入的元素:");
  53.             scanf("%d", &newdata);
  54.             InserttListNode(head, newdata);
  55.             break;
  56.         case 1:
  57.             printf("请输入你要插入的元素:");
  58.             scanf("%d", &newdata);
  59.             InsertHListNode(head, newdata);
  60.             break;
  61.         case 0:
  62.             return;
  63.         default:
  64.             printf("输入错误\n");
  65.             break;
  66.         }
  67.         printf("是否继续(y/n)\n");
  68.         getchar(); //空吞
  69.         ch = getchar();
  70.         if (ch == 'n' || ch == 'N')
  71.         {
  72.             return;
  73.         }
  74.     }
  75. }

整体代码显示

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /**************设计节点类型**************/
  5. typedef struct ListNode
  6. {
  7.     int data;              //数据域
  8.     struct ListNode *next; //地址域
  9. } node_t;
  10.  
  11. node_t *CreateList();                                    //创建链表
  12. int InsertHListNode(node_t *head, int newdata);          //头插法
  13. int InserttListNode(node_t *head, int newdata);          //尾插法
  14. int InsertLocaList(node_t *head, int newdata, int loca); //在指定位置插入
  15. int DeleteHList(node_t *head);                           //头删法
  16. int DeleteTList(node_t *head);                           //尾删法
  17. int DeleteLocaList(node_t *head, int loca);              //在指定位置删除
  18. int ListLength(node_t *head);                            //链表的节点元素个数
  19. void PrintList(node_t *head);                            //打印链表
  20. void menu(node_t *head);                                 //菜单
  21. node_t *SortList(node_t *head);                          //冒泡排序
  22.  
  23. int main()
  24. {
  25.     node_t *head = CreateList();
  26.     if (head == NULL)
  27.     {
  28.         perror("head is null\n");
  29.         return -1;
  30.     }
  31.     menu(head);
  32.     return 0;
  33. }
  34.  
  35. /*****************菜单***********/
  36. void menu(node_t *head)
  37. {
  38.     char ch;
  39.     while (1)
  40.     {
  41.         printf("***************************************\n");
  42.         printf("*****      1.头插                 *****\n");
  43.         printf("*****      2.尾插                 *****\n");
  44.         printf("*****      3.头删                 *****\n");
  45.         printf("*****      4.尾删                 *****\n");
  46.         printf("*****      5.在指定位置插入       *****\n");
  47.         printf("*****      6.在指定位置删除       *****\n");
  48.         printf("*****      7.打印单链表           *****\n");
  49.         printf("*****      8.查看链表中有多少元素 *****\n");
  50.         printf("*****      9.排序                 *****\n");
  51.         printf("*****      0.退出                 *****\n");
  52.         printf("***************************************\n");
  53.  
  54.         int option = 0, loca = 0, newdata = 0;
  55.         printf("请输入选项:> ");
  56.         scanf("%d", &option);
  57.         switch (option)
  58.         {
  59.         case 9:
  60.             head = SortList(head);
  61.             break;
  62.         case 8:
  63.             printf("链表中有%d个元素\n", ListLength(head));
  64.             break;
  65.         case 7:
  66.             PrintList(head);
  67.             break;
  68.         case 6:
  69.             printf("请输入你要删除的位置:");
  70.             scanf("%d", &loca);
  71.             DeleteLocaList(head, loca);
  72.             break;
  73.         case 5:
  74.             printf("请输入你要插入的位置:");
  75.             scanf("%d", &loca);
  76.             printf("请输入你要插入的元素:");
  77.             scanf("%d", &newdata);
  78.             InsertLocaList(head, newdata, loca);
  79.             break;
  80.         case 4:
  81.             DeleteTList(head);
  82.             break;
  83.         case 3:
  84.             DeleteHList(head);
  85.             break;
  86.         case 2:
  87.             printf("请输入你要插入的元素:");
  88.             scanf("%d", &newdata);
  89.             InserttListNode(head, newdata);
  90.             break;
  91.         case 1:
  92.             printf("请输入你要插入的元素:");
  93.             scanf("%d", &newdata);
  94.             InsertHListNode(head, newdata);
  95.             break;
  96.         case 0:
  97.             return;
  98.         default:
  99.             printf("输入错误\n");
  100.             break;
  101.         }
  102.         printf("是否继续(y/n)\n");
  103.         getchar(); //空吞
  104.         ch = getchar();
  105.         if (ch == 'n' || ch == 'N')
  106.         {
  107.             return;
  108.         }
  109.     }
  110. }
  111.  
  112. /********创建链表********/
  113. node_t *CreateList()
  114. {
  115.     node_t *head = (node_t *)malloc(sizeof(node_t)); //申请头节点空间
  116.     if (head == NULL)
  117.     {
  118.         perror("head is null\n"); //如果空间申请失败报错
  119.         return NULL;
  120.     }
  121.     head->data = 0; //头节点数据域不放数据，初始化
  122.     head->next = NULL;
  123.  
  124.     return head;
  125. }
  126.  
  127. /************头插法************/
  128. int InsertHListNode(node_t *head, int newdata)
  129. {
  130.     // 1、判断
  131.     if (head == NULL)
  132.     {
  133.         perror("head is null\n");
  134.         return -1;
  135.     }
  136.     // 2、申请新节点空间
  137.     node_t *newnode = (node_t *)malloc(sizeof(node_t));
  138.     if (newnode == NULL)
  139.     {
  140.         perror("newnode is null\n");
  141.         return -1;
  142.     }
  143.     // 3、填写数据
  144.     newnode->data = newdata;
  145.     // 4、修改指针
  146.     newnode->next = head->next;
  147.     head->next = newnode; //头节点指向新节点
  148.     return 0;
  149. }
  150.  
  151. /************尾插法************/
  152. int InserttListNode(node_t *head, int newdata)
  153. {
  154.     // 1、判断
  155.     if (head == NULL)
  156.     {
  157.         perror("head is null\n");
  158.         return -1;
  159.     }
  160.     // 2、申请新节点空间
  161.     node_t *newnode = (node_t *)malloc(sizeof(node_t));
  162.     if (newnode == NULL)
  163.     {
  164.         perror("malloc error\n");
  165.         return -1;
  166.     }
  167.     // 3、填写数据
  168.     newnode->data = newdata;
  169.     // 4、找尾
  170.     node_t *temp = head;       //因为头节点不能动所以申请一个中间变量
  171.     while (temp->next != NULL) //当temp->next = NULL时跳出循环
  172.     {
  173.         temp = temp->next;
  174.     }
  175.  
  176.     // 5、修改指针
  177.     newnode->next = temp->next; //新节点指向最后
  178.     temp->next = newnode;       //新节点接到最后一个节点后
  179.     return 0;
  180. }
  181.  
  182. /*************打印链表***************/
  183. void PrintList(node_t *head)
  184. {
  185.     if (head == NULL)
  186.     {
  187.         perror("There is no data in the linked list, please input it first\n");
  188.         return;
  189.     }
  190.  
  191.     node_t *temp = head;
  192.     while (temp->next != NULL)
  193.     {
  194.         temp = temp->next; //因为头节点不放数据所以从第二个节点开始
  195.         printf("%d\t", temp->data);
  196.     }
  197.     printf("\n");
  198. }
  199.  
  200. /***************头删法*******************/
  201. int DeleteHList(node_t *head)
  202. {
  203.     if (head == NULL)
  204.     {
  205.         perror("head is null\n");
  206.         return -1;
  207.     }
  208.     //设置一个临时变量
  209.     node_t *temp = head->next;
  210.     head->next = temp->next;
  211.     free(temp); //删除成功释放空间
  212.     temp = NULL;
  213.     return 0;
  214. }
  215.  
  216. /***************尾删法*******************/
  217. int DeleteTList(node_t *head)
  218. {
  219.     if (head == NULL)
  220.     {
  221.         perror("head is null\n");
  222.         return -1;
  223.     }
  224.     //设置一个临时变量
  225.     node_t *prev = NULL; //指向尾的前一个节点
  226.     node_t *temp = head;
  227.     //找尾
  228.     while (temp->next->next != NULL)
  229.     {
  230.         temp = temp->next;
  231.     }
  232.     prev = temp;
  233.     temp = temp->next;
  234.     prev->next = NULL;
  235.     free(temp);
  236.     temp = NULL;
  237.     return 0;
  238. }
  239.  
  240. /****************链表的节点元素个数**********************/
  241. int ListLength(node_t *head)
  242. {
  243.     if (head == NULL)
  244.     {
  245.         perror("head is null\n");
  246.         return -1;
  247.     }
  248.     node_t *temp = head;
  249.     int i = 0;
  250.     while (temp->next != NULL)
  251.     {
  252.         temp = temp->next;
  253.         i++;
  254.     }
  255.     return i;
  256. }
  257.  
  258. /***************指定位置插入***************/
  259. int InsertLocaList(node_t *head, int newdata, int loca)
  260. {
  261.     //判错
  262.     int len = ListLength(head);
  263.     if (head == NULL || loca <= 0 || loca > len + 1) //插入的位置超范围
  264.     {
  265.         perror("head is null or out of scope\n");
  266.         return -1;
  267.     }
  268.     //申请新节点空间
  269.     node_t *newnode = (node_t *)malloc(sizeof(node_t));
  270.     if (newnode == NULL)
  271.     {
  272.         perror("malloc error\n");
  273.         return -1;
  274.     }
  275.     //填写数据，建立联系
  276.     newnode->data = newdata;
  277.     node_t *temp = head;
  278.     int i = 1;
  279.     while (loca != i)
  280.     {
  281.         temp = temp->next;
  282.         i++;
  283.     }
  284.     newnode->next = temp->next;
  285.     temp->next = newnode;
  286.     return 0;
  287. }
  288.  
  289. /***************指定位置删除***************/
  290. int DeleteLocaList(node_t *head, int loca)
  291. {
  292.     //判错
  293.     int len = ListLength(head);
  294.     if (head == NULL || loca <= 0 || loca > len) //删除的位置超范围
  295.     {
  296.         perror("head is null or out of scope\n");
  297.         return -1;
  298.     }
  299.  
  300.     node_t *prev = NULL; //指向尾的前一个节点
  301.     node_t *temp = head;
  302.     int i = 1;
  303.     //找要删除节点的前一个位置
  304.     while (loca != i)
  305.     {
  306.         temp = temp->next;
  307.         i++;
  308.     }
  309.     prev = temp;
  310.     temp = temp->next;
  311.     prev->next = temp->next;
  312.     return 0;
  313. }
  314.  
  315. /************链表冒泡排序*************/
  316. node_t *SortList(node_t *head)
  317. {
  318.     if (head == NULL)
  319.     {
  320.         perror("head is null\n");
  321.         return NULL;
  322.     }
  323.     int len = ListLength(head);
  324.     if (len < 2)
  325.     {
  326.         return head;
  327.     }
  328.     node_t *r, *p, *q; //表示前中后三个节点位置
  329.     r = head;
  330.     for (int i = 0; i < len - 1; i++)
  331.     {
  332.         r = head;
  333.         for (int j = 0; j < len - i - 1; j++)
  334.         {
  335.             p = r->next;
  336.             q = p->next;
  337.             if (q->data < p->data)
  338.             {
  339.                 p->next = q->next;
  340.                 q->next = p;
  341.                 r->next = q;
  342.             }
  343.             r = r->next;
  344.         }
  345.     }
  346.     return head;
  347. }

测试

 

 

 

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号