深圳幻海软件技术有限公司 欢迎您！
更多

顺序表的基本操作(超详细）

2023-04-12

int cout endl
目录前言一、顺序表的定义二、顺序表的C语言描述三、顺序表中基本操作的实现 3.1结构初始化操作3.1.1构造一个空的线性表L3.1.2构造一个含n个数据元素的线性表L时间复杂度:O(n)3.2销毁结构操作3.2.1销毁一个顺序表 3.3加工型操作3.3.1改变数据元素的值3.3.

目录

前言

一、顺序表的定义

二、顺序表的 C 语言描述

三、顺序表中基本操作的实现 

3.1结构初始化操作

3.1.1构造一个空的线性表 L

3.1.2构造一个含 n 个数据元素的线性表 L

时间复杂度:O(n)

3.2销毁结构操作

3.2.1销毁一个顺序表  

3.3加工型操作

3.3.1改变数据元素的值

3.3.2插入数据元素

3.3.3删除数据元素

3.3.4线性表置空 

3.4引用型操作

3.4.1线性表判空

3.4.2求线性表的长度

3.4.3求前驱

3.4.4求后继

3.4.5求线性表中某个元素

3.4.6定位函数

3.4.7遍历线性表

四、顺序表代码实现

五、结果

六、总结 

前言

本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》

一、顺序表的定义

由n(n≥0)个类型相同的数据元素构成的有限序列，称为线性表。线性表中数据元素的个数n称为线性表的长度。  n=0时，称为空表。

线性表的顺序存储表示是指用一组地址连续的存储单元依次存放线性表中的数据元素，即顺序表。

二、顺序表的 C 语言描述

代码如下（示例）：

  1. //存储结构 #define  MAXSIZE 100     
  2. //最大长度 typedef  struct 
  3. {
  4.     int *elem;
  5.     int length;
  6. } SqList;  // 顺序表

三、顺序表中基本操作的实现 

3.1结构初始化操作

3.1.1构造一个空的线性表 L

时间复杂度：O(1) 

  1. void InitList(SqList &L)
  2. {
  3. L.elem=new int[MAXSIZE];
  4. if (!L.elem) exit(0);//未分配成功 
  5. L.length=0;
  6. cout<<"初始化成功"<<endl;
  7. }

3.1.2构造一个含 n 个数据元素的线性表 L

时间复杂度:O(n)

空间复杂度:S(n)=O(1)

  1. void CreateList(SqList &L,int n)
  2. {
  3. int e;
  4. if(n>MAXSIZE)
  5. {
  6. cout<<"超出最大长度"<<endl; 
  7. }
  8. else
  9. {
  10. for(int i=0;i<n;i++)
  11. {
  12. cout<<"第"<<i+1<<"次的元素数据"<<endl;
  13. cin>>e;
  14. L.elem[i]=e;
  15. L.length++;
  16. }
  17. } 
  18. }

3.2销毁结构操作

3.2.1销毁一个顺序表  

不空才释放空间，空的话就不需要释放了

注意用new来开辟空间，则用delete释放空间

而用malloc来开辟空间，则使用free来释放空间

  1. void DestoryList(SqList& L)
  2. {
  3. if (L.elem) delete L.elem;//不空才释放空间，空的话就不用了
  4. }

3.3加工型操作

3.3.1改变数据元素的值

随机存取

时间复杂度：O(1)

空间复杂度：O(1)

  1. void PutElem(SqList &L,int i,int &e )
  2. {
  3. int t;
  4. cout<<"输入你想改成的值"<<endl;
  5. cin>>t;
  6. if(i<1||i>L.length)cout<<"i的位置不对"<<endl;
  7. else
  8. {
  9. e=L.elem[i-1];
  10. L.elem[i-1]=t;
  11. cout<<"修改成功"<<endl;
  12. }
  13. }

3.3.2插入数据元素

在顺序表L的第 i 个元素之前插入新的元素e

时间复杂度T(n)=O(n)

顺序表的空间复杂度S(n)=O(1)

没有占用辅助空间

  1. // 在顺序表L的第 i 个元素之前插入新的元素e,
  2. void ListInsert(SqList &L,int i,int e)
  3. { 
  4. if(i<1||i>L.length+1) cout<<"位置不合法\n"<<endl; //位置不合法
  5. else
  6. {
  7. if(L.length == MAXSIZE) cout<<"空间已满\n"<<endl;  //空间已满
  8. else
  9. {
  10. for(int j=L.length-1;j>=i-1;j--)
  11. L.elem[j+1]=L.elem[j]; //插入位及之后元素下移
  12. L.elem[i-1]=e;
  13. L.length++; 
  14. }
  15. }
  16. }

3.3.3删除数据元素

时间复杂度T(n)=O(n)
顺序表的空间复杂度S(n)=O(1)

  1. // 被删除元素之后的元素左移
  2. // ListDelete
  3. //T(n)=O(n)
  4. //顺序表的空间复杂度S(n)=O(1)
  5. void ListDelete(SqList &L, int i,int &e) 
  6. {
  7. if((i<1)||(i>L.length))cout<<"删除位置不对"<<endl; 
  8. else
  9. {
  10. e=L.elem[i-1];
  11. for(int j=i;j<L.length;j++)
  12. L.elem[j-1]=L.elem[j];
  13. L.length--;
  14. }
  15. }

3.3.4线性表置空 

还占用原空间，只是把表长置为0，原来的数据都清除

  1. //清空线性表
  2. void ClearList(SqList& L)
  3. {
  4. L.length = 0;//线性表长度置为0，但是还占用空间
  5. }

3.4引用型操作

3.4.1线性表判空

用L.length来判断是否为空，长度为0则为空，返回1，不为空则返回0

  1. //判断线性表是否为空
  2. int ListEmpty(SqList L)
  3. {
  4. if (!L.length)return 1;//L.length==0返回true
  5. else return 0;
  6. }

3.4.2求线性表的长度

返回L.length即可得到长度

  1. //求线性表长度
  2. int ListLength(SqList& L)
  3. {
  4. return L.length;
  5. }

3.4.3求前驱

cur_e为序号，即第几个元素，则元素下标为cur_e-1，那么它的前驱元素下标为cur_e-2

  1. // （求前驱）
  2. void PriorElem(SqList L,int cur_e,int &pre_e)
  3. {
  4. if(cur_e<1||cur_e>L.length)cout<<"cur_e的位置不对"<<endl;
  5. else
  6. {
  7. pre_e=L.elem[cur_e-2];
  8. cout<<"求前驱成功"<<endl;
  9. }
  10. }

3.4.4求后继

cur_e为序号，即第几个元素，则元素下标为cur_e-1，那么它的后继元素下标为cur_e

  1. //（求后继）
  2. void NextElem(SqList L,int cur_e,int &next_e )
  3. {
  4. if(cur_e<1||cur_e>L.length)cout<<"cur_e的位置不对"<<endl;
  5. else
  6. {
  7. next_e=L.elem[cur_e];
  8. cout<<"求后驱成功"<<endl; 
  9. }
  10. }

3.4.5求线性表中某个元素

i表示序号，是第几个元素的意思，对应下标是i-1

  1. //取值（根据位置i获取相应位置数据元素的内容）
  2. //i表示的是序号，是第几个元素，对应下标是i-1 
  3. void GetElem(SqList L,int i,int &e)
  4. {
  5. if(i<1||i>L.length)cout<<"i的位置不对"<<endl;
  6. else
  7. {
  8. e=L.elem[i-1];//随机存取， 
  9. }
  10. }

3.4.6定位函数

顺序表上的查找操作的实现
在顺序表中查询第一个满足判定条件的数据元素，
若存在，则返回它的位序，否则返回 0 
最好情况： T(n)=O(1)    最坏情况： T(n)=O(n)
平均情况：假设每个元素的查找概率相等.
ASL=(1+2+……n)/n=(n+1)/2
T(n)=O(n) 

  1. //顺序表上的查找操作的实现
  2. //在顺序表中查询第一个满足判定条件的数据元素，
  3. //若存在，则返回它的位序，否则返回 0 
  4. // 最好情况： T(n)=O(1)    最坏情况： T(n)=O(n)
  5. //平均情况：假设每个元素的查找概率相等.
  6. //ASL=(1+2+……n)/n=(n+1)/2
  7. //T(n)=O(n) 
  8. int LocateElem(SqList L,int e) 
  9. {
  10. for (int i=0;i<L.length;i++)
  11.       if(L.elem[i]==e) return i+1;
  12. return 0;
  13. }

3.4.7遍历线性表

时间复杂度:O(n)

空间复杂度:S(n)=O(1)

  1. void ListTraverse(SqList L)
  2. {
  3. for(int i=0;i<L.length;i++)
  4. cout<<i+1<<"位置的数据为"<<L.elem[i]<<endl;
  5. cout<<"遍历成功"<<endl;
  6. }

四、顺序表代码实现

代码如下（示例）：

  1. #include <iostream>
  2. using namespace std;
  3. #define  MAXSIZE 100     //最大长度
  4. typedef  struct sqlist{
  5. int *elem;
  6. int length;
  7. }SqList;  // 顺序表
  8. //初始化顺序表
  9. //时间复杂度：O(1) 
  10. void InitList(SqList &L)
  11. {
  12. L.elem=new int[MAXSIZE];
  13. if (!L.elem) exit(0);//未分配成功 
  14. L.length=0;
  15. cout<<"初始化成功"<<endl;
  16. }
  17. //构造一个含 n 个数据元素的线性表 L
  18. void CreateList(SqList &L,int n)
  19. {
  20. int e;
  21. if(n>MAXSIZE)
  22. {
  23. cout<<"超出最大长度"<<endl; 
  24. }
  25. else
  26. {
  27. for(int i=0;i<n;i++)
  28. {
  29. cout<<"第"<<i+1<<"次的元素数据"<<endl;
  30. cin>>e;
  31. L.elem[i]=e;
  32. L.length++;
  33. }
  34. } 
  35. }    
  36. //销毁一个线性表  
  37. void DestoryList(SqList& L)
  38. {
  39. if (L.elem) delete L.elem;//不空才释放空间，空的话就不用了
  40. }
  41.  
  42. //清空线性表
  43. void ClearList(SqList& L)
  44. {
  45. L.length = 0;//线性表长度置为0，但是还占用空间
  46. }
  47. //求线性表长度
  48. int ListLength(SqList& L)
  49. {
  50. return L.length;
  51. }
  52. //判断线性表是否为空
  53. int ListEmpty(SqList L)
  54. {
  55. if (!L.length)return 1;//L.length==0返回true
  56. else return 0;
  57. }
  58. //( 改变数据元素的值 )
  59. void PutElem(SqList &L,int i,int &e )
  60. {
  61. int t;
  62. cout<<"输入你想改成的值"<<endl;
  63. cin>>t;
  64. if(i<1||i>L.length)cout<<"i的位置不对"<<endl;
  65. else
  66. {
  67. e=L.elem[i-1];
  68. L.elem[i-1]=t;
  69. cout<<"修改成功"<<endl;
  70. }
  71. }
  72. // （求前驱）
  73. void PriorElem(SqList L,int cur_e,int &pre_e)
  74. {
  75. if(cur_e<1||cur_e>L.length)cout<<"cur_e的位置不对"<<endl;
  76. else
  77. {
  78. pre_e=L.elem[cur_e-2];
  79. cout<<"求前驱成功"<<endl;
  80. }
  81. }
  82. //（求后继）
  83. void NextElem(SqList L,int cur_e,int &next_e )
  84. {
  85. if(cur_e<1||cur_e>L.length)cout<<"cur_e的位置不对"<<endl;
  86. else
  87. {
  88. next_e=L.elem[cur_e];
  89. cout<<"求后驱成功"<<endl; 
  90. }
  91. }
  92. //（ 遍历线性表）
  93. void ListTraverse(SqList L)
  94. {
  95. for(int i=0;i<L.length;i++)
  96. cout<<i+1<<"位置的数据为"<<L.elem[i]<<endl;
  97. cout<<"遍历成功"<<endl;
  98. }
  99. //取值（根据位置i获取相应位置数据元素的内容）
  100. //i表示的是序号，是第几个元素，对应下标是i-1 
  101. void GetElem(SqList L,int i,int &e)
  102. {
  103. if(i<1||i>L.length)cout<<"i的位置不对"<<endl;
  104. else
  105. {
  106. e=L.elem[i-1];//随机存取， 
  107. }
  108. } 
  109. //顺序表上的查找操作的实现
  110. //在顺序表中查询第一个满足判定条件的数据元素，
  111. //若存在，则返回它的位序，否则返回 0 
  112. // 最好情况： T(n)=O(1)    最坏情况： T(n)=O(n)
  113. //平均情况：假设每个元素的查找概率相等.
  114. //ASL=(1+2+……n)/n=(n+1)/2
  115. //T(n)=O(n) 
  116. int LocateElem(SqList L,int e) 
  117. {
  118. for (int i=0;i<L.length;i++)
  119.       if(L.elem[i]==e) return i+1;
  120. return 0;
  121. } 
  122. // ListInsert
  123. // 在顺序表L的第 i 个元素之前插入新的元素e,
  124. void ListInsert(SqList &L,int i,int e)
  125. { 
  126. if(i<1||i>L.length+1) cout<<"位置不合法\n"<<endl; //位置不合法
  127. else
  128. {
  129. if(L.length == MAXSIZE) cout<<"空间已满\n"<<endl;  //空间已满
  130. else
  131. {
  132. for(int j=L.length-1;j>=i-1;j--)
  133. L.elem[j+1]=L.elem[j]; //插入位及之后元素下移
  134. L.elem[i-1]=e;
  135. L.length++; 
  136. }
  137. }
  138. } 
  139. // 被删除元素之后的元素左移
  140. // ListDelete
  141. //T(n)=O(n)
  142. //顺序表的空间复杂度S(n)=O(1)
  143. void ListDelete(SqList &L, int i,int &e) 
  144. {
  145. if((i<1)||(i>L.length))cout<<"删除位置不对"<<endl; 
  146. else
  147. {
  148. e=L.elem[i-1];
  149. for(int j=i;j<L.length;j++)
  150. L.elem[j-1]=L.elem[j];
  151. L.length--;
  152. }
  153. } 
  154. void menu()
  155. {
  156. cout<<"**********************************************************"<<endl;
  157. cout<<"1.构造一个空的线性表 L"<<endl;
  158. cout<<"2.构造一个含 n 个数据元素的线性表 L"<<endl;
  159. cout<<"3.销毁线性表 L"<<endl;
  160. cout<<"4.改变数据元素的值"<<endl;
  161. cout<<"5.插入数据元素"<<endl;
  162. cout<<"6. 删除数据元素"<<endl;
  163. cout<<"7.线性表置空"<<endl;
  164. cout<<"8.线性表判空"<<endl;
  165. cout<<"9.求线性表的长度"<<endl;
  166. cout<<"10.求前驱"<<endl;
  167. cout<<"11.求后继"<<endl;
  168. cout<<"12.求线性表中某个元素"<<endl;
  169. cout<<"13.定位函数"<<endl;
  170. cout<<"14.遍历线性表"<<endl;
  171. cout<<"15.退出"<<endl;
  172. cout<<"**********************************************************"<<endl;
  173. }
  174. int main()
  175. {
  176. int choice;
  177. SqList L;
  178. while(1)
  179. {
  180. menu();
  181. cout<<"请输入你的选择"<<endl;
  182. cin>>choice;
  183. switch(choice)
  184. {
  185. case 1:
  186. InitList(L);
  187. break;
  188. case 2:
  189. int n;
  190. cout<<"输入你需要多少个节点"<<endl;
  191. cin>>n;
  192. CreateList(L,n);
  193. break;
  194. case 3:
  195. DestoryList(L);
  196. break;
  197. case 4:
  198. int i1,e1;
  199. cout<<"输入要改变的元素序号"<<endl;
  200. cin>>i1;
  201. PutElem(L,i1,e1);
  202. cout<<"原来数据的值为"<<e1<<endl;
  203. break;
  204. case 5:
  205. int i2,e2;
  206. cout<<"输入要插入的元素位置跟数据"<<endl;
  207. cin>>i2>>e2;
  208. ListInsert(L,i2,e2);
  209. break;
  210. case 6:
  211. int i3,e3;
  212. cout<<"输入要删除的元素位置"<<endl;
  213. cin>>i3;
  214. ListDelete(L,i3,e3);
  215. cout<<"原来删除的元素数据:"<<e3<<endl;
  216. break;
  217. case 7:
  218. ClearList(L);
  219. break;
  220. case 8:
  221. if(ListEmpty(L))cout<<"顺序表为空"<<endl;
  222. else cout<<"顺序表不为空"<<endl;
  223. break;
  224. case 9:
  225. cout<<"顺序表的长度为："<<ListLength(L)<<endl;
  226. break;
  227. case 10:
  228. int i4,e4;
  229. cout<<"输入元素序号"<<endl;
  230. cin>>i4;
  231. PriorElem(L,i4,e4);
  232. cout<<"该元素的前驱节点的数据："<<e4<<endl;
  233. break;
  234. case 11:
  235. int i5,e5;
  236. cout<<"输入元素序号"<<endl;
  237. cin>>i5;
  238. NextElem(L,i5,e5);
  239. cout<<"该元素的后继节点的数据："<<e5<<endl;
  240. break;
  241. case 12:
  242. int i6,e6;
  243. cout<<"输入元素序号"<<endl;
  244. cin>>i6;
  245. GetElem(L,i6,e6); 
  246. cout<<"该元素的数据："<<e6<<endl;
  247. break;
  248. case 13:
  249. int e7;
  250. cout<<"输入定位的元素数据"<<endl;
  251. cin>>e7;
  252. cout<<"定位到的位置为："<<LocateElem(L,e7)<<endl;
  253. break;
  254. case 14:
  255. ListTraverse(L);
  256. break;
  257. case 15:
  258. exit(0);
  259. default:
  260. cout<<"输入错误，请重新输入"<<endl;
  261. break;
  262. }
  263. }
  264. return 0;
  265. }

五、结果

图一

图二

图三

图四

图五

图六

 图七

图八

 

图九

图十 

 图十一

 ​​​

 图十二

图十三

 

图十四

 

图十五

 ​​​

 图十六

六、总结 

        看完王卓老师的视频后，我把顺序表的基本操作都实现了一遍，使我对顺序表有了更好的理解。顺序表有好的一面，比如存储密度大，可以随机存取表中任一元素，但是也有不好的一面，比如在插入、删除某一元素时，需要移动大量元素 浪费存储空间 属于静态存储形式，数据元素的个数不能自由扩充。针对这个缺点，我将在下一篇把自己学到的链表介绍给大家。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览43870 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪