数据结构-C语言版本（二）链表

卖不甜枣  论坛元老 | 6 天前 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1623|帖子 1623|积分 4869

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

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

x
数据结构中的链表：概念、操纵与实战

第一部分 链表分类及常见形式

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组差别，链表中的元素在内存中不是连续存储的。
1. 单链表

最根本的链表形式，每个节点包含数据和指向下一个节点的指针。
  1. // 单链表节点结构
  2. typedef struct Node {
  3.     int data;
  4.     struct Node* next;
  5. } Node;
复制代码
2. 双链表

每个节点包含指向前一个节点和后一个节点的指针，可以双向遍历。
  1. // 双链表节点结构
  2. typedef struct DNode {
  3.     int data;
  4.     struct DNode* prev;
  5.     struct DNode* next;
  6. } DNode;
复制代码
3. 循环链表

尾节点指向头节点形成环状结构，可以是单向或双向循环。
  1. // 循环单链表示例
  2. Node* createCircularList(int data) {
  3.     Node* head = (Node*)malloc(sizeof(Node));
  4.     head->data = data;
  5.     head->next = head; // 指向自己形成循环
  6.     return head;
  7. }
复制代码
4. 带头节点的链表

有一个不存储实际数据的头节点，简化操纵。
  1. // 带头节点的单链表
  2. Node* createListWithHead() {
  3.     Node* head = (Node*)malloc(sizeof(Node));
  4.     head->next = NULL;
  5.     return head;
  6. }
复制代码
第二部分 链表常见操纵

1. 创建节点

  1. // 创建单链表节点
  2. Node* createNode(int data) {
  3.     Node* newNode = (Node*)malloc(sizeof(Node));
  4.     if(newNode == NULL) {
  5.         printf("内存分配失败\n");
  6.         exit(1);
  7.     }
  8.     newNode->data = data;
  9.     newNode->next = NULL;
  10.     return newNode;
  11. }
复制代码
2. 插入节点

  1. // 在单链表头部插入
  2. void insertAtHead(Node** head, int data) {
  3.     Node* newNode = createNode(data);
  4.     newNode->next = *head;
  5.     *head = newNode;
  6. }
  8. // 在单链表尾部插入
  9. void insertAtTail(Node** head, int data) {
  10.     Node* newNode = createNode(data);
  11.     if(*head == NULL) {
  12.         *head = newNode;
  13.         return;
  14.     }
  15.    
  16.     Node* current = *head;
  17.     while(current->next != NULL) {
  18.         current = current->next;
  19.     }
  20.     current->next = newNode;
  21. }
  23. // 在双链表特定位置插入
  24. void insertDNodeAfter(DNode* prevNode, int data) {
  25.     if(prevNode == NULL) return;
  26.    
  27.     DNode* newNode = (DNode*)malloc(sizeof(DNode));
  28.     newNode->data = data;
  29.     newNode->next = prevNode->next;
  30.     newNode->prev = prevNode;
  31.    
  32.     if(prevNode->next != NULL) {
  33.         prevNode->next->prev = newNode;
  34.     }
  35.     prevNode->next = newNode;
  36. }
复制代码
3. 删除节点

  1. // 删除单链表中指定值的节点
  2. void deleteNode(Node** head, int key) {
  3.     Node *temp = *head, *prev = NULL;
  4.    
  5.     if(temp != NULL && temp->data == key) {
  6.         *head = temp->next;
  7.         free(temp);
  8.         return;
  9.     }
  10.    
  11.     while(temp != NULL && temp->data != key) {
  12.         prev = temp;
  13.         temp = temp->next;
  14.     }
  15.    
  16.     if(temp == NULL) return;
  17.    
  18.     prev->next = temp->next;
  19.     free(temp);
  20. }
  22. // 删除双链表中的节点
  23. void deleteDNode(DNode** head, DNode* delNode) {
  24.     if(*head == NULL || delNode == NULL) return;
  25.    
  26.     if(*head == delNode) *head = delNode->next;
  27.     if(delNode->next != NULL) delNode->next->prev = delNode->prev;
  28.     if(delNode->prev != NULL) delNode->prev->next = delNode->next;
  29.    
  30.     free(delNode);
  31. }
复制代码
4. 遍历链表

  1. // 遍历单链表
  2. void printList(Node* head) {
  3.     Node* current = head;
  4.     while(current != NULL) {
  5.         printf("%d -> ", current->data);
  6.         current = current->next;
  7.     }
  8.     printf("NULL\n");
  9. }
  11. // 反向遍历双链表
  12. void printListReverse(DNode* tail) {
  13.     DNode* current = tail;
  14.     while(current != NULL) {
  15.         printf("%d -> ", current->data);
  16.         current = current->prev;
  17.     }
  18.     printf("NULL\n");
  19. }
复制代码
5. 查找节点

  1. // 在单链表中查找
  2. Node* search(Node* head, int key) {
  3.     Node* current = head;
  4.     while(current != NULL) {
  5.         if(current->data == key) {
  6.             return current;
  7.         }
  8.         current = current->next;
  9.     }
  10.     return NULL;
  11. }
复制代码
6. 反转链表

  1. // 反转单链表
  2. void reverseList(Node** head) {
  3.     Node* prev = NULL;
  4.     Node* current = *head;
  5.     Node* next = NULL;
  6.    
  7.     while(current != NULL) {
  8.         next = current->next;
  9.         current->next = prev;
  10.         prev = current;
  11.         current = next;
  12.     }
  13.     *head = prev;
  14. }
复制代码
第三部分 链表编程题例子

1. 检测链表是否有环

  1. int hasCycle(Node *head) {
  2.     if(head == NULL || head->next == NULL) return 0;
  3.    
  4.     Node *slow = head, *fast = head->next;
  5.    
  6.     while(slow != fast) {
  7.         if(fast == NULL || fast->next == NULL) return 0;
  8.         slow = slow->next;
  9.         fast = fast->next->next;
  10.     }
  11.     return 1;
  12. }
复制代码
2. 合并两个有序链表

  1. Node* mergeTwoLists(Node* l1, Node* l2) {
  2.     Node dummy;
  3.     Node* tail = &dummy;
  4.     dummy.next = NULL;
  5.    
  6.     while(l1 != NULL && l2 != NULL) {
  7.         if(l1->data <= l2->data) {
  8.             tail->next = l1;
  9.             l1 = l1->next;
  10.         } else {
  11.             tail->next = l2;
  12.             l2 = l2->next;
  13.         }
  14.         tail = tail->next;
  15.     }
  16.    
  17.     tail->next = (l1 != NULL) ? l1 : l2;
  18.     return dummy.next;
  19. }
复制代码
3. 删除链表的倒数第N个节点

  1. Node* removeNthFromEnd(Node* head, int n) {
  2.     Node dummy;
  3.     dummy.next = head;
  4.     Node *fast = &dummy, *slow = &dummy;
  5.    
  6.     for(int i = 0; i <= n; i++) {
  7.         fast = fast->next;
  8.     }
  9.    
  10.     while(fast != NULL) {
  11.         fast = fast->next;
  12.         slow = slow->next;
  13.     }
  14.    
  15.     Node* toDelete = slow->next;
  16.     slow->next = slow->next->next;
  17.     free(toDelete);
  18.    
  19.     return dummy.next;
  20. }
复制代码
4. 链表的中央节点

  1. Node* middleNode(Node* head) {
  2.     Node *slow = head, *fast = head;
  3.     while(fast != NULL && fast->next != NULL) {
  4.         slow = slow->next;
  5.         fast = fast->next->next;
  6.     }
  7.     return slow;
  8. }
复制代码
5. 回文链表判断

  1. int isPalindrome(Node* head) {
  2.     if(head == NULL || head->next == NULL) return 1;
  3.    
  4.     // 找到中间节点
  5.     Node *slow = head, *fast = head;
  6.     while(fast->next != NULL && fast->next->next != NULL) {
  7.         slow = slow->next;
  8.         fast = fast->next->next;
  9.     }
  10.    
  11.     // 反转后半部分
  12.     Node *prev = NULL, *curr = slow->next, *next;
  13.     while(curr != NULL) {
  14.         next = curr->next;
  15.         curr->next = prev;
  16.         prev = curr;
  17.         curr = next;
  18.     }
  19.     slow->next = prev;
  20.    
  21.     // 比较前后两部分
  22.     Node *p1 = head, *p2 = slow->next;
  23.     while(p2 != NULL) {
  24.         if(p1->data != p2->data) return 0;
  25.         p1 = p1->next;
  26.         p2 = p2->next;
  27.     }
  28.    
  29.     return 1;
  30. }
复制代码
6. 两个链表的交点

  1. Node *getIntersectionNode(Node *headA, Node *headB) {
  2.     if(headA == NULL || headB == NULL) return NULL;
  3.    
  4.     Node *a = headA, *b = headB;
  5.     while(a != b) {
  6.         a = (a == NULL) ? headB : a->next;
  7.         b = (b == NULL) ? headA : b->next;
  8.     }
  9.     return a;
  10. }
复制代码
链表是一种非常灵活的数据结构，在内存分配、插入删除操纵等方面比数组更有优势。掌握链表的各种操纵和算法是步伐员的根本功，对于理解更复杂的数据结构如树、图等也有很大帮助。通过不断练习这些题目，可以深入理解链表的特性和应用场景。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

卖不甜枣

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表