喜欢的话可以扫码关注我们的公众号哦,更多精彩尽在微信公众号【程序猿声】
01 预备知识
1.0 什么是线性表?
线性表(List)是零个或者多个数据元素的有限序列.
- 首先它是一个序列.里面的元素是有顺序的,如果有多个元素,除开头和结尾以外的元素都有一个前驱和一个后继.而开头元素只有后继,结尾元素只有前驱.
- 其次线性表是有限的,也就是里面的元素个数是有限的。
1.1 线性表的基本操作(描述)
1ADT?线性表(List)
2Data
3????线性表的数据对象集合为{a1,?a2,?a3,?......,?an},每个元素类型为DataType。
4Operation
5????InitList(L);????????//初始化线性表
6????IsEmptyList(L);?????//判断线性表是否为空
7????ClearList(L);???????//清空线性表
8????GetElemList(L,?i,?*e);?//获取第i个位置的数据
9????SearchList(L,?e);?//查找与数据e相等的元素
10????InsertNodeList(L,?e);//在第i个位置插入元素
11????DeleteNodeList(L,?*e);//删除第i个位置的元素,e获取删除元素
12????GetLengthList(L);??//获取线性表的长度
13endADT
关于线性表的基本操作就上面几种,还有几个例如线性表的排序,合并,逆序等等操作。为了文章篇幅,就下次再介绍了。
1.2 什么是顺序存储结构?
线性表的顺序存储结构,就是指 用一段地址连续的存储单元一次存储线性表的数据元素。学过高级语言的朋友,相信对数组这玩意儿都不会陌生吧。数组就是一种顺序存储结构。
1.3 什么是链式存储结构?
链式存储结构就是可以用一组任意的内存单元存储线性表中的元素。与顺序存储不同的是,这组内存单元可以是连续的,也可以是不连续的。这就意味着,元素可以存储在内存的任意位置。正因为如此,在链式结构中,每个元素不仅要存它的信息,还需要存储它后继元素的存储地址。我们把存储元素信息的域称为数据域,而把存储后继元素地址的域称为指针域。由这两部分共同组成的数据元素ai,则可以称之为节点(Node)。
如下面这个图所示:
1.5 什么是链表?
链表就是链式存储的线性表。结点之间通过逻辑连接,形成链式存储结构。存储结点的内存单元,可以是连续的也可以是不连续的。逻辑连接与物理存储次序没有关系。
02 顺序表(Sequential List)
2.0 什么是顺序表?
采用顺序存储结构的线性表,就是顺序表。
2.1 顺序表的存储结构代码
这里我们统一采用C语言来描述。
1#define?MAXSIZE?20???//存储空间的初始大小
2typedef?int?DataType?//类型可根据实际情况而定
3typedef?struct?
4{
5????DataType?data[MAXSIZE];?//数组来存储数据
6????int?length;??????????????//实际长度
7}SqlList;
可见,顺序表的几个重要特性:
- 存储空间的位置:数组data
- 顺序表的最大容量:数组长度MAXSIZE
- 顺序表当前长度:length
2.2 顺序表的插入操作
相信大家在排队的时候都有过被插队的体验吧。当一个插队到你前面时,这个时候你内心os mmp外加素质三连的同时,也不得不往后挪一个位置。于是乎这个就不得了了,你后面的也要往后挪,你后面的后面也是……然后队伍里瞬间就狼烟起……
那么,这个顺序表的插入其实也差不多的。由于地址是连续存储的,那么在某个地方插入以后,其后的元素不得不往后挪一个位置。
插入算法描述:
- 异常处理(插入位置不合理、顺序表已经满等等)。抛出异常。
- 从最后一个元素往前遍历到第i个位置,依次将他们都往后挪一个位置。
- 将要插入的元素放入位置i处。
- 别忘记了表长度length++。
由于数组下标是从0开始的,我们习惯要删除的位置第i处又是从1开始算起的。本文就全部统一成,都从0开始吧。比如要在第5个位置插入一个元素,那就是a[5]。不然真的会混乱的。
具体代码如下:
1//功能:在顺序表L第i个位置之前插入元素e
2int?InsertSqlList(SqlList?*L,?int?i,?DataType?data)
3{
4????int?k;
5????if(L->length==MAXSIZE?||?i<0?||?i>L->length)?//记住,都是从0开始的哦
6????????return?0;//异常处理
7????if(i?==?L->length)
8????????L->data[length++]?=?data;//尾插一步到位
9????if(i?<?L->length)??//中间插,要挪人啦
10????{
11????????for(k?=?L->length-1;?k?>=?i;k--)?//再次强调哈,都是从0开始的。
12????????????L->data[k+1]=L->data[k];//后移
13????????L->data[i]?=?data;//新元素插入
14????????L->length++;
15????}
16????return?1;
17}
2.2 顺序表的删除操作
算法描述:
- 异常处理(删除位置不合理、顺序表为空等等)
- 尾删,直接获取然后length--。
- 中间删,从i开始往后遍历,依次将各元素往前挪。e获取要删元素,length--即可。
1//功能:在顺序表L中删除第i个数据元素,用e获取被删除值
2int?DeleteElemList(SqlList?*L,?DataType?*e)
3{
4????int?k;
5????if(L->length==0?||?i<0?||?i>L->length-1)?//记住,都是从0开始的哦
6????????return?0;//异常处理???
7????if(i?==?L->length-1)?//尾删,easy
8????{
9????????*e?=?L->data[i];//获取要删除元素
10????????L->length--;?//删除元素
11????}????????
12????if(i?<?L->length)??//中间删,要挪人啦
13????{
14????????*e?=?L->data[i];//获取要删除元素
15????????for(k?=?i;?k?<?L->length-1;k++)?//再次强调哈,都是从0开始的。
16????????????L->data[k]=L->data[k+1];//前移
17????????L->length--;
18????????return?1;
19????}
3 顺序表的完整代码
1#include?<stdio.h>
2#include?<stdlib.h>
3#define?MAXSIZE?20
4#define?ERROR?0
5#define?OK?1
6#define?NO?0
7#define?YES?1
8
9typedef?int?DataType;
10typedef?int?Status;
11
12typedef?struct?List
13{
14????int?data[MAXSIZE];
15????int?length;
16}SqlList;
17
18void?InitList(SqlList?*?L);??????????????????????//初始化顺序表
19Status?IsEmptyList(SqlList?*L);???????????????//判断顺序表是否为空
20void?ClearList(SqlList?*L);??????????????????????//清空线性表
21Status?GetElemList(SqlList?*L,int?i,DataType?*e);?//获取第i个位置的数据
22int?SearchList(SqlList?*L,?DataType?e);?????????//查找与数据e相等的元素
23Status?InsertNodeList(SqlList?*L,DataType?e);//在第i个位置插入元素
24Status?DeleteNodeList(SqlList?*L,?DataType?*e);//删除第i个位置的元素,e获取删除元素
25int?GetLengthList(SqlList?*L);????????????????????????//获取线性表的长度
26void?PrintList(SqlList?*L);?????????????????????????//遍历顺序表,此函数测试使用,根据实际类型编写
27
28int?main()
29{
30????int?e;
31????SqlList?*pL?=?(SqlList*)malloc(sizeof(SqlList));
32????InitList(pL);
33????InsertNodeList(pL,?0,?1);
34????InsertNodeList(pL,?1,?2);
35????InsertNodeList(pL,?2,?3);
36????InsertNodeList(pL,?3,?4);
37????InsertNodeList(pL,?4,?5);
38????InsertNodeList(pL,?5,?6);
39
40????PrintList(pL);
41
42????DeleteNodeList(pL,?&e);
43????DeleteNodeList(pL,?&e);
44
45????PrintList(pL);
46
47
48????return?0;
49}
50
51void?InitList(SqlList?*?L)
52{
53????for(int?i?=?0;?i?<?MAXSIZE;?i++)
54????????L->data[i]?=?0;
55????L->length?=?0;?//将表设为空
56}
57
58Status?IsEmptyList(SqlList?*L)
59{
60????if(L->length?==?0)
61????????return?YES;//表为空
62????else
63????????return?NO;
64}
65
66void?ClearList(SqlList?*L)
67{
68????InitList(L);//此操作跟初始化一样。
69}
70//这里的第i个位置,为了统一我们也是从0算起的
71Status?GetElemList(SqlList?*L,DataType?*e)
72{
73????if(i?<?0?||?i?>=?L->length?||?L->length?==?0)
74????????return?ERROR;//异常处理
75????*e?=?L->data[i];
76
77????return?OK;
78}
79//找到与数据e相同的节点,返回下标。-1表示没找到,ERROR表示表为空
80int?SearchList(SqlList?*L,?DataType?e)
81{
82????if(L->length?==?0)
83????????return?ERROR;
84????for(int?i?=?0;?i?<?L->length;?i++)
85????{
86????????if(L->data[i]?==?e)
87????????????return?i;
88????}
89
90????return?-1;
91}
92//获取顺序表的长度
93int?GetLengthList(SqlList?*L)
94{
95????return?L->length;
96}
97//在位置i插入元素,再次强调,从0开始
98Status?InsertNodeList(SqlList?*L,DataType?e)
99{
100????if(i?<?0?||?i?>?L->length?||?L->length?==?MAXSIZE)
101????????return?ERROR;//异常处理
102????for(int?k?=?L->length;?k?>?i;?k--)
103????{
104????????L->data[k]?=?L->data[k-1];?//往后挪
105????}
106????L->data[i]?=?e;//插入数据,
107????L->length++;???//长度也要加1
108
109????return?OK;
110}
111
112Status?DeleteNodeList(SqlList?*L,?DataType?*e)
113{
114????if(i?<?0?||?i?>?L->length?||?L->length?==?0)
115????????return?ERROR;//异常处理
116????*e?=?L->data[i];//获取数据
117????for(int?k?=?i;?k?<?L->length?-1;?k++)
118????????L->data[k]?=?L->data[k+1];//往前挪
119????L->length--;?//长度减1
120????return?OK;
121}
122
123void?PrintList(SqlList?*L)
124{
125????if(L->length?==?0)
126????{
127????????printf("顺序表为空\n");
128????}
129????printf("============遍历顺序表如下=============\n");
130????for(int?i?=?0;?i?<?L->length;?i++)
131????{
132????????printf("\tdata[%d]?=?%d\n",?L->data[i]);
133????}
134????printf("============共计%d个元素=============\n",?L->length);
135
136}
简单测试了一下。如果存在问题,欢迎指正,谢谢大家。
(编辑:ASP站长网)