线性表(List)是零个或者多个数据元素的有限序列.
ADT 线性表(List)
Data
线性表的数据对象集合为{a1, a2, a3, ......, an},每个元素类型为DataType。
Operation
InitList(L); //初始化线性表
IsEmptyList(L); //判断线性表是否为空
ClearList(L); //清空线性表
GetElemList(L, i, *e); //获取第i个位置的数据
SearchList(L, e); //查找与数据e相等的元素
InsertNodeList(L, i, e);//在第i个位置插入元素
DeleteNodeList(L, i, *e);//删除第i个位置的元素,e获取删除元素
GetLengthList(L); //获取线性表的长度
endADT
关于线性表的基本操作就上面几种,还有几个例如线性表的排序,合并,逆序等等操作。为了文章篇幅,就下次再介绍了。
线性表的顺序存储结构,就是指 用一段地址连续的存储单元一次存储线性表的数据元素。学过高级语言的朋友,相信对数组这玩意儿都不会陌生吧。数组就是一种顺序存储结构。
链式存储结构就是可以用一组任意的内存单元存储线性表中的元素。与顺序存储不同的是,这组内存单元可以是连续的,也可以是不连续的。这就意味着,元素可以存储在内存的任意位置。正因为如此,在链式结构中,每个元素不仅要存它的信息,还需要存储它后继元素的存储地址。我们把存储元素信息的域称为数据域,而把存储后继元素地址的域称为指针域。由这两部分共同组成的数据元素ai,则可以称之为节点(Node)。
如下面这个图所示:
链表就是链式存储的线性表。结点之间通过逻辑连接,形成链式存储结构。存储结点的内存单元,可以是连续的也可以是不连续的。逻辑连接与物理存储次序没有关系。
采用顺序存储结构的线性表,就是顺序表。
这里我们统一采用C语言来描述。
#define MAXSIZE 20 //存储空间的初始大小
typedef int DataType //类型可根据实际情况而定
typedef struct
{
DataType data[MAXSIZE]; //数组来存储数据
int length; //实际长度
}SqlList;
可见,顺序表的几个重要特性:
相信大家在排队的时候都有过被插队的体验吧。当一个插队到你前面时,这个时候你内心os mmp外加素质三连的同时,也不得不往后挪一个位置。于是乎这个就不得了了,你后面的也要往后挪,你后面的后面也是……然后队伍里瞬间就狼烟起……
那么,这个顺序表的插入其实也差不多的。由于地址是连续存储的,那么在某个地方插入以后,其后的元素不得不往后挪一个位置。
插入算法描述:
由于数组下标是从0开始的,我们习惯要删除的位置第i处又是从1开始算起的。本文就全部统一成,都从0开始吧。比如要在第5个位置插入一个元素,那就是a5。不然真的会混乱的。
具体代码如下:
//功能:在顺序表L第i个位置之前插入元素e
int InsertSqlList(SqlList *L, int i, DataType data)
{
int k;
if(L->length==MAXSIZE || i<0 || i>L->length) //记住,都是从0开始的哦
return 0;//异常处理
if(i == L->length)
L->data[length++] = data;//尾插一步到位
if(i < L->length) //中间插,要挪人啦
{
for(k = L->length-1; k >= i;k--) //再次强调哈,都是从0开始的。
L->data[k+1]=L->data[k];//后移
L->data[i] = data;//新元素插入
L->length++;
}
return 1;
}
算法描述:
纯手打哈。。简单测试了一下。如果存在问题,欢迎指正,谢谢大家。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。