数据结构与算法A 第二章线性表
线性表的概念
线性表的抽象数据类型
线性表的定义：线性表(简称为表)是零个或多个元素的有穷序列L=(k0,k1,…,kn-1)；线性表是由称为元素的数据项组成的一种有限且有序的序列，这些元素也称为结点或表目
线性表的逻辑结构：L=<K,R>其中，K={k0,k1,…,kn-1}，R={r:线性关系}。
i称为ki的索引或下表。所含元素的个数称为表的长度。长度为0的表称为空表。k0是第一个元素kn-1是最后一个元素。ki是ki+1的前驱，ki+1是ki的后继
唯一开始的结点：没有前驱；唯一终止的结点：没有后继。内部节点：有唯一的直接前驱也有一个唯一的直接后继
线性表的关系r是前驱关系，应具有反对称性和传递性
要求：
- 内部结点具有相同的数据类型
- 每个元素都有自己的位置[0,n-1]
在线性表上实施的操作：
- 对整个表的操作：创建或置空一个线性表、合并两个线性表、判断线性表是否为空或满
- 对表中元素的操作：查找线性表中满足一定条件的元素、在线性表中插入或删除指定元素
线性表ADT：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17template <class T>
class list
{
void clear(); //置空线性表
bool isEmpty(); //线性表为空返回true;
bool append(const T value); //表尾添加元素v，表长+1
bool insert(const int p,const T value); //在p位置上插入元素value，表长+1
bool delete(const int p); //删除p位置的元素，表长-1
bool getValue(const int p,T& value); //把位置p的元素值返回到变量value中
bool setValue(const int p,const T value); //用value修改位置p的元素值
bool setPos(int & p,const T value); //把值为value的元素所在的位置返回到变量p中
bool setPos(int pos); //设置当前下标
bool setStart(); //把当前下标移动到表头
bool setEnd(); //把当前下标移动到表尾
bool prev(); //把当前下标左移一位
bool next(); //把当前下标右移一位
};
线性表的存储结构
- 线性表的存储结构主要有两类：
- 定长、静态的顺序存储结构，简称顺序表：数组模式。又称为向量型的一维数据结构。为线性表分配一块连续的存储空间，随机访问，但长度固定。地址相邻表达为线性关系
- 变长、动态的线性存储结构，简称链接式存储结构，简称链表：链表模式。用指针来表示元素间的线性关系，前驱和后继关系通过指针来连接。对长度不加限制，可申请更大的空间
线性表运算分类
list()：创建线性表的一个实例(即构造函数)
~list()：线性表消亡(即析构函数)
获取有关当前线性表的信息
- 位置寻内容
- 内容找位置
访问线性表并且改变线性表的内容或结构，包括插入、删除、更改、清空线性表等
辅助管理操作，例如游标、求当前长度
顺序表
顺序表(向量)：按顺序方式存储的线性表。顺序表中的每个元素按其顺序有唯一的索引值，又称下标值，用来访问元素的内容
主要特性：
- 元素的类型相同
- 存储在连续的空间中，每个元素唯一的索引值，读写元素方便
- 使用常数作为向量长度，程序运行时保持不变
顺序表的类定义
- 假设每个元素占用L个存储单元，设顺序表开始的结点k0的存储位置记为b=loc(k0)，设其为首地址或基地址，下标为i的元素ki的存储位置则为loc(ki)=b+i*L。可知每个元素的存储位置都与起始位置相差一个位序成正比的常数。确定了基地址，任意元素的地址都可以方便的计算出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39enum Boolean {False,True};
const int Max_length = 100;
Template <class T> //假定顺序表的元素类型T
class list
{ //顺序表，向量
private :
T* nodelist; //私有变量，存储顺序表实例的向量
int maxSize; //私有变量，顺序表实例的最大长度
int curLen; //私有变量，顺序表实例的当前长度
int position; //私有变量，当前处理位置
public:
list(const int size); //构造算子，实参是表实例的最大长度
~list(); //析构算子，用于将该表实例删去
arrList(const int size)
{// 创建一个新顺序表，参数为表实例的最大长度
maxSize = size;
aList = new T[maxSize];
curLen = position = 0;
}
~arrList()
{ // 析构函数，用于消除该表实例
delete [] aList;
}
void clear()
{ // 将顺序表存储的内容清除，成为空表
delete [] aList;
curLen = position = 0;
aList = new T[maxSize];
}
void clear(); //将顺序表存储的内容清除，成为空表
int length(); //返回此顺序表的当前实际长度
bool append(const T value); //表尾增一新元素，表长加1
bool insert(const int p, const T value); //在p位置插入值value，表长加1
bool delete(const int p); //删去位置p的元素，表长减1；
bool setValue(int p, const T value); //用value修改位置p的元素值
bool getvalue(const int p, T & value); //把p位置值返回到变量value中
// 查找值为value的元素，并返回第1次出现的位置
bool getPos(int &p, const T value);
}
顺序表的运算实现
顺序表的检索
顺序表的检索运算可以分为按位置的查找和按内容的查找两类，前者在顺序表中可以直接计算其存储地址，可以在常数时间内存取该元素
按内容查找目的: 查找某个值的位置
1
2
3
4
5
6
7
8
9
10
11
12template <class T> // 假定顺序表的元素类型为T
bool arrList<T> :: getPos (int & p, const T value)
{
int i; // 元素下标
for (i = 0; i < n; i++) // 依次比较
if (value == aList[i])
{ // 下标为i的元素与value相等
p = i; // 将下标由参数p返回
return true;
}
return false; // 顺序表没有元素值为value的元素
}
顺序表的插入
bool insert(const int p, const T vlaue)，在当前下标 p= t 位置插入元素新值value
插入的限制条件：除了涉及被更新的那个元素之外，其他元素的线性关系的相对顺序应该保持不变
条件判断：
- 当前下标[0，curr_len]；（是否越界？）
- 当前长度（<msize）（是否溢出?）
- 要先移动，腾出空间，再插入！
1 | template <class T> // 假定顺序表的元素类型为T |
- 算法的主要代价：元素的移动，元素总个数为n，各个位置插入的概率相等为p＝1/(n+1)
顺序表的删除
Delete (const int p)，下标t位置值作为返回值，并删去该元素
事先需要检查是否为空表，只有在非空表时才能进行元素删除
条件判断：
- 当前下标[0，curr_len）删除位置是否有效？
- 当前长度（>0）是否向下溢出？
- 删除后，t后元素向前依次移动！
1
2
3
4
5
6
7
8
9
10
11
12
13template <class T> // 顺序表的元素类型为T
bool arrList<T> :: delete(int p)
{
int i;
if (curLen <= 0 ) // 检查顺序表是否为空
return false ;
if (p < 0 || p > curLen-1) // 检查删除位置是否合法
return false ;
for (i = p; i < curLen-1; i++)
aList[i] = aList[i+1]; // 从位置p开始每个元素左移直到curLen,
curLen--; // 表的实际长度减1
return true;
}
算法的时间代价与插入操作相似，O(n)
链表
顺序表的缺陷：
- 大小固定，改变顺序表的大小需要重新创建一个新的顺序表并复制原有数据
- 逻辑关系是通过物理位置的相邻来表示的，增删元素代价高
链表可以看成一组既存储数据又存储相互连接信息的结点集合，由称为指针的域来按照线性表的后继关系链接结点
链表的特点：
- 指针指向保持前驱关系，节点不必物理相邻
- 动态申请/释放空间，长度动态变化（插入/删除）
单链表
- 单链表：每个节点只包含指向其后继的指针
单链表的存储结点由两部分组成：
- 存放结点数据，称为data域
- 存放指向后继结点的指针域next
对于没有后继结点的终止结点而言，其next域为空指针NULL
单链表的结点定义：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16template <class T>
class Link
{
public:
T data; //用于保存节点元素的内容
Link<T> * next; //指向后继结点的指针
Link(const T info,const Link<T> * nextValue = NULL) //具有两个参数的Link构造函数
{
data = info;
next = nextValue;
}
Link(const Link<T> * nextValue) //具有一个参数的构造函数
{
next = nextValue;
}
};Link是由自身来定义的，因为其中的next域指向正在定义的类型本身，这种类型称为自引用型
由于单链表中的各个结点的存储地址并不连续，因此访问任何结点都只能从头至臻开始沿着结点的next域来进行
单链表的ADT：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18template <class T>
class lnkList : public List<T>
{
private:
Link<T> *head, tail; // 单链表的头、尾指针
Link<T> *setPos(int p); // 返回线性表指向第p个元素的指针值
public:
lnkList(int s); // 构造函数
~lnkList(); // 析构函数
bool isEmpty(); // 判断链表是否为空
void clear(); // 将链表存储的内容清除，成为空表
int length(); // 返回此顺序表的当前实际长度
bool append(T value); // 在表尾添加一个元素value，表的长度增1
bool insert(int p, T value); // 在位置p插入一个元素value，表的长度增1
bool delete(int p); // 删除位置p上的元素，表的长度减 1
bool getValue(int p, T value); // 返回位置p的元素值
bool getPos(int p, const T value); // 查找值为value的元素，并返回第1次出现的位置
};头结点Header Node（或称“哨兵” ）不被作为表中的实际元素，值忽略。head指向该节点，必须从head开始查找链表中的元素
头结点的好处
- 由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上操作一致，无须进行特殊处理
- 无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了
链表检索
由于地址空间不连续，单链表无法像顺序表那样直接通过结点位置来定位其地址，而是需要从头指针head所指的首结点开始沿next域，逐个结点进行访问
1
2
3
4
5
6
7
8
9
10
11
12
13
14// 返回位置i处的结点指针
template <class T> // 线性表的元素类型为T
Link<T> * lnkList <T>:: setPos(int i)
{
int count = 0;
if (i <= -1) return head; // i 为-1则定位到头结点
Link<T> *p = head->next;
while (p != NULL && count < i)
{ // 若i为0则定位到第1个结点
p = p-> next;
count++;
}
return p; // 或者为空，或者指向第i个节点！
}; // i从0开始！平均需要O(n)的时间
链表的插入和删除
链表插入: bool insert(int i, T value)
由于单链表结点之间的前驱后继关系由指针来表示，因此在插入或删除结点时，维护结点之间的逻辑关系只需要改变相关结点的next域
1 | ListNode * Insert(int i, T value) |
- 链表删除: bool delete(int i)
- 与插入操作相同，从单链表中删除一个节点也需要修改被删除结点的前驱的指针域来维护结点见的线性关系，同时要释放被删除结点所占用的内存
1 | template <class T> // 线性表的元素类型为T |
- 尽管插入删除操作本身可在常数时间内完成节点的创建释放和链接信息的修改，但在位置i进行插入删除操作时，需要先定位到位置i-1的结点，而定位操作的平均时间代价为O(n)
双链表
单链表的不足：其指针域仅指向其后继结点，因此从一个结点不能有效的找到其前驱，而补习从表首开始顺着next域逐一查找
双链表的基本思路：每个结点中再增加一个指向前驱的指针。其中next表示指向后继的指针，prev表示指向其前驱的指针
1 | template <class T> |
链表的插入和删除
与单链表不同，若要删除双链表中的一个结点，则不仅要修改该结点的前驱的next域，还要修改该结点后继的prev域
删除一个结点：
- 维护前驱和后继两条链
- 然后吧变量p的前驱和后继置空，再释放p所指的空间
- 插入一个新结点：
- 执行new q开辟新的结点空间
- 填写新结点的数据域信息
- 填写新结点在链表中的链接关系
- 修改p所指结点及其后继结点在新结点插入后的链接信息
- 尽管双链表的空间开销比单链表稍多，但可在O(1)时间内找到给定元素的前驱
循环链表
某些情况需要把结点组成循环链表，将单链表或者双链表的头尾结点链接起来，就是一个循环链表
从循环表中任一结点出发，都能访问到表中其他结点
线性表实现方法的比较
顺序表具有易用、空间开发小、对任意元素进行随机访问的特点，是静态数据的理想选择
链表具有适用于频繁插入删除内部元素，管理长度变化的特点，是动态数据的理想选择
不要使用顺序表的场合：经常插入删除内部元素，无法确定长度的最大值
不要使用链表的场合：经常对线性表进行按位置的访问，而且按位读操作比插入删除操作频繁时，存储开销要求小时
第二章 线性表 OJ作业
1：放苹果
1 | /*描述 |
2：Number Sequence
1 | /*描述 |
3：神奇的幻方
1 | /*描述 |
