简介

此模块为学校数据结构必修课学习内容的记录与分享

全文大体分为一下几个部分

模块解释
可视化GIF合集
整体复现
最终结果

模块解释

定义双向链表

typedef struct DoubleLinkedNode {
    char data;
    struct DoubleLinkedNode *previous;
    struct DoubleLinkedNode *next;
} DLNode, *DLNodePtr;

初始化节点

DLNodePtr InitLinkList () {
    DLNodePtr temphead = (DLNodePtr)malloc(sizeof(DLNode));

    temphead->data = '\0';
    temphead->previous = NULL;
    temphead->next = NULL;

    return temphead;
}

打印双向链表数据

从头节点开始打印节点内数值

void PrintList(DLNodePtr ParaHeader) {
    DLNodePtr temp = ParaHeader->next;

    while (temp != NULL) {
        printf("%c ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

节点插入

在指定位置插入节点

void InsertElement(DLNodePtr ParaHeader, char ParaData, int ParaPosition) {

DLNodePtr p, q, NewNode;

p = ParaHeader;

for (int i = 0; i < ParaPosition; i++) {

p = p->next;

if(p == NULL) {

printf(“The position %d is beyond the scope of the list.”, ParaPosition);

return;

}

q = p->next;

NewNode = (DLNodePtr)malloc(sizeof(DLNode));

NewNode->data = ParaData;

p->next = NewNode;

NewNode->previous = p;

NewNode->next = q;

// NewNode->next = p->next;

// 大意写成这样，导致了节点循环调用，导致程序崩溃

// 如果p是最后一个节点，那么q为NULL，就没有节点指向新节点

if(q != NULL) {

q->previous = NewNode;

}

节点删除

删除含有指定数据的节点

void DeleteElement(DLNodePtr ParaHeader, char ParaData) {
    // p 为要删除节点前的节点
    // DeletNode 为待删除的节点
    // r 为待删除节点后的节点
    DLNodePtr p, DeletNode, r;
    p = ParaHeader;

    while ((p->next != NULL) && (p->next->data != ParaData)) {
        p = p->next;
    }

    // 确保后面是目标节点
    if(p->next == NULL) {
        printf("The element %c is not in the list.", ParaData);
        return;
    }
    
    DeletNode = p->next;
    r = DeletNode->next;

    p->next = r;
    if(r != NULL) {
        r->previous = p;
    }
    free(DeletNode);
    return;

}

输出地址信息

打印链表各节点地址信息

void PrintMemory(DLNodePtr ParaHeader) {
    DLNodePtr temp = ParaHeader->next;
    int i = 0;
    while (temp != NULL) {
        printf("The %d node is %c  |  the previous address is %ld  the adress is %ld  the next address is %ld\n", i, temp->data, temp->previous, temp, temp->next);
        temp = temp->next;
        i++;
    }
}

测试函数

void TestAll () {
    DLNodePtr tempList = InitLinkList();
    printf("Before the insert : \n");
	PrintList(tempList);

	InsertElement(tempList, 'H', 0);
	InsertElement(tempList, 'e', 1);
	InsertElement(tempList, 'l', 2);
	InsertElement(tempList, 'l', 3);
	InsertElement(tempList, 'o', 4);
	InsertElement(tempList, '!', 5);
    printf("After the insert : \n");
	PrintList(tempList);

	DeleteElement(tempList, 'e');
	DeleteElement(tempList, 'a');
	DeleteElement(tempList, 'o');
    printf("After the delete : \n");
	PrintList(tempList);

	InsertElement(tempList, 'o', 1);
    printf("After the insert : \n");
	PrintList(tempList);

    PrintMemory(tempList);
}

main 函数

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

可视化GIF合集

由于双向链表只是在单链表基础上增加了一个 previous 前向指针，其它的处理思路是一致的，因此就不放GIF动画，仅补充对应的图例

主要是我只找到循环双向链表的GIF，哈哈

双向链表结构形式

添加节点

注意在最后节点进行添加的特殊情况

删除节点

注意删除最后节点的特殊情况

整体复现

#include<stdio.h>
#include<malloc.h>

// 双向链表节点定义
typedef struct DoubleLinkedNode {
    char data;
    struct DoubleLinkedNode *previous;
    struct DoubleLinkedNode *next;
} DLNode, *DLNodePtr;

// 初始化节点
DLNodePtr InitLinkList () {
    DLNodePtr temphead = (DLNodePtr)malloc(sizeof(DLNode));

    temphead->data = '\0';
    temphead->previous = NULL;
    temphead->next = NULL;

    return temphead;
}

// 从头节点开始打印节点内数值
void PrintList(DLNodePtr ParaHeader) {
    DLNodePtr temp = ParaHeader->next;

    while (temp != NULL) {
        printf("%c ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// 在指定位置插入节点
void InsertElement(DLNodePtr ParaHeader, char ParaData, int ParaPosition) {
    DLNodePtr p, q, NewNode;
    p = ParaHeader;
    for (int i = 0; i < ParaPosition; i++) {
        p = p->next;
        if(p == NULL) {
            printf("The position %d is beyond the scope of the list.", ParaPosition);
            return;
        }
    }
    q = p->next;

    NewNode = (DLNodePtr)malloc(sizeof(DLNode));
    NewNode->data = ParaData;

    
    p->next = NewNode;
    NewNode->previous = p;
    NewNode->next = q;
    // NewNode->next = p->next;
    // 大意写成这样，导致了节点循环调用，导致程序崩溃

    // 如果p是最后一个节点，那么q为NULL，就没有节点指向新节点
    if(q != NULL) {
        q->previous = NewNode;
    }
    
}

// 删除含有指定元素的节点
void DeleteElement(DLNodePtr ParaHeader, char ParaData) {
    // p 为要删除节点前的节点
    // DeletNode 为待删除的节点
    // r 为待删除节点后的节点
    DLNodePtr p, DeletNode, r;
    p = ParaHeader;

    while ((p->next != NULL) && (p->next->data != ParaData)) {
        p = p->next;
    }

    // 确保后面是目标节点
    if(p->next == NULL) {
        printf("The element %c is not in the list.", ParaData);
        return;
    }
    
    DeletNode = p->next;
    r = DeletNode->next;

    p->next = r;
    if(r != NULL) {
        r->previous = p;
    }
    free(DeletNode);
    return;

}
void PrintMemory(DLNodePtr ParaHeader) {
    DLNodePtr temp = ParaHeader->next;
    int i = 0;
    while (temp != NULL) {
        printf("The %d node is %c  |  the previous address is %ld  the adress is %ld  the next address is %ld\n", i, temp->data, temp->previous, temp, temp->next);
        temp = temp->next;
        i++;
    }
}


void TestAll () {
    DLNodePtr tempList = InitLinkList();
    printf("Before the insert : \n");
	PrintList(tempList);

	InsertElement(tempList, 'H', 0);
	InsertElement(tempList, 'e', 1);
	InsertElement(tempList, 'l', 2);
	InsertElement(tempList, 'l', 3);
	InsertElement(tempList, 'o', 4);
	InsertElement(tempList, '!', 5);
    printf("After the insert : \n");
	PrintList(tempList);

	DeleteElement(tempList, 'e');
	DeleteElement(tempList, 'a');
	DeleteElement(tempList, 'o');
    printf("After the delete : \n");
	PrintList(tempList);

	InsertElement(tempList, 'o', 1);
    printf("After the insert : \n");
	PrintList(tempList);

    PrintMemory(tempList);
}



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

输出结果

PS D:\a_study\code_vs\DataStructure\DoubleLinkedNode> gcc -o kernel code.cpp
PS D:\a_study\code_vs\DataStructure\DoubleLinkedNode> ./kernel
Before the insert : 

After the insert :
H e l l o !
The element a is not in the list.After the delete :
H l l !
After the insert :
H o l l !
The 0 node is H  |  the previous address is 12065536  the adress is 12069680  the next address is 12091408
The 1 node is o  |  the previous address is 12069680  the adress is 12091408  the next address is 12091344
The 2 node is l  |  the previous address is 12091408  the adress is 12091344  the next address is 12091376
The 3 node is l  |  the previous address is 12091344  the adress is 12091376  the next address is 12091440
The 4 node is !  |  the previous address is 12091376  the adress is 12091440  the next address is 0

可以看见，如此（previous address – address – next address）排列下的链表节点地址具有明显的线性对应特点，反映其优美的对应关系

过程记录

复现代码
发现错误【指针指向问题】
修改错误
优化输出结果
迁移文章

Points

最后节点的判断

因为双向链表一个节点（有两个指针）会储存前后节点信息，在对节点处理的时候，要注意对前后节点两个指针进行处理

例如，在进行 delete 操作时，若删除最后一个节点，则需要把倒数第二个节点的 next 指针赋值为 NULL，并 free 掉最后一个节点。

Thinking

what – 什么是双向链表, 在现实世界中有哪些双向链表的例子?

双向链表是具有前后节点信息的链表

浏览器浏览记录（可以进行后退和前进操作）

文本编辑中的前后撤回操作

音乐播放器列表

why – 有了单链表, 为什么还要引入双向链表?

双向链表具有更高的灵活性，更容易地在任意位置插入或删除结点，无需从头节点开始遍历

what – 对双向链表进行操作的时候, 容易出现哪些错误?

访问越界
指针更新错误（造成节点循环）
内存泄漏

Post Views: 4

简介