[教程]掌握C语言，谭浩强教你轻松玩转链表精髓

引言链表是数据结构中的一个重要组成部分，尤其在C语言编程中，它提供了动态内存分配和灵活的数据组织方式。谭浩强老师的《C程序设计》中详细介绍了链表的相关知识，本文将基于谭浩强老师的讲解，结合实际代码示例...

引言

链表是数据结构中的一个重要组成部分，尤其在C语言编程中，它提供了动态内存分配和灵活的数据组织方式。谭浩强老师的《C程序设计》中详细介绍了链表的相关知识，本文将基于谭浩强老师的讲解，结合实际代码示例，帮助读者轻松掌握链表精髓。

链表的基本概念

链表的定义

链表是一种线性表，它由一系列结点（Node）组成，每个结点包含数据和指向下一个结点的指针。链表分为单向链表、双向链表和循环链表等。

链表的特点

• 动态内存分配：链表不需要连续的内存空间，可以动态地增加或减少元素。
• 插入和删除操作效率高：不需要移动其他元素，只需改变指针即可。
• 空间利用率高：不会因为预分配内存而浪费空间。

单向链表

结点结构

typedef struct Node { int data; struct Node* next;
} Node;

创建单向链表

Node* createList(int* arr, int n) { Node* head = NULL; Node* tail = NULL; for (int i = 0; i < n; i++) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; if (head == NULL) { head = newNode; tail = newNode; } else { tail->next = newNode; tail = newNode; } } return head;
}

遍历单向链表

void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n");
}

查找单向链表中的元素

Node* findNode(Node* head, int key) { Node* current = head; while (current != NULL && current->data != key) { current = current->next; } return current;
}

双向链表

结点结构

typedef struct Node { int data; struct Node* next; struct Node* prev;
} Node;

创建双向链表

Node* createDoublyList(int* arr, int n) { Node* head = NULL; Node* tail = NULL; for (int i = 0; i < n; i++) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; newNode->prev = NULL; if (head == NULL) { head = newNode; tail = newNode; } else { tail->next = newNode; newNode->prev = tail; tail = newNode; } } return head;
}

遍历双向链表

void printDoublyList(Node* head) { Node* current = head; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n");
}

反向遍历双向链表

void printReverseDoublyList(Node* head) { Node* current = head; while (current->next != NULL) { current = current->next; } while (current != NULL) { printf("%d ", current->data); current = current->prev; } printf("\n");
}

循环链表

结点结构

typedef struct Node { int data; struct Node* next;
} Node;

创建循环链表

Node* createCircularList(int* arr, int n) { Node* head = NULL; Node* tail = NULL; for (int i = 0; i < n; i++) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; if (head == NULL) { head = newNode; } else { tail->next = newNode; } tail = newNode; } tail->next = head; // 形成循环 return head;
}

遍历循环链表

void printCircularList(Node* head) { Node* current = head; do { printf("%d ", current->data); current = current->next; } while (current != head); printf("\n");
}

总结

通过以上对单向链表、双向链表和循环链表的介绍，结合谭浩强老师的讲解和实际代码示例，相信读者已经对链表有了深入的理解。在实际编程中，链表的应用非常广泛，熟练掌握链表的相关知识将有助于提高编程技能。