data structure

线性表虽然简单,但是要快速地描述出一个极优的结构算法还是要花时间掌握的。

1. 线性表的定义和基本操作

1.1 线性表的定义

线性表是具有相同数据类型的 $n(n\ge0)$ 个数据元素的有序序列,其中 n 为表长,当 n=0 时该线性表是一个空表。若用 L 命名线性表,则其一般表示为

$L=(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n)$

式中,$a_1$ 是唯一的 “第一个” 数据元素,又称为表头元素;$a_n$ 是唯一的 “最后一个” 数据元素,又称为表尾元素。除第一个元素外,每个元素有且仅有一个直接前驱。除最后一个元素外,每一个元素有且仅有一个直接后继。以上就是线性表的逻辑特性,这种线性有序的逻辑结构正是线性名字的由来。

由此,我们可以得到线性表的特点如下:

  1. 表中元素的个数有限。
  2. 表中元素具有逻辑上的顺序性,在序列中各元素排序有其先后次序。
  3. 表中元素都是数据元素,每个元素都是单个元素。
  4. 表中元素的数据类型相同,这意味着每个元素占有相同大小的存储空间。
  5. 表中元素具有抽象性,即仅讨论元素间的逻辑关系,而不考虑元素究竟表示什么内容。

注意:线性表是一种逻辑结构,表示元素之间一对一的相邻关系。顺序表和链表是指存储结构,两者属于不同层面的概念,因此不要将其混淆。

1.2 线性表的基本操作

一个数据结构的基本操作是指其最核心、最基本的操作。其他复杂的操作可通过调用其基本操作来实现。线性表的主要操作如下:

InitList(&L);         // 初始化表。构造一个空的线性表
Length(L);            // 求表长。返回线性表 L 的长度即 L 中数据元素的个数
LocateElem(L,e);      // 按值查找操作。在表 L 中查找具有给定关键字值的元素
GetElem(L,i);         // 按位查找操作。在表 L 中查找具有给定关键字值的元素
ListInsert(&L, i, e); // 插入操作。在表 L 中的第 i 个位置上插入指定元素 e
ListDelete(&L, i, &e);// 删除操作。删除表 L 中第 i 个位置的元素,并用 e 返回删除元素的值
PrintList(L);         // 输出操作。按前后顺序输出线性表 L 的所有元素值。
Empty(L);             // 判空操作。若 L 为空表,则返回 true,否则返回 false
DestroyList(&L);      // 销毁操作。销毁线性表,并释放线性表 L 所占用的内存空间

值得注意的是

  1. 基本操作的实现取决于采用哪种存储结构,存储结构不同,算法的实现也不同。
  2. “&” 表示 C++ 中的引用。若传入的变量是指针型变量,且在函数体内要对传入的指针进行改变,则会用到指针变量的引用型。在 C 中采用指针的指针也可达到相同的效果。

2. 线性表的顺序表示

2.1 顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位置,第 i 个元素的存储位置后面紧跟着存储的是第 i+1 个元素。因此,顺序表的特点是表中元素的逻辑顺序与物理顺序相同。

注意:线性表中元素的为序是从 1 开始的,而数组中元素的下标是从 0 开始的。

假定线性表的元素类型为 ElemType ,则线性顺序存储类型描述为

#define MAXSIZE 50
template<typename ElemType> // 模板参数为数组元素类型和数组长度 
struct SqList {                         // 顺序表类型定义 
	ElemType data[MAXSIZE];              // 顺序表的元素  
	int maxSize, length;                 // 顺序表的最大长度和当前长度 
	SqList() : maxSize(MAXSIZE),length(0) {}
}; 

一维数组可以是静态分配的,也可以是动态分配的。在静态分配时,由于数组的大小和空间事先固定,一旦空间占满,再加入新的数据将会产生溢出,进而导致程序崩溃。

而在动态分配时,存储数组的空间是在程序执行过程中通过动态存储分配语句分配的,一旦数据空间占满,就另外开辟一块更大的存储空间,用以替代原来的存储空间,从而达到扩充存储数组空间的目的,而不需要为线性表一次性地划分所有空间。

#define MAXSZIE 50
template<typename ElemType> // 模板参数为数组元素类型和数组长度 
struct SeqList {                         // 顺序表类型定义 
	ElemType *data;                      // 指向动态分配数组的指针  
	int maxSize, length;                 // 顺序表的最大长度和当前长度 
    SeqList() : maxSize(MAXSIZE),length(0) {
    	data = new ElemType[MAXSIZE];
    }
}; 

C 的初始动态分配语句为

L.data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE)

注意:动态分配并不是链式存储,它同样属于顺序存储结构,物理结构并没有变化,依然是随机存取方式,只是分配的空间大小可以在运行时决定。

顺序表著主要的特点是随机访问,即通过首地址和元素序号可在时间 O(1) 内找到指定的元素。

2.2 顺序表上的基本操作

这里仅给出顺序表的插入操作、删除操作和按值查找的算法,其他基本操作的算法可以从我的 github 仓库找。

  1. 插入操作

    在顺序表 L 的第 $i(1\le i\le L.length+1)$ 个位置插入新元素 e。若 i 的输入不合法,则返回 false,表示插入失败;否则,将顺序表的第 i 个元素及其后的所有元素右移一个位置,腾出一个空位置插入新元素 e,顺序表长度增加 1,插入成功,返回 true 。

    template<typename ElemType>
    bool ListInsert(SqList<ElemType> &L, int i, ElemType e) {
    	// 本算法实现将元素 e 插入到顺序表 L 中第 i 个位置
    	if(i<1 || i > L.length+1)  // 判断 i 的范围是否有效 
    		return false; 
    	if(L.length >= L.maxSize)  // 当前存储空间已满,不能插入
    		return false;
    	for(int j = L.length; j >= i; j--) // 将第 i 个元素及之后的元素后移
    		L.data[j] = L.data[j-1];
    	L.data[i-1] = e;     // 在位置 i 处放入 e
    	L.length ++; 
    	return true; 
    }
    

    注意:区别顺序表的位数和数组下标。为什么判断插入位置是否合法时 if 语句中用 length+1,而移动元素的 for 语句中只用 length ?起始标号不同。

    最好情况:在标为插入(即 i=n+1),元素后移语句将不执行,时间复杂度为 O(1) 。

    最坏情况:在表头插入(即 i=1),元素后移语句将执行 n 次,时间复杂度为 O(n) 。

    平均情况:假设 $p_i(p_i=1/(n+1))$ 是在第 i 个位置上插入一个结点的概率,则在长度为 n 的线性表中插入一个结点时,所需移动结点的平均次数

    因此,线性表插入算法的平均时间复杂度为 O(n) 。

  2. 删除操作

    删除顺序表 L 中第 $i(1\le i\le L.length)$ 个位置的元素,若成功则返回 true,并将被删除的元素用引用变量 e 返回,否则返回 false。

    template<typename ElemType>
    bool ListDelete(SqList<ElemType> &L, int i, ElemType &e) {
    	// 本算法实现删除顺序表 L 中第 i 个位置的元素
    	if(i<1 || i > L.length) // 判断 i 的范围是否有效
    		return false;
    	e = L.data[i-1];
    	for(int j = i; j < L.length; j++) // 将第 i 个位置后的元素前移
    		L.data[j-1] = L.data[j];
    	L.length --;                     // 线性表长度减 1
    	return true; 
    }
    

    最好情况:删除表尾元素(即 i=n ),无须易懂元素,时间复杂度为 O(1)。

    最坏情况:删除表头元素(即 i=1 ),需要移动除第一个元素外的所有元素,时间复杂度为 O(n) 。

    平均情况:假设 $p_i(p_i=1/n)$ 是删除第 i 个位置上结点的概率,则在长度为 n 的顺序表中删除一个结点时,所需移动结点的平均次数

    因此,线性表删除算法的平均时间复杂度为 O(n) 。

  3. 按值查找(顺序查找)

    在顺序表 L 中查找第一个元素值等于 e 的元素,并返回其位序。

    template<typename ElemType>
    int LocateElem(SqList<ElemType> L, ElemType e) {
    	// 本算法实现查找顺序表中值为 e 的元素,如果查找成功,返回元素位序,否则返回 0 
    	for(int i = 0; i < L.length; i++)  
    		if (L.data[i] == e)
    			return i+1;  // 下标为 i 的元素值等于 e,返回其位序 i+1 
    	return 0;    // 退出循环,说明查找失败。 
    }		
    

    最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为 O(1) 。

    最坏情况:查找的元素在表尾(或不存在)时,需要比较 n 次,时间复杂度为 O(n) 。

    平均情况:假设 $p_i(p_i=1/n)$ 是查找的元素在第 $i(1\le i\le L.length)$ 个位置上的概率,则在长度为 n 的线性表中查找值为 e 的元素所需比较的平均次数

    因此,线性表按值查找算法的平均时间复杂度为 O(n) 。

2.3 习题

  1. 从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同。
  2. 从无序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同,且保证时间复杂度为 O(n) 。
  3. 已知在一维数组 A[m+n] 中,前 m 个位置是列表 1,后 n 个位置是列表 2,设计算法实现两个列表调换顺序,空间复杂读为 O(1),时间复杂读为 O(n) 。

2.4 习题答案

  1. 注意有序,顺序遍历做前移即可。
  2. 散列表
  3. 对 A 进行回文串处理,然后对 A[0,n-1] 进行回文串处理,然后对 A[n,m+n-1] 进行回文串处理。