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

【数据结构与算法】顺序表增删查改的实现（动态版本+文件操作）附源码

2023-03-14

void arr ps
目录一.前言二.顺序表1.概念及结构2.顺序表结构体的定义3.初始化顺序表，销毁顺序表和打印3.接口a.尾插SepListpushback  头插SepListpushfrontb.尾删 SepListpopback 头删 SepListpopfro

目录

一.前言

二.顺序表

1.概念及结构

2.顺序表结构体的定义

3.初始化顺序表，销毁顺序表和打印

3.接口

a.尾插 SepListpushback   头插 SepListpushfront

b.尾删  SepListpopback  头删  SepListpopfront

c.查询  SepListsearch

d.修改  SepListmodify

三.源码

SepList.h

SepList.c

test.c

四.顺序表的问题及思考

一.前言

其实顺序表的增删查改和前面的通讯录差不多，可以说通讯录的底层原理就是顺序表。如果你会写通讯录，那么顺序表也不是问题。所以这篇文章不会讲得太详细，如果你有不懂的地方，请看前面通讯录的实现过程，那里讲的非常详细。通讯录

二.顺序表

1.概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储；

在数组上完成数据的增删查改。

顺序表分为静态顺序表和动态顺序表，由于静态顺序表的实用性不高，所以博主在此就不讲述了，主要讲解动态顺序表。

2.顺序表结构体的定义

  1. #define INIT_CAPACITY  5   //顺序表的默认容量
  2.  
  3. typedef int SLdatatype;    //使用 typedef 对类型重定义，方便后续修改
  4.  
  5. typedef struct SepList
  6. {
  7. SLdatatype* arr;  //后续对 arr 进行动态内存开辟
  8. int sz;   //记录当前数据的个数
  9. int capacity;  //顺序表的容量
  10. }SepList;

3.初始化顺序表，销毁顺序表和打印

初始化

  1. void download(SepList* ps)   //从文件中读取数据
  2. {
  3. FILE* pf = fopen("SepList.txt", "r");
  4. assert(pf);
  5. while (fscanf(pf, "%d", &ps->arr[ps->sz]) != EOF)
  6. {
  7. ps->sz++;
  8. expcapacity(ps);
  9. }
  10. fclose(pf);
  11. pf = NULL;
  12. }
  13.  
  14. void SepListinit(SepList* ps)
  15. {
  16. ps->arr = (SLdatatype*)calloc(INIT_CAPACITY, sizeof(SLdatatype)); //动态内存开辟默认容量
  17. assert(ps->arr);  //判断是否开辟成功，若失败会直接报错，终止程序的运行
  18. ps->sz = 0;     //初始化当前数据量为1
  19. ps->capacity = INIT_CAPACITY;   //初始成默认容量
  20. download(ps);  //初始化时从文件中读取数据
  21. }

销毁

  1. void SepListdestroy(SepList* ps)  //销毁的同时将数据保存到文件中
  2. {
  3. int i = 0;
  4. FILE* pf = fopen("SepList.txt", "w");
  5. assert(pf);
  6. for (i = 0; i < ps->sz; i++)
  7. {
  8. fprintf(pf, "%d", ps->arr[i]);
  9. }
  10. free(ps->arr);
  11. ps->arr = NULL;
  12. ps->sz = 0;
  13. ps->capacity = INIT_CAPACITY;
  14. fclose(pf);
  15. pf = NULL;
  16. }

打印

  1. void SepListprint(SepList* ps)
  2. {
  3. int i = 0;
  4. for (i = 0; i < ps->sz; i++)
  5. {
  6. printf("%d  ", ps->arr[i]);
  7. }
  8. printf("\n");
  9. }

3.接口

a.尾插 SepListpushback   头插 SepListpushfront

需要注意的是在插入数据前，需要判断顺序表是否已经满了，所以就需要写一个扩容函数，这和通讯录那里得逻辑是一致的。

扩容  expcapacity 

  1. void expcapacity(SepList* ps)
  2. {
  3. if (ps->sz == ps->capacity)
  4. {
  5. SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, sizeof(SLdatatype) * 2 * ps->capacity);   //使用realloc 函数扩容
  6. assert(tmp);
  7. ps->arr = tmp;  //注意要把tmp赋给原来得指针，否则在一些情况下会出问题
  8. ps->capacity = 2 * ps->capacity;
  9. }
  10. }

尾插 SepListpushback

  1. void SepListpushback(SepList* ps, SLdatatype x)  //这个SLdatatype 是我们之前重定义得类型
  2. {
  3. expcapacity(ps);  //判断顺序表是否已满
  4. ps->arr[ps->sz] = x;
  5. ps->sz++;  //当前数据量 +1
  6. }

头插 SepListpushfront

头插就是把当前有的数据全部向后移1位，把第一个位置空出来，此时仍需判断顺序表是否已满。

  1. void SepListpushfront(SepList* ps, SLdatatype x)
  2. {
  3.     expcapacity(ps); 
  4. int end = ps->sz - 1;  //注意这里要 -1 
  5. for (; end >= 0; end--)
  6. {
  7. ps->arr[end + 1] = ps->arr[end];
  8. }
  9. ps->arr[0] = x;  将数据赋给下标为0的位置，完成头插
  10. ps->sz++;
  11. }

b.尾删  SepListpopback  头删  SepListpopfront

在删除前，我们需要判断顺序表中是否有数据，如果没有，那么则不需要删除。

尾删  SepListpopback 

  1. void SepListpopback(SepList* ps)
  2. {
  3. assert(ps->sz > 0);  //判断顺序表中是否有数据，如果没有会直接报错，终止程序的运行
  4. ps->sz--;
  5. }

头删  SepListpopfront

头删就是把所有数据向前移动1位

  1. void SepListpopfront(SepList* ps)
  2. {
  3. assert(ps->sz > 0);
  4. int begain = 0;
  5. for (; begain < ps->sz-1; begain++)
  6. {
  7. ps->arr[begain] = ps->arr[begain + 1];
  8. }
  9. ps->sz--;
  10. }

c.查询  SepListsearch

查询前需要判断顺序表是否有数据。

  1. void SepListsearch(SepList* ps)
  2. {
  3. if (ps->sz == 0)
  4. {
  5. printf("无数据可供查找\n");
  6. return;
  7. }
  8. SLdatatype x = 0;
  9. int count = 0;
  10. SLdatatype* tmp = (SLdatatype*)calloc(ps->sz, sizeof(SLdatatype));  //要查询的数据可能有重复，所以定义一个数组来存储
  11. assert(tmp);
  12. printf("请输入要查询的数据:>");
  13. scanf("%d", &x);
  14. int i = 0,flag = 0;
  15. for (i = 0; i < ps->sz; i++)
  16. {
  17. if (ps->arr[i] == x)
  18. {
  19. flag = 1;
  20. tmp[count++] = i;
  21. }
  22. }
  23. if (flag == 0)
  24. printf("无此数据\n");
  25. else
  26. {
  27. printf("查到了，下标是:> ");
  28. for (i = 0; i < count; i++)
  29. printf("%d  ", tmp[i]);
  30. }
  31. free(tmp);
  32. tmp = NULL;
  33. printf("\n");
  34. }

d.修改  SepListmodify

  1. void SepListmodify(SepList* ps)
  2. {
  3. if (ps->sz == 0)
  4. {
  5. printf("无数据可供修改\n");
  6. return;
  7. }
  8. SLdatatype x = 0;
  9. again:
  10. printf("请输入要修改的数据:>");
  11. scanf("%d", &x);
  12. int i = 0, pos = 0;
  13. int flag = 0;
  14. for (i = 0; i < ps->sz; i++)
  15. {
  16. if (ps->arr[i] == x)
  17. {
  18. flag = 1;
  19. pos = i;
  20. break;
  21. }
  22. }
  23. if (flag == 0)
  24. {
  25. printf("要修改的数据不存在,重新输入\n");
  26. goto again;
  27. }
  28. else
  29. {
  30. printf("开始修改:>");
  31. scanf("%d", &ps->arr[pos]);
  32. printf("修改成功\n");
  33. }
  34. }

三.源码

SepList.h

  1. #pragma once
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <assert.h>
  6.  
  7.  
  8. #define INIT_CAPACITY  5
  9.  
  10. typedef int SLdatatype;
  11.  
  12. typedef struct SepList
  13. {
  14. SLdatatype* arr;
  15. int sz;
  16. int capacity;
  17. }SepList;
  18.  
  19. //初始化
  20. void SepListinit(SepList* ps);
  21. //销毁
  22. void SepListdestroy(SepList* ps);
  23. //扩容
  24. void expcapacity(SepList* ps);
  25. //打印
  26. void SepListprint(SepList* ps);
  27. //尾插
  28. void SepListpushback(SepList* ps, SLdatatype x);
  29. //头插
  30. void SepListpushfront(SepList* ps, SLdatatype x);
  31. //尾删
  32. void SepListpopback(SepList* ps);
  33. //头删
  34. void SepListpopfront(SepList* ps);
  35. //查询
  36. void SepListsearch(SepList* ps);
  37. //修改
  38. void SepListmodify(SepList* ps);

SepList.c

  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include "SepList.h"
  4.  
  5.  
  6. void download(SepList* ps)
  7. {
  8. FILE* pf = fopen("SepList.txt", "r");
  9. assert(pf);
  10. while (fscanf(pf, "%d", &ps->arr[ps->sz]) != EOF)
  11. {
  12. ps->sz++;
  13. expcapacity(ps);
  14. }
  15. fclose(pf);
  16. pf = NULL;
  17. }
  18.  
  19. void SepListinit(SepList* ps)
  20. {
  21. ps->arr = (SLdatatype*)calloc(INIT_CAPACITY, sizeof(SLdatatype));
  22. assert(ps->arr);
  23. ps->sz = 0;
  24. ps->capacity = INIT_CAPACITY;
  25. download(ps);
  26. }
  27.  
  28. void SepListdestroy(SepList* ps)
  29. {
  30. int i = 0;
  31. FILE* pf = fopen("SepList.txt", "w");
  32. assert(pf);
  33. for (i = 0; i < ps->sz; i++)
  34. {
  35. fprintf(pf, "%d", ps->arr[i]);
  36. }
  37. free(ps->arr);
  38. ps->arr = NULL;
  39. ps->sz = 0;
  40. ps->capacity = INIT_CAPACITY;
  41. fclose(pf);
  42. pf = NULL;
  43. }
  44.  
  45. void expcapacity(SepList* ps)
  46. {
  47. if (ps->sz == ps->capacity)
  48. {
  49. SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, sizeof(SLdatatype) * 2 * ps->capacity);
  50. assert(tmp);
  51. ps->arr = tmp;
  52. ps->capacity = 2 * ps->capacity;
  53. }
  54. }
  55.  
  56. void SepListprint(SepList* ps)
  57. {
  58. int i = 0;
  59. for (i = 0; i < ps->sz; i++)
  60. {
  61. printf("%d  ", ps->arr[i]);
  62. }
  63. printf("\n");
  64. }
  65.  
  66. void SepListpushback(SepList* ps, SLdatatype x)
  67. {
  68. expcapacity(ps);
  69. ps->arr[ps->sz] = x;
  70. ps->sz++;
  71. }
  72.  
  73. void SepListpushfront(SepList* ps, SLdatatype x)
  74. {
  75.     expcapacity(ps);
  76. int end = ps->sz - 1;
  77. for (; end >= 0; end--)
  78. {
  79. ps->arr[end + 1] = ps->arr[end];
  80. }
  81. ps->arr[0] = x;
  82. ps->sz++;
  83. }
  84.  
  85. void SepListpopback(SepList* ps)
  86. {
  87. assert(ps->sz > 0);
  88. ps->sz--;
  89. }
  90.  
  91. void SepListpopfront(SepList* ps)
  92. {
  93. assert(ps->sz > 0);
  94. int begain = 0;
  95. for (; begain < ps->sz-1; begain++)
  96. {
  97. ps->arr[begain] = ps->arr[begain + 1];
  98. }
  99. ps->sz--;
  100. }
  101.  
  102. //#define 
  103.  
  104. void SepListsearch(SepList* ps)
  105. {
  106. if (ps->sz == 0)
  107. {
  108. printf("无数据可供删除\n");
  109. return;
  110. }
  111. SLdatatype x = 0;
  112. int count = 0;
  113. SLdatatype* tmp = (SLdatatype*)calloc(ps->sz, sizeof(SLdatatype));
  114. assert(tmp);
  115. printf("请输入要查询的数据:>");
  116. scanf("%d", &x);
  117. int i = 0,flag = 0;
  118. for (i = 0; i < ps->sz; i++)
  119. {
  120. if (ps->arr[i] == x)
  121. {
  122. flag = 1;
  123. tmp[count++] = i;
  124. }
  125. }
  126. if (flag == 0)
  127. {
  128. printf("无此数据\n");
  129. }
  130. else
  131. {
  132. printf("查到了，下标是:> ");
  133. for (i = 0; i < count; i++)
  134. {
  135. printf("%d  ", tmp[i]);
  136. }
  137. }
  138. free(tmp);
  139. tmp = NULL;
  140. printf("\n");
  141. }
  142.  
  143. void SepListmodify(SepList* ps)
  144. {
  145. if (ps->sz == 0)
  146. {
  147. printf("无数据可供修改\n");
  148. return;
  149. }
  150. SLdatatype x = 0;
  151. again:
  152. printf("请输入要修改的数据:>");
  153. scanf("%d", &x);
  154. int i = 0, pos = 0;
  155. int flag = 0;
  156. for (i = 0; i < ps->sz; i++)
  157. {
  158. if (ps->arr[i] == x)
  159. {
  160. flag = 1;
  161. pos = i;
  162. break;
  163. }
  164. }
  165. if (flag == 0)
  166. {
  167. printf("要修改的数据不存在,重新输入\n");
  168. goto again;
  169. }
  170. else
  171. {
  172. printf("开始修改:>");
  173. scanf("%d", &ps->arr[pos]);
  174. printf("修改成功\n");
  175. }
  176. }

test.c

  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include "SepList.h"
  4.  
  5. void menu()
  6. {
  7. printf("|----------------------顺序表----------------------|\n");
  8. printf("||*********************************************** ||\n");
  9. printf("||*******     1.尾插         2.头插        *******||\n");
  10. printf("||*******     3.尾删         4.头删        *******||\n");
  11. printf("||*******     5.查询         6.修改        *******||\n");
  12. printf("||*******     7.打印         0.退出        *******||\n");
  13. printf("||************************************************||\n");
  14. printf("|--------------------------------------------------|\n");
  15. }
  16.  
  17. int main()
  18. {
  19. SepList s;
  20. SepListinit(&s);
  21. int input = 0;
  22. int x = 0;
  23. do
  24. {
  25. menu();
  26. printf("请选择:>");
  27. scanf("%d", &input);
  28. switch (input)
  29. {
  30. case 1:
  31. printf("请输入要插入的数据:>");
  32. scanf("%d", &x);
  33. SepListpushback(&s,x);
  34. break;
  35. case 2:
  36. printf("请输入要插入的数据:>");
  37. scanf("%d", &x);
  38. SepListpushfront(&s, x);
  39. break;
  40. case 3:
  41. SepListpopback(&s);
  42. break;
  43. case 4:
  44. SepListpopfront(&s);
  45. break;
  46. case 5:
  47. SepListsearch(&s);
  48. break;
  49. case 6:
  50. SepListmodify(&s);
  51. break;
  52. case 7:
  53. SepListprint(&s);
  54. break;
  55. case 0:
  56. SepListdestroy(&s);
  57. printf("退出顺序表\n期待您的下次使用\n");
  58. break;
  59. default :
  60. printf("选择错误，重新选择\n");
  61. break;
  62. }
  63. } while (input);
  64. return 0;
  65. }

四.顺序表的问题及思考

问题：
1. 中间/头部的插入删除，时间复杂度为O(N)；
2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗；
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？

   博主将在下一篇关于链表的文章中解决。

🐲👻关于顺序表的讲解就到这里了，若有错误或是建议欢迎小伙伴们指出。🐯🤖

🥰🤩希望小伙伴们可以多多支持博主哦。😍😃

😁😄谢谢你的阅读。😼😸

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