C 具有抽象数据类型的双链表

AI

双链表是一种常见的数据结构，它具有抽象数据类型的特点。在双链表中，每个节点都包含两个指针，分别指向前一个节点和后一个节点。这种结构使得在双链表中可以方便地在任意位置插入和删除节点，而不需要像单链表那样需要遍历整个链表。

双链表的结构

双链表由多个节点组成，每个节点包含三个部分：数据部分和两个指针部分。数据部分存储节点的数据，而两个指针部分分别指向前一个节点和后一个节点。

下面是一个双链表的示例代码：

c
#include <stdio.h>
#include <stdlib.h>
// 定义双链表的节点结构
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;
// 在双链表的指定位置插入节点
void insert(Node<strong> head, int data, int position) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    // 处理插入位置为头节点的情况
    if (position == 0) {
        newNode->prev = NULL;
        newNode->next = *head;
        if (*head != NULL) {
            (*head)->prev = newNode;
        }
        *head = newNode;
        return;
    }
    // 寻找插入位置的节点
    Node* current = *head;
    int i = 0;
    while (i < position - 1 && current != NULL) {</p>        current = current->next;
        i++;
    }
    // 处理插入位置超过链表长度的情况
    if (current == NULL) {
        printf("插入位置超过链表长度！\n");
        return;
    }
    // 插入新节点
    newNode->prev = current;
    newNode->next = current->next;
    if (current->next != NULL) {
        current->next->prev = newNode;
    }
    current->next = newNode;
}
// 删除双链表中指定位置的节点
void delete(Node</strong> head, int position) {
    // 处理链表为空的情况
    if (*head == NULL) {
        printf("链表为空！\n");
        return;
    }
    // 处理删除位置为头节点的情况
    if (position == 0) {
        Node* temp = *head;
        *head = (*head)->next;
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
        free(temp);
        return;
    }
    // 寻找删除位置的节点
    Node* current = *head;
    int i = 0;
    while (i < position && current != NULL) {</p>        current = current->next;
        i++;
    }
    // 处理删除位置超过链表长度的情况
    if (current == NULL) {
        printf("删除位置超过链表长度！\n");
        return;
    }
    // 删除节点
    current->prev->next = current->next;
    if (current->next != NULL) {
        current->next->prev = current->prev;
    }
    free(current);
}
// 打印双链表中的所有节点
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
int mAIn() {
    Node* head = NULL;
    // 向双链表中插入节点
    insert(&head, 1, 0);
    insert(&head, 2, 1);
    insert(&head, 3, 2);
    // 打印双链表中的所有节点
    printList(head);
    // 删除双链表中的节点
    delete(&head, 1);
    // 打印删除节点后的双链表
    printList(head);
    return 0;
}

双链表的应用

双链表在实际应用中有很多用途。它可以用来实现更复杂的数据结构，比如栈、队列和图等。双链表也可以用于实现各种算法，例如反转链表、合并链表等。

下面是一个使用双链表实现栈的例子：

c
#include <stdio.h>
#include <stdlib.h>
// 定义双链表的节点结构
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;
// 初始化栈
void initStack(Node<strong> head) {
    *head = NULL;
}
// 判断栈是否为空
int isEmpty(Node* head) {
    return head == NULL;
}
// 入栈
void push(Node</strong> head, int data) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    // 插入新节点
    newNode->prev = NULL;
    newNode->next = *head;
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}
// 出栈
int pop(Node** head) {
    // 处理栈为空的情况
    if (*head == NULL) {
        printf("栈为空！\n");
        return -1;
    }
    // 删除栈顶节点
    Node* temp = *head;
    int data = temp->data;
    *head = (*head)->next;
    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    free(temp);
    return data;
}
// 打印栈中的所有元素
void printStack(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
int mAIn() {
    Node* head = NULL;
    // 初始化栈
    initStack(&head);
    // 入栈
    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    // 打印栈中的所有元素
    printStack(head);
    // 出栈
    int data = pop(&head);
    printf("出栈元素：%d\n", data);
    // 打印出栈后的栈
    printStack(head);
    return 0;
}

双链表是一种常见的数据结构，它具有抽象数据类型的特点。通过使用指针，双链表可以在任意位置插入和删除节点，从而灵活地操作数据。双链表可以应用于各种问题和算法中，是程序设计中重要的工具之一。