算法和数据结构

绪论

基本概念和术语

数据结构的两个层次

1.逻辑结构

·描述数据元素之间的逻辑关系

·与数据的存储无关，独立于计算机

·是从具体问题抽象出来的数学模型

2.物理结构(存储结构)

·数据元素及其关系在计算机存储器中的结构(存储方式)

·是数据结构在计算机中的表示

逻辑结构与存储结构的关系

·存储结构是逻辑关系的映像与元素本身的映像

·逻辑结构是数据结构的抽象，存储结构是数据结构的实现

·两者综合起来建立了数据元素之间的结构关系

逻辑结构的种类

划分方法一

（1）线性结构

有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继

例如：线性表、栈、队列、串

（2）非线性结构

一个结点可能有多个直接前驱和直接后继

例如：树、图

划分方法二

（1）集合结构:

结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系

（2）线性结构：

结构中的数据元素之间存在着一对一的线性关系

（3）树形结构:

结构中的数据元素之间存在着一对多的层次关系

（4）图状结构或网状结构

结构中的数据元素之间存在着多对多的任意关系

存储结构的种类

顺序存储结构：

用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示

C语言中用数组来实现顺序存储机构

链式存储结构：

用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示

C语言中用指针来实现链式存储结构

索引存储结构：

在存储结点信息的同时，还建立附加的索引表

索引表中的每一项称为一个索引项

索引项的一般形式是:（关键字，地址）

关键字是能唯一标识一个结点的哪些数据项

若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引（Sparse Index）.

散列存储结构：

根据结点的关键字直接计算出该结点的存储地址

数据类型和抽象数据类型

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量，常量或表达式，明确说明它们所属的数据类型

例如，C语言中：

提供int、char、float、double、等基本数据类型

数组、结构、共用体、枚举等构造数据类型

还有指针，空（void）类型

用户也可以用typedef自己定义数据类型

一些最基本数据结构可以用数据类型来实现，如数组、字符串等

而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示

抽象数据类型

是指一个数学模型以及定义在此数学模型上的一组操作

1.由用户定义，从问题抽象出数据模型（逻辑结构）

2.还包括定义在数据模型上的一组抽象运算（相关操作）

3.不考虑计算机内的具体存储与运算的具体实现算法

抽象数据类型的形式定义

抽象数据类型可用(D,S,P)三元组表示。

其中：

​ D是数据对象

​ S是D上的关系集合

​ P是对D的基本操作集

一个抽象数据类型的定义格式：

ADT 抽象数据类型名{

​ 数据对象:<数据对象的定义>

​ 数据关系:<数据关系的定义>

​ 基本操作:<基本操作的定义>

}ADT 抽象数据类型名

其中：数据对象、数据关系的定义用伪代码描述

基本操作的定义格式为:

- 基本操作名（参数表）
- 初始条件：<初始条件描述>
- 操作结果：<操作结果描述>

基本操作定义格式说明：

参数表：赋值参数只为操作提供输入值

​ 引用参数以&打头，除可提供输入值外，还将返回操作结果

初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之

操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果

抽象数据类型定义举例:Circle的定义

ADT 抽象数据类型名{

​ Data

​ 数据对象的定义

​ 数据元素之间逻辑关系的定义

​ Operation

​ 操作1

​ 初始条件

​ 操作结果描述

​ 操作2

​ …

​ 操作n

​ …

}

ADT Circle{

​ 数据对象: D = {r,x,y|r,x,y均为实数}

​ 数据关系: R = {<r,x,y>|r是半径,<x,y>是圆心坐标}

​ 基本操作:

​ Circle(&C,r,x,y)

​ 操作结构:构造一个圆

​ double Area©

​ 初始条件:圆已存在

​ 操作结构:计算面积

​ double Circumstance©

​ 初始条件:圆已存在

​ 操作结果:计算周长

}

抽象数据类型的表示和实现

ADT 抽象数据类型名{

​ Data

​ 数据对象的定义

​ 数据元素之间逻辑关系的定义

​ Operation

​ 操作1

​ 初始条件

​ 操作结果描述

​ 操作2

​ …

​ 操作n

​ …

}

C语言实现抽象数据类型

用已有的数据类型定义描述它的存储结构

用函数定义描述它的操作

就可以在程序中使用

例如：抽象数据类型“复数”的实现

typedef struct{
	float realpart;         /*实部*/
    float imagpart;          /*虚部*/
}Complex

void assign(Complex *A,float real,float imag){    
	A->realpart = real;			/*实部赋值*/
    A->imagepart = imag;		/*虚部赋值*/	
}							  /*End of assign()*/

void add(Complex *c,Complex A,Complex B){        /*c = A + B */
    c->realpart = A.realpart + B.realpart;		/*实部相加*/
    c->imagpart = A.imagpart + B.imagpart;		/*虚部相加*/
} 										     /*End of assign()*/

注意：Complex是我们定义的一个结构体类型

带*：指针变量，它是指向Complex类型的指针

不带*：Complex类型的普通变量

#include <stdlib.h>
typedef struct{
    float realpart;         /*实部*/
    float imagpart;          /*虚部*/
}Complex;
void assign(Complex *A,float real,float imag){
    A->realpart = real;			/*实部赋值*/
    A->imagpart = imag;		/*虚部赋值*/
}
void add(Complex *c,Complex A,Complex B){        /*c = A + B */
    c->realpart = A.realpart + B.realpart;		/*实部相加*/
    c->imagpart = A.imagpart + B.imagpart;		/*虚部相加*/
}
int main(void){
    Complex z1,z2,z3,z4,z;
    float RealPart,ImagePart;
    assign(&z1,8.0,6.0);
    assign(&z2,4.0,3.0);
    add(&z3,z1,z2);
    multiply(z1,z2,z4);
    if(divide(&z,z4,z3)){
        GetReal(&z,RealPart);
        GetImag(&z,ImagePart);
    }
    return 0;
}

以上代码由类C语言实现，仍有不全之处，读者自行补充

算法和算法分析

算法特性:一个算法必须具备以下五个重要特性

• 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在又穷时间内完成
• 确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
• 可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现
• 输入：一个算法有零个或多个输入
• 输出：一个算法有一个或多个输出

算法设计的要求

• 正确性
• 可读性
• 健壮性
• 高效性

算法效率以下两个方面来考虑：

1.时间效率：指的是算法所消耗的时间

2.空间效率：指的是算法执行的过程中所消耗的存储空间

时间效率和空间效率有时候是矛盾的

算法时间效率的度量

算法时间效率可以用一句该算法编制的程序在计算机上执行所消耗的时间来度量

两种度量方法

事后统计：

将算法实现后，测算其时间和空间开销

事前统计：

对算法所消耗资源的一种估算方法

事前分析方法

一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作(如赋值、比较、移动等)所需的时间与算法中进行的简单操作次数乘积

算法运行时间 = 一个简单操作所需的时间 × 简单操作次数

也即算法中每条语句的执行时间之和

算法运行时间 = ∑每条语句的执行次数 × 该语句执行一次所需的时间

每条语句执行一次所需的时间，一般是由机器而异的。取决于机器的指令性能、速度以及编译的代码质量。是由机器本身软硬件环境决定的，它与算法无关。

所以,我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了。

• 例如：两个n×n矩阵相乘的算法可描述为：

  for(i = 1;i <= n; i++){				//n+1次
      for(j = 1; j <= n; j++){		 //n(n+1)次
          c[i][j] = 0;			     //n*n次	
          for(k = 0; k < n; k++){		  //n*n*(n+1)次
              c[i][j] = c[i][j] + a[i][k]*b[k][j];//n*n*n4次
          }
      }
  }

  • 我们把算法所消耗的时间定义为该算法中每条语句的频度之和，则上述算法的时间消耗T(n)为：

    T(n) = 2n³+3n²+2n+1

为了便于比较不同算法的时间效率，我们仅比较它们的数量级

例如：两个不同的算法，时间消耗分别是：

T1(n) = 10n² 与 T2(n) = 5n³

若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则成f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称 O(f(n))为算法的渐进时间复杂度(O是数量级的符号)，简称时间复杂度

算法时间复杂度定义

算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：T(n) = O(f(n))

基本语句:

算法中重复执行次数和算法的执行时间成正比的语句

对算法运行时间的贡献最大

执行次数最多

n越大算法的执行时间越长

排序：n为记录数

矩阵：n为矩阵的阶数

多项式：n为多项式的项数

集合：n为元素个数

树：n为树的结点个数

图：n为图的定点数或边数

定理1.1

若f(n) = am n^m + am-1 n^m-1 + … + a1 n + a0是m次多项式

则T(n) = O(n^m)

忽略所有低次幂项和最高次幂系数，体现出增长率的含义

分析算法时间复杂度的基本方法

1.找出语句频度最大的那条语句作为基本语句

2计算基本语句的频度得到问题规模n的某个函数f(n)

3.取其数量级用符号"O"表示

例1:

x = 0; y =0;
for (int k = 0;k < n; k++)
    x ++;
for (int i = 0;i < n;i++)
    for(int j = 0;j < n;j++)
        y ++;

时间复杂度是由嵌套最深语句的频度决定的

例2：

for(i = 1ji <= n;i++)
    for(j = 1;j <= i;j ++)
        for(k = 1;k <=j; k ++)
            x = x + 1;

​

$语句频度=\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j1=\sum_{i=1}^n\sum_{j=1}^ij=\sum_{i=1}^n\frac{i(i+1)}{2}$

例3:

i = 1；①while(i <= n) ②    i = i * 2;

关键是要找出来执行次数x与n的关系，并形成n的函数

$若循环执行1次：i = 1*2=2,\\ 若循环执行2次：i = 2*2=2^{2},\\ 若循环执行3次：i = 2*2*2=2^{3},\\ 若循环执行x次：i = 2^{x}\\ 设语句②执行次数为x次，由循环条件\\ i \leq n\\ ∴ 2^{x} \leq n\\ ∴ x \leq {log_2{n}}\\ 2^{f(n)} \leq n\\ 即 f(n) \leq {log_2{n}}\\ 取最大值 f(n) = {log_2{n}}\\ 所以该程序段的时间复杂度T(n) = O({log_2{n}})$

请注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同

例：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置

for(i = 0;i < n;i ++)
    if(a[i] == e) return i+1;
return 0;

最好情况：1次

最坏情况：n

平均时间复杂度：O(n)

最坏时间复杂度：指在最坏情况下，算法的时间复杂度

平均时间复杂度：指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间

最好时间复杂度：指在最好情况下，算法的时间复杂度

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长

对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度：

a）加法规则

T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))

b）乘法规则

T(n) = T1(n) × T2(n) = O(f(n)) × O(g(n)) = O(f(n)×g(n))

算法时间效率的比较

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊

时间复杂度T(n)按数量级递增顺序为：

$常数阶 O(1)\\ 对数阶 O({log_2{n}})\\ 线性阶 O(n)\\ 线性对数阶 O(n {log_2{n}})\\ 平方阶 O(n^2)\\ .........\\ 立方阶 O(n^k)\\ 指数阶 O(2^n)$

渐进空间复杂度

• 空间复杂度：算法所需存储空间的度量

记作 S(n) = O(f(n))

其中n为问题的规模

• 算法要占据的空间

算法本身要占据的空间，输入/输出，指令，常数，变量等

算法要是用的辅助空间

例：将一维数组a中的n个数逆序存放到原数组中

【算法1】

for( i = 0; i < n/2; i++){    t = a[i];    a[i] = a[n-i-1];    a[n-i-1] = t;}

S(n) = O(1)

【算法2】

for(i = 0;i < n;i ++)
    b[i] = a[n-i-1]
for(i = 0; i < n;i ++)
    a[i] = b[i]

S(n) = O(n)

线性表

线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列

线性表（Linear List）：

​ 由n(n>=0)个数据元素(结点)a1,a2,…an组成的有限序列

• 其中数据元素的个数n定义为表的长度
• 当n=0时称为空表
• 将非空的线性表(n>0)记作：（a1,a2,an)
• 这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同的情况下可以不同

线性表的例子

例1：分析26个英文字母组成的英文表

(A,B,C,D,…,Z)

数据元素都是字母；元素关系是线性

例2：分析学生情况登记表

学号 姓名 性别 年龄 班级

498623 nww 男 26 9

线性表的逻辑特征

• 从以上例子可看出线性表的逻辑特征是：

  在非空的线性表，有且仅有一个开始结点a1,它没有直接前驱，而有且仅有一个直接后继a2;

有且仅有一个终端节点an，它没有直接后继，而有且仅有一个直接前驱an-1；

其他的内部节点==结点ai(2<=i<=n-1)都有且仅有一个直接前驱ai-1和一个直接后继ai+1

线性表是一种典型的线性结构

案例引入

案例【2.1】一元多项式的运算：实现两个多项式加、减、乘运算

Pn(x) = p0 + p1x + p2x^2 + … + pnx^n

线性表P = (p0,p1,p2…pn)

（每一项的指数i隐含在其系数pi的序号中）

例如P(x) = 10 +5x - 4x^2 + 3x^3 + 2x^4 用数组来表示

指数（下标i）	0	1	2	3	4
系数p[i]	10	5	-4	3	2

稀疏多项式

S(x) = 1 + 3x^10000 + 2x^20000

会造成存储空间的很大浪费,怎么办？

0	10000	20000
1	3	2

案例【2.2】稀疏多项式的运算

多项式非零项的数组表示

(a) A(x) = 7 + 3x + 9x^8 + 5x^17

下标i	0	1	2	3
系数a[i]	7	3	9	5
指数	0	1	8	17

(b) B(x) = 8x + 22x^7 - 9x^8

下标i	0	1	2
系数b[i]	8	22	-9
指数	1	7	8

Pn(x) = p1x^e1 + p2x^e2 + … + pmx^em

线性表 P = （(p1,e1),(p2,e2),…(pm,em)）

线性表 A = ((7,0),(3,1),(9,8,),(5,17))

线性表 B = ((8,1),(22,7),(-9,8))

• 创建一个新数组c

• 分别从头遍历比较a和b的每一项

  ​ 指数相同：对应系数相加，若其和不为0，则在c中增加一个新项

  ​ 指数不相同：则将指数较小的项复制到c中

• 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

顺序存储结构存在问题

• 存储空间分配不灵活
• 运算的空间复杂度高

链式存储结构

线性表的类型定义

基本操作：

InitList(&L)

• 操作结果：构造一个空的线性表L

DestoryList(&L)

• 初始条件：线性表已经存在
• 操作结构：销毁线性表L

ClearList(&L)

• 初始条件：线性表L已经存在
• 操作结果：将线性表L重置为空表

ListEmpty(L)

• 初始条件：线性表L已经存在
• 操作结果：若线性表L为空表，则返回TRUE；否则返回FALSE4

ListLength(L)

• 初始条件：线性表L已经存在
• 操作结果：返回线性表L中的数据元素个数

GetElem(L,i,&e)

• 初始条件：线性表L已经存在，1<=i<=ListLength(L)
• 操作结果：用e返回线性表L中第i个数据元素的值

LocateElem(L,e,compare())

• 初始条件：线性表L已经存在，compare()是数据元素判定函数
• 操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0

PriorElem(L.cur_e,&pre_e)

• 初始条件：线性表L已经存在
• 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义

NextElem(L,cur_e,&next_e)

• 初始条件：线性表L已经存在
• 操作结果：若cur_e是L的数据元素，且不是第最后个，则用next_e返回它的后继，否则操作失败，next_e无意义

ListInsert(&L,i,e)

• 初始条件：线性表L已经存在，1<=i<=ListLengtgh(L) + 1
• 操作结果：在L的第i个位置之前插入新的数据元素e，L的长度加一

ListDelete(&L,i,&e)

• 初始条件：线性表L已经存在，1<=i<=ListDelete(&L,i,&e)
• 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一

ListTraverse(&L,visited())

• 初始条件：线性表L已经存在
• 操作结果：依次对线性表中的每个元素调用visited()

线性表的顺序表示和实现

用一维数组表示顺序表

用一变量表示顺序表的长度属性

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
typedef int Element;
typedef struct{
    ElemType elem[LIST_INIT_SIZE];
    int length; //当前长度
}SqList;

多项式的顺序存储结构类型定义

Pn(x) = p1x^e1 + p2x^e2 + … +pmx^em

#define MAXSIZE 1000    //多项式可能达到的最大长度
typedef struct{		   //多项式非零项的定义
    float p;    	   //系数
    int e;			  //指数
}Polynomial;
typedef struct{
    Polynomial *elem;  //存储空间的基地址
    int length;		  //多项式当前项的个数
}SqList;		      //多项式的顺序结构类型为SqList

图书表的顺序存储结构类型定义

#define MAXSIZE 10000  //图书表可能达到的最大长度
typedef struct{		  //图书信息定义
    char no[20];	  //图书ISBN
    char name[50];	  //图书名字
    float price;	  //图书价格
}Book;
typedef struct{
    Book *elem;		  //存储空间的基地址
    int length;		  //图书表中当前图书个数
}SqList;			 //图书表的顺序存储结构类型为SqList

补充：元素类型说明

顺序表类型定义:

typedef struct{
    //typedef char ElemType;
    ElemType data[];//ElemType 可以是任意类型，所以也可以是自定义的结构体类型，即结构体数组
    int length;
}SqList; //顺序表类型

补充：数组静态分配

typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList; //顺序表类型

补充：数组动态分配

typedef struct{
    ElemType *data;
    int length;
}SqList; //顺序表类型
//动态分配内存
SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);

补充：C语言的内存动态分配

• malloc(m)函数，开辟m字节长度地址空间，并返回这段空间的首地址
• sizeof(x)运算，计算变量x的长度
• free§函数，释放指针p所指变量的存储空间，即彻底删除一个变量

需要加载头文件:<stdlib.h >

顺序表基本操作实现

线性表的基本操作

• InitList(&L) //初始化操作，建立一个空的线性表L
• Destory(&L) //销毁已存在的线性表L
• ClearList(&L) //将线性表清空
• **ListInsert(&L,i,e) ** //在线性表L中的第i个位置插入新元素e
• ListDelete(&L,i,&e) //删除线性表L中的第i个位置元素，用e返回
• IsEmpty(L) //若线性表为空，则返回True，否则False
• ListLength(L) //返回线性表L的元素个数
• LocateElem(L,e) //L中查找与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0
• GetElem(L,i,&e) //将线性表L的第i个位置元素返回给e

补充：操作算法中用到的预定义常量和类型

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

顺序表基本操作的实现

【算法2.1】线性表L的初始化(参数用引用)

Status InitList_Sq(SqList &L){ //构造一个空的顺序表L
    L.elem = (ElemType*)malloc(sizeof(ElemType)*MaxSize); //为顺序表分配空间
    if(!L.elem) exit(OVERFLOW); //存储分配失败
    L.length = 0; //空表长度为0
    return OK;
}

【算法2.2】销毁线性表

void Destory(SqList &L){
    if(L.elem) free(L.elem); //释放存储空间
}

【算法2.3】清空线性表

void ClearList(SqList &L){    L.length = 0; //将线性表的长度置为0}

【算法2.4】求线性表的长度

int GetLength(SqList L){    return L.length;}

【算法2.5】判断线性表是否为空

int IsEmpty(SqList L){    if (L.length == 0) return 1;    else return 0;}

【算法2.6】顺序表的取值(根据位置i获取相应位置数据元素的内容)

int GetElem(SqList L,int i,ElemType &e){    if (i<1||i>L.length) return ERROR; //判断i值是否合理，若不合理，则返回ERROR    e = L.elem[i-1]; //第i-1单元存储着第i个数据    return OK;}

顺序表上的查找操作

按值查找：

例如：在图书表中，按照给定书号进行查找，确定是否存在该图书

如果存在：输出是第几个元素

如果不存在：输出0

【算法2.7】顺序表的查找

• 在线性表L中查找与指定值e相同的数据元素的位置
• 从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0

int LocateElem(SqList L,ElemType e){    //在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)    for(i = 0; i < L.length ;i ++){        if(L.elem[i] == e){            return i+1;	//查找成功，返回序号        }        return 0;// 查找失败，返回0    }}

int LocateElem(SqList L,ElemType e){
     //在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)
    i = 0；
    while(i<L.length&&L.elem[i]!=e) i++;
    if(i<L.length) return i+1; //查找成功，返回序号
    return 0;// 查找失败，返回0
}

顺序表的查找算法分析：

因为查找算法的基本操作为：将记录的关键字同给定值进行比较

​ 基本操作：L.elem[i] == e

平均查找长度ASL(Average Search Length):

​ 为确定记录在表中位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度

$ASL = \sum_{i = 1}^nP_iC_i$

【算法2.8】顺序表的插入

算法思想：

• 判断插入位置i是否合法
• 判断顺序表的存储空间是否已满，若已满返回ERROR
• 将第n至第i位的元素依次向后移动一个位置，空出第i个位置
• 将要插入的新元素e放入第i个位置

Status ListInsert_Sq(SqList &L,int i,ElemType e){
    ① if(i<1||i>L.length+1) return ERROR;//i值不合法
    ② if(L.length == MAXSIZE) return ERROR;//当前存储空间已满
    ③ for(j = L.length-1;j>=i-1;j--){
      	L.elem[j+1] = L.elem[j];//插入位置及之后的元素后移
    }
    ④ L.elem[i-1] = e;//将新元素e放入第i个位置
    ⑤ L.length ++;//表长加一
}

【算法2.9】顺序表的删除

算法思想：

• 判断删除位置i是否合法（合法值为1<=i<=n）
• 将欲删除的元素保留在e中
• 将第i+1至第n位的元素依次向前移动一个位置
• 表长减一，删除成功返回OK

Status ListDelete_Sq(SqList &L,int i){
    ① if(i<1||i>L.length) return ERROR;//i值不合法
    ② for(j = i;j<=L.length-1;j++){
        L.elem[j-1] = L.elem[j];//被删除元素之后的元素前移
    }
    ④ L.length--;//表长减一
    return OK;
}

小结

顺序表(线性表的顺序存储结构)的特点

（1）利用数据元素的存储位置表示线性表中的相邻数据元素之间的前后关系，即线性表得逻辑结构与存储结构一致

（2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等

• 这种存取元素的方法被称为随机存取法

线性表的基本操作

• InitList(&L) //初始化操作，建立一个空的线性表L
• Destory(&L) //销毁已存在的线性表L
• ClearList(&L) //将线性表清空
• **ListInsert(&L,i,e) ** //在线性表L中的第i个位置插入新元素e
• ListDelete(&L,i,&e) //删除线性表L中的第i个位置元素，用e返回
• IsEmpty(L) //若线性表为空，则返回True，否则False
• ListLength(L) //返回线性表L的元素个数
• LocateElem(L,e) //L中查找与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0
• GetElem(L,i,&e) //将线性表L的第i个位置元素返回给e

优点

• 存储密度大（结点本身所占存储量/结点结构所占存储量）
• 可以随机存取表中任一元素

缺点

• 在插入、删除某一元素时，需要移动大量元素
• 浪费存储空间
• 属于静态存储形式，数据元素的个数不能自由扩充

线性表的链式表示和实现

链式存储结构

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

线性表的链式表示又称为非顺序映像或链式映像

• 用一组物理位置任意的存储单元来存放线性表的数据元素
• 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中任意位置上的
• 链表中元素的逻辑次序和物理次序不一定相同

例

线性表（赵，钱，孙，李，周，吴，郑，王）

顺序表

存储地址	存储状态
0031	赵
0033	钱
0035	孙
0037	李
0039	周
0041	吴
0043	郑
0045	王

链表

存储地址	数据域	指针域
0001	李	0043
0007	钱	0013
0013	孙	0001
0019	王	NULL
0025	吴	0037
0031	赵	0007
0037	郑	0019
0043	周	0025

与链式存储有关的术语

1.结点：数据元素的存储映像。由数据域和指针域两部分组成

2.链表：n个结点由指针链组成一个链表

​ 它是线性表的链式存储映像，称为线性表的链式存储结构

3.单链表、双链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表

结点有两个指针域的链表，称为双链表

首尾相接的链表称为循环链表

4.头指针、头结点和首元结点：

头指针：是指向链表中第一个结点的指针

首元结点：是指向链表中存储第一个数据元素a1的结点

头结点：是在链表的首元结点之前附设的一个结点

如何表示空表？

• 无头结点时，头指针为空时表示空表
• 有头结点时，当头结点的指针域为空时表示空表

在链表中设置头结点有什么好处？

1 便于首元结点的处理

​ 首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理

2 便于空表和非空表的统一处理

​ 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了

头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放表长度等附加信息，但此结点不能计入链表长度值

链表的特点

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
• 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费时间不等。这种存取元素的方法被称为顺序存取法

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名，若头指针名是L，则把链表称为表L

单链表的存储结构：

typedef struct Lnode{//声明结点的类型和指向结点的指针类型
    ElemType data;//结点的数据域
    struct Lnode *next;//结点的指针域
}Lnode,*LinkList;//LinkList为指向结构体Lnode的指针类型

**定义一个链表L：**LinkList L;

**定义结点指针p：**LNode *p；LinkList p；

例如：存储学生学号、姓名、成绩的单链表结点类型定义如下：

typedef struct student{
    char num[8];//数据域
    char name[8];//数据域
    int score;//数据域
    struct student *next;//指针域
}Lnode,*LinkList;

单链表基本操作的实现

单链表的初始化

即构造一个空表

【算法步骤】

1. 生成新结点作头结点，用头指针L指向头结点
2. 将头结点的指针域置空

【算法描述】

typedef struct Lnode{//声明结点的类型和指向结点的指针类型
    ElemType data;//结点的数据域
    struct Lnode *next;//结点的指针域
}LNode,*LinkList;//LinkList为指向结构体Lnode的指针类型

Status InitList L(LinkList &L){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

【补充算法1】判断链表是否为空

空表：链表中无元素，称为空链表(头指针和头结点仍然在)

【算法思路】判断头结点指针域是否为空

int ListEmpty(LinkList L){//若L为空表，则返回1，否则返回0
    if(L->next)//非空
        return 0;
    else
        return 1;
}

【补充算法2】单链表的销毁：链表销毁后不存在

【算法思路】从头指针开始，依次释放所有结点

Status DestoryList L(LinkList &L){//销毁单链表L
    Lnode *p;//或LinkList p;
	 while(L){
        p = L;
        L = L->next;
        free(p);
    }
    return OK;
}

【补充算法3】清空链表

链表仍存在，但链表中无元素，成为空链表(头指针和头结点仍然在)

【算法思路】依次释放所有结点，并将头结点指针域设置为空

Status ClearList(LinkList &L){//将L重置为空表
    Lnode *p,*q;//或LinkList p,q;
    p = L->next;
    while(p){//没到表尾
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL; //头结点指针域为空
    return OK;
}

【补充算法4】求单链表的表长

【算法思路】从首元结点开始，依次计数所有结点

int ListLength_L(LinkList L){//返回L中数据元素个数
    LinkList p;
    p = L->next;//p指向第一个结点
    i = 0;
    while(p){//遍历单链表，统计结点数
        i++;
        p = p->next;
    }
    return i;
}

【算法2.7】取值——取单链表中第i个元素的内容

【算法思路】从链表的头指针出发，顺着链域next逐个结点往下搜索，直到搜索到底i个结点为止。因此，链表不是随机存取结构

1.从第1个结点(L->next)顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next

2.j做计数器，累计当前扫描过得结点数，j初值为1

3.当p指向扫描到的下一结点时，计数器j加1

4.当j==i时，p所指的结点就是要找的第i个结点

Status GetElem_L(LinkList L,int i,ElemType &e){//获取线性表L中的某个数据元素的内容，通过变量e返回
    p = L->next; j =1;//初始化
    while(p&&j<i){//向后扫描，直到p指向第i个元素或p为空
    	p = p->next; ++j;
    }
    if(!p||j>i) return ERROR; //第i个元素不存在
    e = p->data; //取第i个元素
    return OK;
}

【算法2.8】按值查找——根据指定数据获取该数据所在的位置(地址)

【算法思路】

1.从第一个结点起，依次和相比较

2.如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址；

3.如果查遍整个链表都没找到其值和e相等的元素，则返回0或“NULL“

Lnode *LocateElem_L(LinkList L,ElemType e){
    //在线性表L中查找值为e的数据元素
    //找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
    p = L->next;
    while(p&&p->data!=e){
        p = p->next;
    }
    return p;
}

【算法2.8变化】按值查找——根据指定数据获取该数据位置序号

//在线性表L中查找值为e的数据元素的位置序号
int LocateElem_L(LinkList L,ElemType e){
    //返回L中值为e的数据元素的位置序号查找失败返回0
    p = L->next; j = 1;
    while(p&&p->data!=e){
        p = p->next;
        j ++;
    }
    if(p) return j;
    else return 0;
}

【算法2.9】插入——在第i个结点前插入值为e的新结点

【算法思路】

$1.首先找到a_{i-1}的存储位置p\\ 2.生成一个数据域为e的新结点s\\ 3.插入新结点:\\①新结点的指针域指向结点a_i\\ ②结点a_{i-1}的指针域指向新结点\\ s->next = p->next\\ p->next = s$

//在L中第i个元素之前插入数据元素e
Status ListInsert(LinkList &L.int i,ElemType e){
    p = L;j = 0;
    while(p&&j<i-1){
        p = p->next;//寻找第i-1个结点，p指向i-1结点
        ++j;
    }
    if(!p||j>i-1) return ERROR;//i大于表长+1或者小于1，插入位置非法
    s = (LinkList)malloc(sizeof(LNode)); s->data = e;//生成新结点s，将结点s的数据域置为e
    s->next = p->next;//将结点s插入L中
    p->next = s;
    return OK;
}

【算法2.10】删除——删除第i个结点

【算法思路】

$1.首先找到a_{i-1}的存储位置p，保存要删除的a_i的值\\ 2.令p->next指向a_{i+1}\\ p->next = p->next->next\\ 3.释放结点a_i的空间$

//将线性表L中的第i个元素删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p = L; j = 0;
    while(p->next&&j<i-1){
        //寻找第i个结点，并令p指向其前驱
        p = p->next;
        ++ j;
    }
    if(!(p->next)||j>i-1) return ERROR;//删除位置不合理
    q = q->next;//临时保存被删结点的地址以备释放
    p->next = q->next;//改变删除结点前驱结点的指针域
    e = q->data;//保存删除结点的数据域
    free(q);//释放删除结点的空间  
    return Ok;
}

单链表的查找、插入、删除算法时间效率分析

1.查找：

因线性表只能顺序存取，即查找时要从头指针找起，查找的时间复杂度为O(n)

2.插入和删除:

因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度O(1)

但是，如果要在单链表中进行前插或者删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)

【算法2.11】建立单链表：头插法——元素插入在链表头部，也叫前插法

【算法思路】

1.从一个空表开始，重复读入数据

2.生成新结点，将读入数据存放到新结点的数据域中

3.从最后一个结点开始，依次将各结点插入到链表的前端

void CreatList_H(LinkList &L,int n){
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;//先建立一个带头结点的单链表
    for(i = n;i > 0;i --){
        p = (LNode*)malloc(sizeof(LNode));//生成新结点
        scanf(&p->data);//输入元素值
        p->next = L->next;//插入到表头
        L->next = p;
    }
}

【算法2.12】建立单链表：尾插法——元素插入在链表尾部，也叫后插法

【算法思路】

1.从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点

2.初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点

//正位序输入n个元素的值，建立带表头结点的单链表L
void CreatList_R(LinkList &L,int n){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    r = L;//尾指针r指向头结点
    for(int i = 0 ; i < n; i ++){
        p = (LinkList)malloc(sizeof(LNode)); // 生成新结点
        scanf(&p->data);//输入元素值
        p->next = NULL;
        r->next = p; //插入到表尾
        r = p; //r指向新的表尾结点
    }
}

循环链表

是一种头尾相接的链表(即：表中最后一个结点的指针域指向头结点，整个链表形成一个环)

优点：从表中任一结点出发均可找到表中其他结点

注意：

​ 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断它们是否等于头指针

循环条件：

​ 单链表

p != NULL
p->next != NULL

​ 单循环链表

p != L
p->next != L

注意：表的操作常常是在表的首尾位置上进行

​ 头指针表示单循环列表

$找a_1的时间复杂度：O(1)\\ 找a_n的时间复杂度：O(n)$

不方便

​ 尾指针表示单循环链表

$a_1的存储位置是: R->next->next\\ a_n的存储位置是: R\\ 时间复杂度都是O(1)$

带尾指针的循环链表的合并(将Tb合并在Ta之后)

分析有哪些操作？

• p存表头结点
• Tb表头连接到Ta表尾
• 释放Tb表头结点
• 修改指针

p = Ta->next
Ta->next = Tb->next->next
free(Tb->next)
Tb->next = p

LinkList Connect(LinkList Ta,LinkList Tb){
    //假设Ta,Tb都是非空的单循环链表
    p = Ta->next; //①p存表头结点
    Ta->next = Tb->next->next;//②Tb表头连接Ta表尾
    free(Tb->next);//③释放Tb表头结点
    Tb->next = p;//④修改指针
    return Tb;
}

双向链表

为什么要讨论双向链表:

单链表：

• 单链表的结点-有指示后继的指针域-找后继结点方便

即：查找某结点的后继结点的执行时间为O(1)

• 无指示前驱的指针域-找前驱结点难：从表头出发查找

即：查找某结点的前驱结点的执行时间为O(n)

在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样链表中就形成了有两个方向不同的链，故称为双向链表

双向链表的结构可以定义如下：

typedef struct DuLNode{
    Elemtype data;
    struct *prior,*next;
}DuLNode,*DuLinkList;

双向循环链表

​ 和单链的循环表类似，双向链表也可以有循环链表

• 让头结点的前驱指针指向链表的最后一个结点
• 让最后一个结点的后继指针指向头结点

双向链表的对称性（设指针p指向某一个结点）：

​ p->prior->next = p = p->next->prior

在双向链表中有些操作(如：ListLength、GetElem等)，因仅涉及一个方向的指针，故它们的算法与线性链表的相同。但在插入、删除时在，则需同时修改两个方向上的指针，两者操作的时间复杂度均为O(n)

【算法2.13】双向链表的插入

1. s->prior = p->prior
2. p->prior->next = s
3. s->next = p
4. p->prior = s

void ListInsert_DuL(DuLinkList &L,int i,ElemType e){
    //在带头结点的双向循环链表L中第i个位置之前插入元素e
    if(!(p=GetElemP_DuL(L,i))) return ERRPR;
    s = (DuLinkList)malloc(sizeof(DuLNode));
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}

【算法2.14】双向链表的删除

1. p->prior->next = p->next
2. p->next->prior = p->prior

void ListDelete_DuL(DuLink &L,int i,ElemType e){
    //删除带头结点的双向链表L的第i个元素，并用e返回
    if(!(p = GetElemP_DuL(L,i))) return  ERROR;
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}

单链表、循环链表、和双向链表时间效率比较

	查找表头结点(首元结点)	查找表尾结点	查找结点*p的前驱结点
带头结点的单链表L	L->next 时间复杂度O(1)	从L->next 依次向后遍历时间复杂度O(n)	通过p->next无法找到其前驱
带头结点仅设头指针的循环单链表	L->next 时间复杂度O(1)	从L->next 依次向后遍历时间复杂度O(n)	通过p->next可以找到前驱 时间复杂度O(n)
带头结点仅设尾指针R的循环单链表	R->next 时间复杂度O(1)	R 时间复杂度O(1)	通过p->next可以找到前驱 时间复杂度O(n)
带头结点的双向循环链表L	L->next 时间复杂度O(1)	L-prior 时间复杂度O(1)	p->prior 时间复杂度O(1)

顺序表和链表的比较

链式存储结构优点：

​ 结点空间可以动态申请和释放

​ 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素

链式存储结构缺点：

​ 存储密度小没每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大

​ 链式存储结构是非随机存取结构。对任一节点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度

存储密度

是指结点数本身所占的存储量和整个结点结构所占存储量之比，即

存储密度 = 结点数据本身占用的空间/结点占用的空间总量

线性表的应用

线性表的合并：

​ 问题描述：

​ 假设利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=A∪B

​ La = （7,5,3,11）Lb = （2,6,3）=》 La = （7,5,3,11,2,6）

【算法思路】

依次取出Lb中的每个元素，执行以下操作：

1.在La中查找该元素

2.如果找不到，则将其插入La的最后

void union(List &La,List &Lb){
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    for( i = 1 ; i < Lb_len; i ++ ){
        GetElem(Lb,i,e);
        if(!LocateElem(La,e)) ListInsert(&La,++La_len,e);
    }
}

有序表的合并：

​ 问题描述：

​ 已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素扔按值非递减有序排列

La = (1,7,8) Lb = (2,4,6,8,10,11) => Lc = (1,2,4,6,7,8,8,10,11)

【算法思路】

1.创建一个空表

2.依次从La中或Lb中"摘取"元素值娇小的结点插入到Lc表的最后，直至其中一个变空表为止

3.继续将La或Lb其中一个表的剩余结点插入在Lc表的最后

顺序表实现

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
    pa = LA.elem;
    pb = LB.elem;//指针pa，pb的初值分别指向两个标的第一个元素
    LC.length = LA.length + LB.length; //新表长度为待合并两表的长度之和
    LC.elem = (int *)malloc(sizeof(LC.length));//为合并后的新表分配一个数组空间
    pc = LC.elem; //指针pc指向新表的第一个元素
    pa_last = LA.elem + LA.length - 1;//指针pa_last指向LA表的最后一个元素
    pb_last = LB.elem + LB.length - 1;//指针pb_Last指向LB表的最后一个元素
    while(pa<=pa_last&&pb<=pb_last){//两个表都非空
        if(*pa<=*pb) *pc ++ = *pa++;//依次"摘取"两表中值娇小的结点
        else *pc ++ = *pb ++;
    }
    while(pa<=pa_last) *pc++ = *pa++; //LB表已到达表尾，将LA中剩余元素加入LC
    while(pb<=pb_last) *pc++ = *pb++;//表LA已到达表尾，将LB中剩余元素加入LC
}

链表实现

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    pa = La->next;
    pb = Lb->next;
    pc = Lc = La; //用La的头结点作为Lc的头结点
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }else{
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa?pa:pb;//插入剩余段
    free(Lb);//释放Lb的头结点        
}

案例分析与实现

【案例2.1】一元多项式的运算：实现两个多项式加、减、乘运算

$P_n(x) = p_0+p_1x+p_2x^2+...+p_nx^n\\ 线性表P = (p_0,p_1,p_2,...,p_n)\\ 每一项的指数i隐含在其系数p_i的序号中$

例如:

$P(x) = 10 + 5x - 4x^2 + 3x^3 + 2x^4$

​

指数(下标i)	0	1	2	3	4
系数p[i]	10	5	-4	3	2

例如 实现两个多项式相加运算

$Pa(x) = 10 + 5x - 4x^2 + 3x^3 + 2x^4\\ Pb(x) = -3 + 8x + 4x^2 - 5x^4 + 7x^5 - 2x^6$

系数Pa[i] 10 5 -4 3 2

系数Pb[i] -3 8 4 0 -5 7 -2

系数Pc[i] 7 13 0 3 -3 7 -2

【案例2.2】系数多项式的运算

多项式非零项的数组表示

$(a) A(x) = 7 + 3x + 9x^8 + 5x^{17}$

下标i	0	1	2	3
系数a[i]	7	3	9	5
指数	0	1	8	17

$(b) B(x) = 8x + 22x^7 - 9x^8$

下标i	0	1	2
系数b[i]	8	22	-9
指数	1	7	8

$P_n(x) = p_1x^{e_1} + p_2x^{e_2} + ... + p_mx^{e_m}$

$线性表 P = ((p_1,e_1),(p_2,e_2),...,(p_m,e_m))$

线性表A = ((7,0),(3,1),(9,8),(5,17))

线性表B = ((8,1),(22,7),(-9,8))

• 创建一个新数组C

• 分别从头遍历比较a和b的每一项

  ​ 指数相同，对应系数相加，若其和不为零，则在c中增加一个新项

  ​ 指数不相同，则将指数较小的项复制到c中

• 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

链式存储结构结点定义

typedef struct PNode{
    float coef; //系数
    int expn; //指数
    struct PNode *next;//指针域
}PNode,*Polynomial;

【算法步骤】多项式创建

①0创建一个只有头结点的空链表

②根据多项式的项的个数n，循环n次执行以下操作：

• 生成一个新结点*s
• 输入多项式当前项的系数和指数赋给新结点*s的数据域
• 设置一前驱指针pre，用于指向待找到的第一大于输入项指数的结点的前驱，pre初始值指向头结点
• 指针q初始化，指向首元结点
• 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q
• 将输入项结点 *s 插入到结点 *q之前

void CreatPolyn(Polynomial &P,int n){
    //输入m项的系数和指数，建立表示多项式的有序链表P
    P = new PNode;
    P->next = NULL;//先建立一个带头结点的单链表
    for(i = 1;i <=n ;i++){//依次输入n个非零项
    	s = new PNode;//生成新结点
        cin>>s->coef>>s->expn;//输入系数和指数
        pre = P;//pre用于保存q前驱，初值为头结点
        q = P->next;//q初始化，指向首元结点
        while( q && q->expn < s->expn ){//找到第一个大于输入项指数的项*q
            pre = q;
            q = q->next;
        }
        s->next = q;//将输入项s插入到q和其前驱结点pre之间
        pre->next = s;
    }
}

【算法思路】多项式相加

①指针p1和p2初始化，分别指向Pa和Pb的首元结点

②p3指向和多项式的当前结点，初值为Pa的头结点

③当指针p1和p2均未到达表尾时，则循环比较p1的p2所指结点对应的指数值

（p1->expn与p2->expn),有下列3种情况

• 当p1->expn==p2->expn时，则将两个结点中的系数相加

  若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点

  若和为零，则删除p1和p2所指结点

• 当 p1->expn < p2->expn时，则应摘取p1所指结点插入到"和多项式"链表中去

• 当p1->expn > p2->expn时，则应摘取p2所指结点插入到"和多项式"链表中去

④将非空多项式的剩余段插入到p3所指结点之后

⑤释放Pb的头结点

【案例2.3】图书信息管理系统

struct Book{
    char id[20]; //ISBN
    char name[50]; //书名
    int price; //定价
};

typedef struct{//顺序表
    Book *elem;
    int  length;
}SqList;

typedef struct LNode{//链表
	Book data;
    struct LNode *next;
}LNode,*LinkList;

栈和队列

栈和队列的定义和特点

栈和队列是两种常用的、重要的数据结构

栈和队列是限定插入和删除只能在表的"端点"进行的线性表

线性表

Insert(L,i,x) 1<=i<=n+1

Delete(L,i) 1<=i<=n

栈 先进后出

Insert(S,n+1,x)

Delete(S,n)

队列 先进先出

Insert(Q,n+1,x)

Delete(Q,1)

栈的应用

• 由于栈的操作具有后进先出的固有特性，使得栈称为程序设计的有用工具。另外，如果问题求解的过程具有"后进先出"的天然特性的话，则求解的算法中也必然需要利用"栈"

  例如：

  - 数值转换                           - 表达式求值

  - 括号匹配的检验                - 八皇后问题

  - 行编辑程序                       - 函数调用

  - 迷宫求解                           - 递归调用的实现

队列的常见应用

• 由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具

  - 脱机打印输出：按申请的先后顺序依次输出

  - 多用户系统中，多个用户排成队，分时地循环使用CPU和主存

  - 按用户的优先级排成多个队，每个优先级一个队列

  - 实时控制系统中，信号按接收的先后顺序依次处理

  - 网络电文传输，按到达时间先后顺序依次进行

栈的定义和特点

栈(Stack)是一个特殊的线性表，是限定仅在一端(通常是表尾)进行插入和删除操作的线性表

又称为后进先出(Last In First Out)的线性表，简称LIFO结构

栈的相关概念

​ 栈是仅在表尾进行插入、删除操作的线性表

​ 表尾（即an端）称为栈顶Top；表头（即a1端）称为栈底Base

$例如：栈 S = (a_1,a_2,a_3,...,a_n)\\ a_1称为栈底元素 \\ a_n称为栈顶元素$

插入元素到栈顶(即表尾)的操作，称为入栈

从栈顶(即表尾)删除最后一个元素的操作，称为入栈

“入” = 压入 = PUSH(x)

“出” = 弹出 = POP(x)

【思考】假设有3个元素a,b,c，入栈顺序是a,b,c,则它们的出栈顺序有几种可能？

​ c b a , a b c, a c b, b a c, b c a

插入的时机不一样 出栈顺序不一样

队列的定义和特点

队列(queue)是一种先进先出(First In First Out ----FIFO)的线性表。在表的一端插入(表尾)，在另一端(表头)删除

案例引入

【案例3.1】进制转换

• 十进制整数N向其他进制数d(二、八、十六)的转换是计算机实现计算的基本问题

转换法则:除以d倒取余

该转换法则对应于一个简单算法原理

n = (n div d)*d + n mod d

其中：div为整除运算，mod为求余运算

例 把十进制数159转换成八进制数

159/8 = 19 余7

19/8 = 2 余3

2/8 = 0 余2

所以是237 后进先出 用栈

【案例3.2】括号匹配的检验

• 假设表达式中允许包含两种括号：圆括号和方括号
• 其嵌套的顺序随意，即：
  1. （ [ ] ( ) ) 或 [ ( [ ] [ ])]为正确格式
  2. [ ( ] ) 为错误格式
  3. ( [ ( ) 或 ( ( ) ] )为错误格式

【算法思路】

• 可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况
• 在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论
  1. 当遇到某一个右括号时，栈已空，说明到目前为止，右括号多余左括号
  2. 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况
  3. 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号

【案例3.3】表达式求值

• 表达式求值是程序设计语言编译中一个最基本的问题，它的实现也需要运用栈
• 这里介绍算法是由运算符优先级确定运算顺序的对表达式求值算法

算符优先算法

• 表达式的组成

  • 操作符(operand)：常数、变量
  • 运算法(operator)：算术运算符、关系运算符和逻辑运算符
  • 界限符(delimiter)：左右括弧的表达式结束符

• 任何一个算术表达式都由操作数(常数、变量)、算数运算符(+、-、*、/)和界限符(括号、表达式结束符’#’.虚设的表达式起始符’#’)组成。后者统称为运算符

  • 例如： # 3 *(7-2) #

为了实现表达式求值。需要设置两个栈:

​ 一个是算符栈OPTR，用于寄存运算符

​ 另一个是称为操作数符OPND，用于寄存运算数和运算结果

求值的处理过程是自左至右扫描表达式的每一个字符

• 当扫描到的是运算符，则将其压入栈OPND

• 当扫描到的是运算符时

  • 若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理
  • 若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算符，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果入栈OPND

• 继续处理当前字符，直到遇见结束符为止

【案例3.4】舞伴问题

• 假设在舞会上，男士和女士各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题

• 显然，先入队的男士或女士先出队配成舞伴。因此该问题具有典型的先进先出特性，可以用队列作为算法的数据结构

  • 首先构造两个队列
  • 依次从队头元素出队配成舞伴
  • 某队为空，则另外一队等待者则是下一舞曲第一个可获得舞伴的人

栈的表示和操作的实现

顺序栈的表示和实现

存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端

• 附设top指针，指示栈顶元素在顺序栈中的位置
• 另设base指针，指示栈底元素在顺序栈中的位置

但是，为了方便操作，通常top指示真正的栈顶元素之上的下标地址

• 另外，用stacksize表示栈可使用的最大容量

空栈：base==top是栈空标志

栈满：top-base==stacksize

栈满时的处理方法：

​ 1.报错，返回操作系统

​ 2.分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈

使用数组作为顺序栈存储方式的特点：

​ 简单方便 但易溢出 （数组大小固定）

上溢(overflow):栈已经满，又要压入元素

下溢(underflow):栈已经空，还要弹出元素

**注：**上溢是一种错误，使问题的处理无法进行，而下溢一般认为是一种结束条件，即问题处理结束

顺序栈的表示

#define MAXSIZE 100
typedef struct{
    SElemType *base;//栈底指针
    SElemType *top;//栈顶指针
    int stacksize;//栈可用最大容量
}SqStack;

顺序栈相关算法

【算法3.1】顺序栈的初始化

Status InitStack(SqStack &S){//构造一个空栈
	S.base = (SElemType)malloc(MAXSIZE*sizeof(SElemType));
    if(!S.base) exit(OVERFLOW);//存储分配失败
    S.top = S.base;//栈顶指针等于栈底指针
    S.tacksize = MAXSIZE;
    return OK;
}

【算法补充】顺序栈判断栈是否为空

Status StackEmpty(SqStack S){
    //若栈为空，则返回TRUE；否则返回FALSE
    if(S.top == S.base){
        return TRUE;
    }else{
        return FALSE;
    }
}

【算法补充】求顺序栈的长度

int StackLength(SqStack S){
    return S.top-S.base;
}

【算法补充】清空顺序栈

Status ClearStack(SqStack &S){
    if(S.base) S.top == S.base;
    return OK;
}

【算法补充】销毁顺序栈

Status DestoryStack(SqStack &S){
    if(S.base){
        free(S.base);
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return OK; 
}

【算法3.2】顺序栈的入栈

1.判断是否栈满，若满则出错(上溢)

2.元素e压入栈顶

3.栈顶指针加1

Status Push(SqStack &S,SElemType e){
    if(S.top-S.base == S.stacksize) //栈满
        return ERRPR;
    *S.top = e;
    S.top++;
}

【算法3.3】顺序栈的出栈

1. 判断是否栈空，若空则出错(下溢)
2. 栈顶指针减1
3. 获取栈顶元素e

Status Pop(SqStack &S,SElemType &e){
    //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
    if(S.top == S.base) //等价于if(StackEmpty(S))
        return ERROR;
    e = *--S.top;
    return OK; 
}

链栈的表示和实现

链栈的表示

链栈是运算受限的单链表，只能在链表头部进行操作

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*Linkstack;

注意：链表中指针的方向是反过来的

• 链表的头指针就是栈顶
• 不需要头结点
• 基本不存在栈满的情况
• 空栈相当于头指针指向空
• 插入和删除仅在栈顶处执行

【算法3.5】链栈的初始化

void InitStack(LinkStack &S){
    //构造一个空栈，栈顶指针置为空
    S = NULL;
    return OK;
}

【补充算法】判断链栈是否为空

Status StackEmpty(LinkStack S){
    if(S == NULL) return TRUE;
    else return FALSE;
}

【算法3.6】链栈的入栈

Status Push(LinkStack &S,SElemType e){
    p = (LinkStack)malloc(sizeof(StackNode)); //生成新结点p
    p->data = e; //将新结点数据域置为e
    p->next = S; //将新结点插入栈顶
    S = p;//修改栈顶指针
    return OK;
}

【算法3.7】链栈的出栈

Status Pop(LinkStack &S,SElemType &e){
    if(S==NULL) return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    free(p);
    return OK;
}

【算法3.8】取栈顶元素

SElemType GetTop(LinkStack S){
    if(S!==NULL)
        return S->data;
}

栈与递归

• 递归的定义
  • 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的
  • 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程

分治法求解递归算法的一般形式：

void p(参数表){
    if(递归结束条件) 可直接求解步骤; //基本项
    else p(较小的参数); //归纳项
}

• 函数调用过程

  调用前，系统完成

  1. 将实参，返回地址等传递给被调函数
  2. 为被调函数的局部变量分配存储区
  3. 将控制转移到被调函数的入口

  调用后，系统完成

  1. 保存被调函数的计算结果
  2. 释放被调函数的数据区
  3. 依照被调用函数保存的返回地址将控制转移到调用函数

队列的表示和操作的实现

队列的顺序表示——用一位维数组base[MAXSIZE]

#define MAXSIZE 100//最大队列长度
typedef struct{
    QElemType *base;//初始化的动态分配存储空间
    int front;//头指针 称为指针，但不是指针变量
    int rear;//尾指针
}SqQueue;

入队存在的问题

设数组大小为MAXSIZE

rear =MAISIZE时，发生溢出

若 front = 0 rear = MAXSIZE时，再入队，真溢出

若 front ≠ 0 rear = MAXSIZE时，再入队，假溢出

解决假上溢的办法

1. 将队中元素依次向队头方向移动

   缺点：浪费时间。每移动一次，队中元素都要移动

2. 将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxsize时，若向量的开始端空着，又可以从头使用空着的空间。当front为maxsize时，也是一样

引入循环队列

base[0]

接在base[MAXSIZE-1]之后，若rear+1==M,则令rear=0

实现方法:利用模(mod,C语言中:%)运算

插入元素:Q.base[Q.rear] = x

​ Q.rear = (Q.rear+1)%MAXSIZE

删除元素：x = Q.base[s.front]

​ Q.front = (Q.front+1)%MAXSIZE

队空：front == rear

队满：front == rear

解决方案：

1. 另外设一个标志以区别队空、队满
2. 另设一个变量，记录元素个数
3. 少用一个元素空间

【算法3.11】队列的初始化

Status InitQueue(SqQueue &Q){
    Q.base = (QElemType*)malloc(MAXSIZE*sizeof(QElemType));//分配数组空间
    if(!Q.base) exit(OVERFLOW);//存储分配失败
    Q.front = Q.base = 0;//头指针尾指针置为0，队列为空
    return OK;
}

【算法3.12】求队列的长度

int QueueLength(SqQueue Q){
	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;                        
}

【算法3.13】循环队列入队

Status ENQueue(SqQueue &){
    if((Q.rear+1)%MAXSIZE==Q.front) return ERROR;//队满
    Q.base[Q.rear] = e;//新元素加入队尾
    Q.rear = (Q.rear+1)%MAXSIZE;//队尾指针+1
}

【算法3.14】循环队列出队

Status DeQueue(SqQueue &Q,QElemType &e){
    if(Q.front == Q.rear) return ERROR;//队空
    e = Q.base[Q.base];//保存队头元素
    Q.front = (Q.front+1)%MAXSIZE;//队头指针+1
}

【算法3.15】取队头元素

SElemType GetHead(SqQueue Q){
    if(Q.front!=Q.rear)//队列不为空
        return Q.base[Q.base];//返回队头指针元素的值，队头指针不变
}

链队

若用户无法估计所用队列的长度，则宜采用链队列

链队列的类型定义

#define MAXSIZE 100 //最大队列长度
typedef struct Qnode{
    QElemType data;
    struct Qnode *next;
}QNode,*QuenePtr;

typedef struct{
    QuenePtr front;//队头指针
    QuenePtr rear;//队尾指针
}LinkQueue;

链队列运算指针变化状况

【算法3.16】链队列的初始化

Status InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->NULL;
    return OK;
}

【补充算法】销毁链队列

Status DestroyQueue(LinkQueue &Q){
    while(Q.front){
        p = Q.front->next;
        free(Q.next);
        Q.front = p;
    }
    return OK;
}

【算法3.17】将元素e入队

Status EnQueue(LinkQueue &Q,QElemType e){
    p = (QueuePtr)malloc(sizeof(QNode));
    p->data = e;
    p->next = NULL;
    Q.rear = p;
    return OK;
}

【算法3.18】链队列出队

Status DeQueue(LinkQueue &Q,QElemType &e){
    if(Q.front == Q.rear) return ERROR;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p){
        Q.rear  = Q.front;
    }
    free(p);
    return OK;
}

【算法3.19】求链队列的队头元素

Status GetHead(LinkQueue Q,QElemType &e){
    if(Q.front == Q.rear) return ERROR;
    e = Q.front->next->data;
    return OK;
}

串、数组和广义表

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      ## 串

串的定义

零个或多个任意字符组成的有限序列

子串：串中任意个连续字符组成的子序列（含空串）称为该串的子串

主串：包含子串的串相应的称为主串

字符位置：字符在序列中的序号为该字符在串中的位置

子串位置：****子串中第一个字符在主串中的位置

**空格串：**由一个或多个空格组成的串 与空串不同

串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相等时，这两个串才是相等的

• 所有的空串都是相等的

案例引入

【案例4.1】病毒感染监测

研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列，然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染

例如：假设被病毒的DN序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则未感染

注意，人的DNA序列是线性的，而病毒的DNA序列是环状的

串的类型定义、存储结构及运算

• 串的顺序存储结构

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN+1];//存储串的一维数组
    int length; //串的当前长度
}SString;

• 串的链式存储结构–块链结构

#define CHUNKSIZE 80 //块的大小可由用户定义
typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct{
    Chunk *head,*tail;//串的头指针和尾指针
    int curlen; //串的当前长度
}LString;//字符串的块链结构

串的模式匹配算法

算法目的：

确定主串中所含子串(模式串)第一次出现的位置(定位)

算法应用：

搜索引擎 拼写检查 语言翻译 数据压缩

算法种类：

• BF算法(Brute-Force,又称古典的、经典的、朴素的、穷举的)
• KMP算法(特点：速度快)

Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举法的思想

S: a a a a b c d 主串：正文串

T: a b c 子串：模式

算法思路是从S的每一个字符开始依次与T的字符进行匹配

BF算法设计思想：

• 将主串的第pos个字符和模式串的第一个字符比较
  • 若相等，继续逐个比较后续字符
  • 若不等，从主串的下一字符起，重新与模式串的第一个字符比较

直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的的序号，即匹配成功。否则，匹配失败，返回0

int Index_BF(SString S,SString T){
     int i = 1, j = 1;
    while(i<=S.length&&j<=T.length){
        if(s.ch[i] == t.ch[i]){//主串和子串依次匹配下一个字符
        	++i;
            ++j;
        }else{
            i = i-j+2;//主串子串指针回溯重新开始下一次匹配
            j = 1;
        }
    }
    if(j>T.length) return i-T.length;//返回匹配的第一个字符的下标
    else return 0;//模式匹配不成功 
}

KMP算法

KMP算法设计思想

利用已经部分匹配的结果而加快模式串的滑动速度且主串S的指针i不必回溯

可提速到O(n+m)

j	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
模式串	a	b	c	a	a	b	b	c	a	b	c	a	a	b	d	a	b
next[j]	0	1	1	1	2	2	3	1	1	2	3	4	5	6	7	1	2

int Index_KMP(SString S,SString T,int pos){
    i = pos,j = 1;
    while(i<S.length&&j<T.length){
        if(j == 0||S.ch[i] = S.ch[j]){
            i++;
            j++;
        }else{
            j = next[j]; //i不变，j后退
        }
    }
    if(j>T.length) return i-T.length; //匹配成功
    else return 0;//不匹配
}

void get_next(SString T,int &next[]){
    i = 1;
    next[1] = 0;
    j = 0;
    while(i<T.length){
        if(j == 0||T.ch[i] == T.ch[j]){
    		i++;
             j++;
             next[i] = j;
        }else{
            j = next[j];                                                 
        }
    }
}

数组

声明格式: 数据类型 变量名称 [行数] [列数]

n维数组：若n-1维数组中的元素又是一个一维数组结构，则称作n维数组

一维数组：

例如，有数组定义：int a[5]

每个字节占用4字节，假设a[0]存储在2000单元，a[3]地址是多少

数组的顺序存储

存储单元是一维结构，而数组是个多维结构，则用一维连续存储单元存放数组的数据元素就有个次序约定问题

• 以行序为主序

C JAVA PASCAL BASIC

特殊矩阵的压缩存储

1. 什么是压缩存储？

   若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间

2. 什么样的矩阵能够压缩？

   一些特殊矩阵，如：对称矩阵，三角矩阵，对角矩阵，稀疏矩阵等

3. 什么叫稀疏矩阵？

   矩阵中非零元素的个数很少(一般小于5%)

1.对称矩阵

【特点】在n×n的矩阵a中，满足如下性质：

$a_{ij} = a_{ji}(1<=i,j<=n)$

【存储方式】只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间

下三角：k = i(i-1)/2 + j

2.三角矩阵

【特点】对角线以下（或者以上）的数据元素（不包括对角线）全部为常数c

【存储方法】重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间

下三角矩阵

k = i×(i-1)/2 + j i>= j

​ n(n+1)/2 + 1 i<j

上三角矩阵

k = i(2n-i+1)/2+j-1 i<=j

​ n(n+1)/2 + 1 i>j

3.对角矩阵

【特点】在n×n的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则成为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等

稀疏矩阵存储

$设在m×n的矩阵中有t个非零元素\\ 令 {\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,} \delta = t/(m×n)\\ {\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}当{\,}{\,}{\,}{\,}{\,}{\,}\delta \leq0.05时称为稀疏矩阵$

三元组顺序表：

用行数、列数表示非零元素所在位置

十字链表：

在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了(row,col,value)以外，还要有两个域：

• right:用于链接同一行中的下一个非零元素
• down:用于链接同一列中的下一个非零元素