数据结构与算法的线性表

前言

达到同首《数据结构和算法的日复杂度和空中复杂度》中介绍了日复杂度的概念与普遍的日子复杂度,并各自举例子进行了各个说明。这同篇重要介绍线性表。
线性表属于数据结构中逻辑结构面临的线性结构。回忆一下,数据结构分为物理构造及逻辑结构,逻辑结构分为线性结构、几哪结构、树形结构与图片结构四雅结构。其中,线性表就属线性结构。剩余的老三死逻辑结构从此见面相继介绍。

线性表

基本概念

丝性表(List):由零个或多只数据元素构成的点滴序列。
注意
1.线性表是一个行列。
2.0单要素做的线性表是空表。
3.线性表中的率先单元素无前驱,最后一个要素无后继,其他因素来还仅发一个前任和晚。
4.线性表是发出长的,其长度就是素个数,且线性表的要素个数是少数的,也就是说,线性表的尺寸是零星的。
假使就此数学语言来进行定义,可正如:
比方用线性表记为(a1,…,ai-1,ai,ai+1,…an),则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直前驱元素,ai+1是ai的直白后继元素。

线性表的概念

线性表基本操作

InitList(L): 初始化操作,建立一个拖欠的线性表L。
ListEmpty(L):
判断线性表是否为空表,若线性表为空,返回true,否则回false。
ClearList(
L): 将线性表清空。 GetElem(L,i,e):
将线性表L中之第i独岗位正素值返回给e。
LocateElem(L,e):
在线性表L中找找和给定值e相等的素,如果找成功,返回该因素于表明中序号表示成功;否则,返回0表示失败。
ListInsert(
L,i,e): 在线性表L中第i只位置插入新元素e。
ListDelete(L,i,e): 删除线性表L中第i单职位元素,并用e返回其价。
ListLength(L): 返回线性表L的素个数。

对于不同之以,线性表的基本操作是殊的,上述操作是最为中心的。
对实际问题遭受涉及的有关线性表的更复杂操作,完全可据此这些基本操作的整合来促成。

片栽不同之线性表

俺们掌握,数据结构分为逻辑结构以及情理结构,逻辑结构分为集合结构、线性结构、树形结构及图纸结构四良类。物理结构分为顺序存储结构与链式存储结构。我当前写的《数据结构和算法》中一度介绍过。
线性表是线性结构的同等种,那么线性表当然也生大体构造,也就是说,线性表来半点种,分别是逐一结构的线性表(叫做顺序表)和链式结构的线性表(叫做链表)。

1.顺序存储结构的线性表

顺序表是因顺序存储结构的线性表,指的是为此同一段子地址连续的存储单元依次存储线性表的多少元素。
顺序表表现于情理内存中,也就是大体及之囤方,事实上就是是在内存中找寻个起来地址,然后经占位的样式,把自然之内存空间给占了,然后拿同数据类型的数元素依次放在这块空地被。注意,这块物理内存的地方空间是连续的。

个例证,比如C语言中的核心变量的囤就是连的囤积于内存中之,比如声明一个整数i,在64各类系统中整数i在内存中占有8字节,那么网即见面当内存中为即
个整型变量分配一个长度为8单字节的连日的地址空间,然后拿此i的二进制形式从高地址为没有地址存储,长度相差上,最高位用0补一起。

顺序表的布局体定义

#define MAXSIZE 20  // 顺序表的最大存储容量
typedef int ElemType; // 顺序表存储的数据类型 
typedef struct
{ 
    ElemType data[MAXSIZE]; // 用数组表示顺序表 
    int length; // 线性表当前长度
} SqList;

由此上面用结构体定义顺序表,我们得以看到顺序表的卷入需要三个特性:
1.仓储空间的起首位置。频繁组data的囤位置就是线性表存储空间的仓储位置
2.线性表的最为特别存储容量。数组长度MAXSIZE
3.线性表的时长。length
注意:数组的长及丝性表的眼前长是匪平等的。数组的长度是存放线性表的贮存空间的毕竟长度,一般初始化后无变换。而线性表的手上长是线性表中元素的个数,是会见改变的。

各个表查找元素操作

代码实现:

逐表插入元素操作

思路如下:

1.如插入位置不成立,抛来老;

2.设线性表长度超过等于数组长度,则弃来非常或者动态增加数组容量;

3.起最终一个素开始上遍历到第i单职位,分别用她都向后活动一个位置;

4.将插入元素填入职i处;
5.线性表长+1。
代码实现:

顺序表删除元素操作

思路如下:
1.一旦除去元素的职务不成立,抛来老。比如用户删除第0只位置的要素(线性表是从1发端之)、删除元素的职位大于线性表的长度为如抛开来异常。
2.删减第i独职务的素。
3.把第i只位置的要素后面的有所的素的职加一。
4.线性表长度减一。
代码实现:

顺序表优缺点

由于以上代码可以视:
丝性表的顺序存储结构,在满怀、读取数据时,不管是以谁位置,时间复杂度都是O(1)。而当插入或者去除时,时间复杂度都是O(n)。
即时为就是线性表的顺序存储结构比较相符存取数据,不吻合经常插入和去数据的应用。

优点:

1.任需以表示表中元素中的逻辑关系而益额外的积存空间(相对于链式存储而言)。
2.好长足的存取表中自由位置的素。

缺点:

1.插和去操作需要走大量底要素。
2.当线性表长度变化较生时,难以确定存储空间的容量。
3.便于招存储空间的“碎片”(因为线性表的顺序存储结构申请之内存空间都为连续的,如果坐某些操作(比如去操作)导致某个部分出现了平等稍稍片的不连续内存空间,因为就等同有些片内存空间太小莫可知还被用/分配,那么即便招致了内存浪费,也便是“碎片”)
PS:windows系统有磁盘碎片整理工具,而Linux系统没有,因为Linux系统内核优化的万分好,几乎是不曾磁盘碎片的。

2.链式存储结构的线性表

前方我们说的线性表的顺序存储结构,它极其可怜的短C语言就是是插和去时得活动大量因素,这明确就是得吃时间。
这就是说我们会免可知对这毛病要说不满提出解决之方式也?要解决这个题材,我们就得考虑一下导致这问题的故!
缘何当插入和去时,就要走大量底要素?
原因就是在于相邻两元素的仓储位置吗拥有邻居关系,它们当内存中之位置是困难守的,中间没有空,当然就无法迅速插入和去。
线性表的链式存储结构的风味是用同一组随机的存储单元存储线性表的数量元素,这组存储单元可以在内存中未给挤占的自由位置。
也就是说,链式存储结构的线性表由一个(可以要零)或者多只结点(Node)组成。每个节点内又分为数据域和指针域(链)。数据域存储了数码元素的信息。指针域存储了眼前结点指向的直接后继的指针地址。
因每个结点只含有一个凭针域,所以称为单链表。顾名思义,当然还有对链表。

单链表

链式存储结构被,除了要存储数据元素信息外,还要存储它们的后继元素的贮存地点(指针)。
也就是说除了存储其自己的音讯外,还待贮存一个指令其一直后继的蕴藏位置的信。
俺们将仓储数据元素信息的域称为数据域,把仓储直接后继位置的域称为指针域。

凭借针域中存储的信称指针或链。
即时片有些信息整合数据元素称为存储映像,或曰结点(Node)。
n个结点链接成一个链表,即为线性表(a1, a2, a3, …, an)的链式存储结构。

坐此链表的每个结点中单含有一个借助针域,所以叫单链表。

丝性表的链式存储结构

对此线性表来说,总得有身材有只尾,链表也无例外。我们拿链表中的第一单结点的仓储位置让做头指针,最后一个结点指针也空(NULL)。
单链表是线性表中极具有代表性的同样栽,下同样篇稿子被,本人用见面以出一致章节来介绍单链表,敬请期待!
图表源于参考自:鱼C工作室。感谢鱼C工作室贡献出了这么好的图纸。
PS:本篇文章在博客园也产生一块创新,大家为足以走博客园关注我,后续会更新更多精品文章!*
博客园地方:http://home.cnblogs.com/u/wsnb/

如非特别说明,笔者有文章还是原创文章。如果你喜欢就首稿子,转载请注明出处。如果你对数据结构感兴趣,请关注自己,后续会更新大量精品文章供大家参考!