数据结构-C语言版本（二）链表
数据结构中的链表：概念、操纵与实战第一部分 链表分类及常见形式
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组差别，链表中的元素在内存中不是连续存储的。
1. 单链表
最根本的链表形式，每个节点包含数据和指向下一个节点的指针。
// 单链表节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;
2. 双链表
每个节点包含指向前一个节点和后一个节点的指针，可以双向遍历。
// 双链表节点结构
typedef struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
} DNode;
3. 循环链表
尾节点指向头节点形成环状结构，可以是单向或双向循环。
// 循环单链表示例
Node* createCircularList(int data) {
Node* head = (Node*)malloc(sizeof(Node));
head->data = data;
head->next = head; // 指向自己形成循环
return head;
}
4. 带头节点的链表
有一个不存储实际数据的头节点，简化操纵。
// 带头节点的单链表
Node* createListWithHead() {
Node* head = (Node*)malloc(sizeof(Node));
head->next = NULL;
return head;
}
第二部分 链表常见操纵
1. 创建节点
// 创建单链表节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if(newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
2. 插入节点
// 在单链表头部插入
void insertAtHead(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// 在单链表尾部插入
void insertAtTail(Node** head, int data) {
Node* newNode = createNode(data);
if(*head == NULL) {
*head = newNode;
return;
}
Node* current = *head;
while(current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
// 在双链表特定位置插入
void insertDNodeAfter(DNode* prevNode, int data) {
if(prevNode == NULL) return;
DNode* newNode = (DNode*)malloc(sizeof(DNode));
newNode->data = data;
newNode->next = prevNode->next;
newNode->prev = prevNode;
if(prevNode->next != NULL) {
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
}
3. 删除节点
// 删除单链表中指定值的节点
void deleteNode(Node** head, int key) {
Node *temp = *head, *prev = NULL;
if(temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while(temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if(temp == NULL) return;
prev->next = temp->next;
free(temp);
}
// 删除双链表中的节点
void deleteDNode(DNode** head, DNode* delNode) {
if(*head == NULL || delNode == NULL) return;
if(*head == delNode) *head = delNode->next;
if(delNode->next != NULL) delNode->next->prev = delNode->prev;
if(delNode->prev != NULL) delNode->prev->next = delNode->next;
free(delNode);
}
4. 遍历链表
// 遍历单链表
void printList(Node* head) {
Node* current = head;
while(current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// 反向遍历双链表
void printListReverse(DNode* tail) {
DNode* current = tail;
while(current != NULL) {
printf("%d -> ", current->data);
current = current->prev;
}
printf("NULL\n");
}
5. 查找节点
// 在单链表中查找
Node* search(Node* head, int key) {
Node* current = head;
while(current != NULL) {
if(current->data == key) {
return current;
}
current = current->next;
}
return NULL;
}
6. 反转链表
// 反转单链表
void reverseList(Node** head) {
Node* prev = NULL;
Node* current = *head;
Node* next = NULL;
while(current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}
第三部分 链表编程题例子
1. 检测链表是否有环
int hasCycle(Node *head) {
if(head == NULL || head->next == NULL) return 0;
Node *slow = head, *fast = head->next;
while(slow != fast) {
if(fast == NULL || fast->next == NULL) return 0;
slow = slow->next;
fast = fast->next->next;
}
return 1;
}
2. 合并两个有序链表
Node* mergeTwoLists(Node* l1, Node* l2) {
Node dummy;
Node* tail = &dummy;
dummy.next = NULL;
while(l1 != NULL && l2 != NULL) {
if(l1->data <= l2->data) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = (l1 != NULL) ? l1 : l2;
return dummy.next;
}
3. 删除链表的倒数第N个节点
Node* removeNthFromEnd(Node* head, int n) {
Node dummy;
dummy.next = head;
Node *fast = &dummy, *slow = &dummy;
for(int i = 0; i <= n; i++) {
fast = fast->next;
}
while(fast != NULL) {
fast = fast->next;
slow = slow->next;
}
Node* toDelete = slow->next;
slow->next = slow->next->next;
free(toDelete);
return dummy.next;
}
4. 链表的中央节点
Node* middleNode(Node* head) {
Node *slow = head, *fast = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
5. 回文链表判断
int isPalindrome(Node* head) {
if(head == NULL || head->next == NULL) return 1;
// 找到中间节点
Node *slow = head, *fast = head;
while(fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
// 反转后半部分
Node *prev = NULL, *curr = slow->next, *next;
while(curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
slow->next = prev;
// 比较前后两部分
Node *p1 = head, *p2 = slow->next;
while(p2 != NULL) {
if(p1->data != p2->data) return 0;
p1 = p1->next;
p2 = p2->next;
}
return 1;
}
6. 两个链表的交点
Node *getIntersectionNode(Node *headA, Node *headB) {
if(headA == NULL || headB == NULL) return NULL;
Node *a = headA, *b = headB;
while(a != b) {
a = (a == NULL) ? headB : a->next;
b = (b == NULL) ? headA : b->next;
}
return a;
}
链表是一种非常灵活的数据结构，在内存分配、插入删除操纵等方面比数组更有优势。掌握链表的各种操纵和算法是步伐员的根本功，对于理解更复杂的数据结构如树、图等也有很大帮助。通过不断练习这些题目，可以深入理解链表的特性和应用场景。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]