线性表之单链表C++实现

  1 //单链表是用一组任意的存储单元存放线性表的元素，这组单元可以是连续的也可以是不连续的，甚至可以是零散分布在内存中的任意位置。
  2 //单链表头文件
  3 #include<iostream>
  4 using namespace std;
  5 //定义单链表结点-结构体类型
  6 template<class DataType>
  7 struct Node
  8 {
  9 　　//数据域，存放该结点的数据
 10 　　DataType data;
 11 　　//指针域，指向下一个结点
 12 　　Node<DataType> *next;
 13 };
 14 
 15 template<class DataType>
 16 class LinkedList{
 17 public:
 18 　　//单链表无参构造器
 19 　　LinkedList();
 20 　　//单链表有参构造器
 21 　　LinkedList(DataType array[], int n);
 22 　　LinkedList(int n, DataType array[]);
 23 　　//单链表析构函数
 24 　　~LinkedList();
 25 　　//获取单链表的长度
 26 　　int GetLength();
 27 　　//查找单链表指定元素的序号
 28 　　int GetLocal(DataType x);
 29 　　//获取单链表指序号的元素
 30 　　DataType GetElement(int index);
 31 　　//单链表中在指定位置插入指定的元素
 32 　　void Insert(int index, DataType x);
 33 　　//在单链表中删除指定位置的元素
 34 　　DataType Delete(int index);
 35 　　//按序号输出单链表中的元素
 36 　　void PrintLinkedList();
 37 
 38 private :
 39 　　//声明单链表的头指针
 40 　　Node<DataType> *first;
 41 };
 42 
 43 //实现单链表的无参构造函数
 44 template<class DataType>
 45 LinkedList<DataType>::LinkedList()
 46 {
 47 　　first = new Node<DataType>;
 48 　　first->next = NULL;
 49 }
 50 
 51 //头插法建立单链表
 52 template<class DataType>
 53 LinkedList<DataType>::LinkedList(int n,DataType array[])
 54 {
 55 　　//初始化一个空链表
 56 　　first = new Node<DataType>;
 57 　　first->next = NULL;
 58 　　for (int i = 0; i < n; i++)
 59 　　{
 60 　　　　//为每一个数组元素都申请新结点
 61 　　　　Node<DataType> *s = new Node<DataType>;
 62 　　　　//数组元素赋值给结点数据域
 63 　　　　s->data = array[i];
 64 　　　　//将结点插入到头结点之前
 65 　　　　s->next = first->next;
 66 　　　　first->next = s;
 67 
 68 　　}
 69 }
 70 
 71 //尾插法建立单链表
 72 template<class DataType>
 73 LinkedList<DataType>::LinkedList(DataType array[], int n)
 74 {
 75 　　//生成头结点
 76 　　first = new Node<DataType>;
 77 　　//定义尾结点
 78 　　Node<DataType> *r = first;
 79 　　for (int i = 0; i < n; i++)
 80 　　{
 81 　　　　//为每一个数组元素申请一个结点
 82 　　　　Node<DataType> *s = new Node<DataType>;
 83 　　　　//把数组元素赋值给结点的数据域
 84 　　　　s->data = array[i];
 85 　　　　//将每一个结点追加到终端结点之后
 86 　　　　r->next = s;
 87 　　　　r = s;
 88 　　}
 89 　　//尾结点尾NULL
 90 　　r->next = NULL;
 91 }
 92 
 93 //实现单链表的析构函数
 94 template<class DataType>
 95 LinkedList<DataType>::~LinkedList()
 96 {
 97 　　//声明工作指针
 98 　　Node<DataType> *q;
 99 　　while (first != NULL)
100 　　{
101 　　　　//暂存被释放的结点
102 　　　　q = first;
103 　　　　//让头指针指向要释放结点的下一个结点
104 　　　　first = first->next;
105 　　　　delete q;
106 　　}
107 }
108 
109 //实现单链表插入:在指定的位置插入指定的元素
110 template<class DataType>
111 void LinkedList<DataType>::Insert(int index, DataType x)
112 {
113 　　//定义工作指针
114 　　Node<DataType> *p = first->next;
115 　　//定义计数器，初始值为0
116 　　int count = 0;
117 　　while (p != NULL &&count < index - 1)
118 　　{
119 　　　　//工作指针后移
120 　　　　p = p->next;
121 　　　　count ++;
122 　　}
123 　　//找到 index-1 的位置
124 　　if (p == NULL)
125 　　{
126 　　　　throw "插入的位置有误";
127 　　}
128 　　else
129 　　{
130 　　　　//申请一个新结点
131 　　　　Node<DataType> *s;
132 　　　　s= new Node<DataType>;
133 　　　　//其数据域为 x
134 　　　　s->data = x;
135 　　　　//在新结点的指针域存放工作指针p的指针域
136 　　　　s->next = p->next;
137 　　　　//将结点s插入到p结点之后
138 　　　　p->next = s;
139 　　}
140 }
141 
142 //实现单链表的按值查找，返回指定元素在单链表中的序号（如不存在，则返回0）
143 template<class DataType>
144 int LinkedList<DataType>::GetLocal(DataType x)
145 {
146 　　//定义工作指针
147 　　Node<DataType> *p = first->next;
148 　　//定义计数器，初始值是1
149 　　int count = 1;
150 　　//查找序号所对应的位置
151 　　while (p != NULL)
152 　　{
153 　　　　if (p->data == x)
154 　　　　{
155 　　　　　　return count;
156 　　　　}
157 　　　　//工作指针后移
158 　　　　p = p->next;
159 　　　　//计数器加1
160 　　　　count++;
161 　　}
162 　　//如果找不到该元素，则返回0
163 　　return 0;
164 }
165 
166 //实现单链表按位查找，返回指定位置的元素
167 template<class DataType>
168 DataType LinkedList<DataType>::GetElement(int index)
169 {
170 　　//定义工作指针
171 　　Node<DataType> *p = first->next;
172 　　//定义计数器，初始值是1
173 　　int count = 1;
174 　　//查找序号所对应的位置
175 　　while (p != NULL&&count < index)
176 　　{
177 　　　　//工作指针后移
178 　　　　p = p->next;
179 　　　　//计数器加1
180 　　　　count++;
181 　　}
182 　　//如果找到单链表的末尾，还找不到指定的位置，则抛出异常
183 　　if (p == NULL)
184 　　{
185 　　　　throw "查找的位置有误";
186 　　}
187 　　else
188 　　{
189 　　　　//当找到合适的位置时，返回该位置上的元素
190 　　　　return p->data;
191 　　}
192 
193 }
194 
195 //实现获取单链表的长度
196 template<class DataType>
197 int LinkedList<DataType>::GetLength()
198 {
199 　　//定义计数器，用来计算单链表的长度
200 　　int count = 0;
201 　　//定义工作指针
202 　　Node<DataType> *p = first->next;
203 　　while (p != NULL)
204 　　{
205 　　　　p = p->next;
206 　　　　count++;
207 　　}
208 　　return count;
209 
210 }
211 
212 //实现单链表的按序号输出元素
213 template<class DataType>
214 void LinkedList<DataType>::PrintLinkedList()
215 {
216 　　//声明工作指针
217 　　Node<DataType> *p;
218 　　//初始化工作指针
219 　　p = first->next;
220 　　while(p != NULL)
221 　　{
222 　　　　cout << p->data << " ";
223 　　　　//工作指针向后移动
224 　　　　p = p->next;
225 　　}
226 　　cout << endl;
227 }
228 
229 //实现单链表的删除
230 template<class DataType>
231 DataType LinkedList<DataType>::Delete(int index)
232 {
233 　　Node<DataType> *p = first->next;
234 　　int count = 0;
235 　　//查找第 index-1 位置结点
236 　　while (p != NULL&&count < index - 1)
237 　　{
238 　　　　p = p->next;
239 　　　　count++;
240 　　}
241 　　//如果能找到
242 　　if (p == NULL || p->next == NULL)
243 　　{
244 　　　　throw "删除的位置有误";
245 　　}
246 　　else
247 　　{
248 　　　　Node<DataType> *q = p->next;
249 　　　　DataType x = q->data;
250 　　　　p->next = q->next;
251 　　　　delete q;
252 　　　　return x;
253 　　}
254 }

 1 #include<iostream>
 2 #include "LinkedList.h"
 3 using namespace std;
 4 void show()
 5 {
 6 　　cout << "---------------------------------------" << endl;
 7 }
 8 int main()
 9 {
10 　　int array[] = { 1, 3, 5, 2, 7, 6, 9, 8, 10, 4};
11 　　//声明单链表
12 　　LinkedList<int> linkedList = LinkedList<int>(10,array);
13 　　cout << "输出单链表：" << endl;
14 　　linkedList.PrintLinkedList();
15 　　show();
16 　　cout << "单链表的长度:" << linkedList.GetLength() << endl;
17 　　cout << "单链表中第5个元素是：" << linkedList.GetElement(5) << endl;
18 　　cout << "单链表中元素5的位置是：" << linkedList.GetLocal(5) << endl;
19 　　show();
20 　　cout << "在单链表的第5个位置上插入元素22" << endl;
21 　　linkedList.Insert(5, 22);
22 　　cout << "输出单链表：" << endl;
23 　　linkedList.PrintLinkedList();
24 　　cout << "单链表的长度:" << linkedList.GetLength() << endl;
25 　　show();
26 　　cout << "删除第5位置的元素" << endl;
27 　　linkedList.Delete(5);
28 　　cout << "输出单链表：" << endl;
29 　　linkedList.PrintLinkedList();
30 　　cout << "单链表的长度:" << linkedList.GetLength() << endl;
31 　　show();
32 　　return 0;
33 }