双链表的操作

双链表的代码定义

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;

typedef struct _DLNode
{
int data; //结点数据域
struct _DLNode *next; //指向后继的指针
struct _DLNode *prev; //指向前驱的指针

}DbLinkNode,DbLinkList;

双链表的操作

初始化双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//初始化双链表
bool initDbLinkList(DbLinkList* &L)
{
L = new DbLinkNode;

//合法性检查,检查内存是否分配成功
if(!L) return false;

L->next = NULL;
L->prev = NULL;
L->data = -1;

return true;
}

插入

前插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//前插法
bool DbListInsertFront(DbLinkList* &L, DbLinkNode *node)
{
//合法性检查
if(!L || !node) return false;

// if(L->next == NULL)
// {
// //若只有头结点,则在头结点后面插入一个结点
// node->next = NULL;
// node->prev = L;
// L->next = node;
// }
// else
// {
// //若有多个结点,则在头结点与其后结点之间插入
// L->next->prev = node; //令第二结点指向前驱的指针指向node
// node->next = L->next;
// node->prev = L;
// L->next = node;
// }

//优化
if(L->next) L->next->prev = node;
node->next = L->next;
node->prev = L;
L->next = node;

return true;
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//尾插法
bool DbListInsertBack(DbLinkList* &L, DbLinkNode *node)
{
//合法性检查
if(!L || !node) return false;

DbLinkNode *p = L;

//找到尾结点
while(p->next)
{
p = p->next;
}

node->next = NULL;
node->prev = p;
p->next = node;

return true;
}

任意位置插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//任意位置插入
/* 参数: 插入的双向链表, 插入位置, 插入结点数据域的值*/
bool DbListInsert(DbLinkList* &L, int i, int &e)
{
//若链表为空未初始化,返回false
if(!L) return false;

//若只有头结点,但插入位置不等于1,则返回false
if((!L->next && i != 1) || i < 1) return false;

int j = 0;
DbLinkList *p = L, *s;

while(p && j < i)
{
//找查位置为i的结点
p = p->next;
j++;
}

if(!p || j != i)
{
cout << "不存在结点" << i << endl;
return false;
}

cout << "p: " << p << endl;

s = new DbLinkNode; //生成新的结点
s->data = e;

s->next = p;
s->prev = p->prev;
p->prev->next = s;
p->prev = s;

return true;
}

双链表的遍历输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//双向链表的遍历输出
void printDbList(DbLinkList *L)
{
//检查链表是否为空
if(!L)
{
cout << "链表为空" << endl;
return;
}

DbLinkList *p = L;
p = p->next;

while(p)
{
cout << p->data << endl;
p = p->next;
}

}

元素删除与双链表的销毁

本部分操作与单链表一致,请参考《单链表的操作

作者

CairBin

发布于

2021-09-28

更新于

2021-09-28

许可协议

评论