数据结构：次序表

目次

一、数据结构的概念
什么是数据结构？
为什么还必要数据结构？
二、次序表
1.线性表
2.次序表和数组的区别
3.次序表分类
3.1静态次序表
3.2动态次序表
三、动态次序表的实现

---

一、数据结构的概念

什么是数据结构？

数据结构可以划分为数据和结构两部门。
数据是我们一样平常生活中相称广泛的东西，好比数值1、2、3...，教务系统的教师、学生、姓名等肉眼可以看到的一切事物都可以是数据；
而结构则是基于该数据的某一特点使用数组进行划分的方式，好比1、2、3等都是数字，而教师、学生等都是学校这个数组的内容。
   数据结构是盘算机存储、构造数据的方式，数组是最基础的数据结构。
  为什么还必要数据结构？

这时候就有了疑问，既然有了数组还为什么必要数据结构？
在我们一样平常现实工作当中我们会遇到大量的数据，如果只依靠数组这个基础的数据结构来进行数据处置惩罚的话会用到大量的人力物力，还会浪费很多的时间成本，也就是说数组无法满足复杂操作的运算。
二、次序表

1.线性表

线性表是n个具有相同特性的数据元素组成的有限序列，常见的线性表有：栈、队列、次序表、链表等等。
线性表在逻辑上是线性结构，也就说是一连的⼀条直线。但是在物理结构上并不⼀定是一连的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
比方：蔬菜可以分为绿叶类、瓜类、菌菇类等，线性表是指具有部门特性相同的一类数据结构的集合。
2.次序表和数组的区别

次序表和数组的唯一区别就是次序表对数组进行了封装，它增加了“增“、“删”、”查“、”改”四个功能接口。
3.次序表分类

3.1静态次序表

3.2动态次序表

三、动态次序表的实现

1. //SeqList.c 示例代码
2. #define _CRT_SECURE_NO_WARNINGS 1
3. #include"SeqList.h"
4. //初始化顺序表
5. void SLInit(SL* sl)
6. {
7.         sl->arr = NULL;
8.         sl->capacity = sl->length = 0;
9. }
10. //检查顺序表空间是否足够
11. void CheckCapacity(SL* sl)
12. {
13.         int Newcapacity = 0;
14.         if (sl->capacity == sl->length)
15.         {
16.                 if (sl->capacity == 0)
17.                 {
18.                         Newcapacity = 2 * sl->capacity;
19.                 }
20.                 else
21.                 {
22.                         Newcapacity = 4;
23.                 }
24.                 SLDatatype* tmp = (SLDatatype*)realloc(sl->arr, Newcapacity * sizeof(SLDatatype));
25.                 sl->arr = tmp;
26.                 sl->capacity = Newcapacity;
27.         }
28. }
31. //头插
32. void SLPushFront(SL* ps, int x)
33. {
34.         assert(ps);
35.         CheckCapacity(ps);
36.         memmove(ps->arr+1, ps->arr, ps->length * sizeof(SLDatatype));
37.         ps->arr[0] = x;
38.         ps->length++;
39. }
40. //头删
41. void SLPopFront(SL* ps)
42. {
43.         assert(ps);
44.         assert(ps->length);
45.         memmove(ps->arr, ps->arr + 1, ps->length * sizeof(SLDatatype));
46.         ps->length--;
47. }
48. //尾插
49. void SLPushBack(SL* ps, int x)
50. {
51.         assert(ps);
52.         CheckCapacity(ps);
53.         ps->arr[ps->length++] = x;
54. }
55. //尾删
56. void SLPopBack(SL* ps)
57. {
58.         assert(ps);
59.         assert(ps->length);
60.         ps->length--;
61. }
62. //打印数据
63. void SLPrint(SL* p)
64. {
65.         for (int i = 0; i < p->length; i++)
66.         {
67.                 printf("%d ", p->arr[i]);
68.         }
69. }
70. //顺序表销毁
71. void SLDestory(SL* ps)
72. {
73.         if (ps->arr)
74.         {
75.                 free(ps->arr);
76.         }
77.         ps->arr = NULL;
78.         ps->capacity = 0;
79.         ps->length = 0;
80. }

复制代码

1. //SeqList.h示例代码
2. #pragma once
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<string.h>
6. #include<assert.h>
7. //创建顺序表
8. typedef int SLDatatype;
9. typedef struct SeqList
10. {
11.         SLDatatype* arr;
12.         SLDatatype length;//真正被填充的大小
13.         SLDatatype capacity;//被开辟的有效空间
14. }SL;
15. //初始化顺序表
16. void SLInit(SL* sl);
17. //检查顺序表空间是否满足插入条件
18. void CheckCapacity(SL* sl);
19. //头插
20. void SLPushFront(SL* ps, int x);
21. //头删
22. void SLPopFront(SL* ps);
23. //打印
24. void SLPrint(SL* p);
25. //尾插
26. void SLPushBack(SL* ps, int x);
27. //尾删
28. void SLPopBack(SL* ps);
29. //顺序表销毁
30. void SLDestory(SL* ps);

复制代码

1. //test.c示例代码
2. #define _CRT_SECURE_NO_WARNINGS 1
3. #include"SeqList.h"
4. void SLTest01()
5. {
6.         SL sl;
7.         SLInit(&sl);
8.         //测试
9.         SLPushBack(&sl, 1);
10.         SLPushBack(&sl, 2);
11.         SLPushBack(&sl, 3);
12.         SLPushBack(&sl, 4);
13.         SLPushFront(&sl, 5);
14.         SLPushFront(&sl, 6);
15.         SLPushFront(&sl, 7);
16.         //SLPopFront(&sl);
17.         //SLPopFront(&sl);
18.         SLPopBack(&sl);
19.         //打印顺序表
20.         SLPrint(&sl);
21.         //销毁顺序表
22.         SLDestory(&sl);
23. }
24. int main()
25. {
26.         SLTest01();
27.         return 0;
28. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。