下面我将详细讲解“C语言学习之链表的实现详解”的完整攻略。
1. 链表的定义
链表是一种数据结构，它由一系列节点组成。每个节点由一个数据部分和一个指向下一个节点的地址部分组成。链表可以有多种形式，例如单向链表、双向链表、循环链表等。
2. 链表的实现
2.1. 单向链表
单向链表是最简单的链表形式，一个节点只包含一个指向下一个节点的指针。在C语言中，我们可以使用结构体来表示一个节点，如下所示：
struct Node{
int data;
struct Node* next;
};
链表的头指针指向第一个节点的地址，如果为空链表则指向 NULL。可以定义如下：
struct Node* head = NULL;
可以通过遍历链表找到某个节点，如下所示：
struct Node* p = head;
while(p != NULL && p->data != target){
p = p->next;
}
其它操作，例如插入节点、删除节点等，也比较容易实现。
2.2. 双向链表
双向链表是一种带有前向指针和后向指针的链表结构。每个节点都有一个指向前驱节点的指针和一个指向后继节点的指针。定义如下：
struct DNode{
int data;
struct DNode* prev;
struct DNode* next;
};
可以通过前向、后向指针轻松在双向链表上进行遍历和操作。
2.3. 循环链表
循环链表是一种特殊的链表，最后一个节点的后继指针指向第一个节点。定义与单向链表和双向链表类似，只是需要注意循环链接的实现。
3. 示例说明
下面我们看两个示例，分别是单向链表和双向链表的实现。
3.1. 单向链表示例
#include <stdio.h>
#include <stdlib.h>
/*定义节点类型*/
struct Node{
int data;
struct Node* next;
};
/*头插法插入节点*/
void insertAtHead(struct Node** headRef, int data){
/*创建节点*/
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
/*将新节点插入链表头部*/
new_node->next = (*headRef);
(*headRef) = new_node;
}
/*尾插法插入节点*/
void insertAtTail(struct Node** headRef, int data){
/*创建节点*/
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
if((*headRef) == NULL){
(*headRef) = new_node;
return;
}
struct Node* p = (*headRef);
while(p->next != NULL){
p = p->next;
}
p->next = new_node;
}
/*删除节点*/
void deleteNode(struct Node** headRef, int target){
/*如果要删除的节点是头节点*/
if((*headRef) != NULL && (*headRef)->data == target){
(*headRef) = (*headRef)->next;
return;
}
struct Node* p = (*headRef);
struct Node* prev = NULL;
while(p != NULL && p->data != target){
prev = p;
p = p->next;
}
/*如果找到目标节点*/
if(p != NULL){
prev->next = p->next;
free(p);
}
}
/*打印链表*/
void printList(struct Node* head){
struct Node* p = head;
while(p != NULL){
printf("%d ", p->data);
p = p->next;
}
}
int main(){
struct Node* head = NULL;
insertAtHead(&head, 2);
insertAtHead(&head, 1);
insertAtTail(&head, 3);
insertAtTail(&head, 4);
printList(head);
deleteNode(&head, 3);
deleteNode(&head, 1);
printList(head);
return 0;
}
3.2. 双向链表示例
#include <stdio.h>
#include <stdlib.h>
/*定义节点类型*/
struct DNode{
int data;
struct DNode* prev;
struct DNode* next;
};
/*头插法插入节点*/
void insertAtHead(struct DNode** headRef, int data){
/*创建节点*/
struct DNode* new_node = (struct DNode*)malloc(sizeof(struct DNode));
new_node->data = data;
/*插入链表头*/
new_node->prev = NULL;
new_node->next = (*headRef);
if((*headRef) != NULL){
(*headRef)->prev = new_node;
}
(*headRef) = new_node;
}
/*尾插法插入节点*/
void insertAtTail(struct DNode** headRef, int data){
/*创建节点*/
struct DNode* new_node = (struct DNode*)malloc(sizeof(struct DNode));
new_node->data = data;
new_node->next = NULL;
if((*headRef) == NULL){
new_node->prev = NULL;
(*headRef) = new_node;
return;
}
struct DNode* p = (*headRef);
while(p->next != NULL){
p = p->next;
}
new_node->prev = p;
p->next = new_node;
}
/*删除节点*/
void deleteNode(struct DNode** headRef, int target){
struct DNode* p = (*headRef);
while(p != NULL && p->data != target){
p = p->next;
}
/*如果要删除的节点是头节点*/
if(p != NULL && p == (*headRef)){
(*headRef) = p->next;
if((*headRef) != NULL){
(*headRef)->prev = NULL;
}
free(p);
return;
}
/*如果找到目标节点*/
if(p != NULL){
p->prev->next = p->next;
if(p->next != NULL){
p->next->prev = p->prev;
}
free(p);
}
}
/*打印链表（正序）*/
void printList(struct DNode* head){
struct DNode* p = head;
while(p != NULL){
printf("%d ", p->data);
p = p->next;
}
}
/*打印链表（反序）*/
void printListReverse(struct DNode* head){
struct DNode* p = head;
while(p != NULL && p->next != NULL){
p = p->next;
}
while(p != NULL){
printf("%d ", p->data);
p = p->prev;
}
}
int main(){
struct DNode* head = NULL;
insertAtHead(&head, 2);
insertAtHead(&head, 1);
insertAtTail(&head, 3);
insertAtTail(&head, 4);
printList(head);
printf("\n");
printListReverse(head);
deleteNode(&head, 3);
deleteNode(&head, 1);
printf("\n");
printList(head);
return 0;
}
以上就是链表的实现攻略和两个示例的说明，希望对你有所帮助。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言学习之链表的实现详解 - Python技术站
微信扫一扫 
支付宝扫一扫 