本文实例为大家分享了C++实现双向链表的具体代码，供大家参考，具体内容如下
双向链表：两个指针域，一个指向前结点，一个指向后结点
list.h
|
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
|
#pragma once#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status;typedef int ElemType;typedef struct DNode{ struct DNode *prior; //前结点指针域 ElemType data; //数据域 struct DNode *next; //后结点指针域}DNode, *DLinkList; //结点和指向结点的指针bool InitDLinkList(DLinkList &L); //双链表初始化Status CreatDLinkList(DLinkList &L); //尾插法创建链表，包含初始化功能bool InsertNextDNode(DNode *p, DNode *s); //结点s插入在结点p之后Status DeleteNextDNode(DNode *p, ElemType &e); //删除结点p的后继节点 void ListTraverse(const DLinkList L); //双链表的遍历Status ListInsert(DLinkList &L, int i, ElemType e); //指定位置插入元素Status ListDelete(DLinkList &L, int i, ElemType &e); //指定位置删除元素DNode* GetElem(DLinkList L, int i); //查找链表指定位置节点，返回的是结点void DestoryList(DLinkList &L); //销毁双链表,需要释放头结点 |
oper_func.cpp
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
#include <iostream>#include"list.h"bool InitDLinkList(DLinkList &L){ //构建空的双链表，作为双链表的头结点，数据域为空 L = new DNode; if (L == NULL) //内存分配失败 return FALSE; L->prior = NULL; //头结点的前驱指针始终指向NULL L->next = NULL; //暂时指向NULL return TRUE;}Status CreatDLinkList(DLinkList &L){ //利用InsertNextDNode函数来创建 using std::cin; using std::cout; using std::endl; if (InitDLinkList(L)) { DNode *s,*r = L; //s为新建的新结点，用来存储数据，而r为尾指针，始终指向尾部节点 int num; cout << "输入你需要创建的双链表的个数："; cin >> num; for (int i = 1; i <= num; i++) { s = new DNode; //创建的新结点 cout << "输入第" << i << "个元素："; cin >> s->data; //输入数据 s->next = NULL; InsertNextDNode(r,s); //结点s插在尾部节点之后 r = s; //尾指针指向新的尾结点 } return OK; } else { cout << "内存不够，单链表创建失败！" << endl; return ERROR; }}//结点s插入在结点p之后bool InsertNextDNode(DNode *p, DNode *s){ if (p == NULL || s == NULL) return FALSE; //非法参数 s->next = p->next; if (p->next != NULL) //如果p不是最后一个结点 { p->next->prior = s; } s->prior = p; p->next = s; return TRUE;}Status DeleteNextDNode(DNode *p, ElemType &e){ if(p == NULL) return FALSE; //非法参数 DNode *q = p->next; //找到p节点的后继节点 if (q == NULL) //节点p没有后继节点 { return ERROR; } else { //有后继节点，但是p的后继节点为空 p->next = q->next; e = q->data; if (q->next != NULL) { q->next->prior = p; } delete q; return OK; }}void ListTraverse(const DLinkList L){ using std::cout; using std::endl; int i = 1; DNode *p = L->next; //指向第一个元素 if (p == NULL) { cout << "双链表为空，无法输出元素！" << endl; return; } while (p) { cout << "第" << i++ << "个元素为：" << p->data << endl; p = p->next; }}Status ListDelete(DLinkList &L, int i, ElemType &e){ if (i < 1) //位置不合理 return ERROR; //寻找第i-1个结点 DNode *p = GetElem(L, i - 1); //删除i-1结点的后面结点 return DeleteNextDNode(p,e);}DNode* GetElem(DLinkList L, int i){ DNode *p = L; int j = 0; //表示p指向的当前结点的位置，此时为头结点 while (p != NULL && j < i) { p = p->next; //指向下一个结点 j++; } return p;}void DestoryList(DLinkList &L){ using std::cout; using std::endl; ElemType temp; int i = 1; while (L->next != NULL) { DeleteNextDNode(L,temp); cout << "第" << i++ << "个删除的元素为：" << temp << endl; } cout << "双链表全部数据销毁成功！" << endl; delete L; cout << "头结点销毁，整个双链表销毁成功！" << endl; L = NULL; //头指针指向NULL}Status ListInsert(DLinkList &L, int i, ElemType e){ if (i < 1) return FALSE; //寻找第i-1个结点 DNode *p = GetElem(L, i - 1); //直接在i-1结点的后面插入元素即可 DNode *s = new DNode; //新建节点 s->data = e; s->next = NULL; s->prior = NULL; return InsertNextDNode(p,s);} |
main.cpp
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
/* 双向链表：带头结点，且头结点的prior指针时钟指向为NULL1、双链表的初始化2、双链表的创建3、双链表的结点插入（相当于后插操作）：（结点s插入结点p之后）需要考虑p结点是不是最后一个结点 如果想前插操作，则找到该节点的i-1节点，然后实行后插操作也是一样4、双链表的结点删除（相当于后删操作）：（删除p节点的后序节点q）需要考虑p结点是不是最后一个结点 也要考虑q节点是不是最后一个结点5、双链表的删除：6、双链表的遍历：7、双链表的销毁：需要回收头结点*/#include <iostream>#include"list.h"void showMenu(){ using std::cout; using std::cin; using std::endl; cout << "*********************************************************" << endl; cout << "*** 1.指定位置插入元素 2.删除指定位置元素 ***" << endl; cout << "*** 3.遍历单链表 0.销毁双链表并退出 ***" << endl; cout << "*********************************************************" << endl;}int main(){ using std::cout; using std::cin; using std::endl; int select = 0, flag = -1; //输入的选择 DLinkList L; //L表示头指针，始终指向表头 if (CreatDLinkList(L)) //尾插法创建单链表 { cout << "双链表创建成功！" << endl; } else cout << "双链表创建失败！" << endl; while (true) { showMenu(); cout << "输入你的选择："; cin >> select; switch (select) { case 1: { //指定位置插入元素 int position = 0, elem = 0; cout << "输入插入的位置和元素:"; cin >> position >> elem; if (ListInsert(L, position, elem)) cout << "指定位置插入元素成功！" << endl; else cout << "内存分配失败或者插入位置越界，插入失败！" << endl; } break; case 2: { //删除指定位置节点 int position = 0, elem = 0; cout << "输入指定位置:"; cin >> position; if (ListDelete(L, position, elem)) { cout << "删除指定位置元素成功！元素为：" << elem << endl; } else { cout << "单链表为空或者删除位置不合理！" << endl; } } break; case 3: { ListTraverse(L); } break; case 0: { DestoryList(L); system("pause"); return 0; } break; } } return 0;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/qq_33373460/article/details/124498538
