C语言中数据结构——顺序表

简介: 🐰顺序表🏡顺序表的定义🏡顺序表的初始化🏡顺序表空间的检查🏡顺序表中指定位置插入数据🏡顺序表中指定位置删除数据🏡顺序表中的头插数据🏡顺序表中的尾插数据🏡顺序表中的头删数据🏡顺序表中的尾删数据🏡顺序表中查找数据🏡顺序表中改动数据🏡顺序表中的打印数据🏡顺序表中的销毁数据🏡顺序表中的源码🌸main文件🌸头文件test.h🌸test.c文件

🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀

目录

🐰顺序表

🏡顺序表的定义

🏡顺序表的初始化

🏡顺序表空间的检查

🏡顺序表中指定位置插入数据

🏡顺序表中指定位置删除数据

🏡顺序表中的头插数据

🏡顺序表中的尾插数据

🏡顺序表中的头删数据

🏡顺序表中的尾删数据

🏡顺序表中查找数据

🏡顺序表中改动数据

🏡顺序表中的打印数据

🏡顺序表中的销毁数据

🏡顺序表中的源码

🌸main文件

🌸头文件test.h

🌸test.c文件


🐰顺序表

3ACE768D-93EF-434E-BD6B-698A8CF0A0B8.png

🏡顺序表的定义

有两种顺序表的定义,一种是静态的,一种是动态的

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. }

🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区,我们共同探讨,共同学习,共同进步。谢谢大家! 🌸🌸🌸



相关文章
|
16天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
15天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
57 16
|
15天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
65 8
|
17天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
44 4
|
19天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
19天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
50 3
|
19天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
17天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
38 0
|
存储 缓存 C语言
数据结构——双链表(C语言)
数据结构——双链表(C语言)
|
5月前
|
存储
数据结构——双向链表(C语言版)
数据结构——双向链表(C语言版)
31 2