数据结构-单链表

Computer

      整个数据结构分为三个部分，Node类，LinkList类，SeqList类，Main函数，其中Main函数是测试两种链表的代码书写是否成立，LinkList类中的每个结点都是一个Node的实例，SeqList类单独成一例，用数组存储，已经写成模板的形式，我忘了以前不知道在哪里看过说用类模板的时候不能够将声明单独出来放在头文件中，所以我把声明和实现放在一起了。
      Node.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
template<typename T>
class Node {
public:
	Node() {}
	Node(T data, Node<T> *ptr) :data(data), next(ptr) {}
	~Node() {}
	T getData();
	void setData(T newData);
	Node<T> *getNext();
	void setNext(Node<T> *ptr);
private:
	T data;
	Node<T> *next;
};
template<typename T>
T Node<T>::getData() {
	return data;
}
template<typename T>
void Node<T>::setData(T newData) {
	data = newData;
}
template<typename T>
Node<T> *Node<T>::getNext() {
	return next;
}
template<typename T>
void Node<T>::setNext(Node<T> *ptr) {
	next = ptr;
}

      LinkList.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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<iostream>
#include"Node.cpp"
template<typename T>
class LinkList {
public:
	LinkList();
	LinkList(T array[], int n);
	~LinkList();
	void printList();
	void Insert(int i, T x);
	int Length();
	T Get(int i);
	Node<T> *getFirst() { return first; };
	int Locate(T x);
	T Delete(int i);
	void reverse();
	void add(T x);
private:
	Node<T> *first;
};
template<typename T>
LinkList<T>::LinkList() {
	first = new Node<T>();
	first->setNext(NULL);
}
//尾插法构造链表
template<typename T>
LinkList<T>::LinkList(T array[], int n) {
	first = new Node<T>();
	//first->setData(NULL);
	first->setNext(NULL);
	Node<T> *s, *r;
	r = first;
	for (int i = 0; i < n; i++) {
		s = new Node<T>;
		s->setData(array[i]);
		r->setNext(s);
		r = s;
	}
}
//头插法构造链表
//template<typename T>
//LinkList<T>::LinkList(T array[], int n) {
//	first = new Node<T>();
//	first->setData(NULL);
//	first->setNext(NULL);
//	Node<T> *s;
//	for (int i = 0; i < n; i++) {
//		s = new Node<T>;
//		s->setData(array[i]);
//		s->setNext(first->getNext());
//		first->setNext(s);
//	}
//}
template<typename T>
LinkList<T>::~LinkList() {
	while (first != NULL) {
		Node<T> *q = first;
		first = first->getNext();
		delete q;
	}
}
template<typename T>
void LinkList<T>::printList() {
	Node<T> *p = first->getNext();
	while (p != NULL) {
		cout << p->getData() << " ";
		p = p->getNext();
	}
	cout << endl;
}
template<typename T>
void LinkList<T>::Insert(int index, T x) {
	Node<T> *p = first;
	Node<T> *s;
	int count = 0;
	while (p != NULL && count < index - 1) {
		p = p->getNext();
		count++;
	}
	if (p == NULL) {
		throw "在插入的位置前面有空结点，不能在所需序号处插入结点！";
	}
	else {
		s = new Node<T>;
		s->setData(x);
		s->setNext(p->getNext());
		p->setNext(s);
	}
}
template<typename T>
int LinkList<T>::Length() {
	int count = 0;
	Node<T> *p = first->getNext();
	while (p != NULL) {
		count++;
		p = p->getNext();
	}
	return count;
}
template<typename T>
T LinkList<T>::Get(int index) {
	Node<T> *p = first->getNext();
	int count = 1;
	while (p != NULL && count < index) {
		p = p->getNext();
		count++;
	}
	if (p == NULL) {
		throw "该位置为空结点！";
	}
	else {
		return p->getData();
	}
}
template<typename T>
int LinkList<T>::Locate(T x) {
	Node<T> *p = first->getNext();
	int count = 1;
	while (p != NULL) {
		if (p->getData() == x) {
			return count;
		}
		p = p->getNext();
		count++;
	}
	return 0;
}
template<typename T>
T LinkList<T>::Delete(int index) {
	Node<T> *p = first;
	int count = 0;
	while (p != NULL && count < index - 1) {
		p = p->getNext();
		count++;
	}
	if (p == NULL || p->getNext() == NULL) {
		throw "被删的结点不存在！";
	}
	else {
		Node<T> *q = p->getNext();
		T x = q->getData();
		p->setNext(q->getNext());
		delete q;
		return x;
	}
}
template<typename T>
void LinkList<T>::reverse() {
	//头结点
	Node<T> *p = first;
	//第一个结点
	Node<T> *q = p->getNext();
	Node<T> *r;
	while (q->getNext() != NULL) {
		r = q->getNext();
		if (q == first->getNext()) {
			q->setNext(NULL);
			p = q;
			q = r;
		}
		else {
			//p->q->r
			q->setNext(p);
			p = q;
			q = r;
		}
	}
	q->setNext(p);
	first->setNext(q);
}
template<typename T>
void LinkList<T>::add(T x) {
	int length = Length();
	Insert(length+1, x);
}

      SeqList.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
#include<iostream>
const int MaxSize = 10;
template<typename T>
class SeqList {
public:
	SeqList() { length = 0; }
	SeqList(T array[], int n);
	~SeqList() {}
	int Length() { return length; }
	T Get(int index);
	int Locate(T x);
	void Insert(int index, T x);
	T Delete(int index);
	void PrintList();
	void reverse();
private:
	T data[MaxSize];
	int length;
};
template<typename T>
SeqList<T>::SeqList(T array[], int n) {
	if (n > MaxSize) {
		throw "数组的长度大于顺序表的长度！";
	}
	else {
		for (int i = 0; i < n; i++) {
			data[i] = array[i];
		}
		length = n;
	}
}
template<typename T>
T SeqList<T>::Get(int index) {
	if (index <  1 || index > length) {
		throw "索引值不正确！";
	}
	else {
		return data[index - 1];
	}
}
template<typename T>
int SeqList<T>::Locate(T x) {
	for (int i = 0; i < length; i++) {
		if (data[i] == x) {
			return i + 1;
		}
	}
	return 0;
}
template<typename T>
void SeqList<T>::Insert(int index, T x) {
	if (length >= MaxSize) {
		throw"顺序表已满！";
	}
	else if (index < 1 || index > length + 1) {
		throw"索引值超出当前已有数据位置!";
	}
	else {
		for (int j = length; j >= index; j--) {
			data[j] = data[j - 1];
		}
		data[index - 1] = x;
		length++;
	}
}
template<typename T>
T SeqList<T>::Delete(int index) {
	if (length == 0) {
		throw "顺序表长度为0！";
	}
	else if(index < 1 || index > length) {
		throw"索引表超出当前已有数据位置！";
	}
	else {
		T x = data[index - 1];
		for (int j = index; j < length; j++) {
			data[j - 1] = data[j];
		}
		length--;
		return x;
	}
}
template<typename T>
void SeqList<T>::PrintList() {
	for (int i = 0; i < length; i++) {
		cout << data[i] << " ";
	}
	cout << endl;
}
template<typename T>
void SeqList<T>::reverse() {
	for (int i = 0; i < length / 2 + 1; i++) {
		T temp = data[i];
		data[i] = data[length - 1 - i];
		data[length - 1 - i] = temp;
	}
}

      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
#include"LinkList.cpp"
#include"SeqList.cpp"
using namespace std;
/*
	单链表main函数
*/
int main() {
	//构造测试
	int array1[] = { 1,3,5,7,9,10,12,14,16,18,20 };
	int array2[] = { 2,4,6,8,11,13,15,16,17,19,20 };
	LinkList<int> List1(array1, 11);
	//遍历测试
	List1.printList();
	LinkList<int> List2(array2, 11);
	//遍历测试
	List2.printList();
	//mergeLinkList(List1, List2);
	////Insert测试
	//try {
	//	List.Insert(2, 6);
	//	List.Insert(7, 6);
	//	List.printList();
	//}
	//catch (char *s) {
	//	cout << s << endl;
	//}
	////Length测试
	//cout << "线性表的长度是：" << List.Length() << endl;
	////Get测试
	//try {
	//	cout << "第5位的数字是：" << List.Get(5) << endl;
	//	cout << "第8位的数字是：" << List.Get(8) << endl;
	//}
	//catch (char *s) {
	//	cout << s << endl;
	//}
	////Locate测试
	//cout << List.Locate(6) << endl;
	////Delete测试
	//try{
	//	List.Delete(5);
	//	List.printList();
	//}
	//catch (char *s) {
	//	cout << s << endl;
	//}
	//reverse测试
	//List.reverse();
	//List.printList();
	system("pause");
	return 0;
}
/*
	顺序表main函数
*/
//int main() {
//	int array[] = { 1,2,4,3,5,6,7 };
//	//测试
//	try {
//		SeqList<int> List(array, 7);
//		List.PrintList();
//		cout << "顺序表的长度是：" << List.Length() << endl;
//		cout << "顺序表要查找的值是：" << List.Get(3) << endl;
//		cout << "顺序表中3所在的位置是:" << List.Locate(3) << endl;
//		cout << endl;
//
//		List.Insert(4, 8);
//		List.PrintList();
//		cout << "顺序表的长度是：" << List.Length() << endl;
//		cout << endl;
//
//		List.Delete(4);
//		List.PrintList();
//		cout << "顺序表的长度是：" << List.Length() << endl;
//		cout << endl;
//
//		List.reverse();
//		List.PrintList();
//	}
//	catch (char *s) {
//		cout << s << endl;
//	}
//	system("pause");
//	return 0;
//}

文章目录
|