🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀
目录
🐰顺序表
🏡顺序表的定义
有两种顺序表的定义,一种是静态的,一种是动态的
1.静态顺序表的定义
1. 静态顺序表 2. 1.空间是固定的,没有办法存储超过空间的数据 3. 2.如果空间开辟大了,浪费空间 4. 不推荐使用静态顺序表,没有实际用途 5. #define N 10 6. typedef int SLDatatype; 7. 8. struct SeqList 9. { 10. int a[N]; 11. int size; 12. };
2.动态顺序表的定义
1. 动态定义的顺序表,有效规避了静态的不足 2. typedef int SLDatatype; 3. typedef struct SeqList 4. { 5. SLDatatype* a;//有效数据 6. SLDatatype size;//存储的有效数据个数 7. SLDatatype capacity;//存放数据的最大容量 8. }SL;
🏡顺序表的初始化
初始时,顺序表动态开辟了4个空间,有效数据的个数为0,最大容量为4
1. void SLInit(SL* psl) 2. { 3. assert(psl); 4. psl->a=(SLDatatype*)malloc(sizeof(SLDatatype)*4);//初始化时开辟4个SLDatatype类型的空间给a 5. if(psl->a==NULL) 6. { 7. perror("malloc fail"); 8. return ; 9. } 10. psl->size=0; 11. psl->capacity=4; 12. }
🏡顺序表空间的检查
我们在给顺序表插入数据之前,我们应该检查一下顺序表的空间是否充足,如果充足我们就插入数据,如果不充足,就开辟更大的空间,然后再进行插入数据
1. void SLCheckCapacity(SL* psl) 2. { 3. assert(psl); 4. if(psl->size==psl->capacity) 5. { 6. SLDatatype* tmp=(SLDatatype*)realloc(psl->a,sizeof(SLDatatype)*psl->capacity*2);//在原来的的空间,扩为原来空间的二倍 7. if(tmp==NULL) 8. { 9. perror("realloc fail"); 10. return ; 11. } 12. else 13. { 14. psl->a=tmp; 15. psl->capacity=psl->capacity*2; 16. } 17. } 18. }
🏡顺序表中指定位置插入数据
我们可以在自己指定的位置插入数据,这里需要注意的是,我们指定的位置必须合法,也就说,只能从头到尾之间插入数据,且尾也可以插入数据
1. void SLInsert(SL* psl,int pos,SLDatatype x) 2. { 3. assert(psl); 4. assert(pos>=0&&pos<=psl->size);//判断插入位置是否符合合法 5. SLCheckCapacity(psl); 6. int end=psl->size-1; 7. while(end>=pos) 8. { 9. psl->a[end+1]=psl->a[end]; 10. end--; 11. } 12. psl->a[pos]=x; 13. psl->size++; 14. }
🏡顺序表中指定位置删除数据
我们可以在自己指定的位置删除数据,这里需要注意的是,我们指定的位置必须合法,也就说,只能从头到尾之间删除数据
1. void SLEarse(SL* psl,int pos) 2. { 3. assert(psl); 4. assert(pos>=0&&pos<psl->size);//判断插入位置是否符合合法 5. int start=pos+1; 6. while(start<psl->size) 7. { 8. psl->a[start-1]=psl->a[start]; 9. start++; 10. } 11. psl->size--; 12. }
🏡顺序表中的头插数据
顺序表中的头插数据有两种方法
1.第一种方法
这种方法就是将最后的数据移动到后一个位置,然后倒数第二个数据往最后一个位置移动,依此类推,直到第一个数据移到第二个位置,然后在第一个位置插入数据
1. void SLPushFront(SL* psl,SLDatatype x) 2. { 3. assert(psl); 4. SLCheckCapacity(psl); 5. //从后往前移动数据 6. int end=psl->size-1; 7. while(end>=0) 8. { 9. psl->a[end+1]=psl->a[end]; 10. end--; 11. } 12. psl->a[0]=x; 13. psl->size++; 14. }
1.第二种方法
这种方法复用了顺序表中指定位置插入数据
1. void SLPushFront(SL* psl,SLDatatype x) 2. { 3. assert(psl); 4. SLInsert(psl,0,x); 5. }
🏡顺序表中的尾插数据
顺序表中的尾插数据有两种方法
1.第一种
直接在最后一个数据的位置后面插入数据
1. void SLPushBack(SL* psl,SLDatatype x) 2. { 3. assert(psl); 4. SLCheckCapacity(psl); 5. psl->a[psl->size]=x; 6. psl->size++; 7. }
2.第二种
这种方法复用了顺序表中指定位置插入数据
1. void SLPushBack(SL* psl,SLDatatype x) 2. { 3. assert(psl); 4. SLInsert(psl,psl->size,x); 5. }
🏡顺序表中的头删数据
顺序表中的头删数据有两种方法
1.第一种:
将第二个数据放到第一个数据的位置,把第三个的数据放到第二个数据最开始的位置,以此类推,直到最后一个数据放到倒数第二个数据最开始的位置
1. void SLPopFront(SL* psl) 2. { 3. assert(psl); 4. assert(psl->size>0); 5. //从前往后移动 6. int start=0; 7. while(start<psl->size-1) 8. { 9. psl->a[start]=psl->a[start+1]; 10. start++; 11. } 12. psl->size--; 13. }
2.第二种:
这种方法复用了顺序表中指定位置删除数据
1. void SLPopFront(SL* psl) 2. { 3. assert(psl); 4. SLEarse(psl,0); 5. }
🏡顺序表中的尾删数据
顺序表中的头删数据有两种方法
1.第一种
1. void SLPophBack(SL* psl) 2. { 3. assert(psl); 4. //(1)if是温柔处理顺序表为空 5. if(psl->size==0) 6. { 7. printf("顺序表数据为空,不能尾删\n"); 8. return ; 9. } 10. else 11. { 12. psl->size--; 13. } 14. //(2)暴力解法 15. assert(psl->size>0); 16. psl->size--; 17. }
2.第二种
这种方法复用了顺序表中指定位置删除数据
1. void SLPophBack(SL* psl) 2. { 3. assert(psl); 4. SLEarse(psl,psl->a[psl->size-1]); 5. }
🏡顺序表中查找数据
如果找到数据我们就返回它的下标位置,如果找不到就返回-1,这里这种算法有一点缺陷,就是如果数据中有重复的数据,则只会返回这个数据第一次出现的位置
1. int SLFind(SL* psl,SLDatatype x) 2. { 3. assert(psl); 4. for(int i=0;i<psl->size;i++) 5. { 6. if(psl->a[i]==x) 7. { 8. return i; 9. } 10. } 11. return -1; 12. }
🏡顺序表中改动数据
直接在想要改变数据的位置,直接赋新值,但是要注意想要改变数据的位置是合法的
1. void SLModify(SL* psl,int pos,SLDatatype x) 2. { 3. assert(psl); 4. assert(pos>=0&&pos<psl->size); 5. psl->a[pos]=x; 6. }
🏡顺序表中的打印数据
依次打印出顺序表中存储的数据
1. void SLPrint(SL* psl) 2. { 3. assert(psl); 4. for(int i=0;i<psl->size;i++) 5. { 6. printf("%d ",psl->a[i]); 7. } 8. printf("\n"); 9. }
🏡顺序表中的销毁数据
将动态分配的空间归还给系统,将数据个数置为0,最大容量置为0
1. void SLDestroy(SL* psl) 2. { 3. assert(psl); 4. free(psl->a); 5. psl->a=NULL; 6. psl->size=0; 7. psl->capacity=0; 8. }
🏡顺序表中的源码
为了更形象观察顺序表,这里使用了菜单,如果想要方便调试,建议大家不要使用菜单
🌸main文件
1. //顺序表 2. //顺序表的本质就是一个数组 3. //链表不支持二分查找,数组可以 4. 5. //顺序表的增、删、查、改 6. 7. #include"test.h" 8. void menu(void) 9. { 10. printf("****************顺序表****************\n"); 11. printf(" 1.头插数据 2.尾插数据 \n"); 12. printf(" 3.头删数据 4.尾删数据 \n"); 13. printf(" 5.自定义插数据 6.自定义删数据 \n"); 14. printf(" 7.查找数据 8.修改数据 \n"); 15. printf(" 9.打印数据 x.销毁数据 \n"); 16. printf(" e.退出 \n"); 17. printf("*************************************\n"); 18. } 19. void test(void) 20. { 21. SL s1; 22. SLInit(&s1); 23. char input=0; 24. do 25. { 26. menu(); 27. printf("请选择:>"); 28. scanf("%c",&input); 29. if(input=='1') 30. { 31. SLDatatype x=0; 32. printf("请输入插入的数据\n"); 33. scanf("%d",&x); 34. SLPushFront(&s1,x); 35. printf("数据完成插入^_^\n"); 36. } 37. else if(input=='2') 38. { 39. SLDatatype x=0; 40. printf("请输入插入的数据\n"); 41. scanf("%d",&x); 42. SLPushFront(&s1,x); 43. printf("数据完成插入^_^\n"); 44. } 45. else if(input=='3') 46. { 47. SLPophBack(&s1); 48. printf("数据完成删除@_@\n"); 49. } 50. else if(input=='4') 51. { 52. SLPophBack(&s1); 53. printf("数据完成删除@_@\n"); 54. } 55. else if(input=='5') 56. { 57. int pos=0; 58. int x=0; 59. printf("请输入你想要插入数据的位置\n"); 60. scanf("%d",&pos); 61. printf("请输入插入的数据\n"); 62. scanf("%d",&x); 63. SLInsert(&s1,pos,x); 64. printf("数据完成插入^_^\n"); 65. } 66. else if(input=='6') 67. { 68. int pos=0; 69. printf("请输入你想要删除数据的位置\n"); 70. scanf("%d",&pos); 71. SLEarse(&s1,pos); 72. printf("数据完成删除@_@\n"); 73. } 74. else if(input=='7') 75. { 76. int x=0; 77. printf("请输入查找的数据\n"); 78. scanf("%d",&x); 79. int num=SLFind(&s1,x); 80. if(num!=-1) 81. printf("数据的位置为%d\n",num); 82. else 83. printf("顺序表里没有此数据\n"); 84. } 85. else if(input=='8') 86. { 87. int pos=0; 88. printf("请输入你想要修改数据的位置\n"); 89. scanf("%d",&pos); 90. int x=0; 91. printf("请输入修改的数据\n"); 92. scanf("%d",&x); 93. SLModify(&s1,pos,x); 94. printf("修改数据成功O_o\n"); 95. } 96. else if(input=='9') 97. { 98. SLPrint(&s1); 99. printf("打印完成...\n"); 100. } 101. else if(input=='x') 102. { 103. SLDestroy(&s1); 104. printf("销毁数据成功...\n"); 105. } 106. else if(input=='e') 107. { 108. printf("退出顺序表...\n"); 109. } 110. else 111. { 112. printf("无此选项,请重新选择\n"); 113. } 114. getchar(); 115. }while(input!='e'); 116. } 117. int main() 118. { 119. test(); 120. return 0; 121. }
🌸头文件test.h
1. #ifndef test_h 2. #define test_h 3. #include <stdio.h> 4. #include<stdlib.h> 5. #endif /* test_h */ 6. 7. #include<assert.h> 8. 9. //静态顺序表 10. //1.空间是固定的,没有办法存储超过空间的数据 11. //2.如果空间开辟大了,浪费空间 12. //不推荐使用静态顺序表,没有实际用途 13. //#define N 10 14. //typedef int SLDatatype; 15. // 16. //struct SeqList 17. //{ 18. // int a[N]; 19. // int size; 20. //}; 21. 22. 23. 24. typedef int SLDatatype; 25. typedef struct SeqList 26. { 27. SLDatatype* a; 28. SLDatatype size;//存储的有效数据个数 29. SLDatatype capacity;//容量 30. }SL; 31. 32. 33. //STL的命名风格(C++) 34. //顺序表的初始化 35. void SLInit(SL* psl); 36. //打印顺序表 37. void SLPrint(SL* psl); 38. //销毁顺序表 39. void SLDestroy(SL* psl); 40. //尾插数据 41. void SLPushBack(SL* psl,SLDatatype x); 42. //头插数据 43. void SLPushFront(SL* psl,SLDatatype x); 44. //尾删数据 45. void SLPophBack(SL* psl); 46. //头删数据 47. void SLPopFront(SL* psl); 48. //在pos位置插入一个数据 49. void SLInsert(SL* psl,int pos,SLDatatype x); 50. //在pos位置删除一个数据 51. void SLEarse(SL* psl,int pos); 52. //查找数据 53. //找到了返回下标,没找到返回-1 54. int SLFind(SL* psl,SLDatatype x); 55. //修改指定位置的数据 56. void SLModify(SL* psl,int pos,SLDatatype x);
🌸test.c文件
1. #include"test.h" 2. void SLInit(SL* psl) 3. { 4. assert(psl); 5. psl->a=(SLDatatype*)malloc(sizeof(SLDatatype)*4);//初始化时开辟4个SLDatatype类型的空间给a 6. if(psl->a==NULL) 7. { 8. perror("malloc fail"); 9. return ; 10. } 11. psl->size=0; 12. psl->capacity=4; 13. } 14. 15. void SLDestroy(SL* psl) 16. { 17. assert(psl); 18. free(psl->a); 19. psl->a=NULL; 20. psl->size=0; 21. psl->capacity=0; 22. } 23. void SLPrint(SL* psl) 24. { 25. assert(psl); 26. for(int i=0;i<psl->size;i++) 27. { 28. printf("%d ",psl->a[i]); 29. } 30. printf("\n"); 31. } 32. //插入的时候要去判断容量是否充足 33. //可以写一个检查容量是否充足的函数 34. //如果空间不足,就需要扩容 35. 36. void SLCheckCapacity(SL* psl) 37. { 38. assert(psl); 39. if(psl->size==psl->capacity) 40. { 41. SLDatatype* tmp=(SLDatatype*)realloc(psl->a,sizeof(SLDatatype)*psl->capacity*2);//在原来的的空间,扩为原来空间的二倍 42. if(tmp==NULL) 43. { 44. perror("realloc fail"); 45. return ; 46. } 47. else 48. { 49. psl->a=tmp; 50. psl->capacity=psl->capacity*2; 51. } 52. } 53. } 54. //尾插数据 55. //尾插数据的原理:在最后一个数据后面再添加一个数据 56. void SLPushBack(SL* psl,SLDatatype x) 57. { 58. assert(psl); 59. // SLCheckCapacity(psl); 60. // psl->a[psl->size]=x; 61. // psl->size++; 62. 63. SLInsert(psl,psl->size,x); 64. } 65. //头插数据 66. void SLPushFront(SL* psl,SLDatatype x) 67. { 68. assert(psl); 69. SLCheckCapacity(psl); 70. //从后往前移动数据 71. int end=psl->size-1; 72. while(end>=0) 73. { 74. psl->a[end+1]=psl->a[end]; 75. end--; 76. } 77. psl->a[0]=x; 78. psl->size++; 79. // SLInsert(psl,0,x); 80. } 81. //尾删数据 82. void SLPophBack(SL* psl) 83. { 84. assert(psl); 85. // if是温柔处理顺序表为空 86. // if(psl->size==0) 87. // { 88. // printf("顺序表数据为空,不能尾删\n"); 89. // return ; 90. // } 91. // else 92. // { 93. // psl->size--; 94. // } 95. // 暴力解法 96. // assert(psl->size>0); 97. // psl->size--; 98. 99. SLEarse(psl,psl->a[psl->size-1]); 100. } 101. //头删数据 102. void SLPopFront(SL* psl) 103. { 104. assert(psl); 105. //方法一: 106. // assert(psl->size>0); 107. // //从前往后移动 108. // int start=0; 109. // while(start<psl->size-1) 110. // { 111. // psl->a[start]=psl->a[start+1]; 112. // start++; 113. // } 114. // psl->size--; 115. 116. //方法二: 117. SLEarse(psl,0); 118. } 119. 120. void SLInsert(SL* psl,int pos,SLDatatype x) 121. { 122. assert(psl); 123. assert(pos>=0&&pos<=psl->size);//判断插入位置是否符合合法 124. SLCheckCapacity(psl); 125. int end=psl->size-1; 126. while(end>=pos) 127. { 128. psl->a[end+1]=psl->a[end]; 129. end--; 130. } 131. psl->a[pos]=x; 132. psl->size++; 133. } 134. void SLEarse(SL* psl,int pos) 135. { 136. assert(psl); 137. assert(pos>=0&&pos<psl->size);//判断插入位置是否符合合法 138. int start=pos+1; 139. while(start<psl->size) 140. { 141. psl->a[start-1]=psl->a[start]; 142. start++; 143. } 144. psl->size--; 145. } 146. int SLFind(SL* psl,SLDatatype x) 147. { 148. assert(psl); 149. for(int i=0;i<psl->size;i++) 150. { 151. if(psl->a[i]==x) 152. { 153. return i; 154. } 155. } 156. return -1; 157. } 158. void SLModify(SL* psl,int pos,SLDatatype x) 159. { 160. assert(psl); 161. assert(pos>=0&&pos<psl->size); 162. psl->a[pos]=x; 163. }
🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区,我们共同探讨,共同学习,共同进步。谢谢大家! 🌸🌸🌸