c++实现带头结点的单链表的基本操作

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
struct ListNode {
int val;//数据域
ListNode* next;//指针域
};
class LinkList
{
public:
LinkList();
~LinkList();
void CreateLinkList(int n);
void TravelLinkList();
int getLength();
bool isEmpty();
bool findData(int data);//查找节点，如果能够找到，返回true；否则返回false;
void InsertElemAtEnd(int data);
//在尾部插入指定的元素
void InsertElemAtIndex(int data, int n);
//在指定位置插入指定元素
void InsertElemAtHead(int data);
//在头部插入指定元素
void DeleteElemAtEnd();
//在尾部删除元素
void DeleteAll();
//删除所有数据
void DeleteElemAtPoint(int data);
//删除指定的数据
void DeleteElemAtHead();//在头部删除节点
private:
ListNode *head;
};

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
#include "stdafx.h"
#include "LinkList.h"
#include <iostream>
using namespace std;
LinkList::LinkList()
{
head = new ListNode;
head->val = 0;
head->next = NULL;
}
LinkList::~LinkList()
{
delete head;
}
void LinkList::CreateLinkList(int n) {
if (n < 0) {
cout << "节点个数错误，请重新输入" << endl;
exit(EXIT_FAILURE);
}
else {
ListNode* p = head;
ListNode* nextNode;
for (int i = 0; i < n;i++) {
nextNode = new ListNode;
cout << "请输入新节点的值域" << endl;
cin >> nextNode->val;
nextNode->next = NULL;
p->next = nextNode;
p = p->next;
}
}
}
void LinkList::TravelLinkList() {
if (head == NULL || head->next == NULL) {
cout << "链表为空" << endl;
}
else {
ListNode* p = head;
while (p ->next!= NULL) {
p = p->next;
cout << p->val << endl;
}
}
}
int LinkList::getLength() {//头结点不计入总长度
int length = 0;
ListNode* p = head->next;
while (p != NULL) {
length++;
p = p->next;
}
return length;
}
bool LinkList::isEmpty() {
if (head == NULL) {
return true;
}
else {
return false;
}
}
bool LinkList::findData(int data)//查找节点，如果能够找到，返回true；否则返回false;
{
if (head == NULL || head->next == NULL) { return false; }
else {
ListNode* p = head->next;
while (p != NULL) {
if (p->val == data) { return true; }
else { p = p->next; }
}
return false;
}
}
void LinkList::InsertElemAtEnd(int data)//在尾部插入指定的元素
{
//准备好新的节点
ListNode* newNode;
newNode = new ListNode;
newNode->val = data;
newNode->next = NULL;
//在链表尾部插入节点
if (head == NULL) { head = newNode; }
else {
ListNode* p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = newNode;
}
}
void LinkList::InsertElemAtIndex(int data, int n)//在指定位置插入指定元素,插入的元素在head之后。
{
int length = this->getLength();
if (n > length||n<1) { cout << "输入的位置不存在" << endl; }
else {
ListNode* p = head;
ListNode* q = head->next;
ListNode* newNode=new ListNode;
newNode->val = data;
newNode->next = NULL;
int i = 0;
for (; i != n; i++) {
p = p->next;
q = q->next;
}
p->next = newNode;
newNode->next = q;
}
}
void LinkList::InsertElemAtHead(int data)//在头部插入指定元素
{
ListNode* newNode = new ListNode;
newNode->val = data;
newNode->next = NULL;
if (head == NULL) { head = newNode; }
else {
newNode->next = head->next;
head->next = newNode;
}
}
void LinkList::DeleteElemAtEnd()//在尾部删除元素
{
if (head == NULL) { cout << "链表为空，无须删除" << endl;; }
else {
ListNode* p = head;
ListNode* q = head->next;
while (q->next != NULL) {
p = p->next;
q = q->next;
}
p->next = NULL;
delete q;
}
}
void LinkList::DeleteAll()//删除所有数据
{
if (head == NULL) { ; }
else {
ListNode* p = head->next;
//ListNode* p_temp = new ListNode;
while (p != NULL) {
/*p_temp = p;
p = p->next;
head->next = p;
p_temp->next = NULL;
delete p_temp;*/
head->next = p->next;
delete p;
p = head->next;
}
}
}
void LinkList::DeleteElemAtPoint(int data)//删除指定的数据
{
//也就是说要考虑data 是否存在的两种情况。
if (findData(data)) {
//如果能够找到该数据
ListNode* p = head;
ListNode* q = head->next;
while (q->val != data) {
p = p->next;
q = q->next;
}
//此时q的值为data,接下来删除q节点。
p->next = q->next;
q->next = NULL;
delete q;
}
}
void LinkList::DeleteElemAtHead()//在头部删除节点
{
if (head == NULL) { ; }
else {
ListNode* p = head;
ListNode* q = head->next;
p->next = q->next;
delete q;
}
}

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
#include<vector>
using namespace std;
int main()
{
LinkList lst;
int i;
int pos;
int data;
cout << "1.创建单链表
2.遍历单链表
3.获取单链表的长度
4.判断单链表是否为空
5.获取节点n";
cout << "6.在尾部插入指定元素
7.在指定位置插入指定元素
8.在头部插入指定元素n";
cout << "9.在尾部删除元素
10.删除所有元素
11.删除指定元素
12.在头部删除元素
0.退出" << endl;
do {
cout << "请输入指令" << endl;
cin >> i;
switch (i)
{
case 1:
cout << "请输入表单的长度" << endl;
int length;
cin >> length;
lst.CreateLinkList(length);
continue;
case 2:
lst.TravelLinkList();
continue;
case 3:
cout << "该链表的长度为" << lst.getLength()<<endl;
continue;
case 4:
cout << "该链表是否为空 " << lst.isEmpty() << endl;
continue;
case 5:
cout << "输入待寻找的数值：" << endl;
cin >> data;
cout << "是否找到了该数 " << lst.findData(data)<<endl;
continue;
case 6:
cout << "请输入在结尾插入的数据" << endl;
cin >> data;
lst.InsertElemAtEnd(data);
continue;
case 7:
cout << "请输入插入数据的位置" << endl;
cin >> pos;
cout << "请输入插入的数据" << endl;
cin >> data;
lst.InsertElemAtIndex(data, pos);
continue;
case 8:
cout << "请输入插入的数据" << endl;
cin >> data;
lst.InsertElemAtHead(data);
continue;
case 9:
lst.DeleteElemAtEnd();
continue;
case 10:
lst.DeleteAll();
continue;
case 11:
cout << "请输入要删除的数据" << endl;
cin >> pos;
lst.DeleteElemAtPoint(pos);
continue;
case 12:
lst.DeleteElemAtHead();
continue;
default:
break;
}
} while (i != 0);
return 0;
}