c++数据结构之实现链表操作

实现链表，首先要实现节点，然后由节点串成链表，一般来说会有打印节点、插入、删除、返回长度、空不空判断等操作。其中最重要的就是插入和删除操作。我觉得在实现上，主要还是要理解节点在链表中是怎么表示的，在对节点操作时是以什么形式进行操作的。

代码

#include
//#include
//#include
//#include

using namespace std;

struct ListNode
{
	double value;
	ListNode* next; // 指向相同类型节点的指针
};

// 链表类
class LinkList
{
private:
	ListNode* head;
public:
	LinkList():head(nullptr){}
	~LinkList() { cout << "析构链表" << endl; }
	void insert(int i, double value);
	bool isempty();
	void shownodes();
	int length();
	void erase(int i);
};

void LinkList::erase(int i)
{
	// 删除第i个节点,检查合法性
	if (i<0 || i>this->length()) {
		cout << "i = " << i << ", 输入不合法!" << endl;
		return;
	}
	if (i == 1) {
		// 如果删除头节点
		ListNode* temp_head = head; // 保存目前的头结点
		head = head->next; // 将head後的节点置为头节点
		delete temp_head; // 删除之前的头结点
	}
	else {
		// 否则就是删除其他节点
		// 首先找到这个节点和这个节点的前一个节点
		ListNode* node_del = head->next;
		ListNode* node_pre = head;
		while (i>2) {
			node_del = node_del->next;
			node_pre = node_pre->next;
			i--;
		}
		node_pre->next = node_del->next;
		delete node_del;
	}
}

int LinkList::length()
{
	if (isempty()) return 0;
	int l = 0;
	ListNode* node = head;
	while (node) {
		l += 1;
		node = node->next;
	}
	return l;
}


void LinkList::shownodes()
{
	ListNode* begin = this->head;
	while (begin) {
		cout << begin->value << "\t";
		begin = begin->next;
	}
	cout << endl;
}

bool LinkList::isempty()
{
	if (this->head == nullptr) return true;
	else return false;
}

void LinkList::insert(int i, double value) {
	if (this->isempty()) {
		// 如果是空表,就只能接在头上
		cout << "空表,将接在头上" << endl;
		head = new ListNode; // 申请空间
		head->value = value;
		head->next = nullptr;
		return;
	}
	// 检查i的合法性
	if (i > this->length()) {
		cout << "i = " << i << "的值大于链表长度,异常输入!" << endl;
		return;
	}
	
	// 否则插入节点
	ListNode* s = new ListNode; // 新建节点
	s->value = value;
	if (i == 1) { // 如果是头节点
		// 插入表头
		s->next = head;
		head = s; // 修改头节点的值
		return;
	}

	// 找到第i个节点
	ListNode* node = head;
	while (i > 2) {
		node = node->next;
		i--;			
	}
	if (node != nullptr)
	{
		// 现在node是插入位置的前一个节点
		s->next = node->next;
		node->next = s;
	}	
}


int main()
{
	LinkList alinklist;
	alinklist.insert(2, 2.3); // 插入节点，作为第2个节点(由于此时是空表，所有会被当成插入头节点)
	alinklist.insert(1, 4.4);
	alinklist.insert(1, 3.3);
	alinklist.insert(8, 8.5); // 插入节点，作为第8个节点
	alinklist.insert(2, 2.5); // 插入节点，作为第2个节点
	alinklist.insert(3, 3.5); // 插入节点，作为第2个节点


	alinklist.shownodes(); // 打印节点内容

	alinklist.erase(5); // 删除第5个节点
	alinklist.erase(5); // 删除第5个节点
	alinklist.erase(3); // 删除第3个节点
	alinklist.shownodes(); // 打印节点内容

	cout << "这里程序结束" << endl;
	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

结果