数据结构与算法之双链表的操作_算法与数据双链表的操作实验

双链表的操作

/*
实现双链表的构建、初始化、数据添加（在指定位置添加）、数据删除（删除指定元素，并返回该元素的位置）的算法设计；
*/
#include<iostream>
#include<Windows.h>

using namespace std;

typedef struct _DoubleLink {
	int data;
	struct _DoubleLink *pre;	//指向上一节点的指针域
	struct _DoubleLink *next;	//指向下一节点的指针域
}DbLinkList, DbLinkNode;

//初始化双链表
bool InitList(DbLinkList* &l) {
	l = new DbLinkList;
	if (!l) return false;
	l->pre = NULL;
	l->next = NULL;
	return true;
}
//前插法添加双向链表元素
bool addLinkFront(DbLinkList* &l, DbLinkNode* s) {
	if (!l || !s) return false;
	if (l->next==NULL) {	//只有头结点
		l->next = s;
		s->pre = l;
		s->next = NULL;
	} else {
		s->next = l->next;
		l->next->pre = s;
		l->next = s;
		s->pre = l;
	}
	return true;
}
//尾插法添加双向链表元素
bool (addLinkLasr(DbLinkList* &l,DbLinkNode* s)) {
	if (!l || !s) return false;
	DbLinkList *last = l;
	while (last->next) last = last->next;	//差找到尾结点;

	s->next = NULL;
	last->next = s;
	s->pre = last;

	return true;
}
//打印输出双向链表
void PrintLinkst(DbLinkList* & l) {
	if (!l) return ;
	DbLinkList *p = l;
	while (p->next) {
		cout << p->next->data << " ";
		p = p->next;
	}
	return;
}
//在双向链表中插入指定元素
bool insert(DbLinkList* & l, int i, int x) {
	if (!l) return false;
	DbLinkList *p, *q;
	p = l;
	
	q = new DbLinkList;

	q->data = x;

	int index = 0;
	while (p->next) {
		if (index < i) {	//找到要插入节点的前一个节点
			index++;
			p = p->next;
		} else {
			p->next->pre = q;
			q->next = p->next;
			p->next = q;
			q->pre = p;
			return true;
		}
	}
	return false;
}
//在双向链表中删除指定元素
bool DeleteList(DbLinkList* &l, int Element, int &index) {
	if (!l||!l->next) return false;
	DbLinkList *p = l;
	while (p->next&&p->next->next) {
		if (p->next->data==Element) {
			p = p->next;
			p->pre->next = p->next;
			p->next->pre = p->pre;
			delete p;
			return true;
		}else{
			p = p->next;
			index++;
		}
	}
	if (p->next->data == Element) {
		p->next = NULL;

		return true;
	}

	return false;
}


int main(void) {
	DbLinkList *l = NULL;
	DbLinkNode *s = NULL;


	if (InitList(l)) {
		cout << "双向链表初始化成功! " << endl;
	} else {
		cout << "双向链表初始化失败! " << endl;
	}

	int chose;	//由用户选择是用前插法还是尾插法插入数据!
	//由用户选择是用前插法还是尾插法
	cout << "请选择使用前插法插入数据还是使用尾插法插入数据!" << endl;
	cout << "若要使用前插法插入数据请输入: 1" << endl;
	cout << "若要使用尾插法插入数据请输入: 2" << endl;
	cin >> chose;

	cout << "请输入要插入的元素个数: " << endl;
	int num = 0;	//用户要插入的元素个数
	cin >> num;

	//由用户选择何种方插入元素
	switch (chose) {

	case 1:
		while (num > 0) {
			cout << "请输入你想要插入的元素的值: ";
			s = new DbLinkNode;
			cin >> s->data;
			//单链表的数据添加 之 前插法
			if (addLinkFront(l, s)) {
				cout << "前插入元素!" << s->data << "成功! " << endl;
			} else {
				cout << "前插入元素失败! " << endl;
			}
			num--;
		}

		break;
	case 2:
		while (num > 0) {
			cout << "请输入你想要插入的元素的值: ";
			s = new DbLinkNode;
			cin >> s->data;
			//单链表的数据添加 之 尾插法
			if (addLinkLasr(l, s)) {
				cout << "尾插入元素!" << s->data << "成功! " << endl;
			} else {
				cout << "尾插入元素失败! " << endl;
			}
			num--;
		}
		break;
	default:
		cout << "输入不合法!!!!, 请重新输入" << endl;
		while (1) {
			cout << "请选择使用前插法插入数据还是使用尾插法插入数据!" << endl;
			cout << "若要使用前插法插入数据请输入: 1" << endl;
			cout << "若要使用尾插法插入数据请输入: 2" << endl;
			cin >> chose;
			if (chose == 1 || chose == 2) 
				break;
		}
		break;
	}

	PrintLinkst(l);

	int i;	//	插入的位置
	int x;//插入的值
	cout << "请输入你想要插入的位置: ";
	cin >> i;
	cout << "请输入你想要插入的元素: ";
	cin >> x;
	//实现双链表的构建、数据添加、数据删除的算法设计；
	if (insert(l, i, x)) {
		cout << "双向链表插入数据 : " << x << "成功,在双向链表的位置是: " << i << endl;
	} else {
		cout << "双向链表插入元素失败! " << endl;
	}

	PrintLinkst(l);

// 实现双链表的构建、数据添加、数据删除的算法设计；
	int Element;	//要删除的元素
	int index = 0;	//要删除的元素的位置
	cout << "请输入要删除的元素的值: ";
	cin >> Element;
	if (DeleteList(l, Element, index)) {
		cout << "双向链表删除数据 : " << Element << "成功,在双向链表的位置是: " << index << endl;
	} else {
		cout << "双向链表删除元素失败! " << endl;
	}
	PrintLinkst(l);
	system("pause");
	return 0;
}
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

前插法:

尾插法: