线性表(List)

Wu Jun 2019-12-25 15:59:03
Categories: > > Tags:

一、线性表的定义和基本操作

1)定义

线性表:零个或多个数据元素的有序排列。

除第一个元素外,每个元素有且只有一个直接前驱元素;初最后一个元素外,每个元素有且只有一个直接后继元素。

2)基本操作

二、线性表的实现

1 顺序存储

1)定义

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

2)存储结构

一维数组,存取时间性能为O(1),随机存取结构

3)主要操作
4)优缺点

优点

缺点

2 链式存储

2.1 单链表

1)定义

不考虑相邻,哪有空就存哪,让每个元素知道它下一个元素的位置

2)存储结构

链式结构中,除了要存数据元素信息外,还要存储它的后继元素的存储地址。

3)主要操作
4)单链表与顺序存储优缺点

2.2 静态链表

1)定义

针对没有指针的语言,用数组来代替指针描述链表,被称为静态链表。

2)存储结构

游标实现法:数组的元素都是由两个数据域组成, data 和 cur

3)主要操作

将可用空间链成备用链表

4)静态链表优缺点

2.3 循环链表

1)定义

循环链表:将单链表中终端结点的指针端由空指针改为指向头结点,这种头尾相接的单链表称为单循环链表,简称循环链表。

2)差异

循环链表和单链表的主要差异就在于循环的判断条件上,原沫是判断 p->next 是否为空,现在则是 p -> next 不等于头结点,则循环未结束。

3)尾指针

如用尾指针替代头指针,则查找开始结点和终端结点都很方便。

2.4 双向链表

1)定义

双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。

2)主要操作

在插入和删除时,需要更改两个指针变量。顺序很重要,千万不能写反了。

3 线性表的应用

一元整系数的加法和乘法操作

队列和堆栈