4.双向链表

第一章 自测&关键词回顾

第二章 手撕

只实现了带头的双向链表 【不带头的和单链表不带头一样】

• doubleLinkList.h
• doubleLinkList.c
• test.c

// 带头节点
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct DoubleLinkListNode {
    DataType data;
    struct DoubleLinkListNode *prev;
    struct DoubleLinkListNode *next;
} DListNode;

// 初始化
DListNode *initDoubleLinkList(void);
// 销毁
void destoryDoubleLinkList(DListNode *dlist);
// 遍历
void traverseDoubleLinkeList(DListNode* dlist);
// 指定位置插入
void insert(DListNode* dlist, DataType data, int posIndex);
// 指定位置删除
void earse(DListNode* dlist, int posIndex);

#include "doubleLinkList.h"

// 初始化
DListNode *initDoubleLinkList(void) {
    // 创建头节点
    DListNode *phead = (DListNode *)malloc(sizeof(DListNode));
    phead->data = 0;  // 头节点的值域维护链表长度
    phead->prev = NULL;

    DListNode *pmove = phead;

    DataType input;
    while (scanf("%d", &input) == 1 && input != -1) {
        DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
        newNode->data = input;
        // 相互指
        newNode->prev = pmove;
        pmove->next = newNode;
        // 移动到新创建的节点
        pmove = pmove->next;
        phead->data++;
    }
    pmove->next = NULL;  // 最后一个置空
    return phead;
}
// 销毁
void destoryDoubleLinkList(DListNode *dlist) {
    DListNode *temp = dlist;
    while (dlist) {
        temp = dlist;
        dlist = dlist->next;
        free(temp);
    }
}
// 遍历
void traverseDoubleLinkeList(DListNode *dlist) {
    // 正向遍历
    int flag = 1;
    DListNode *pmove = dlist->next;
    DListNode *backward = NULL;
    while (pmove) {
        if (flag) printf("%d->", pmove->data);
        if (pmove->next == NULL) backward = pmove;  // 记录下反向指针
        pmove = pmove->next;
    }
    //  反向遍历 (为了确定, 链表生成没有问题)
    while (backward && backward->prev) {
        if (!flag) printf("%d->", backward->data);
        backward = backward->prev;
    }

    printf("NULL Length:%d\n", dlist->data);
}
// 指定位置插入
void insert(DListNode *dlist, DataType data, int posIndex) {
    assert(!(posIndex < 0 || posIndex > dlist->data) && "insert posIndex is illegal");
    DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
    newNode->data = data;

    DListNode *pmove = dlist;  // 临时变量

    while (posIndex-- > 0) pmove = pmove->next;
    if (pmove->next != NULL) pmove->next->prev = newNode;
    newNode->next = pmove->next;
    pmove->next = newNode;
    newNode->prev = pmove;
    dlist->data++;
}
// 指定位置删除
void earse(DListNode *dlist, int posIndex) {
    assert(!(posIndex < 0 || posIndex >= dlist->data) && "earse posIndex is illegal");
    DListNode *pmove = dlist;

    while (posIndex-- > 0) pmove = pmove->next;
    DListNode *temp = pmove->next;  // 存储中间节点,得会释放
    pmove->next = pmove->next->next;
    if (pmove->next != NULL) pmove->next->prev = pmove;
    free(temp);
    dlist->data--;
}

#include "doubleLinkList.h"
#include <stdbool.h>
#include <string.h>
#include <time.h>

// 辅助函数：创建指定数组内容的链表
DListNode *createTestList(int *arr, int size) {
    DListNode *head = (DListNode *)malloc(sizeof(DListNode));
    head->data = 0;
    head->prev = NULL;
    head->next = NULL;

    DListNode *pmove = head;
    for (int i = 0; i < size; i++) {
        DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
        newNode->data = arr[i];
        newNode->prev = pmove;
        newNode->next = NULL;
        pmove->next = newNode;
        pmove = newNode;
        head->data++;
    }

    return head;
}

// 辅助函数：验证链表的双向性
bool verifyDoubleLinkList(DListNode *list) {
    if (!list) return false;

    // 正向遍历检查prev指针
    DListNode *pmove = list->next;
    while (pmove) {
        if (pmove->prev->next != pmove) return false;
        pmove = pmove->next;
    }

    // 反向遍历检查next指针
    pmove = list;
    while (pmove->next) pmove = pmove->next;
    while (pmove != list) {
        if (pmove->prev->next != pmove) return false;
        pmove = pmove->prev;
    }

    return true;
}

// 测试初始化功能
bool testInit() {
    printf("测试初始化功能:\n");
    bool allPassed = true;

    // 测试空链表
    printf("  测试创建空链表: ");
    DListNode *list = createTestList(NULL, 0);
    bool result = (list->data == 0 && list->next == NULL);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destoryDoubleLinkList(list);

    // 测试单节点链表
    printf("  测试创建单节点链表: ");
    int arr[] = {1};
    list = createTestList(arr, 1);
    result = (list->data == 1 && verifyDoubleLinkList(list));
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destoryDoubleLinkList(list);

    return allPassed;
}

// 测试插入功能
bool testInsert() {
    printf("测试插入功能:\n");
    bool allPassed = true;

    // 创建测试链表
    int arr[] = {1, 2, 3};
    DListNode *list = createTestList(arr, 3);

    // 测试头部插入
    printf("  测试头部插入: ");
    insert(list, 0, 0);
    bool result = (list->next->data == 0 && verifyDoubleLinkList(list));
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;

    // 测试尾部插入
    printf("  测试尾部插入: ");
    insert(list, 4, list->data);
    result = (list->data == 5 && verifyDoubleLinkList(list));
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;

    destoryDoubleLinkList(list);
    return allPassed;
}

// 测试删除功能
bool testErase() {
    printf("测试删除功能:\n");
    bool allPassed = true;

    // 创建测试链表
    int arr[] = {1, 2, 3, 4};
    DListNode *list = createTestList(arr, 4);

    // 测试头部删除
    printf("  测试头部删除: ");
    earse(list, 0);
    bool result = (list->next->data == 2 && verifyDoubleLinkList(list));
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;

    // 测试尾部删除
    printf("  测试尾部删除: ");
    earse(list, list->data - 1);
    result = (list->data == 2 && verifyDoubleLinkList(list));
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;

    destoryDoubleLinkList(list);
    return allPassed;
}

// 运行所有测试
void runAllTests() {
    printf("============== 双向链表测试 ==============\n");

    bool initTestPassed = testInit();
    bool insertTestPassed = testInsert();
    bool eraseTestPassed = testErase();

    printf("\n============== 测试结果汇总 ==============\n");
    printf("初始化测试: %s\n", initTestPassed ? "通过" : "失败");
    printf("插入操作测试: %s\n", insertTestPassed ? "通过" : "失败");
    printf("删除操作测试: %s\n", eraseTestPassed ? "通过" : "失败");
    printf("总体结果: %s\n",
           (initTestPassed && insertTestPassed && eraseTestPassed) ? "全部通过" : "存在失败");
}

void test01() {
    DListNode *dlist = initDoubleLinkList();
    traverseDoubleLinkeList(dlist);

    earse(dlist, -7);
    traverseDoubleLinkeList(dlist);

    destoryDoubleLinkList(dlist);
}

int main() {
    runAllTests();
    return 0;
}

第三章 相关应用

第四章 上手真题

第五章 比赛怎么用