线性表

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
# Node
class Node
{
private:
	//学号 姓名 三个成绩
	string StdNumber;
	string StdName;
	int Score[3];
public:
	Node(){};
	Node(char* NumberofStudent, char* NameodStudent, int grade[]);
	//得到节点数据, Node引用
	Node& GetNode();
	//输出节点数据
	void OutPutNode(ostream& out) const;
};

Node::Node(char* NumberofStudent, char* NameodStudent, int grade[])
{
	// 字符串赋值之前用的stringcopy（scpy），因为stdNumber是一个string类的对象，=已经重载过了
	StdNumber = NumberofStudent;
	StdName = NameodStudent;
	for (int i = 0; i < 3; i++) {
		Score[i] = grade[i];
	}
}

Node& Node::GetNode()	// 返回是Node的引用
{
	return *this;
}

// 实现输出结点数据函数，out是输出流对象
void Node::OutPutNode(ostream& out) const
{
	out << StdNumber << ' ' << StdName << endl;
	out << "语文：" << Score[0];
	out << "数学：" << Score[1];
	out << "英语：" << Score[2];
}

// 重载预算符 <<
ostream& operator<<(ostream& out, const Node& x)	
{
	x.OutPutNode(out);
	return out;
}
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
// 构造类模板
template<class T>
class LinearList
{
private:
	int length;		// 当前元素个数
	int MaxSize;	// 线性表中最大元素个数
	T *element;		// 一维动态数组，指向T类型的地址命名为element，T类型的指针
public:
	LinearList(int LLMaxsize);	// 构造函数：创建空表
	~LinearList();				// 析构函数：删除表
	LinearList<T>& Insert(int k, const T& x);	// 第k个位置插入值x，返回表，T&为T类型元素x（&是线性表的引用）
	bool IsEmpty() const;			//判断表是否为空，空true，不空false
	int GetLength() const;			// 返回表中元素个数
	bool GetData(int k, T& x);		// 表中第k个元素保存到x中，不存在返回 false，值放到x里面，要修改x不用const
	bool ModifyData(int k, const T& x);		// 将表中第k个元素改为x，不存在返回false
	int Find(const T &x);					// 返回x在表中的位置，如果x不在表中返回0
	LinearList<T>& DeleteByIndex(int k, T& x);		// 删除表中第k个元素，把他保存在x中，返回删除后的线性表(&是变量的引用)
	LinearList<T>& DeleteByKey(const T& x, T& y);	// 删除表中关键字为x的元素，x存储在y参数中，返回删除后的线性表
	void OutPut(ostream& out) const;				// 线性表放到输出流out中输出
};

// 类外构造函数——————建表—————————
template<class T>
LinearList<T>::LinearList(int LLMaxsize)
{
	MaxSize = LLMaxsize;	// Maxsize是数据成员
	element = new T[LLMaxsize];	// 分配出来的空表
	length = 0;
}
// 类外析构函数——————删除表—————————
template<class T>
LinearList<T>::~LinearList() 
{
	delete[]element;
}

/*
* —————————插入————————————
* k位置插入x元素
* 1. 判断表是否存在,位置是否合理，是否已满
* 2. 从后面移动，长度+1
*/
template<class T>
LinearList<T>& LinearList<T>::Insert(int k, const T& x)		// LinearList<T>&是返回类型
{
	if (k < 1 || k > length + 1) {		// 插入元素最多放在数组尾巴上，length+1，最小在第一位
		cout << "元素下标越界，添加元素失败" << endl;
	}
	else
		if (length == MaxSize) {		// 判断表满没满
			cout << "此表已满，添加元素失败" << endl;
		}
		else
		{
			for (int i = length; i > k - 1; i--) {		// i--，i为length长度，实际上是下标+1，k位置的下标是k-1
				element[i] = element[i-1];
			}
			element[k - 1] = x;
			length++;									// 不要忘了最后长度要+1
		}
	return *this;	// 对象自己*this，最后要返回表自身
}

/*————————判断是否为空表——————————*/
template<class T>
bool LinearList<T>::IsEmpty() const						// 返回类型 bool
{
	/*
		if (length == 0) {
		return false;
	}
	else
		return true;
	*/
	return length == 0;
}

/*——————求当前表长度------------*/
template<class T>
int LinearList<T>::GetLength() const	// const其他的成员变量在这个函数内一律不能修改，只读属性，增强安全性
{
	return length;
}

/*------------按位置取元素------------*/
template<class T>
bool LinearList<T>::GetData(int k, T& x) 
{
	if (k < 1 || k > length)			// k > length排除了空表的情况，空表length = 0， k >0不合理
	{
		return false;
	}
	else
	{
		x = element[k - 1];
		return true;
	}
}


/*--------------按位置修改表中元素-----------*/
template<class T>
bool LinearList<T>::ModifyData(int k, const T& x)
{
	if (k < 1 || k > length)			// k > length排除了空表的情况，空表length = 0， k >0不合理
	{
		return false;
	}
	else
	{
		element[k - 1] = x;
		return true;
	}
}

/*---------------按关键字查找下标---------------*/
template<class T>
int LinearList<T>::Find(const T& x)
{
	for (int i = 0; i < length; i++) 
	{
		if (element[i] == x)
			return i + 1;
	}
	return 0;
}


/*--------------按位置删除元素-----------------
* 1. 判断表是否存在，位置是否合理，表是否为空表
* 2. 向前移动，长度-1
*/
template<class T>
LinearList<T>& LinearList<T>::DeleteByIndex(int k, T& x)
{
	if (GetData(k, x))							// 能取到元素则元素存在
	{
		for (int i = k - 1; i < length - 1; i++)
		{
			element[i] = element[i + 1];
		}
		length--;
	}
	else
		cout << "元素下标越界，删除失败" << endl;
	return *this;
}

/*-----------按关键字删除-------------
关键字x有无，若有则删除
*/
template<class T>
LinearList<T>& LinearList<T>::DeleteByKey(const T& x, T& y)
{
	int index = Find(x);	// 返回位置或者0
	if (index != 0)
		return DeleteByIndex(index, y);			// 要按关键字删除，先定位出关键字的位置，然后用按位置删除的函数
	else
	{
		cout << "没有此元素，删除失败" << endl;
		return *this;
	}
}

/*-------------顺序表输出---------------*/
template<class T>
void LinearList<T>::OutPut(ostream& out) const
{
	for (int i = 0; i < length; i++)
		out << element[i] << endl;
}
// 重载插入运算符<<
template<class T>
ostream& operator<<(ostream& out, const LinearList<T>& x)	// 第一个参数输出流对象，cout操作，第二个是线性表
{
	x.OutPut(out);
	return out;
}

链表

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
# Node
class Node
{
private:
	//学号 姓名 三个成绩
	string StdNumber;
	string StdName;
	int Score[3];
public:
	Node(){};
	Node(char* NumberofStudent, char* NameodStudent, int grade[]);
	//得到节点数据, Node引用
	Node& GetNode();
	//输出节点数据
	void OutPutNode(ostream& out) const;
};

Node::Node(char* NumberofStudent, char* NameodStudent, int grade[])
{
	// 字符串赋值之前用的stringcopy（scpy），因为stdNumber是一个string类的对象，=已经重载过了
	StdNumber = NumberofStudent;
	StdName = NameodStudent;
	for (int i = 0; i < 3; i++) {
		Score[i] = grade[i];
	}
}

Node& Node::GetNode()	// 返回是Node的引用
{
	return *this;
}

// 实现输出结点数据函数，out是输出流对象
void Node::OutPutNode(ostream& out) const
{
	out << StdNumber << ' ' << StdName << endl;
	out << "语文：" << Score[0];
	out << "数学：" << Score[1];
	out << "英语：" << Score[2];
}

// 重载预算符 <<
ostream& operator<<(ostream& out, const Node& x)
{
	x.OutPutNode(out);
	return out;
}
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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
template<class T>
class LinkNode
{
	// 声明LinkList为友元，可直接访问
	template<class T>
	friend class LinkList;
public:
	LinkNode()		//创建节点的时候先让新创建的节点->next为空
	{
		next = NULL;
	}
	~LinkNode() {};
private:
	T data;				// 节点元素
	LinkNode<T>* next;	// 指向下一个元素（LinkNode<T>类型元素）的指针
};

template<class T>
class LinkList
{
public:
	LinkList();
	~LinkList();
	LinkList<T>& Insert(int k, const T& x);
	bool IsEmpty() const;
	int GetLength();
	bool GetData(int k, T& x);
	bool ModiflyData(int k, const T& x);
	int Find(const T& x);
	LinkList<T>& DeleteByIndex(int k, T& x);
	LinkList<T>& DeleteByKey(const T& x, T& y);
	void OutPut(ostream& out);
private:
	LinkNode<T>* head;	// 唯一的一个数据成员指向头结点
};

/*------------建表（构造函数）----------*/
template<class T>
LinkList<T>::LinkList()
{
	//建表就是建立第一个指针，创建头结点
	head = new LinkNode<T>();
}

/*-------------删除表（析构函数）---------------
 一个节点一个节点删除，直到释放头结点
*/
template<class T>
LinkList<T>::~LinkList()
{
	T x;
	for (int i = GetLength(); i > 0; i--)
	{
		DeleteByIndex(i, x);
	}
	delete head;
}

/*-----------是否为空表---------*/
template<class T>
bool LinkList<T>::IsEmpty() const
{
	return head->next == NULL;
}

/*-----------求当前表长度---------*/ 
template<class T>
int LinkList<T>::GetLength()
{
	LinkNode<T>* p = head->next;	//p指针指向第一个元素
	int length = 0;
	while (p)
	{
		length++;
		p = p->next;
	}
	return length;
}

/*------------按位置获取元素----------
1. 判断位置是否合适
2. 按位置寻找，若p为空也不行
3. 找到
*/
template<class T>
bool LinkList<T>::GetData(int k, T& x)
{
	LinkNode<T>* p = head->next;
	int index = 1;
	if (k < 1 || k > GetLength())
		return false;
	while(p != NULL && index < k)
	{
		index++;
		p = p->next;
	}
	if (p == NULL)
		return false;
	else
	{
		x = p->data;
		return true;
	}
}

/*-------------按位置修改元素------------
查找到位置后替换，和按位置获取元素一致
*/
template<class T>
bool LinkList<T>::ModiflyData(int k, const T& x)
{
	int index = 1;
	LinkNode<T>* p = head->next;
	if (k < 1 || k > GetLength())
		return false;
	while (p != NULL && index < k)		// 最后p指向k位置，判断index !< k循环停止
	{
		index++;
		p = p->next;
	}
	if (p == NULL)
		return false;
	else
	{
		p->data = x;
		return true;
	}

}

/*-----------按关键字查找元素-----------*/
template<class T>
int LinkList<T>::Find(const T& x)
{
	LinkNode<T>* p = head->next;	//index和p指向的位置保持一致
	int index = 1;
	while (p != NULL && p->data != x)		// 最后p指向k位置，判断index !< k循环停止
	{
		index++;
		p = p->next;
	}
	if (p != NULL)
		return index;
	else
		return 0;
}


/*------------插入------------
1. 位置
2. 空表 head->next指向插入的
3. 非空表第一个元素插入 新元素->next指向原本第一个，head->next指向新元素
4. 非空表插入中间位置
*/
template<class T>
LinkList<T>& LinkList<T>::Insert(int k, const T& x)
{
	LinkNode<T>* p = head;
	LinkNode<T>* newNode = new LinkNode<T>;		// 创建一个新节点
	newNode->data = x;
	int len = GetLength();
	if (k < 1 || k > len + 1)
		cout << "下标越界" << endl;
	else
	{
		for (int i = 1; i < k; i++)
		{
			p = p->next;
		}
		newNode->next = p->next;
		p->next = newNode;
	}
	return *this;
}

/*-----------按下标删除--------------
1. 位置
2. k = 1， 头结点next指向第二个
3. 中间
4. 最后一个，n-1节点next指针为null
用GetData先找到位置，能找到就删除
*/
template<class T>
LinkList<T>& LinkList<T>::DeleteByIndex(int k, T& x)
{
	if (GetData(k, x))
	{
		LinkNode<T>* p = head;	// p指向头结点
		LinkNode<T>* q = NULL;	// q指向空地址
		for (int i = 1; i < k; i++)
		{
			p = p->next;
		}
		q = p->next;
		p->next = q->next;
		x = q->data;
		delete q;
	}
	else
		cout << "元素下标越界！" << endl;
	return *this;
}

/*--------------按关键字删除-----------
用Find先找到下标，再按下标删除
*/
template<class T>
LinkList<T>& LinkList<T>::DeleteByKey(const T& x, T& y)
{
	int index = Find(x);
	if (index != 0)
		return DeleteByIndex(index, y);
	else
	{
		cout << "没有此元素，删除失败" << endl;
		return *this;
	}
}

/*------------输出-------------*/
template<class T>
void LinkList<T>::OutPut(ostream& out)
{
	LinkNode<T>* p = head->next;
	while (p != NULL)
	{
		out << p->data << endl;
		p = p->next;
	}
}
// 重载插入运算符<<
template<class T>
ostream& operator<<(ostream& out, LinkList<T>& x) {
	x.OutPut(out);
	return out;
}