数据结构(次序表)

数据结构概述

什么是数据结构

数据结构：数据结构就是计算机存储，构造，管理数据的方式方法
数据结构的范例

①根据数据的逻辑结构划分(数据间关系)

• 集合:数据结构的元素之间除了“同属一个构造”之外，别无其他关系
  
• 线性数据结构：数据之间“一对一”的关系，数据具有唯一的前驱和后继，典型代表是链表
  
• 非线性数据结构:数据之间不具有唯一的前驱和后继。例如：二维数组，二叉树…，典型代表是二叉树
  
  
  
  ②根据数据在内存中的存储方式划分
  
• 次序结构：各个元素存储在连续的内存空间，典型代表是数组
  
• 链式结构：各个元素存储在不连续的内存空间，典型代表是链表
  
• 索引结构：元素在存储时，不仅存储元素数据，还建立元素附加的索引表来标识元素的地点
  
• 哈希(散列)结构:元素在存储时，为元素提供关键字，在元素访问时，可根据关键字来访问数据
  

常见的数据结构

链表 次序表 树 图 映射 栈 队列
线性表

概念

​ 对于一组拥有n个数据元素的线性表，其严酷数学界说是：其中任何一个数据元素 ai，有且仅有一个直接前驱 ai-1，有且仅有一个直接后继ai+1 。首元素a0无直接前驱，尾元素an-1 无直接后继。满足这种数学关系的一组数据，当中的数据是一个挨着一个的，常被称为一对一关系。反之，如果数据之间的关系不是一对一的，就黑白线性的
举例

生存中的线性表例子非常多，比如一个班级中的以学号编排的弟子，一座图书馆中的以序号编排的图书、一条正常列队等候的队列、一摞从上到下堆叠的餐盘，这些都是线性表。他们的特点都是：除了首尾两个元素，其余任何一个元素前后都对应相邻的另一个元素。
   注意：
  线性表是一种数据内部的逻辑关系，与存储形式无关
  线性表既可以采用连续的次序存储（次序表），也可以采用离散的链式存储（链表）
  次序表

根本概念

• 次序表:次序存储的线性表
  
• 链式表：链式存储的线性表，简称链表
  

次序存储就是将数据存储到一片连续的内存中，在C语言环境下，可以是具名的栈数组，大概是匿名的堆数组
​ 存储方式不仅仅只是提供数据的存储空间，而是必须要能体现数据之间的逻辑关系。当采用次序存储的方式来存放数据时，唯一能用来表达数据间本身的逻辑关系的就是存储位置。比如队列中的两个人，小明和小花，如果小明在逻辑上排在相邻的小花的前面，那么在存储位置上也必须把小明存放在相邻的小花的前面
根本操纵

• 次序表设计
  

​ 一般而言，为了方便操纵次序表，必要一个专门管理次序表的“管理结构体”，管理结构体中一般会包罗：

1. 1. 顺序表总容量
2. 1. 顺序表当前最末元素下标位置
3. 1. 顺序表指针

复制代码

下面是管理结构体示例代码：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <unistd.h>
4. #include <string.h>
6. typedef struct
7. {
8.     int capacity;//顺序表容量
9.     int last;        //最末元素下标
10.     int* data;        //顺序表，以整型数据为例
11. }sequenceList;

复制代码

• 初始化
  

​ 所谓初始化就是建立一个不包罗任何元素的次序表，设置好管理结构体中的表的总容量、末元素下标，申请好次序表内存空间等系列准备工作
下面是初始化次序表的示例代码：

1. sequenceList *init_list(int cap)
2. {
3.     sequenceLits *list = malloc(sizeof(sequenceList));
4.     if(list != NULL)
5.     {
6.         list -> data = malloc(sizeof(int)*cap);
7.         if(list -> data == NULL)
8.         {
9.             free(list);
10.             return NULL;
11.         }
12.         list -> capacity = cap;
13.         list -> last = -1;
14.     }
15.    
16.     return list;
17. }

复制代码

测试

1. int main()
2. {
3.     sequenceList *list = init_list(10);
4.    
5.     if(list == NULL)
6.     {
7.         perror("初始化顺序表失败!");
8.         return -1;
9.     }
10.     else
11.     {
12.         printf("初始化顺序表成功!\n");
13.     }
14. }

复制代码

• 增删节点
  

​ 在次序表中增加一个数据，可以有多种方式，比如在原数组的末尾增加，大概在原数组的头部增加，大概在数组中心恣意一个位置增加。根据实际必要来定
下面以在次序表头部增删数据为例，示例代码如下：

1. //判定顺序表是否为空
2. bool isEmpty(sequenceList *s)
3. {
4.     return s ->last == -1;
5. }
7. //判断顺序表是否已满
8. bool isFull(sequenceList *s)
9. {
10.     return s->last == s->capacity-1;
11. }
13. //在顺序表表头插入一个新数据
14. bool insert(sequenceLits *s,int data)
15. {
16.     if(isFull(s))
17.         return false;
18.    
19.     //将原有数据全部往后挪一位
20.     for(int i = s->last;i>=0;i--)
21.         s->data[i+1] = s->data[i];
22.    
23.     //将新数据置入表头
24.     s->data[0] = data;
25.     s->last++;
26.    
27.     return true;
28. }
30. //将顺序表表头的数据删除掉
31. bool removeNode(sequenceLits *s)
32. {
33.     if(isEmpty(s))
34.         rerurn false;
35.    
36.     //将所有数据全部往前挪一位
37.     for(int i = 0;i<s->last;i++)
38.         s->data[i] = s->data[i+1];
39.    
40.     s->last--;
41.     return true;
42. }

复制代码

• 销毁次序表
  

​ 一个次序表最后不再必要，应当要释放其所占用的内存空间，这被称为次序表的销毁
下面是销毁操纵的示例代码:

1. void destroy(sequenceList *s)
2. {
3.     if(s == NULL)
4.         rerurn;
5.    
6.     free(s->data);
7.     free(s);
8. }

复制代码

完备代码

• seqlist.h
  

1. #ifndef _SEQLIST_H//防止头文件重复
2. #define _SEQLIST_H
4. #include <stdio.h>
5. #include <stdlib.h>
6. #include <string.h>
7. #include <stdbool.h>
9. //定义一个顺序表的结构体
10. typedef struct
11. {
12.     int capacity; //顺序表容量
13.     int last;     //最末元素下标
14.     int *data;    //顺序表数据， {0,0,0}
15. } SequenceList;
17. /*
18. * 初始化顺序表
19. * @param cap 初始化容量
20. */
22. SequenceList *init_list(int cap);
24. /*
25. *判断顺序表是否为空(删除的时候判断用)
26. *@param list 待判断的顺序表
27. */
28. bool is_empty(SequenceList *list);
31. /*
32. *判断顺序表是否已满(插入的时候判断用)
33. *@param list 待判断的顺序表
34. */
35. bool is_full(SequenceList *list);
38. /*
39. *向顺序表插入数据(头插法)
40. * @param list 待插入的顺序表
41. * @param data 待插入的数据
42. */
43. bool insert(SequenceList *list,int data);
45. /**
46. * 遍历顺序表
47. * @param list 待插入的顺序表
48. */
49. void show(SequenceList *list);
51. /**
52. * 删除顺序表数据
53. * @param list 待删除的顺序表
54. * @param data 待删除数据
55. */
56. bool remove_node(SequenceList *list,int data);
58. /**
59. * 释放内存
60. * @param list 待释放的顺序表
61. */
62. void destroy(SequenceList *list);
64. #endif

复制代码

• seqlist.c
  

1. #include "seqlist.h"
3. /**
4. * 初始化顺序表
5. * @param cap 初始化容量
6. */
7. SequenceList *init_list(int cap)
8. {
9.     // 创建顺序表（堆内存）
10.     SequenceList *list = malloc(sizeof(SequenceList));
11.     if(list!=NULL)
12.     {
13.         // 给顺序表中的元素分配存储空间（顺序表就是数组，数据是存储在元素中的）
14.         list->data = malloc(sizeof(int) * cap);
15.         // 校验元素空间是否分配成功
16.         if(list->data == NULL)
17.         {
18.             free(list);
19.             return NULL;
20.         }
21.         // 初始化
22.         list->capacity = cap;
23.         list->last = -1;
24.     }
25.     return list;
26. }
28. /**
29. * 判断顺序表是否为空（删除的时候判断用）
30. */
31. bool is_empty(SequenceList *list)
32. {
33.     return list->last == -1;
34. }
36. /**
37. * 判断顺序表是否已满（插入的时候判断用）
38. */
39. bool is_full(SequenceList *list)
40. {
41.     return list->last == list->capacity -1;
42. }
44. /**
45. * 向顺序表插入数据（头插法）
46. * @param list 待插入的顺序表
47. * @param data 待插入的数据
48. */
49. bool insert(SequenceList *list, int data)
50. {
51.     // 插入数据前，先判断是否已满
52.     if(is_full(list))
53.         return false;
55.     // 将原有的数据全部后移一位
56.     for(int i = list->last; i >= 0; i--)
57.     {
58.          list->data[i+1] = list->data[i];
59.     }
61.     // 将新数据置入表头（也就是索引0的位置）
62.     list->data[0] = data;
63.     list->last++;
64. }
67. /**
68. * 遍历顺序表
69. * @param list 待插入的顺序表
70. */
71. void show(SequenceList *list)
72. {
73.     // 判断顺表表是否为空
74.     if(is_empty(list))
75.        return;
77.     // 使用for循环进行遍历
78.     for(int i = 0; i <= list->last; i++)
79.     {
80.         printf("%d\t",list->data[i]);
81.     }
82.     printf("\n");
83. }
86. /**
87. * 删除顺序表数据
88. * @param list 待删除的顺序表
89. * @param data 待删除数据
90. */
92. bool remove_node(SequenceList *list, int data)
93. {
94.     // 判断是否为空
95.     if(is_empty(list))
96.         return false;
98.     // 找到要删除数据（节点）的位置（下标）
99.     int i, pos = -1;
100.     // 通过一个循环，查找数据对应的位置
101.     for(i = 0; i <= list->last; i++)
102.     {
103.         if(list->data[i]== data)
104.         {
105.             pos = i;
106.             break;// 找到之后，就结束循环
107.         }
109.     }
110.     // 找不到要删除的数据
111.     if(i > list->last)
112.     {
113.         return false;
114.     }
116.     // 将要删除的索引后的数据全部往前移动一位
117.     for(i = pos; i < list->last;i++)
118.     {
119.         list->data[i] = list->data[i+1];
120.     }
122.     // 改变索引
123.     list->last--;
124.     return true;
125. }
128. /**
129. * 释放内存
130. * @param list 待释放的顺序表
131. */
132. void destroy(SequenceList *list)
133. {
134.     if(list == NULL)
135.     {
136.         return;
137.     }
138.     free(list->data);
139.     free(list);
140.     list = NULL;
141. }

复制代码

次序表优缺点总结

次序存储中，由于逻辑关系是用物理位置来表达的，因此从上述示例代码可以很清晰看到，增删数据都非常困难，必要成片地移动数据。次序表对数据节点的增删操纵是很不友好的。
总结其特点如下：

• 长处:
  

• 不必要多余的信息来记载数据间的关系，存储密度高
  
• 所有数据次序存储在一片连续的内存中，支持立刻访问恣意一个随机数据，比如上述次序表中第i个节点是 s->data
  

• 缺点:
  

• 插入、删除时必要保持数据的物理位置反映其逻辑关系，一般必要成片移动数据
  
• 当数据节点数量较多时，必要一整片较大的连续内存空间
  
• 当数据节点数量变化剧烈时，内存的释放和分配不机动
  

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