数据结构之线性表

本文是coursera的课程（数据结构基础）的学习笔记：https://www.coursera.org/learn/shuju-jiegou-suanfa

线性表的概念

线性表简称表，是零或多个元素的有穷序列，通常可以表示成K1,K2,…….,Kn(n>=1)

表目：线性表中元素（可包含多个数据项，记录）

索引（下标）：i称为表目k1的“索引”或“下标”

表的长度：线性表中所含元素的个数n

空表：长度为零的线性表（n=0）

线性表特点

操作灵活，其长度可以增长、缩短

线性结构

二元组B=(K,R),K= R=

有一个唯一的开始结点，它没有前驱，有一个唯一的直接后继

一个唯一的终止结点，它有一个唯一的直接前驱，而没有后继

其它的结点皆称为内部结点，每一个内部结点都有且仅有一个唯一的直接前驱，也有一个唯一的直接后继。

前驱/后继关系r，具有反对称性和传递性

特点

均匀性：虽然不同线性表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。

有序性：各数据元素在线性表中都有自己的位置，且数据元素之间的相对位置是线性的

线性结构——分类

按复杂长度划分

简单的：线性表、栈、队列、散列表

高级的：广义表、多维数组、文件……

按访问方式划分

直接访问型

搜索访问型

目录索引型

按操作划分

插入操作在表的一端，删除操作在另一端

插入和删除操作都限制在表的同一端进行

所有表目都是同一类型结点的线性表

不限制操作形式

根据存储的不同分为：顺序表，链表

线性表

栈(LIFO)

队列(FIFO)

2.1 线性表

三个方面

线性表的逻辑结构

线性表的存储结构

线性表运算

2.1.1 线性表逻辑结构

主要属性包括

线性表的长度

表头(head)

表尾(tail)

当前位置(current position)

2.1.2 线性表存储结构2.1.2.1 线性表分类(按存储)

线性表

- 所有表目都是同一类型结点的线性表

- 不限制操作形式

- 根据的不同分为：顺序表，链表

线性表的存储结构

顺序表

按索引值从小岛大存放在一片相邻的连续区域

紧凑结构，存储密度为1

链表

单链表

双链表

循环链表

2.1.2.2 线性表分类(按操作)

线性表

不限制操作

栈

在同一端操作

队列

在两端操作（插入操作在表的一端，删除操作在另一端）

2.1.3 线性表运算

建立线性表

清除线性表

插入一个新元素

删除某个元素

修改某个元素

排序

检索

2.2 顺序表

也称向量，采用定长的一维数组存储结构

主要特征

元素的类型相同

元素顺序地存储在连续存储空间中，每一个元素有唯一的索引值

使用常数作为向量长度

数组存储

读写其元素很方便，通过下标即可指定位置

只要确定首地址，线性表中任意数据元素都可以随机存取

元数据地址计算如下所示：

顺序表的运算

重点讨论

插入元素运算

bool insert(const int p,const T value);

删除元素运算

bool delete(const int p);

插入元素运算

删除元素运算

顺序表插入运算的算法分析

表中元素的移动

插入：移动n-i

删除：移动n-i-1个

i的位置插入和删除的概率分别是

插入的平均移动次数为

删除的平均移动次数为

2.3 链表(linked list)

通过指针把它的一串存储节点链接成一个链

存储结点由两部分组成：

数据域+指针域(后继地址)

分类（根据链接方式和指针多幂）

单链

双链

循环链

2.3.1 单链表

简单的链表

整个单链表：head

第一个节点：head

空表判断：head==NULL

当前节点a：curr

带头节点的单链表

整个单链表：head

第一个结点：head->next,head不等于NULL

空表判断： head -> next==NULL

查找单链表中第i个结点

单链表的插入

创建新结点

新结点指向右边的结点

左边节点指向新结点

单链表的删除

从链表中删除结点x

用p指向元素x的结点的前驱结点

删除元素为x的结点

释放x占据的空间

单链表上运算的分析

对一个结点操作，必先找到它，即用一个指针指向它

单链表中任一结点，都必须从第一个点开始

p=head；

while(没有达到) p=p->next;

单链表的时间复杂度O(1)

定位：O(n)

插入：O(n)+O(1)

删除：O(n)+O(1)

2.3.2 双链表

为弥补单链表的不足，而产生双链表

单链表的next字段仅仅指向后继结点，不能有效地找到前驱，反之亦然

增加一个指向前驱的指针

双链表及其结点类型的说明

双链表插入过程（注意顺序）

删除过程

2.3.3 循环表

将单链表或者双链表的头尾结点链接起来，就是一个循环链表

不增加额外存储花销，却给不少操作带来了方便

从循环表中任一结点出发，都能访问到表中其他结点

链表的边界问题

几个特殊点的处理

头指针处理

非循环链表尾结点的指针域保持为NULL

循环链表尾结点的指针回指头结点

链表处理

插入

查找或遍历

空链表的特殊处理

插入或删除结点时指针勾链的顺序

指针移动的正确性

2.4 线性表实现方法的比较

顺序表的主要优点

没有使用指针，不要花费额外开销

线性表元素的读访问非常简洁便利

链表的主要优点

无需事先了解线性表的长度

允许线性表的长度动态变化

能够适应经常插入输出内部元素的情况

总结

顺序表是存储静态数据的不二选择

链表是存储动态变化数据的良方

顺序表和链表的比较

顺序表

插入、删除运算时间代价O(n),查找则可常数时间完成

预先申请给定长度的连续空间

如果整个数组元素很满，则没有结构性存储开销

链表

插入、删除运算时间代价O(1),但找第i个元素运算时间代价O(n)

存储利用指针。动态地按照需要为表中的元素分配存储空间

每个元素都有结构性存储开销

顺序表和链表存储密度

n 表示线性表中当前元素的数目，

p 表示指针的存储单元大小（通常为4bytes）

E 表示数据元素的存储单元大小

D 表示可以在数组中存储的线性表元素的最大数目

空间需求

顺序表的空间需求为DE

链表的空间需求为n(P+E)

n的临界值，即n>DE/(P+E)

应用场合的选择

n越大，顺序表的空间效率就更高

如果P=E，则临界值为n=D/2

顺序表不适用的场合

经常插入删除是，不宜使用顺序表

线性表的最大长度也是一个重要因素

链表不适用的场合

当读操作比插入删除操作频率大时，不应选择链表

当指针的存储开销，和整个结点内容所占空间相比其比例较大时，应该慎重选择

顺序表和链表的选择

顺序表

结点总数目大概可以估计

线性表中结点比较稳定（插入删除少）

n > DE / ( P+E )

链表

结点数目无法预计

线性表中结点动态变化（插入删除多）

n < DE / ( P+E )

约瑟夫问题

n个人围成一个圈，每个人分别标注为1、2、…、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。