发帖
翼度科技»论坛 › 云主机 › LINUX › 查看内容

数据结构的练习day1

追风猎人

12

主题

12

帖子

36

积分

新手上路

Rank: 1

积分
36
显示全部楼层

链表只能一个一个的遍历，不能通过随机访问来获取节点

链表的地址是并要求连续的，是通过内部的指针来进行联系的
  1. /********************************************************************************************************
  2. *
  3. *
  4. *
  5. *
  6. *
  7. *
  8. * Copyright (c)  2023-2024   2556560122@qq.com    All right Reserved
  9. * ******************************************************************************************************/
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <stdbool.h>
  15. // 指的是单向链表中的结点有效数据类型，用户可以根据需要进行修改
  16. typedef int DataType_t;
  18. // 构造链表的结点,链表中所有结点的数据类型应该是相同的
  19. typedef struct LinkedList
  20. {
  21.   DataType_t data;         // 结点的数据域
  22.   struct LinkedList *next; // 结点的指针域
  24. } LList_t;
  26. // 创建一个空链表，空链表应该有一个头结点，对链表进行初始化
  27. LList_t *LList_Create(void)
  28. {
  29.   // 1.创建一个头结点并对头结点申请内存
  30.   LList_t *Head = (LList_t *)calloc(1, sizeof(LList_t));
  31.   if (NULL == Head)
  32.   {
  33.     perror("Calloc memory for Head is Failed");
  34.     exit(-1);
  35.   }
  37.   // 2.对头结点进行初始化，头结点是不存储有效内容的！！！
  38.   Head->next = NULL;
  40.   // 3.把头结点的地址返回即可
  41.   return Head;
  42. }
  44. // 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
  45. LList_t *LList_NewNode(DataType_t data)
  46. {
  47.   // 1.创建一个新结点并对新结点申请内存
  48.   LList_t *New = (LList_t *)calloc(1, sizeof(LList_t));
  49.   if (NULL == New)
  50.   {
  51.     perror("Calloc memory for NewNode is Failed");
  52.     return NULL;
  53.   }
  55.   // 2.对新结点的数据域和指针域进行初始化
  56.   New->data = data;
  57.   New->next = NULL;
  59.   return New;
  60. }
  62. // 头插
  63. bool LList_HeadInsert(LList_t *Head, DataType_t data)
  64. {
  65.   // 1.创建新的结点，并对新结点进行初始化
  66.   LList_t *New = LList_NewNode(data);
  67.   if (NULL == New)
  68.   {
  69.     printf("can not insert new node\n");
  70.     return false;
  71.   }
  73.   // 2.判断链表是否为空，如果为空，则直接插入即可
  74.   if (NULL == Head->next)
  75.   {
  76.     Head->next = New;
  77.     return true;
  78.   }
  80.   // 3.如果链表为非空，则把新结点插入到链表的头部
  81.   New->next = Head->next;
  82.   Head->next = New;
  84.   return true;
  85. }
  87. // 尾插
  88. bool LList_TailInsert(LList_t *Head, DataType_t data)
  89. {
  90.   if (Head->next == NULL)
  91.   {
  92.     printf("链表尾空!\n");
  93.     return false;
  94.   }
  95.   // 新建一个指针指向Head的next
  96.   LList_t *copy_head = Head->next;
  97.   // 创建一个新的节点
  98.   LList_t *newNode = LList_NewNode(data);
  99.   while (copy_head)
  100.   {
  101.     // 到了尾节点了
  102.     if (copy_head->next == NULL)
  103.     {
  104.       // 尾插
  105.       copy_head->next = newNode;
  106.       // 退出循环
  107.       break;
  108.     }
  109.     copy_head = copy_head->next;
  110.   }
  111.   return true;
  112. }
  114. // 插到目标节点的后面
  115. bool LList_DestInsert(LList_t *Head, DataType_t dest, DataType_t data)
  116. {
  117.   if (Head->next == NULL)
  118.   {
  119.     printf("链表尾空!\n");
  120.     return false;
  121.   }
  122.   // 新建一个指针指向Head的next
  123.   LList_t *copy_head = Head->next;
  124.   // 创建一个新的节点
  125.   LList_t *newNode = LList_NewNode(data);
  126.   while (copy_head)
  127.   {
  128.     // 找到了目标节点
  129.     if (copy_head->data == dest)
  130.     {
  131.       // 指向目标节点的next
  132.       newNode->next = copy_head->next;
  133.       // 目标节点指向新节点
  134.       copy_head->next = newNode;
  135.       // 找到了，退出方法，放回true
  136.       return true;
  137.     }
  138.     // 没找到,指针指向下个节点
  139.     copy_head = copy_head->next;
  140.   }
  141.   // 没找到
  142.   return false;
  143. }
  145. // 寻找链表的最小值
  146. int Select_Min_Node(LList_t *Head)
  147. {
  148.   if (Head->next == NULL)
  149.   {
  150.     printf("链表尾空!\n");
  151.     return -1;
  152.   }
  153.   // 新建一个指针指向Head的next
  154.   LList_t *copy_head = Head->next;
  155.   // 默认最小值是copy_head的data
  156.   int min = copy_head->data;
  157.   while (copy_head->next)
  158.   {
  159.     // 如果min大于下个节点的数值，min就发生交换
  160.     if (min > copy_head->next->data)
  161.     {
  162.       min = copy_head->next->data;
  163.     }
  164.     // 进入下个节点
  165.     copy_head = copy_head->next;
  166.   }
  167.   return min;
  168. }
  170. // 删除最小数据的节点
  171. void DelectMinDataNode(LList_t *Head)
  172. {
  173.   if (Head->next == NULL)
  174.   {
  175.     printf("链表为空!\n");
  176.     return;
  177.   }
  178.   // 新建一个指针指向Head的next
  179.   LList_t *copy_head = Head;
  180.   // 获取链表中的最小数据
  181.   int delVal = Select_Min_Node(Head);
  182.   while (copy_head->next)
  183.   {
  184.     if (copy_head->next->data == delVal)
  185.     {
  186.       // 创建一个指针保存要删除的节点的next
  187.       LList_t *copy_del_next = copy_head->next->next;
  188.       // 释放空间
  189.       free(copy_head->next);
  190.       // 指向要删除的节点的next
  191.       copy_head->next = copy_del_next;
  192.       // 退出循环
  193.       break;
  194.     }
  195.     copy_head = copy_head->next;
  196.   }
  197.   return;
  198. }
  200. // 遍历
  201. void LList_Print(LList_t *Head)
  202. {
  203.   // 对链表的头文件的地址进行备份
  204.   LList_t *Phead = Head;
  206.   // 首结点
  207.   while (Phead->next)
  208.   {
  209.     // 把头的直接后继作为新的头结点
  210.     Phead = Phead->next;
  212.     // 输出头结点的直接后继的数据域
  213.     printf("data = %d\n", Phead->data);
  214.   }
  215. }
  217. int main(int argc, char const *argv[])
  218. {
  219.   // 创建链表头节点
  220.   LList_t *Head = LList_Create();
  221.   // 头插
  222.   LList_HeadInsert(Head, 0);
  223.   LList_HeadInsert(Head, 5);
  224.   LList_HeadInsert(Head, 20);
  225.   LList_HeadInsert(Head, 1);
  226.   // 尾插
  227.   LList_TailInsert(Head, 20);
  228.   // 在目标后面插
  229.   LList_DestInsert(Head, 5, 2);
  230.   // 删除链表中数据最小的节点
  231.   DelectMinDataNode(Head);
  232.   // 遍历链表
  233.   LList_Print(Head);
  234.   return 0;
  235. }
复制代码
  1. /********************************************************************************************************
  2. *
  3. *查找链表的倒数第k个节点的数据
  4. *思想: 可以根据链表的节点数-k来获取需要head的next的次数来获取节点
  5. *
  6. *
  7. *
  8. * Copyright (c)  2023-2024   2556560122@qq.com   All right Reserved
  9. * ******************************************************************************************************/
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <stdbool.h>
  15. // 指的是单向链表中的结点有效数据类型，用户可以根据需要进行修改
  16. typedef int DataType_t;
  18. // 构造链表的结点,链表中所有结点的数据类型应该是相同的
  19. typedef struct LinkedList
  20. {
  21.   DataType_t data;         // 结点的数据域
  22.   struct LinkedList *next; // 结点的指针域
  24. } LList_t;
  26. // 创建一个空链表，空链表应该有一个头结点，对链表进行初始化
  27. LList_t *LList_Create(void)
  28. {
  29.   // 1.创建一个头结点并对头结点申请内存
  30.   LList_t *Head = (LList_t *)calloc(1, sizeof(LList_t));
  31.   if (NULL == Head)
  32.   {
  33.     perror("Calloc memory for Head is Failed");
  34.     exit(-1);
  35.   }
  37.   // 2.对头结点进行初始化，头结点是不存储有效内容的！！！
  38.   Head->next = NULL;
  40.   // 3.把头结点的地址返回即可
  41.   return Head;
  42. }
  44. // 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
  45. LList_t *LList_NewNode(DataType_t data)
  46. {
  47.   // 1.创建一个新结点并对新结点申请内存
  48.   LList_t *New = (LList_t *)calloc(1, sizeof(LList_t));
  49.   if (NULL == New)
  50.   {
  51.     perror("Calloc memory for NewNode is Failed");
  52.     return NULL;
  53.   }
  55.   // 2.对新结点的数据域和指针域进行初始化
  56.   New->data = data;
  57.   New->next = NULL;
  59.   return New;
  60. }
  62. // 头插
  63. bool LList_HeadInsert(LList_t *Head, DataType_t data)
  64. {
  65.   // 1.创建新的结点，并对新结点进行初始化
  66.   LList_t *New = LList_NewNode(data);
  67.   if (NULL == New)
  68.   {
  69.     printf("can not insert new node\n");
  70.     return false;
  71.   }
  73.   // 2.判断链表是否为空，如果为空，则直接插入即可
  74.   if (NULL == Head->next)
  75.   {
  76.     Head->next = New;
  77.     return true;
  78.   }
  80.   // 3.如果链表为非空，则把新结点插入到链表的头部
  81.   New->next = Head->next;
  82.   Head->next = New;
  84.   return true;
  85. }
  87. // 遍历
  88. void LList_Print(LList_t *Head)
  89. {
  90.   // 对链表的头文件的地址进行备份
  91.   LList_t *Phead = Head;
  93.   // 首结点
  94.   while (Phead->next)
  95.   {
  96.     // 把头的直接后继作为新的头结点
  97.     Phead = Phead->next;
  99.     // 输出头结点的直接后继的数据域
  100.     printf("data = %d\n", Phead->data);
  101.   }
  102. }
  103. /********************************************************************************************************
  104. *
  105. * 查找链表中倒数第k个位置上的节点
  106. * ①先遍历链表记录链表的节点数
  107. * ②然后通过for循环链表来获取到链表中倒数第k个位置上的节点，并且返回其data
  108. * ③找到返回1，没找到返回0
  109. *
  110. *
  111. *
  112. * ******************************************************************************************************/
  113. int SelectRecNode(LList_t *Head, DataType_t k)
  114. {
  115.   if (Head->next == NULL)
  116.   {
  117.     printf("链表为空!\n");
  118.     return 0;
  119.   }
  120.   // 新建一个指针指向Head的next
  121.   LList_t *copy_head = Head->next;
  122.   // 记录其节点数
  123.   int count = 0;
  124.   // 通过while循环记录链表的节点数
  125.   while (copy_head)
  126.   {
  127.     count++;
  128.     copy_head = copy_head->next;
  129.   }
  130.   // 把copy_head重新指向Head的next
  131.   copy_head = Head->next;
  132.   // 通过节点数-k就是其节点在链表中的位置
  133.   for (int i = 0; i < count - k; i++)
  134.   {
  135.     copy_head = copy_head->next;
  136.   }
  137.   printf("链表中倒数第%d个节点的数值是%d\n", k, copy_head->data);
  138.   return 1;
  139. }
  141. int main()
  142. {
  143.   // 创建链表头节点
  144.   LList_t *Head = LList_Create();
  145.   // 头插
  146.   LList_HeadInsert(Head, 1);
  147.   LList_HeadInsert(Head, 2);
  148.   LList_HeadInsert(Head, 3);
  149.   LList_HeadInsert(Head, 4);
  150.   LList_HeadInsert(Head, 5);
  151.   LList_HeadInsert(Head, 6);
  152.   LList_Print(Head);
  153.   SelectRecNode(Head, 3);
  154. }
复制代码
来源:https://www.cnblogs.com/DengJian111222/p/18151538
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x

上一篇: shell脚本正则表达式

下一篇: 实验

发表于 2024-4-22 23:14:09

举报 回复 使用道具

返回列表 发新帖

Archiver|手机版|小黑屋|翼度科技

Copyright © 2001-2020, Tencent Cloud.　Powered by Discuz! X3.4