C语言学习之链表的实现详解

下面我将详细讲解“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;
}

以上就是链表的实现攻略和两个示例的说明，希望对你有所帮助。