• C语言对单链表所有操作与一些相关面试题

    目录

    单链表的特性

    单链表的所有操作

    定义一个单链表

    创建一个链表头

    插入数据(头插法)

    插入数据(尾插法)

    查找节点

    修改数据节点

    删除节点

    打印数据

    销毁链表

    翻转链表

    打印链表长度

    冒泡排序

    快排

    堆排

    查找倒数第K个节点（双指针法）

    完整测试代码

    单链表的特性

    单链表是一种线性数据结构，它由一系列的节点组成，每个节点包含一个数据域和一个指向下一个节点的指针域。单链表的特性有：

    • 单链表的长度是可变的，可以动态地插入和删除节点。
    • 单链表的访问是顺序的，要访问某个节点，必须从头节点开始遍历，直到找到该节点或者到达链表尾部。
    • 单链表不需要连续的内存空间，可以利用零散的空间存储数据。
    • 单链表的优势是：
      • 插入和删除操作比较简单，只需要修改指针域即可，不需要移动其他节点。
      • 单链表可以实现一些特殊的功能，如栈、队列、循环链表等。
    • 单链表的劣势是：
      • 访问操作比较慢，需要遍历整个链表，时间复杂度为O(n)。
      • 单链表需要额外的空间存储指针域，增加了空间开销。
      • 单链表容易产生内存碎片，如果频繁地插入和删除节点，可能导致内存不连续。

    单链表的所有操作

    定义一个单链表
    1. // 声明并定义个单链表结构体
    2. typedef struct _ListNode
    3. {
    4.     int val;                //数据 成员变量
    5.     struct _ListNode * next;//结构体调用自己的类型
    6. }ListNode;
    创建一个链表头
    1. void listCreate(ListNode *node)
    2. {
    3.     //初始化链表内数据
    4.     node->val = -1;
    5.     node->next = NULL;
    6. }
    插入数据(头插法)
    1. void listInsert(ListNode *node, int data)
    2. {
    3.     // 创建一个节点,并申请内存
    4.     ListNode *t_node = (ListNode *)malloc(sizeof(ListNode));
    5.  
    6.     //  节点内容赋值
    7.     t_node->val = data;
    8.  
    9.     //   头插法，新数据在前
    10.     t_node->next = node->next;
    11.     node->next = t_node;
    12. }
    插入数据(尾插法)
    1. void listTailInsert(ListNode *node, int data)
    2. {
    3.     // 创建一个节点
    4.     ListNode *t_node = (ListNode*)malloc(sizeof(ListNode));
    5.     
    6.     // 节点内容赋值
    7.     t_node->val = data;
    8.     t_node->next = NULL;
    9.     
    10.     // 声明一个尾节点
    11.     ListNode* t_tail = node;
    12.  
    13.     // 获取最后一个节点
    14.     while(t_tail->next != NULL)
    15.     {
    16.         // 后移
    17.         t_tail = t_tail->next;
    18.     }
    19.     //添加节点
    20.     t_tail->next = t_node;
    21. }
    查找节点
    1. ListNode* listFind(ListNode *node, int data)
    2. {
    3.     //申明一个空节点
    4.     ListNode *t_node = NULL;
    5.     
    6.     //遍历链表
    7.     ListNode *t_temp;
    8.     for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next)
    9.     {
    10.         //如果找到该节点
    11.         if(t_temp->val == data)
    12.         {
    13.             t_node = t_temp;
    14.             //跳出循环
    15.             break;
    16.         }
    17.     }
    18.     return t_node;
    19. }
    修改数据节点
    1. void listModify(ListNode *node, int oldData, int newData)
    2. {
    3.     // 查找值是否存在
    4.     ListNode *t_node = listFind(node, oldData);
    5.     
    6.     // 判断值是否存在
    7.     if(t_node == NULL)
    8.     {
    9.         printf("该值不存在\n");
    10.         return;
    11.     }
    12.     t_node->val = newData;
    13. }
    删除节点
    1. void listDelete(ListNode *node, int data)
    2. {
    3.     // 查找是否存在改制的数据
    4.     ListNode *t_node = listFind(node, data);
    5.     
    6.     // 如果该值对应的节点不存在
    7.     if(NULL == t_node)
    8.     {
    9.         printf("该值不存在\n");
    10.         return;
    11.     }
    12.  
    13.     // 求出被删节点的前一个节点
    14.     ListNode *t_prev = node;
    15.     
    16.     // 遍历链表
    17.     while(t_prev->next != t_node)
    18.     {
    19.         t_prev = t_prev->next;
    20.     }
    21.  
    22.     // 前一个节点的next指向被删除节点的下一个节点
    23.     t_prev->next = t_node->next;
    24.     // 释放内存
    25.     free(t_node);
    26.     // 指针置空
    27.     t_node = NULL;
    28. }
    打印数据
    1. void listDisplay(ListNode *node)
    2. {
    3.     // 遍历链表
    4.     ListNode *t_temp;
    5.     
    6.     for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next)
    7.     {
    8.         printf("%d ",t_temp->val);
    9.     }
    10.     printf("\n");
    11. }
    销毁链表
    1. void listDestroy(ListNode *node)
    2. {
    3.     // 遍历链表
    4.     ListNode *t_temp = node->next;
    5.     
    6.     while(t_temp != NULL)
    7.     {
    8.         // 先将当前节点保存
    9.         ListNode *t_node = t_temp;
    10.         // 移动到下一各节点
    11.         t_temp = t_temp->next;
    12.         // 释放保存内容的节点
    13.         free(t_node);
    14.     }
    15. }
    翻转链表
    1. void listReverse(ListNode *node)
    2. {
    3.     ListNode * head = NULL, *now = NULL, *temp = NULL;
    4.     head = node->next;
    5.     // head是来保存我们翻转以后链表中的头节点的
    6.     now = head->next;
    7.     // now用来保存我们当前待处理的节点
    8.     head->next = NULL;
    9.     // 一定要置为NULL，否则可能导致循环
    10.  
    11.     while(now)
    12.     {
    13.         temp = now->next; // 利用一个临时指针来保存下一个待处理的节点
    14.         
    15.         now->next = head; // 将当前节点插入到逆序节点的第一个节点之前，并更改head指向
    16.         
    17.         head = now;
    18.         node->next = head; // 使链表头指针指向逆序后的第一个节点
    19.         
    20.         now = temp; // 更新链表到下一个待处理的节点
    21.     }
    22. }
    打印链表长度
    1. int listLength(ListNode *node)
    2. {
    3.     ListNode *t_temp;
    4.     int t_length = 0;
    5.     for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next)
    6.     {
    7.         t_length++;
    8.     }
    9.     return t_length;
    10. }
    冒泡排序
    1. void listBubbleSort(ListNode *node)
    2. {
    3.     int t_length = listLength(node);
    4.     int i,j;
    5.     ListNode *t_temp;
    6.     for(i = 0; i < t_length; i++)
    7.     {
    8.         t_temp = node->next;
    9.         for(j = 0;j < t_length - i - 1; j++)
    10.         {
    11.             if(t_temp->val > t_temp->next->val)
    12.             {
    13.                 int t_data = t_temp->val;
    14.                 t_temp->val = t_temp->next->val;
    15.                 t_temp->next->val = t_data;
    16.             }
    17.             t_temp = t_temp->next;
    18.         }
    19.     }
    20. }
    快排
    1. void quickSort(struct _ListNode *head, struct _ListNode *tail) {
    2.     // 如果链表为空或只有一个节点，直接返回
    3.     if (head == NULL || head == tail) return;
    4.     // 定义两个指针p和q，用于分割链表
    5.     struct _ListNode *p = head, *q = head->next;
    6.     // 选取第一个节点作为基准值
    7.     int pivot = head->val;
    8.     // 遍历链表，将小于基准值的节点放到p的后面
    9.     while (q != tail->next) {
    10.         if (q->val < pivot) {
    11.             p = p->next;
    12.             // 交换p和q指向的节点的值
    13.             int temp = p->val;
    14.             p->val = q->val;
    15.             q->val = temp;
    16.         }
    17.         q = q->next;
    18.     }
    19.     // 交换head和p指向的节点的值，使得p指向的节点为基准值
    20.     int temp = head->val;
    21.     head->val = p->val;
    22.     p->val = temp;
    23.     // 对左右两部分递归进行快速排序
    24.     quickSort(head, p);
    25.     quickSort(p->next, tail);
    26. }
    堆排
    // 待实现
    查找倒数第K个节点（双指针法）
    1. ListNode* listFindKthToTail(ListNode *node, int k)
    2. {
    3.     // 超过长度直接返回空
    4.     if(node == NULL || k >= listLength(node))return NULL;
    5.  
    6.     ListNode *first = node, *second = node;
    7.     for(int i = 0; i < k; i++){
    8.         first = first->next;
    9.     }
    10.  
    11.     while (first)
    12.     {
    13.         first = first->next;
    14.         second = second->next;
    15.     }
    16.     return second;
    17. }

    完整测试代码

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. // 声明并定义个单链表结构体
    5. typedef struct _ListNode
    6. {
    7.     int val;                //数据 成员变量
    8.     struct _ListNode * next;//结构体调用自己的类型
    9. }ListNode;
    10.  
    11.  
    12. /**
    13.  * 创建链表
    14. */
    15. void listCreate(ListNode *node)
    16. {
    17.     //初始化链表内数据
    18.     node->val = -1;
    19.     node->next = NULL;
    20. }
    21.  
    22. /**
    23.  * 插入数据,头插法
    24. */
    25. void listInsert(ListNode *node, int data)
    26. {
    27.     // 创建一个节点,并申请内存
    28.     ListNode *t_node = (ListNode *)malloc(sizeof(ListNode));
    29.  
    30.     //  节点内容赋值
    31.     t_node->val = data;
    32.  
    33.     //   头插法，新数据在前
    34.     t_node->next = node->next;
    35.     node->next = t_node;
    36. }
    37.  
    38. /**
    39.  * 插入数据,尾插法
    40. */
    41. void listTailInsert(ListNode *node, int data)
    42. {
    43.     // 创建一个节点
    44.     ListNode *t_node = (ListNode*)malloc(sizeof(ListNode));
    45.     
    46.     // 节点内容赋值
    47.     t_node->val = data;
    48.     t_node->next = NULL;
    49.     
    50.     // 声明一个尾节点
    51.     ListNode* t_tail = node;
    52.  
    53.     // 获取最后一个节点
    54.     while(t_tail->next != NULL)
    55.     {
    56.         // 后移
    57.         t_tail = t_tail->next;
    58.     }
    59.     //添加节点
    60.     t_tail->next = t_node;
    61. }
    62.  
    63. /**
    64.  * 查找数据
    65. */
    66. ListNode* listFind(ListNode *node, int data)
    67. {
    68.     //申明一个空节点
    69.     ListNode *t_node = NULL;
    70.     
    71.     //遍历链表
    72.     ListNode *t_temp;
    73.     for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next)
    74.     {
    75.         //如果找到该节点
    76.         if(t_temp->val == data)
    77.         {
    78.             t_node = t_temp;
    79.             //跳出循环
    80.             break;
    81.         }
    82.     }
    83.     return t_node;
    84. }
    85.  
    86. /**
    87.  * 修改数据
    88. */
    89. void listModify(ListNode *node, int oldData, int newData)
    90. {
    91.     // 查找值是否存在
    92.     ListNode *t_node = listFind(node, oldData);
    93.     
    94.     // 判断值是否存在
    95.     if(t_node == NULL)
    96.     {
    97.         printf("该值不存在\n");
    98.         return;
    99.     }
    100.     t_node->val = newData;
    101. }
    102.  
    103. /**
    104.  * 删除数据
    105. */
    106. void listDelete(ListNode *node, int data)
    107. {
    108.     // 查找是否存在改制的数据
    109.     ListNode *t_node = listFind(node, data);
    110.     
    111.     // 如果该值对应的节点不存在
    112.     if(NULL == t_node)
    113.     {
    114.         printf("该值不存在\n");
    115.         return;
    116.     }
    117.  
    118.     // 求出被删节点的前一个节点
    119.     ListNode *t_prev = node;
    120.     
    121.     // 遍历链表
    122.     while(t_prev->next != t_node)
    123.     {
    124.         t_prev = t_prev->next;
    125.     }
    126.  
    127.     // 前一个节点的next指向被删除节点的下一个节点
    128.     t_prev->next = t_node->next;
    129.     // 释放内存
    130.     free(t_node);
    131.     // 指针置空
    132.     t_node = NULL;
    133. }
    134.  
    135. /**
    136.  * 打印数据
    137. */
    138. void listDisplay(ListNode *node)
    139. {
    140.     // 遍历链表
    141.     ListNode *t_temp;
    142.     
    143.     for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next)
    144.     {
    145.         printf("%d ",t_temp->val);
    146.     }
    147.     printf("\n");
    148. }
    149.  
    150. /**
    151.  * 销毁链表
    152. */
    153. void listDestroy(ListNode *node)
    154. {
    155.     // 遍历链表
    156.     ListNode *t_temp = node->next;
    157.     
    158.     while(t_temp != NULL)
    159.     {
    160.         // 先将当前节点保存
    161.         ListNode *t_node = t_temp;
    162.         // 移动到下一各节点
    163.         t_temp = t_temp->next;
    164.         // 释放保存内容的节点
    165.         free(t_node);
    166.     }
    167. }
    168.  
    169.  
    170. /**
    171.  * 翻转链表
    172. */
    173. void listReverse(ListNode *node)
    174. {
    175.     ListNode * head = NULL, *now = NULL, *temp = NULL;
    176.     head = node->next;
    177.     // head是来保存我们翻转以后链表中的头节点的
    178.     now = head->next;
    179.     // now用来保存我们当前待处理的节点
    180.     head->next = NULL;
    181.     // 一定要置为NULL，否则可能导致循环
    182.  
    183.     while(now)
    184.     {
    185.         temp = now->next; // 利用一个临时指针来保存下一个待处理的节点
    186.         
    187.         now->next = head; // 将当前节点插入到逆序节点的第一个节点之前，并更改head指向
    188.         
    189.         head = now;
    190.         node->next = head; // 使链表头指针指向逆序后的第一个节点
    191.         
    192.         now = temp; // 更新链表到下一个待处理的节点
    193.     }
    194. }
    195.  
    196.  
    197. /**
    198.  * 求长度
    199. */
    200. int listLength(ListNode *node)
    201. {
    202.     ListNode *t_temp;
    203.     int t_length = 0;
    204.     for(t_temp = node->next; t_temp != NULL; t_temp = t_temp->next)
    205.     {
    206.         t_length++;
    207.     }
    208.     return t_length;
    209. }
    210.  
    211.  
    212. /**
    213.  * 冒泡排序
    214. */
    215. void listBubbleSort(ListNode *node)
    216. {
    217.     int t_length = listLength(node);
    218.     int i,j;
    219.     ListNode *t_temp;
    220.     for(i = 0; i < t_length; i++)
    221.     {
    222.         t_temp = node->next;
    223.         for(j = 0;j < t_length - i - 1; j++)
    224.         {
    225.             if(t_temp->val > t_temp->next->val)
    226.             {
    227.                 int t_data = t_temp->val;
    228.                 t_temp->val = t_temp->next->val;
    229.                 t_temp->next->val = t_data;
    230.             }
    231.             t_temp = t_temp->next;
    232.         }
    233.     }
    234. }
    235.  
    236. /**
    237.  * 定义快速排序算法
    238. */
    239. void quickSort(struct _ListNode *head, struct _ListNode *tail) {
    240.     // 如果链表为空或只有一个节点，直接返回
    241.     if (head == NULL || head == tail) return;
    242.     // 定义两个指针p和q，用于分割链表
    243.     struct _ListNode *p = head, *q = head->next;
    244.     // 选取第一个节点作为基准值
    245.     int pivot = head->val;
    246.     // 遍历链表，将小于基准值的节点放到p的后面
    247.     while (q != tail->next) {
    248.         if (q->val < pivot) {
    249.             p = p->next;
    250.             // 交换p和q指向的节点的值
    251.             int temp = p->val;
    252.             p->val = q->val;
    253.             q->val = temp;
    254.         }
    255.         q = q->next;
    256.     }
    257.     // 交换head和p指向的节点的值，使得p指向的节点为基准值
    258.     int temp = head->val;
    259.     head->val = p->val;
    260.     p->val = temp;
    261.     // 对左右两部分递归进行快速排序
    262.     quickSort(head, p);
    263.     quickSort(p->next, tail);
    264. }
    265.  
    266. /**
    267.  * 快速排序
    268. */
    269. void listQuickSort(ListNode *node)
    270. {
    271.     ListNode *tail = node->next;
    272.     while (tail->next)
    273.     {
    274.         tail = tail->next;
    275.     }
    276.     quickSort(node, tail);
    277. }
    278.  
    279. /**
    280.  * 堆排序
    281. */
    282. void listHeapSort(ListNode *node)
    283. {
    284.  
    285. }
    286.  
    287. /**
    288.  * 获取链表倒数第k个节点,双指针方法
    289. */
    290. ListNode* listFindKthToTail(ListNode *node, int k)
    291. {
    292.     // 超过长度直接返回空
    293.     if(node == NULL || k >= listLength(node))return NULL;
    294.  
    295.     ListNode *first = node, *second = node;
    296.     for(int i = 0; i < k; i++){
    297.         first = first->next;
    298.     }
    299.  
    300.     while (first)
    301.     {
    302.         first = first->next;
    303.         second = second->next;
    304.     }
    305.     return second;
    306. }
    307.  
    308. /**
    309.  * 测试所有函数是否正确有效
    310. */
    311. int main(int argc, char* argv[])
    312. {
    313.     //创建一个ListNode变量
    314.     ListNode node;
    315.  
    316.     //创建链表
    317.     listCreate(&node);
    318.  
    319.  
    320.     int i = 0;
    321.     for(i = 0;i < 10;i++)
    322.     {
    323. #if 0  
    324.         listInsert(&node,i); // 插入数据头插法
    325. #else
    326.         listTailInsert(&node, i); // 插入数据尾插法
    327. #endif
    328.     }
    329.     listDisplay(&node);
    330.  
    331.     ListNode* nodeFind = listFind(&node, 3);
    332.     if(nodeFind)
    333.         printf("listFind:%d\n", nodeFind->val);  
    334.  
    335.     const int k = 5;
    336.     ListNode* nodeFindK = listFindKthToTail(&node, k);
    337.     if(nodeFindK)
    338.         printf("listFindKthToTail step:%d :%d\n", k, nodeFindK->val);  
    339.     
    340.  
    341.     listModify(&node, 1, 999); //修改节点1为999
    342.     listDisplay(&node);
    343.     
    344.     listDelete(&node, 5); // 删除节点5
    345.     listDisplay(&node);
    346.     
    347.     
    348.     // listBubbleSort(&node); // 冒泡排序
    349.     listQuickSort(&node);    // quick sort
    350.     listDisplay(&node);   // 打印链表数据
    351.     
    352.     listReverse(&node);       // 翻转链表
    353.     
    354.     listDisplay(&node);   // 打印反转后的链表
    355.     listDestroy(&node);   // 销毁链表
    356.     return 0;
    357. }
  • 相关阅读:
    学习STM32第十九天
    LeetCode(力扣)47.全排列 IIPython
    文献学习-14-一种用于高精度微创手术的纤维机器人
    Spring Cloud Gateway 搭建网关
    构建用于签名/加密双证书测试体系的可执行命令
    通过媒体查询来实现 WPF 响应式设计
    背包问题讨论
    使用CycleGAN训练自己的数据集
    DSPE-PEG-FSHB，FSHB-PEG-DSPE，磷脂-聚乙二醇-卵泡刺激素多肽FSHB
    Leetcode 86. Partition List （链表好题）
  • 原文地址：https://blog.csdn.net/CHNIM/article/details/132712711