简单介绍线性表以及如何实现双链表

1. 线性表的简介：

线性表是一类数据结构，其特点是数据元素之间存在一种线性关系。换句话说，线性表可以看作是一组有顺序的数据元素的集合，其中每个元素最多只有一个前驱和一个后继。（注：链表也是线性表的一种）

线性表的常见实现方式有数组和链表两种。

1. 双向链表的实现：

双向链表是一种常见的链式存储结构，每个节点除了存储数据之外，还包括指向前驱和后继节点的指针。在操作链表时，我们可以通过这些指针实现对链表中任意节点的访问、插入和删除等操作。

下面是一个如何实现双向链表的代码示例：

typedef struct Node{
    int data;  
    struct Node *prev;  //指向前驱节点的指针
    struct Node *next;  //指向后继节点的指针
}Node;

Node* CreateDblList(int arr[], int n){  //创建双向链表
    Node *head, *tail, *p;
    head = (Node*)malloc(sizeof(Node));
    tail = head;
    for(int i=0; i<n; i++){
       p = (Node*)malloc(sizeof(Node));
       p->data=arr[i];
       p->prev=tail;
       p->next=NULL;
       tail->next=p;
       tail=p;
    }
    head->prev=NULL;
    return head;
}

void ShowDblList(Node *p){  //打印双向链表
    while(p->next!=NULL){
        p=p->next;
        printf("%d ", p->data);
    }
    printf("\n");
}

void InsertDblList(Node *p, int i, int x){  //在双向链表中插入节点
    Node *q=p;
    for(int j=0; j<i-1; j++) q=q->next;
    Node *t=(Node*)malloc(sizeof(Node));
    t->data=x;
    t->prev=q;
    t->next=q->next;
    if(q->next) q->next->prev=t;
    q->next=t;
}

void DeleteDblList(Node *p, int i){  //删除双向链表中的指定节点
    Node *q=p;
    for(int j=0; j<i-1; j++) q=q->next;
    q->prev->next=q->next;
    if(q->next) q->next->prev=q->prev;
    free(q);
}

接下来对上述代码做简单说明：

• 结构体 Node 表示双向链表的每个节点，包含数据域 data，以及指向前驱节点和后继节点的指针 prev 和 next。
• 函数 CreateDblList 表示创建一个双向链表，传入参数为数组 arr 和数组长度 n，返回值为双向链表的头结点指针。
• 函数 ShowDblList 表示打印双向链表，传入参数为头结点指针。
• 函数 InsertDblList 表示在双向链表中插入指定节点，传入参数为头结点指针、插入位置 i 和插入值 x。
• 函数 DeleteDblList 表示删除双向链表中的指定节点，传入参数为头结点指针和待删除节点位置 i。

下面是一个基于上述代码的示例：

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

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

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

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

void InsertDblList(Node *p, int i, int x){
    Node *q=p;
    for(int j=0; j<i-1; j++) q=q->next;
    Node *t=(Node*)malloc(sizeof(Node));
    t->data=x;
    t->prev=q;
    t->next=q->next;
    if(q->next) q->next->prev=t;
    q->next=t;
}

void DeleteDblList(Node *p, int i){
    Node *q=p;
    for(int j=0; j<i-1; j++) q=q->next;
    q->prev->next=q->next;
    if(q->next) q->next->prev=q->prev;
    free(q);
}

int main(){
    int a[5] = {1, 2, 3, 4, 5};
    Node *L = CreateDblList(a, 5);

    printf("Original doubly linked list:\n");
    ShowDblList(L);

    printf("Insert value '6' into index '2':\n");
    InsertDblList(L, 2, 6);
    ShowDblList(L);

    printf("Delete value in index '4':\n");
    DeleteDblList(L, 4);
    ShowDblList(L);

    return 0;
}

以上代码示例中，我们通过 CreateDblList 函数创建了一个原始的双向链表，包含五个节点，值分别为 1,2,3,4,5；然后通过 InsertDblList 函数，我们在索引为 2 的位置插入了一个值为 6 的新节点；最后，我们通过 DeleteDblList 函数，将索引为 4 的节点删除。可以看到，通过双向链表的相关操作，我们可以实现动态的节点插入和删除，从而满足各种实际应用场景的需求。