线性表之单链表C 实现

    **线性表之单链表**

线性表是数据结构中最简单的基本数据结构。线性表的使用和维护都很简单,这一特点使其成为很多算法的基础。数组、链表、栈、队列是4中最常见的线性表,其外部行为和接口都各有特色。

一、头文件:LinkedList.h

线性表(List):零个或多个数据元素的一有限序列

  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 }
  • 序列:元素之间是有顺序的,若元素存在多个则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。
  • 有限:元素个数是有限制的

二、测试线性表之单链表的源文件:TestLinkedList.cpp

图片 1

 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 }

线性表

三、运行示例结果

线性表元素的个数n(n>0)定义为线性表的长度,当n=0时称为空表。

图片 2

图片 3

 

星座列表

在较复杂的线性表中,一个数据元素可以由若干个数据项组成。

图片 4

复杂线性表中数据元素可由若干数据项组成

线性表的抽象数据类型

ADT 线性表(List)
Data
  线性表的数据对象集合为{a1,a2,a3...an},每个元素的类型均为DataType。
  其中除第一个元素a1外,每个元素有且只有一个直接前驱元素。
  除了最后一个元素an外,每个元素有且只有一个直接后继元素。
  数据元素之间的关系是一对一的关系。
Operation
  InitList(*L) 初始化建立一个空的线性表L
  ListEmpty(L) 若线性表为空则返回true否则返回false
  ClearList(*L) 将线性表清空
  GetElem(L,i,*e) 将线性表L中的第i个位置元素值返回给e
  LocateElem(L,e) 在线性表L中查找与给定值e相等的元素,若查找成功返回该元素在表中序号表示成功,否则返回0表示失败。
  ListInsert(*L, i, e) 在线性表L中的第i个位置插入新元素e
  ListDelete(*L, i, *e) 删除线性表L中第i个位置元素并用e返回其值
  ListLength(L) 返回线性表L的元素个数
endADT

本文由美洲杯在哪买球发布于计算机教程,转载请注明出处:线性表之单链表C 实现

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。