【数据结构】线性表|顺序表|链表(上)

简介: 线性表(List)是零个或者多个数据元素的有限序列.

01 预备知识


1.0 什么是线性表?


线性表(List)是零个或者多个数据元素的有限序列.

Pay attention:

1)    首先它是一个序列.里面的元素是有顺序的,如果有多个元素,除开头和结尾以外的元素都有一个前驱和一个后继.而开头元素只有后继,结尾元素只有前驱.

2)    其次线性表是有限的,也就是里面的元素个数是有限的。

1.1 线性表的基本操作(描述)


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个位置数据

    GetLengthList(L);  //获取线性表的长度

endADT

关于线性表的基本操作就上面几种,还有几个例如线性表的排序,合并,逆序等等操作。为了文章篇幅,就下次再介绍了。


1.2 什么是顺序存储结构?


线性表的顺序存储结构,就是指 用一段地址连续的存储单元一次存储线性表的数据元素。学过高级语言的朋友,相信对数组这玩意儿都不会陌生吧。数组就是一种顺序存储结构。


1.3 什么是链式存储结构?


链式存储结构就是可以用一组任意的内存单元存储线性表中的元素。与顺序存储不同的是,这组内存单元可以是连续的,也可以是不连续的。这就意味着,元素可以存储在内存的任意位置。(嗯对的,强调三连)正因为如此,在链式结构中,每个元素不仅要存它的信息,还需要存储它后继元素的存储地址。我们把存储元素信息的域称为数据域,而把存储后继元素地址的域称为指针域。由这两部分共同组成的数据元素ai,则可以称之为节点(Node)。


如下面这个图所示:


微信图片_20220420191411.jpg


1.4什么是链表?


链表就是链式存储的线性表。结点之间通过逻辑连接,形成链式存储结构。存储结点的内存单元,可以是连续的也可以是不连续的。逻辑连接与物理存储次序没有关系。


02 顺序表(Sequential List)

2.0 什么是顺序表?


采用顺序存储结构的线性表,就是顺序表。

2.1 顺序表的存储结构代码


这里我们统一采用C语言来描述。


#define MAXSIZE 20   //存储空间的初始大小

typedef int DataType //类型可根据实际情况而定typedef struct

{

    DataType data[MAXSIZE]; //数组来存储数据

    int length;              //实际长度

}SqlList;


可见,顺序表的几个重要特性:


1)    存储空间的位置:数组data

2)    顺序表的最大容量:数组长度MAXSIZE

3)    顺序表当前长度:length


2.2 顺序表的插入操作


相信大家在排队的时候都有过被插队的体验吧。当一个插队到你前面时,这个时候你内心os mmp外加素质三连的同时,也不得不往后挪一个位置。于是乎这个就不得了了,你后面的也要往后挪,你后面的后面也是……然后队伍里瞬间就炸锅了……

那么,这个顺序表的插入其实也差不多的。由于地址是连续存储的,那么在某个地方插入以后,其后的元素不得不往后挪一个位置。

微信图片_20220420191544.jpg


插入算法描述:


1)    异常处理(插入位置不合理、顺序表已经满等等),返回异常。

2)    从最后一个元素往前遍历到第i个位置,依次将他们都往后挪一个位置。

3)     将要插入的元素放入位置i处。

4)     别忘记了表长度length++。


由于数组下标是从0开始的,我们习惯要删除的位置第i处又是从1开始算起的。本文就全部统一成,都从0开始吧。比如要在第5个位置插入一个元素,那就是a[5]。不然新手朋友真的会纠结死在这个点上.当然,如果你喜欢,也可以将数组设置为从1开始.....


具体代码如下:


微信图片_20220420191643.jpg



2.2 顺序表的删除操作


算法描述:


1)    异常处理(删除位置不合理、顺序表为空等等)


2)    尾删,直接获取然后length--。


3)    中间删,从i开始往后遍历,依次将各元素往前挪。e获取要删元素,length--即可。


微信图片_20220420191654.jpg

2.3 顺序表的完整代码


微信图片_20220420191744.jpg



相关文章
|
6天前
【数据结构OJ题】环形链表
力扣题目——环形链表
14 3
【数据结构OJ题】环形链表
|
6天前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
13 1
【数据结构OJ题】复制带随机指针的链表
|
6天前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
10 1
【数据结构OJ题】环形链表II
|
6天前
【数据结构OJ题】相交链表
力扣题目——相交链表
14 1
【数据结构OJ题】相交链表
|
1月前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
6天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
12 1
【数据结构】栈和队列
|
6天前
【数据结构OJ题】用栈实现队列
力扣题目——用栈实现队列
14 0
【数据结构OJ题】用栈实现队列
|
6天前
【数据结构OJ题】用队列实现栈
力扣题目——用队列实现栈
17 0
【数据结构OJ题】用队列实现栈
|
24天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
1月前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)