C语言实现数据结构和双向链表操作

下面是详细讲解 "C语言实现数据结构和双向链表操作" 的完整攻略。

什么是数据结构？

数据结构是计算机中存储、组织和管理数据的方式。数据结构可以分为线性结构和非线性结构两种。其中，线性结构包括数组、链表、栈、队列等，非线性结构包括树、图等。

什么是链表？

链表是一种动态的数据结构，它由许多个结点组成。每个结点包含两个部分：数据域和指针域。数据域存储数据，指针域则存储指向下一个结点（单向链表）或上一个结点（双向链表）的指针。其中，第一个结点称为头结点，最后一个结点称为尾结点。

双向链表的实现

以下是双向链表的结构体实现：

typedef struct Node{
    int data;
    struct Node *prev;  // 指向前一个结点的指针
    struct Node *next;  // 指向下一个结点的指针
}Node, *LinkList;

其中，prev指向前驱结点，next指向后继结点。

以下是创建双向链表的函数：

/**
 * 创建双向链表
 */
LinkList create(){
    Node *head = (Node*) malloc(sizeof(Node));  // 创建头结点
    head->prev = NULL;
    head->next = NULL;

    Node *tail = head;  // 记录尾结点位置

    int n;
    printf("请输入双向链表的长度:\n");
    scanf("%d",&n);  // 输入结点个数

    for (int i = 0; i < n; i++){
        Node *node = (Node*) malloc(sizeof(Node));  // 创建一个新结点
        printf("请输入第%d个结点的数据:\n",i+1);
        scanf("%d",&node->data);  // 输入结点数据

        node->prev = tail;  // 设置前驱指针
        node->next = NULL;  // 设置后继指针
        tail->next = node;  // 将新结点插到尾部
        tail = node;  // 更新尾结点位置
    }
    return head;
}

该函数会先创建一个头结点，然后根据输入的结点个数，依次创建新的结点。在创建新结点时，我们需要将该结点的前驱指针指向链表的尾结点，将尾结点的后继指针指向该结点，最后更新尾结点位置。

以下是双向链表的遍历函数：

/**
 * 遍历双向链表
 */
void traverse(LinkList L){
    Node *p = L->next;  // 从头结点的后继结点开始遍历
    while (p != NULL){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

遍历时，我们从头结点的后继结点开始遍历，直到遍历到尾结点为止。

以下是双向链表的插入函数：

/**
 * 双向链表中插入新结点
 */
void insert(LinkList L,int pos,int data){
    Node *node = (Node*) malloc(sizeof(Node));  // 创建新结点
    node->data = data;

    Node *p = L->next;
    int i = 1;
    while (p != NULL && i < pos){
        p = p->next;
        i++;
    }
    if (p == NULL){
        printf("插入的位置非法！\n");
        return;
    }
    node->prev = p->prev;  // 插入新结点
    node->next = p;
    p->prev->next = node;
    p->prev = node;
}

插入时，我们需要定位到插入位置上一个结点的位置，然后将插入结点的前驱指针指向该结点的前驱结点，将插入结点的后继指针指向该结点，将该结点的前驱结点的后继指针指向插入结点，将该结点的前驱指针指向插入结点。

以下是双向链表的删除函数：

/**
 * 双向链表中删除指定结点
 */
void remove_node(LinkList L,int pos){
    Node *p = L->next;
    int i = 1;
    while (p != NULL && i < pos){
        p = p->next;
        i++;
    }
    if (p == NULL){
        printf("删除的位置非法！\n");
        return;
    }
    p->prev->next = p->next;
    if (p->next != NULL){
        p->next->prev = p->prev;
    }
    free(p);
}

删除时，我们同样需要定位到删除结点的位置，然后将删除结点的前驱结点的后继指针指向删除结点的后继结点，将删除结点的后继结点的前驱指针指向删除结点的前驱结点，最后释放删除结点占用的内存空间。

示例1

假设我们要创建一个包含10个结点的双向链表，并对该双向链表进行遍历、插入和删除操作，具体代码如下：

#include <stdio.h>
#include <stdlib.h>

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

/**
 * 创建双向链表
 */
LinkList create(){
    Node *head = (Node*) malloc(sizeof(Node));  // 创建头结点
    head->prev = NULL;
    head->next = NULL;

    Node *tail = head;  // 记录尾结点位置

    int n;
    printf("请输入双向链表的长度:\n");
    scanf("%d",&n);

    for (int i = 0; i < n; i++){
        Node *node = (Node*) malloc(sizeof(Node));  // 创建一个新结点
        printf("请输入第%d个结点的数据:\n",i+1);
        scanf("%d",&node->data);

        node->prev = tail;  // 设置前驱指针
        node->next = NULL;  // 设置后继指针
        tail->next = node;  // 将新结点插到尾部
        tail = node;  // 更新尾结点位置
    }
    return head;
}

/**
 * 遍历双向链表
 */
void traverse(LinkList L){
    Node *p = L->next;
    while (p != NULL){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * 双向链表中插入新结点
 */
void insert(LinkList L,int pos,int data){
    Node *node = (Node*) malloc(sizeof(Node));  // 创建新结点
    node->data = data;

    Node *p = L->next;
    int i = 1;
    while (p != NULL && i < pos){
        p = p->next;
        i++;
    }
    if (p == NULL){
        printf("插入的位置非法！\n");
        return;
    }
    node->prev = p->prev;  // 插入新结点
    node->next = p;
    p->prev->next = node;
    p->prev = node;
}

/**
 * 双向链表中删除指定结点
 */
void remove_node(LinkList L,int pos){
    Node *p = L->next;
    int i = 1;
    while (p != NULL && i < pos){
        p = p->next;
        i++;
    }
    if (p == NULL){
        printf("删除的位置非法！\n");
        return;
    }
    p->prev->next = p->next;
    if (p->next != NULL){
        p->next->prev = p->prev;
    }
    free(p);
}

int main(){
    LinkList L = create();  // 创建双向链表
    traverse(L);  // 遍历双向链表
    insert(L, 3, 99);  // 向双向链表中插入新结点
    traverse(L);  // 遍历插入新结点后的双向链表
    remove_node(L, 5);  // 从双向链表中删除指定结点
    traverse(L);  // 遍历删除指定结点后的双向链表
    return 0;
}

以上代码会首先让用户输入该双向链表的长度，然后依次输入每个结点的数据。创建完成后，打印该双向链表的所有结点。接着，向该链表的第3个位置插入一个新结点（data=99），再打印插入结点后的所有结点。最后，从该链表的第5个位置删除一个结点，并打印删除结点后的所有结点。

示例2

假设我们已经有一个双向链表，其中包含了若干结点，我们想要从该链表中查找某个特定数据的结点并打印出该结点的位置，如果没有找到则打印未找到的提示信息。这个问题可以通过以下代码实现：

#include <stdio.h>
#include <stdlib.h>

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

/**
 * 遍历双向链表
 */
void traverse(LinkList L){
    Node *p = L->next;
    while (p != NULL){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * 查找双向链表中特定数据的结点
 */
void find(LinkList L,int data){
    Node *p = L->next;
    int pos = 1;
    while (p != NULL && p->data != data){
        p = p->next;
        pos++;
    }
    if (p == NULL){
        printf("未找到数据为%d的结点！\n",data);
    }
    else{
        printf("数据为%d的结点在链表中的位置是%d。\n",data,pos);
    }
}

int main(){
    LinkList L = (LinkList) malloc(sizeof(Node));  // 创建头结点
    L->prev = NULL;
    L->next = NULL;

    Node *tail = L;  // 记录尾结点位置

    for (int i = 1; i <= 5; i++){
        Node *node = (Node*) malloc(sizeof(Node));  // 创建一个新结点
        node->data = i;

        node->prev = tail;  // 设置前驱指针
        node->next = NULL;  // 设置后继指针
        tail->next = node;  // 将新结点插到尾部
        tail = node;  // 更新尾结点位置
    }
    traverse(L);  // 遍历双向链表
    find(L, 3);  // 查找数据为3的结点
    find(L, 7);  // 查找数据为7的结点
    return 0;
}

以上代码会首先创建一个双向链表，并打印该链表中的所有结点。然后，查找该链表中数据为3和7的结点（其中只有数据为3的结点能被找到）。如果找到了，则打印结点的位置；如果没找到，则打印未找到的提示信息。

总而言之，在使用C语言来实现数据结构和双向链表操作的过程中，我们需要清楚每个方法的实现原理，同时遵守良好的编程规范，例如使用函数、结构体等方式将代码模块化，并进行模块间的相互调用。