据结构教程（C语言版）码源

数据结构是计算机科学中的核心概念，它涉及到如何有效地组织和管理数据，以便于高效地进行存储和检索。在本教程中，我们将重点关注链表这一重要数据结构，它在C语言中有着广泛的应用。链表不同于数组，不需预先分配连续的内存空间，而是通过节点间的指针链接来构成序列。 链表主要分为单向链表和双向链表。单向链表每个节点仅有一个指针，指向下一个节点；双向链表则每个节点有两个指针，分别指向前一个和后一个节点。链表的操作主要包括初始化、插入、删除和查找。 **初始化链表** 初始化链表通常涉及创建一个空链表，即没有头节点或所有节点都为空的链表。在C语言中，可以定义一个结构体类型来表示链表节点，其中包含数据域和指针域。然后创建一个头节点，其指针域初始为NULL，表示链表为空。 ```c typedef struct Node { int data; struct Node* next; } ListNode; ListNode* initList() { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); head->next = NULL; return head; } ``` **插入节点** 在链表中插入节点通常分为在头部插入和在尾部插入。在头部插入时，新节点成为新的头节点，原头节点变为新节点的下一个节点。在尾部插入则需要遍历链表找到最后一个节点，将新节点插入其后。 ```c void insertAtHead(ListNode* head, int value) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = value; newNode->next = head; head = newNode; } void insertAtTail(ListNode* head, int value) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = value; newNode->next = NULL; if (head == NULL) { head = newNode; } else { ListNode* temp = head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } } ``` **删除节点** 删除节点操作需要找到要删除的节点，然后更新其前一个节点的指针，指向被删除节点的下一个节点。如果删除的是头节点，需要更新头节点为第二个节点。 ```c void deleteNode(ListNode* head, int value) { if (head == NULL) return; ListNode* temp = head; ListNode* prev = NULL; while (temp != NULL && temp->data != value) { prev = temp; temp = temp->next; } if (temp == NULL) return; // 节点未找到 if (prev == NULL) { // 删除头节点 head = temp->next; } else { prev->next = temp->next; } free(temp); } ``` **按值查找节点** 查找链表中特定值的节点可以通过遍历链表实现。如果找到，返回该节点；否则返回NULL。 ```c ListNode* findNode(ListNode* head, int value) { ListNode* temp = head; while (temp != NULL) { if (temp->data == value) { return temp; } temp = temp->next; } return NULL; } ``` **比较链表** 比较两个链表通常涉及比较它们的长度或者按顺序比较节点值。这里我们可以实现一个简单的函数来判断两个链表是否相等。 ```c int compareLists(ListNode* list1, ListNode* list2) { ListNode* temp1 = list1; ListNode* temp2 = list2; while (temp1 != NULL && temp2 != NULL) { if (temp1->data != temp2->data) { return 0; // 不相等 } temp1 = temp1->next; temp2 = temp2->next; } if (temp1 != NULL || temp2 != NULL) { return 0; // 长度不同，不相等 } return 1; // 相等 } ``` 以上就是关于链表的基本操作，包括初始化、插入、删除、查找以及比较。在C++中，虽然这些操作可以使用STL中的`list`容器简化，但理解底层的C语言实现对于深入掌握数据结构和算法至关重要。通过实践这些操作，你可以更好地理解和运用链表这种数据结构，从而提高程序设计的能力。在李春葆的数据结构教程中，你将能够找到更详尽的讲解和实例，帮助你进一步提升对数据结构的理解。