Last updated on a day ago

使用书籍《大话数据结构》-程杰

数据结构

基础概念和术语

数据

数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合，数据不仅仅包含整型，实型等数据类型，还包括字符及声音、图像、视频等非数值类型。对于数值类型可以进行数值运算，对于字符数据类型，需要进行非数值的处理，而声音、图像等则可以通过编码手段变成字符数据类型来处理。

数据元素

数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。
比如在人类中，人就是数据元素，在畜类中，猪马牛羊就是数据元素。

数据项

一个数据元素可以由多个数据项组成，数据项是数据不可分割的最小单位。
比如人这个数据元素，可以有眼鼻手脚等数据项，也可以有名字、性别等数据项。而数据项是数据不可分割的最小单位，但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点，就好像讨论电影，讨论的是主角这个数据元素，而不是它名字、性别等数据项。

数据对象

数据对象是性质相同的数据元素的集合，是数据的子集。，性质相同指的是数据元素具有相同数量和类型的数据项。数据对象是数据的子集，所以有相同的性质，在日常使用中，在不产生混淆的情况下，通常把数据对象简称为数据。

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，简单理解，结构就是关系。

逻辑结构和物理结构

逻辑结构是指数据对象中数据元素间的相互关系。逻辑结构分以下四种：

集合结构

集合结构中的元素除了同属于一个集合外，它们之间没有其他关系
线性结构

线性结构中，数据元素是一对一的关系：
树形结构

树形结构中的数据元素存在一对多的层次关系：
图形结构

图形结构的数据元素是多对多的关系：

物理结构是指数据的逻辑结构在计算机中的存储形式。物理结构有两种：

顺序存储结构：

是把数据元素存放在地址连续的存储单元内，其数据间的逻辑关系和物理关系是一致的。比如我们创建数组的时候，计算机会在内存中开辟一段连续的空间，第一个数据放第一个位置，第二个数据放第二个。像排队一样：
链式存储结构：

是把结构元素存放在任意的存储单元内，这组存储单元可以是连续的，也可以是不连续的。这种存储关系并不能反映逻辑关系，因此需要用一个指针数据元素的地址，这样通过地址就能找到相关联数据元素的位置。就像银行排队，取号后想坐那都行：

逻辑结构是面向问题的，而物理结构是面向计算机的，其基本目的就是将数据及其逻辑关系存储到计算机内存中。

抽象数据类型

数据类型

数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
数据类型是按照值得不同进行划分的。在高级语言中，每个变量、常量、表达式都有各自的取值类型，类型就用来说明变量或表达式的取值范围和所能进行的操作
为什么要设计出数据类型呢？为了节约内存，比如计算1+1=2，显然不需要开辟出适合实型甚至字符运算的内存空间，于是就对数据分类，分出了多种数据类型：

原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等
结构类型：由若干个类型组合而成，是可以再分解的，例如整型数组是由若干整型数据组成的。

比如C语言中的int a，给a赋值时就不能超出int类型的范围，运算时只能是int类型所允许的运算。
因为不同的计算机由不同的硬件系统，这就要求程序语言最终通过编译器或解释器转换成底层语言，如汇编甚至是机器语言的数据类型来实现的。可事实上高级语言的开发者根本不关心这个，它不需要知道计算机内部是如何表示的，CPU进行几次开关操作，这些如何实现对高级语言开发者根本不重要。于是我们就会考虑，无论什么计算机、什么计算机语言，大都会面临如整数运算、实型运算、字符运算等操作，我们可以考虑把它们都抽象出来
抽象是指抽取出事物具有的普遍性的本质。它是抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留了实现目标所必需的信息。

抽象数据类型

我们对已有的数据类型进行抽象，就由了抽象数据类型。抽象数据类型(Abstarct Date Type,ADT):是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。
比如各个计算机甚至手机，都有“整型”类型，那么整型就是一个抽象数据类型，尽管它在不同设备上实现方法可能不同，但由于其定义的数学特性相同，在计算机编程者开来，它们都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特征。
而且，抽象数据类型不仅仅指哪些已经定义并实现的数据类型，还可以是计算机编程者在设计软件程序时自己定义的数据类型，比如我们编写绘图的软件系统，会用到坐标，总会有成对的x，y出现，我们就定义一个叫point的抽象数据类型，它有x,y两个整型变量，这样我们就很方便地操作一个point数据变量就能知道这一点的坐标了。
事实上，抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模校且容易处理的问题，然后建立一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。
描述抽象数据类型的标准格式：

ADT 抽象数据类型名
Data
	数据元素之间逻辑关系的定义
Operation
	操作1
		初始条件
		操作结果
	操作2
		...
	操作N
		...
endADT

算法

算法的定义

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性

输入和输出：

算法具有零个或多个输入，且算法至少有一个或多个输出，算法一定需要输出，输出的形式可以是打印也可以是返回值。
有穷性

算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。而且这个有限并不纯是数学意义的，而是在实际应用中合理的、可以接收的“有边界”。总不能一个算法算上几十年才才结束。
确定性

算法的每一步骤都有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧异。
可执行性

算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。意味着算法可以转化为程序上机运行，并得到正确结果。尽管在目前也存在那种没有实现的极为复杂的算法。

算法设计的要求

正确性：

至少应该具有输入、输出和加工处理无歧义性、能够正确反映问题的需求、能够得到问题的正确答案。大体分为以下四个层次：
1. 算法程序没有语法错误
2. 对于合法输入数据能给出满足要求的输出结果
3. 对于非法输入数据能给出满足规格说明的结果
4. 对于精心选择甚至刁难的测试数据都有满足要求的输出结果
可读性：

算法设计的另一目的是便于阅读、理解和交流。
健壮性：

当输入数据不合法时，算法也能做出相应的处理，而不是产生异常或奇怪的结果。
时间效率高和存储量低：

时间效率指的是算法的执行时间，存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存空间或外部硬盘存储空间。

算法效率的量度方法

时候统计方法：

主要通过设计好的程序和数据，利用计算机计时器对不同算法编制的程序的运行时间比较，但这种方法有很大缺陷：
1. 必须先编制好程序，如果编制出来就是种坏的算法，那不是很浪费时间吗？
2. 时间的比较依赖计算机硬件和软件等因素，有时会掩盖算法本身的优缺点，而所用的系统、编译器、运行框架不同都会影响时间，就算同一台机器，CPU使用率和内存占用情况不同，也会造成细微的差距
3. 算法的测试数据设计困难，效率高的算法在小的测试数据面前往往得不到体现，如果有100万个测试数据，算法间的差距就很大了。

所以对于事后统计的方法，我们不予考虑

事前估计分析方法：

一个高级语言编写的程序在计算机上运行时所消耗的时间取决于以下：
1. 算法采用的策略方法
2. 编译产生的代码质量
3. 问题的输入规模
4. 机器执行指令的效率

第1条是算法好坏的根本，第2条要由软件来支持，第4条看硬件性能。也就是说，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。输入规模就是输入量的多少。举个例子：

//从1加到100
//第一种算法：
int i,sum=0,n=100;		//执行1次
for(i = 1; i<=n; i++)	//执行n+1次
{
 	sum=sum+1;  		//执行1次
}
printf("%d",sum);		//执行1次
//第二种算法：
int sum=0,n=100;		//执行1次
sum=(1+n)*2/n;			//执行1次
printf("%d",sum);		//执行1次

可以看出，第一种算法执行了1+(n+1)+n+1=2n+3次；而第二种算法是3次，忽略开头结尾，把循环看成一个整体，两个算法就是n次与1次的差距。
测定运行时间最可靠的方法就是计算对运算时间有消耗的基本操作的执行次数。对于第一种算法，同样问题的输入规模是n，需要一段代码运行n次。那么操作数量是f(n)=n，而第二种，则是f(n)=1。将两个函数绘制图像可以发现，随着n值得增大，它们在时间效率上得差异也就越来越大。

函数得渐近增长

函数得渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N,都有f(n)>g(n)，那么我们说f(n)的增长渐近快于g(n)，对于n+8和n+1，随着n的增大，我们可以忽略后面的加法常数，它们并不影响最终的算法变化。
而对于2n、3n^2这类，即使把乘数去掉也不会影响，也就是说与最高次项相乘的常数并不重要。
而对于n，n^2，n^3会发现，最高次项的指数大的，函数随着n的增长，结果也会变得增长特别快
最后，对于3n+1和3n^2和3n^2+n，当n的值越来越大，3n+1的值和其他两者差距也会越来越大，最终甚至可以忽略不记，而另外两者的值随着n的增大越来越相近，所以判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注最高次项的阶数。
判断一个苏纳法好不好，我们不能只通过少量的数据，某个算法，随着n的增大，它会越来越优与另一个算法，通过算法时间复杂度来估算算法时间效率

算法时间复杂度

算法时间复杂度定义：

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率系统，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数
这样用大写O()来体现算法时间复杂度的记法，称之为大P记法

推到大O阶方法

用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项去除与这个项相乘的常数

举几个例子：

常数阶：
1
2
3
int sum = 0,n = 100; //执行一次 sum = (1+n)*n/2; //执行一次 printf("%d", sum) //执行一次
这个算法的运行次数函数是f(n)=3，把常数项3改为1，保留最高此项发现并没有，所以这个算法的时间复杂度为O(1)，这种与问题的大小无关，时间恒定的算法，称之为常数阶

线性阶：

int i;
for(i = 0;i < n; i++)
{
    //时间复杂度为O(1)的程序步骤序列
}

它的时间复杂度为O(n)

对数阶：
1
2
3
4
5
int count = 1; while(count < n) { count -= count * 2; }
有多少个2相乘后大于n，则会退出循环，2^x=n，x=log2(n)，所以这个循环的时间复杂度为O(logn).
平方阶：
1
2
3
4
5
6
7
8
int i, j; for(i = 0; i < n; j++) { for(j = 0; j < n; j++) { //时间复杂度为0(1)的程序步骤序列 } }
这段代码的时间复杂度为O(n^2)；如果外循环的次数改为m，时间复杂度就是O(m*n)。

常见的时间复杂度

最坏情况与平均情况

假设我们要查找n个随机数字组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1),但也有可能这个数字是最后一位，那么算法的时间复杂度就是O(n)，这是最坏的情况。最坏情况运算时间是一种保证，那就是运行时间将不会再坏。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是系统的，所以平均的查找时间为n/2次后发现这个目标。
平均时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望，看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。
对于算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一个种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：O(f(n))，其中n为问题规模，f(n)为语句关于n所占存储空间的函数
一般情况下，除了需要存储程序本身的指令、常数变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。
通常，若不加限定的使用“复杂度”，是指时间复杂度，必要时，可以考虑使用空间换取时间。

线性表

线性表是数据结构中最常用最简单的一种结构

线性表的定义

线性表就好像排队，一个跟着一个，有一个打头的，有一个收尾的，每个人都知道前后是谁。线性表(List):零个或多个数据元素的有限序列。
首先，线性表是有序的，元素之间是有顺序的，若元素有多个，则第一个无前驱，最后一个无后继，其他每个元素都有且只有一个前驱和后继。
然后，线性表强调是有限的，实际上计算机处理的对象都是有限的，无限只存在于数学概念中。

线性表

线性表元素的个数n(n>=0)定义为表的长度，若n=0，称为空表。在非空的线性表中，每个元素都有确定的位置，如a1是第一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。

线性表的抽象数据类型

对于不同的应用，线性表的操作是不同的，上述操作是最基本的

线性表的顺序存储结构

定义

线性表的顺序存储结构，指的是用一段地址连续的内存单元依次存储线性表的数据元素，线性表可以用C语言的数组来实现，线性表的顺序存储的结构代码如下：

#define MAXSIZE 20  		//存储空间初始分配量
typedef int ElemType;		//元素类型，这里定义为int
typedef struct
{
    ElemType data[MAXSIZE];	//用数组存储数据元素，最大为MAXSIZE
    int length;				//线性表当前长度
}SqList;

描述顺序存储结构需要三个属性：

存储空间的起始位置：数组data，它的起始位置就是存储空间的存储位置
线性表的最大存储容量：数组长度MAXSIZE
线性表的当前长度：length

数据长度和线性表长度的区别

数组的长度是存放线性表的存储空间的长度，这个长度一般是不变的，也可以用编程手段实现动态分配，不过会带来性能上的损耗。而线性表的长度是线性表中数据元素的个数，随着元素的插入删除，这个值会发生改变。在任意时刻，线性表的长度小于等于数组的长度。

顺序存储结构的插入与删除

获得元素操作

如果我们要实现GetElem操作，即将线性表的第i个元素返回，只要i的数值在下标范围内，把i-1的值返回就成了：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status是函数的类型，其值是函数结果状态码，如OK等
//初始条件：顺序线性表L已存在，1<=i<=ListLenth(L)
//操作结果：用e返回L中的第i个数据元素的值
Status GetElem(Sqlist L, int i, ELemType *e)
{
	if(L.length == 0 || i < 1 || i > L.length)
        return ERROR;
    *e = L.data[i-1];
    return OK;
}

插入操作

如果我们要实现ListInsert(*L,i,e)，即在线性表L中的第i个位置插入心元素e，该如何操作？插入算法的思路如下：

如果插入位置不合理，抛出异常
如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
将要插入元素填入位置处
表长加1

代码如下：

//初始条件:顺序线性表L已存在，1<=i<=Listlength(L)
//操作结果：在L中第i个位置之前插入心得数据元素e，L的长度加1
Status ListInsert(SqList *L,int i,ElemType e)
{
	int k;
    if (L->length == MAXSIZE) //顺序表已满
        return ERROE;
    if (i<1 || i> L->length+1)//当i不在范围内时
        return ERROR;
    if(i<=L->length)//插入位置不在表尾
    {
        for(k = L->length - 1; k >= i - 1; k--)//将插入位置之后的数据元素向后移动一位
            L->data[k+1]=L->data[k];
    }
    L->data[i-1] = e;//插入新元素
    L->length++；
    return OK;
}

删除操作

删除算法的思路：

如果删除位置不合理，抛出异常
取出删除元素
从删除元素位置开始遍历最后一个元素位置，分别将它们都向前移动一位
表长减1

代码实现如下：

Status ListDelete(SqList *L， int i, ElemType *e)
{
    int k;
    if (L->length == 0)//线性表为空
        return ERROR;
    if(i > L->length || i < 1)//删除位置不正确
        return ERROR;
    *e = L->data[i-1];
    if (i<L->length)如果删除不是最后位置
    {
        for(k = i; k < L->length)
            L->data[k-1]=L->data[k];//将删除位置后继元素前移
    }
    L->length--;
    return OK;
}

线性表顺序存储结构的优缺点

优点：
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任意位置的元素
缺点：
- 插入和删除操作需要移动大量数据
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的“碎片”

线性表的链式存储结构

顺序存储结构不足的解决方法

线性表的顺序存储结构插入和删除时需要移动大量元素，这需要耗费时间，要解决这个问题，我们可以：
让所有元素都不考虑相邻位置，哪里有空位就到哪里，而只是让每个元素知道它下一个元素的位置在哪里。

线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组数据元素可以是连续的，也可以是不连续的，这意味着这些数据元素可以存在内存未被占用的任意位置。在以前的顺序结构中，每个元素只要存数据信息就可以了，在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的地址
我们把存储数据元素信息的域成为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分组成数据元素ai的存储映像，称为结点(Node)
n个结点链结成一个链表，即为线性表(a1,a2…an)的链式存储结构，因此此链表的每个结点只包含一个指针域，所以叫单链表

单链表

对于线性表来说，总得有个头和尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须从头指针开始进行。之后的每个结点，其实就是上一个的后继指针指向的位置，最后一个结点的指针指向“空”(通常用NULL或^表示)

头指针

有时，我们为了方便对链表操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表长度等附加信息，头结点的指针域指向第一个结点的指针

头结点

头指针与头结点的异同

头指针	头结点
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针头指针具有标识作用，所以常常用头指针冠以链表的名字无论链表是否为空，头指针均不为空，头指针是链表的必要元素	头结点是为了操作的统一和方便而设立额，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了头结点不一定是链表的必须要素

线性表链式存储结构代码描述

单链表中，我们可以用C语言的结构指针来描述

typedef struct Node
{
	ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList;

单链表的读取

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的，但在单链表中，由于不知道第i个元素到底在哪？必须从头开始找。因此对于单链表实现获取第i个元素的GetElem操作，在算法上要麻烦一些：

声明一个结点p指向链表第一个结点，初始化j从1开始
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
若到链表末尾o为空，则说明第i个元素不存在
若查找成功，返回结点p的数据

实现代码如下：

Status GetElem(LinkList L, int i, ElemType *e)
{
	int j;
    LinkList p;			//声明结点p
    p = L -> next;		//让p指向链表L的第一个结点
    j = 1;				//j为计数器
    while( p && j < i)	//p不为空或j还没有等于i时，循环继续
    {
        p = p -> next;	//p指向下一个结点
        ++j;
    }
    if (!p || j>i)
		return ERROR;	//第i个元素不存在
    *e = p -> data;		//取第i个元素的数据
    return OK;
}

单链表的插入与删除

单链表的插入

单链表第i个元素插入结点的算法思路是：

声明结点p指向第一个结点，初始化j从1开始
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加
若到链表末尾p为空，则说明第i个元素不存在
否则查找成功，在系统中生成一个空结点s
将数据元素e赋值给s->data
单链表的插入标准语句 s->next = p->next; p->next = s;
返回成功

Status ListInsert(LinkList *L, int i, ElemType e)
{
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    while(p && i < i)
    {
        p = p->next;
        +=j;
    }
    if (!p || j > i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node));//生成新结点s（C标准函数）
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

单链表的删除

设存储ai的结点为q，要实现将q删除单链表的操作，其实就是将它的前即继结点p的指针，指向它的后继结点。实际上就是：

1	`q = p -> next; p -> next = q -> next;`

打个比方：妈->爸->儿,三人散步，爸爸看了美铝一眼，妈咪不开心，把爸比的手(′д｀ )…彡…彡甩开，拉起儿砸就走，只留下爸爸一人呆在原地，搓着手(q->next = p->next)不知所措。爸爸就已经和母子没有牵手联系了。
单链表第i个元素删除结点的算法思路：

申明一节点p指向链表的第一个结点，初始化j从1开始
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
若到链表末尾p为空，则说明第i个元素不存在
否则查找成功，将欲删除的结点p->next赋值给q
单链表的删除标准语句p->next = q->next
将q结点中的数据赋值给e，作为返回
释放q结点
返回成功

实现代码算法如下：

Status LissDelete(LinkList *L; int i; ElemType *e);
{
    int j;
    LinkList p, q;
    p = *L;
    j = 1;
    while(p -> next && j < i)
    {
		p = p -> next;
        ++j;
    }
    if (!(p -> next) || j > i)
        return ERROR;
    q = p -> next;
    p -> next = q -> next;
    *e = q -> data;
    free(q);
    return OK;
}

单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化，而单链表不像顺序存储结构这么集中，是一种动态结构，所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态启，依次建立各结点，并逐个插入链表-头插法：

声明一结点p和计数器变量i
初始化空链表L
让L的头结点的指针指向NULL，即建立一个带头结点的单链表
循环：
1. 生成一新节点赋值给p
2. 随机生成一数字赋值给p的数据域p->data
3. 将p插入到头结点与前一新结点之间

实现代码算法如下：

//随机产生n个元素的值，建立带头结点的单链线性表L（头插法）
void CreateListHead(LinkList *L, int n)
{
    LinkList p;
    int i;s
    srand(time(0));		//初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;		//建立一个带头结点的单链表
    for(i = 0; i < n; i++)
    {
		p = (LinkList)malloc(sizeof(Node));	//生成新结点
        p->data = rand()%100+1;		//随机生成100以内的数字
        p->next = (*L)->next;	
        (*L)->next = p;				//插入到表头
    }
}

还可以把新结点放到最后，即尾插法，实现代码算法如下：

//随机产生n个元素的值，建立带头结点的单链线性表L(尾插法)
void CreateListTail(LinkList *L, int n)
{
	LinkList p,r;
    int i;
    srand(time(0));		//初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));	
    r = *L;			//r为指向尾部的结点
    for (i = 0; i < n; i++)
    {
		p = (Node*)maclloc(sizeof(Node));	//生成新结点
        p->data = rand()%100+1;			
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

单链表整表删除

单链表整表删除的算法思路如下：

声明一结点p和s
将第一个结点赋值给p
循环：
1. 将下一个结点赋值给s
2. 释放p
3. 将s赋值给p

实现代码算法如下：

ClearList(LinkList *L)
{
	LinkList p,s;
    p = (*L)->next;
    while(p)
    {
		s = p->next;
        free(p);
        p = s;
    }
    (*L)->next = NULL;
}

单链表结构与顺序存储结构优缺点

	顺序存储结构	链式存储结构
存储分配方式	用一段连续的存储单元依次存储线性表的数据元素	采用链式存储结构，用一组任意的存储单元存放线性表
时间性能	查找：O(1) 插入和删除：平均移动表长一半的元素O(n)	查找：O(n) 插入和删除：单链表在超出某位置后，插入和删除的时间仅为O(1)
空间性能	需要预分配，分大了浪费，小了容易发生上溢	不需要预分配，只要有就可以分配，元素个数也不受限制

静态链表

C语言有指针，可以非常容易地操作内存中的地址和数据，而后来的面向对象，如Java、C#等，虽不用指针，单因为启用了对象引用机制，从某种角度也间接实现了指针的某些作用。但对于Bassic、Fortran等早期的编程高级语言，由于没有指针，链表结构无法按照我们前面的方法实现，怎么办呢？
有人就想到了用数组代替指针，来描述单链表
首先，我们让数组的元素都是由来个数据域组成，data和cur。也就是说数组的每个下标都对应一个data和cur，data用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把这种用数组描述的链表叫静态链表，也有叫游标实现法

#define MAXSIZE 1000	//假设链表的最大长度是1000
typedef struct
{
    ElemType data;
    int cur;			//游标Cursor,为0时表示无指向
}Component, StaticLinkList[MAXSIZE];

我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为0^2

//将一维数组space中各分量链成一备用链表
//spance[0].cur为头指针，“0”表示空指针
Status InitList(StaticLinkList space)
{
	int i;
    for(i = 0; i < MAXSIZE - 1; i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0;//目前静态链表为空，最后一个元素的cur为0
    return 0;
}

对于不提供struct的，可以使用一对并行数组data和cur来处理。
假设现在我们已经存入元素“甲、乙，丁…”

静态链表

在最后一个有值元素，它的cur设置为0。而最后一个元素的cur，则因”甲“是第一有值元素而存有它的下标1.第一个元素则因空闲空间的第一个元素下标为7，所以它的cur存为7。

静态链表的插入操作

在动态链表中，结点的申请和释放分别使用malloc()和free（），在静态链表中，操作的是数组，不存在这样的问题。为了辨明数组中哪些分量未被使用，解决的方法是将所有未被使用过的及 已被删除的分量用游标链组成一个备用链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

//若备用空间链表非空，则返回分配的结点下标，否则返回0
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;	//当前数组第一个元素的cur存的值
    						//就是要返回的第一个备用空间的下标
    if(space[0].cur)
		space[0].cur = space[i].cur;
        					//由于要拿出一个分量来使用，所以得
        					//把下一个分量用来做备用
    return i;
}

这段代码可以返回数组头元素的cur存的第一个空闲的下标。然后将下一个空闲的下标赋值给头元素。

循环链表

**将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linkedlist)**。循环链表可以解决一个很麻烦的问题：如何从当中一个结点出发，访问到链表的全部结点。
为了使空链表与非空链表处理一致，我们通常设一个头结点，但并不是说一定要有头结点。循环链表带有头结点的空链表如图：

带头结点循环空链表

带头结点的非空链表如图：

带头结点循环非空链表

其实循环链表和单链表的主要差异再循环的判断条件上，原来判断p->next是否为空，现在则是p->next != 头结点。在单链表中，可以用O(1)的时间访问第一个结点，而最后一个结点却要O(n)，有没有可能用O(1)的时间访问到最后一个结点呢？
我们改造一个循环链表，不用头指针表示链表，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点就很方便了

用尾指针表示循环链表

终端结点用尾指针rear指示，则查找终端结点是0(1)，而开始结点，其实就是rear->next->next，其时间复杂度也为0(1)。
有了尾指针会方便很多，比如要将两个循环链表合并成一个表时，两个尾指针分别为rearA和rearB：

p = rearA->next;		//保存A表的头结点
rearA->next = rearB->next->next		//将本是指向B表的第一个			//结点（不是头结点）赋值给rearA->next
rearB->next = p;	//将原A表的头结点赋值给rearB->next
free(p);			//释放P

双向链表

在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度未O(1)。可是如果要查找上一结点的话，那最坏的情况就是O(n)了，因为要从头开始遍历查找。为了克服这一缺点，就设计出了双向链表。双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以再双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

typedef struct DulNode
{
	ElemType data;
    struct DulNode *prior;	//直接前驱指针
    struct DulNode *next;	//直接后继指针
}DulNode, *DuLinkList;

既然单链表有循环链表，那么双向链表也可以有循环链表。
双向链表的循环带头节点的空链表如图：

空循环双向链表

非空的循环的带头节点的双向链表如图

非空循环带头节点双向链表

双向链表的插入，假设待插入结点为s，s将插入到p与p->next之间

s->prior = p;
s->next = p->prior;
p->next->prior = s;
p->next = s;

双向链表的删除比较简单，假设要删除p结点

1
2
3

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

栈与队列

栈的定义：****栈（stack）是限定仅在表尾进行插入和删除操作的线性表
我们把插入和删除的一段成为栈顶（top），另一端成为栈底（bottom），不含任何元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。
栈的插入操作，叫作压栈、入栈。类似子弹入弹夹；
栈的输出操作，叫作出栈，有的也叫弹栈。如同弹夹中的子弹出夹

进栈出栈变化形式

最先进栈的元素，不一定最后出栈，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以，比如可以进一个出一个（123进，123出）、全进再出（123进，321出）…以此类推，仅仅三个元素就有5种可能的出栈次序，如果元素数量多，变化还会更多。

栈的抽象数据结构

对于栈来讲，理论上线性表的操作特性它都具备，可由于他的特殊性，所以它的操作会有些变化，特别是插入和删除操作，我们改名push和pop，英文直译的话是弹和压，我们一般叫进栈和出栈

栈的抽象结构

栈的顺序存储结构及实现

既然栈式线性表的特例，那么栈的顺序存储结构其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表式用数组实现的，对于栈，我们把下标为0的一端作为栈底，定义一个top变量指示栈顶元素在数组中的位置，同时若存储栈的长度为StackSize，则栈顶位置top必须小于它。当栈存在一个元素时，top等0，因此通常把空栈的判定条件定位top等于-1

栈的结构定义：

typedef int SElmType;
typedef struct
{
	SelemType data[MAXSIZE];
    int top;
}SqStack;

顺序存储结构-进栈操作

对于进栈操作pash，代码如下：

Status Push(SqStack *s, SElemType e)
{
	if(s->top == MAXSIZE - 1)	//栈满
        return ERROR;
    s->top ++;
    s->data[s->top] = e;
    return OK;
}

顺序存储结构-出栈操作

出栈操作pop，代码如下：

//若栈不为空，则删除s的栈顶元素并用e返回其值并返回OK，否则返回ERROER
Status Pop(SqStack *s, SElemType *e)
{
	if(s->top == -1)	//空栈
        return ERROR
    *e = s->data[s->top];
    s->top --;
    return OK;
}

两栈共享空间

栈的顺序结构还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题，不过它必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，我们只能考虑周全，设计出合适大小的数组空间来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。我们可以用一个数组来存储两个栈，只不过需要点小技巧。
关键思路就是：它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，只要它们两个不见面，两个栈就可以一直使用了。

typedef struct
{
	SElemType data[MAXSIZE];
    int top1;//栈1栈顶指针
    int top2;//栈2栈顶指针
}SqDoubleStack;

对于v两栈共享空间的push方法，我们除了要插入元素值参数外，还需要一个判断是栈1还是栈2的栈号参数stackNumber。插入代码如下：

Status Push(SqDoubleStack *s, SelemType e, int stackNumber)
{
	if (s->top1 + 1 == s->top2)//栈已满，不能再push新元素了
        return ERROR;
    if (stackNumber == 1)//栈1有元素进栈
        s->data[ ++ s->top1] = e;//先top1+1后给元素赋值
    else if (stackNumber == 2)//栈2有元素进栈
        s->data[ -- s->top2] = e;//先top2-1后给元素赋值
    return OK;

}

对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber:

//若栈不为空，则删除s的栈顶元素，用e返回其值，并发返回OK，否则返回ERROR
Status Pop(SqDoubleStack *s, SEmemType *e, int stackNumber)
{
	if(stackNumber == 1)
    {
        if(s->top1 == -1)	//栈1为空
            return ERROR;
        *e = s->data[ s->top1 --];	//将栈1的栈顶元素出栈
    }
    else if (stacakNumber == 2)
    {
		if(s->top2 == MAXSIZE)	//栈2为空
            return ERROR;
        *e = s->data[ s->top2 ++]	//将栈2的栈顶元素出栈
    }
    return OK;
}

栈的链式存储结构及实现

栈的链式存储结构，简称链栈，栈只有栈顶来插入和删除，那么栈顶是放在链表的头部还是尾部好呢？由于单链表有头指针，而栈顶指针也是必须的，不如让它两合二为一，另外都已经有了栈顶再头部了，单链表中常用的头节点也就失去了意义，通常对于链栈来说，是不需要头节点的。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的边缘了，而不是这个链栈是否溢出的问题。
但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候：

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

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

栈的链式存储结构-进栈操作

链栈进栈

代码如下：

//输入元素e为新的栈顶元素
Status Push(LinkStack *s, SEmleType e)
{
	LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    p->data = e;
    p->next = s->top;
    s->top = p;
    s->count ++;
    return OK;
}

栈的链式存储结构-出栈操作

Status pop(LinkStack *s)
{
    if(s->top == NULL)
        return ERROE;
	LinkStackPtr p;
    p = (*s)->top->next;
    free((*s)->top);
    (*s)->top = p;
    (*s)->count --;
    return OK;
}

如果栈的使用过程中元素变化不可预料，有时很大，有时很小，那么最好使用链栈，反之，若在可控范围内，则建议使用顺序栈。

栈的应用- 递归

栈有一个很重要的应用：在程序设计语言中实现了递归。先来看一个经典的递归例子：斐波那契数列：
我们拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔子，小兔子数共有2对；三个月后，老兔子又生下了一对，因为小兔子还没有繁殖能力，所以一共是3对……依次类推，可以得出下表：

所经过的月数	1	2	3	4	5	6	7	8	9
兔子对数	1	1	2	3	4	8	13	21	34

这个数列有个十分明显的特点：前面相邻两项之和，构成了后一项，如图所示：

斐波那契数列

可以发现，编号①的一对兔子经过6个月就变成了8对兔子，如果我们用数学函数来定义就是：

	0，当n=0
F(n)	1，当n=1
	F(n-1)+F(n-2),当n>1

如果我们要实现这样的数列用常规的迭代的办法，假设要打印出前40位斐波那契数列。代码如下：

int main()
{
	int i;
    int a[40];
    a[0] = 0;
    a[1] = 1;
    printf("%d",a[0]);
    printf("%d",a[1]);
    for(i = 2; i < 40; i++)
    {
		a[i] = a[i-1] + a[i-2];
        printf("%d",a[i]);
    }
    return 0;
}

但其实我们如果用递归来实现，还可以更简单

int Fbi(int i)
{
	i(i<2)
        return i == 0 ? 0:1;
    return Fbi(i-1) + Fbi(i-2);
}

int main()
{
	int i ;
    for(int i = 0; i <40; i++)
        printf("%d",Fbi(i));
    return 0;
}

递归定义

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。
写递归程序最怕的就是陷入无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。
对比两种实现斐波那契的代码。迭代和递归的区别时：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简介、更容易让人理解，从而减少读懂代码的时间。但大量的递归调用回建立函数的副本，回耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

讲了那么多递归，和栈有什么关系呢？这得从计算机系统的内部说起。前面我们已经看到递归是如何执行它的前行和退回阶段。递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括回复在前行过程中存储起来的某些数据。
这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。
简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。
当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统代劳了。

栈的应用-四则运算表达式求值

后缀（逆波兰）表示法定义

栈的现实应用也很多，我们再来重点讲一个比较常见的应用：数学表达式的求值。
比如计算器，单纯的加减或乘除计算器都能很快的算出，但遇上四则运算，先乘除后加减和带括号的算式，早期的计算器就有点吃力了，而在后来出的计算器就引入了四则运算表达式的概念，也可以输入括号了。
那么在新式计算器中，它是如何实现的呢？这里面的困难就在于乘除在加减的后面，却要先运算，而加入括号后，就变得更加复杂。不知道如何处理。
但仔细观察后发现，括号都是成对出现的，有左括号就一定会有右括号，对于多重括号，最终也是完全嵌套匹配的。这用栈结构正好合适，只有碰到左括号，就将此左括号进栈，不管表达式有多少重括号，反正遇到左括号就进栈，而后面出现右括号时，就让栈顶的左括号出栈，期间让数字运算，这样，最终有括号的表达式从左到右时巡查一遍，栈应该是由空到有元素，最终再因全部匹配成功后成为空栈的结果。

但对于四则运算，括号也只是其中的一部分，先乘除后加减使得问题依然复杂，如何有效地处理它们呢？我们伟大的科学家想到了好办法。

20世纪50年代，一位波兰逻辑学家想到了一种不需要括号的后缀表达式，我们把它称为逆波兰(Reverse Polish Notation, RPN)表示。
我们先来看看，对于“9+（3-1）*3+10/2”，如果要用后缀表示法应该是：“9 3 1-3*+10 2/+”这样的表达式称为后缀表达式，所有的符号都是再要运算数字的后面出现。

后缀表达式计算结果

为了解释后缀表达式的好处，我们先来看看计算机如何应用后缀表达式计算出最终的结果：“9 3 1-3*+10 2/+
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果出栈，一直到最终获得结果。

初始化一个空栈，此栈用来对要计算的数字进出使用
后缀表达式中前三个都是数组，所以9 3 1进栈
接下来是”-“，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1，得到2，再将2进栈
接着是数字3进栈
后面是”*“，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈
下面是”+“，所以栈中6和9出栈，9与6相加，得到15，将15进栈
接着是10与2两数字进栈
接下来是符号”/“，栈顶的2与10出栈，10与2相除，得到5，将5进栈
最后一个符号是”+“，15与5出栈并相加，得到20，将20进栈
结果是20，出栈，栈变为空

后缀表达法可以很顺利的解决计算的问题，那么这个后缀表达式是怎么出来的？

中缀表达式转后缀表达式

我们把平时所用的标准四则运算表达式叫做中缀表达式，所有的运算符号都在两数字的中间，中缀表达式转后缀表达式规则：
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式中的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

初始化一空栈，用来对符号进出栈使用
第一个字符是9，输出9，后面符号是”+“，进栈
第三个符号是”（“，依然是符号，因其只是左括号，还未配对，故进栈
第四个字符是数字3，输出，总表达式9 3，接着是”-“，进栈
接下来是数字1，输出，总表达式9 3 1，后面是符号”）“，此时我们需要去匹配此前的”（“，所以栈顶依次出栈，并输出，知道”（“出栈为止。此时左括号上方只有”-“，因此输出”-“，总表达式为9 3 1-
接着是数字3，输出，总表达式9 3 1-3.接着是符号“*”，此时栈顶符号是”+“，优先级低于”x”，因此不能输出，”x”进栈
之后是符号“+”，此时当前栈顶元素“x”比“+”的优先级高，因此栈中元素出栈并输出（没有比“+”优先级更低的优先级，所以全部出栈），总输出表达式为9 3 1 - 3*+。然后将当前这个符号“+”进栈。
紧接着数字10，输出，后是符号“/”，所以“/”进栈
最后一个数字2，输出，总的表达式为9 3 1-3*+10 2.
因已经到最后，所以将栈中符号全部出栈并输出，最终输出的后缀表达式结果为9 3 1-3*+10 2/+

从刚才的推到中会发现，要想让计算机具有处理我们通常的标准（中缀表达式）的能力，最重要的两步九四：

将中缀表达式转化为后缀表达式（栈用来进出运算的符号）
将后缀表达式进行运算得出结果（栈用来进出运算的数字）

队列的定义

有时用电脑时，机器有时处于疑似死机的状态，鼠标点什么似乎都没用，双击任何快捷方式都不动弹。就当你失去耐心打算reset时突然他像酒醒了一样，把你刚才点击的所有操作全部都按顺序执行了一遍。这其实是因为操作系统中的多个程序需要通过一个通道输出，而按先后次序排队等待造成的。
队列(queue)是只允许再一段进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一段称为队尾，允许删除的一段称为队头。

队列的抽象数据结构

同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行

1队列

循环队列

线性表有顺序存储和链式存储，队列也是线性表，同样存在这两种存储方式。

队列顺序存储的不足

假设队列有n个元素，建立一个大于n的数组，并把元素存储在前n个单元，数组下标为0的一段是队头。入队列操作就是在队尾追加一个元素，时间复杂度为O(1)。而与栈不同，队列的出列是在队头，下标为0的位置，那就意味着所有元素都得向前移动，以保证队列的队头不为空。此时时间复杂度为O(n)
但想想，为什么出队列一定要全部移动呢？如果队头不需要一定在下标为0的位置，出队列的性能将会大大增加，引入两个指针front指向队头，rear指向队尾元素的下一个位置（不指向队尾，因为只有一个元素时会两指针会重合），但两者重合时，为空队列。
但这样又有新的问题，随着出队列和入队列的操作，前面会产生空缺未被使用，随着入队列元素的增加，就会产生数组越界的错误，可实际上前面位置是空闲的，我们把这种现象叫做”假溢出“。

循环队列的定义

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环，我们把队列的这种头尾相接的顺序存储结构称为循环队列
继续我们刚才的例子，当即将假溢出时，将rear指向下标0，接着继续插入元素，当rear与front指针重合时，队列就满了，但是这样又有新问题：

我们刚才说，空队列时，front等于rear，现在队列满了也是，那么该如何判断时空还是满呢？
办法一就是设置一个标志变量flag，当front == rear，且flag = 0时，队列为空，当front == rear且flag=1时，队列为满
办法二说是当队列为空时，条件就是front==rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，当队列满时，数组中还有一个空闲单元。

我们重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize,那么队列满的条件是（rear+1)%QueueSize == front(取模的目的就是为了整个rear与front大小为一个问题)。

另外当rear>front时，此时队列的长度为rear-front。但当rear<front时，队列长度为两段，一段是QueueSize-front，另一段0+rear，加在一起，队列长度为rear-front+QueueSize。因此通用的计算队列长度公式为：

1	`(rear-front+QueueSize)%QuwuwSize`

队列的顺序存储结构代码如下：

typedef int QElemType;

typedef struct
{
	QElemType data[MAXSIZE];
    int front;		//头指针
    int rear;		//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

循环队列的初始化代码如下：

Status InitQueue(SqQueue *Q)
{
	Q->front = 0;
    Q->rear = 0;
    return 0K;
}

循环队列求队列长度代码如下：

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

循环队列的入队列操作代码如下

Status EnQueue(SqQueue *Q, QElemType e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)	//队列满的判断
        return ERROR;
    Q->data[Q->rear] = e;	//将e元素赋值给队尾
    Q->rear = (Q->rear + 1) % MAXSIZE;	//若到最后则转到数组头部
    
    return OK;
}

循环队列的出队操作

Status DeQueue(SqQueue *Q, QElemType *e)
{
    if(Q->front == Q->rear)	//队列空的判断
        return ERROR;
   	*e = Q->data[Q->front];		//将队头元素赋值给e
    Q->front = (Q->front +1)%MAXSIZE;	//front指针向后移一位，若到最后则转到数组头部
    return OK;
}

队列存储结构及实现

队列的链式存储结构，其实就是现象表的单链表，只不过它只能尾进头出而已，我们简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。空队列时，front和rear都指向头节点。链队列的结构为：

typedef int QElemType;

typedef struct QNode//结点结构
{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct	//队列的链表结构
{
	QueuePtr front, rear;	//队头、队尾指针
}LinkQueue;

队列的链式存储结构-入队操作

//插入元素e为Q的新的队尾元素
Status EnQueue(LinkQueue *Q, QElemType e)
{
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!s)		//存储分配失败
        exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;	//把拥有元素e的新节点s赋值给原队尾结点的后继
    Q->rear = s;		//把当前的s设置为队尾结点，rear指向s
    return OK;
}

队列的链式存储结构-出队操作

Status DeQueue(LinkQueue *Q, QElemType *e)
{
	QueuePtr p;
    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;
}

串

串（string）是由零个或多个字符组成的有限序列，又名字符串

，一般记为s =”a1a2a3…an”（n>=0），s是字符串的名称，用双引号。n称为串的长度，是一个有限的值。零个字符的串称为空串（null string），长度为0，可以直接用两双引号表示“ ”“ ”。也可以使用希腊字符“fai”（打不出来）。所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。

串的比较

串要如何比较呢？它们在计算机中的大小，其实取决于它们挨个字母的前后顺序。比如”silly“和”stupid“，它们第一个字母都是”s”，它们认为不存在大小初一，而第二个字母”i“比”t“更要靠前，所以“i”<”t”，于是“silly”<“stupid”
事实上，串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。计算机中常用字符是使用标志的ASCII编码，更准确一点，由7位二进制数表示一个字符，总共可以表示128个字符。后来发现一些特殊字符的传销，128个不够了，于是扩展ASCII码由8位二进制数表示一个字符，总共可以表示256个字符，这已经足够满足以英语为主的语言和特殊符号进行输入、存储、输出等操作。可是单我们国家就有除汉族的满、回、藏等多个少数民族文字，换做全世界估计要有成百上千种语言与文字。所以后来就有了Unicode编码，比较常用的是由16位的二进制数表示一个字符，约65万个字符，当然为了和ASCII码兼容，Unicode的前256个字符与ASCII码完全相同。

串的抽象数据类型

串的逻辑结构和线性表很相似，但串针对的是字符集，也就是串中的元素都是字符，因此对于串的基本操作与线性表是有很大差异的，线性表中关注的是单个元素的操作，比如查找一个元素、插入或删除一个元素，但串中更多的是查找子串的位置、得到指定位置的子串、替换子串等操作

串的抽象数据类型

我们先来看一个操作index的实现算法

//t为非空串。若主串s中第pos个字符之后存在与t相等的子串，则返回第一个这样的子串在s中的位置，否则返回0
int Index(String s, String t, int pos)
{
	int n, m, j;
    if(pos > 0)
    {
		n = StrLength(s);	//得到主串s的长度
        m = StrLength(t);	//得到子串t的长度
        i = pos;
        while(i <= n-m+1)
        {
            SubString(sub, s, i, m);	//取主串第i个位置，长度与t相等子串给sub
            if(StrCompare(sub, t) != 0)		//如果两串不相等
                ++i;
            else 		//如果两串相等
                return i;	//放回i值
        }
    }
    return 0;	//若无子串与t相等，返回0
}

串的存储结构

串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列。一般用定长数组来定义。

串的链式存储结构

串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会造成很大的空间浪费。因此，一个结点也可以考虑存放多个字符，最后一个结点若是未被占满，可以用“#”或其他非串值字符补全。

朴素的模式匹配算法

子串的定位操作通常称为串的模式匹配，应该算是串中最重要的操作之一。

//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0
//T非空，1<= pos <= StrLength(S)
//假设长度存在[0]中
int Index(String S, String T, int pos)
{
	int i = pos;	//i用于主串s中当前位置下标，若pos不为1泽聪pos位置开始匹配
    int j = 1;	//j用于子串t中当前位置下标值
    while(i <= S[0] && j <= T[0])	//若i小于s长度且j小于t的长度时循环
    {
		if(S[i] == T[j])	//若两字符相等则继续
        {
			++i;
            ++j;
        }
        else		//指针后退重新开始匹配
        {
			i = i-j+2;	//返回上次匹配首位的下一位
            j = 1;		//j退回到子串t的首位
        }
    }
    if(j > T[0])
        return i-T[0];
    else 
        return 0;
}

KMP模式匹配算法

朴素模式匹配算法很低效，于是就有三位前辈发表了一个模式匹配算法我们称之为克努特-莫里斯-普拉特算法，简称KMP算法。如果有人搜索到我的博客，想学习KMP算法，还是建议看视频教学，或搭配着看，这部分图片或视频更容易理解，光看文字可能没什么概念。同时KMP算法的next数组实现方法不止一种。

算法原理

定义一个next数组，记录子串各个部分的最长公共前后缀长度，再利用next数组，在进行主串与子串之间的挨个比对时，当出现不等元素时，跳过已经遍历过的公共部分，比如s=”ababcxxxx” t=”ababd” next=”00120”。当对比到最后一位元素时，出现了不同，此时对于前面遍历过的abab，最长公共前后缀长度是2，也就是ab。我们可以跳过2个元素，因为后缀元素与前缀元素是相同的。

KMP算法C语言实现

我们前面说了，在对比s和t中的元素时，若出现不等于的情况，可以直接跳过最长公共前后缀个元素，接着比较。s=“ababbaa” t=“ababc”。我们对比到第5个元素时，发现不相同，我们就看next数组的第4（就是5-1）个元素，它的值是2，说明前面这些元素最长公共前后缀是2，也就是说，我们可以跳过t的前2个元素，直接从t的第3个元素对比。具体代码实现为：

int indexKMP(string s, string t){
	int i = 0;	//主串s的元素
	int j = 0;	//子串t的元素
	int next[100];
	getNext(t, next);
	while( i < strlen(s) && j < strlen(t)){		//当未达到主串或子串的末尾时，继续
		if( s[i] == t[j]){		//元素相等，主串指针和子串指针同时后移
			i++;
			j++;
		}
		else {
			if(j == 0){			//如果j等于0，则子串无法再回溯，说明主串的对应元素不是遍历过的子串中的一部分，下一个
				i++;			//主串指针后移
			}
			else{				//如果不相等且j != 0 ，则需要对子串指针进行回溯
				j = next[j-1];	//回溯并跳过公共前后缀
			}
		}
	}
	if( j == strlen(t))			//子串被遍历完，说明子串存在于主串
		return i - j;
	else 
		return -1;
}

创建next数组

void getNext(string t, int* next){
	int f = 0;	//前缀末尾元素 和 最长公共前后缀长度
	int b = 1;	//后缀末尾元素
	next[0] = 0;
	while( b < strlen(t)){
		if(t[f] == t[b]){	//相等
			f++;			//前缀指针后移，同时也表示最长公共前后缀长度+1
			next[b] = f;	//记录b位置的最长公共前后缀长度
			b++;			//后缀指针后移
		}
		else{				//不相等
			if( f == 0){	//如果前缀指针指向0/当前最长公共前后缀长度为0 且t[f] != t[b]
				next[b] = 0;	//b位置的最长公共前后缀长度为0
				b++;			//后缀指针后移
			}
			else{			//如果f不为0且前后缀不等
				f = next[f-1];	//前缀指针回溯，并跳过公共部分
			}
		}
	}
}

树

树的定义

之前我们一直在谈论一对一的关系，而树则是一种一对多的关系，
树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：有且只有一个特定的称为根（root）的结点；当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2…Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）

树的定义骑士就是我们在讲解栈时提到的递归的方法，也就是在数之中还用到了树的概念，这是一种比较新的定义方法。下图的子树T1和子树T2就是根结点A的子树。当然D、G、H、I组成的树又是B为结点的子树，E、J组成的树是C为结点的子树。

定于树的定义还需强调两点：

n>0时根节点是唯一的，不可能存在多个根节点
m>0时，子树的个数没有限制，但它们一定是互不相交的。

结点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶节点（leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称内部结点。树的度是树内各结点的度的最大值。

结点分类

结点间关系

结点的子树的根称为该结点的孩子（child），相应的，该结点称为孩子的双亲（parent），同一个双亲的孩子之间互称兄弟（sibling）（这个词本身是可以泛指兄弟姐妹）。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说，DBA都是它的祖先。以某结点为根的子树中的任一结点都称为该结点的子孙。

树的其他相关概念

结点的层次（level）从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第i层，则其子树的根就在第i+1层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（depth）或高度，当前树的深度为4。

结点的层次

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林（forest）是m（m>=0）棵互不相交的树的集合。对于树中每个结点而言，其子树的集合即为森林。
线性表与树结构对比：

线性结构	树结构
第一个元素：无前驱	根结点：无双亲，唯一
最后一个元素：无后继	叶结点：无孩子，可以多个
中间元素：一个前驱一个后继	中间结点：一个双亲多个孩子

树的抽象数据类型

树的存储结构

说到存储结构，就会想到我们前面讲过的顺序存储结构和链式存储结构两种结构。对于树的存储结构的表示，我们要介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

双亲表示法

无论是谁都不可能是从石头里蹦出来的，所以一定会有父母。树里除了根节点外，其余每个结点，它不一定有孩子，但一定有且仅有一个双亲。

#define MAX_SIZE 100
typeof int TElemType;		// 数结点的数据类型
typeof struct PTnode		// 结点结构
{
  TElemType data;				//结点数据
  int parent;						//双亲位置
}	PTnode
typeof struct
{
  PTnode nodes[MAX_SIZE];//结点数组
  int r,n;								//根的位置和结点数
} PTree;

这样就可以通过双亲来表示结点了，由于根节点没有双亲，所以它双亲位置下标为-1

学习笔记

#C语言 #学习笔记 #数据结构 #算法

easyX制作菜单页面 Previous

C/C++ EasyX图形库 Next

C语言数据结构与算法

数据结构

基础概念和术语

数据

数据元素

数据项

数据对象

数据结构

逻辑结构和物理结构

抽象数据类型

数据类型

抽象数据类型

算法

算法的定义

算法的特性

算法设计的要求

算法效率的量度方法

函数得渐近增长

算法时间复杂度

算法时间复杂度定义：

推到大O阶方法

常见的时间复杂度

最坏情况与平均情况

算法空间复杂度

线性表

线性表的定义

线性表的抽象数据类型

线性表的顺序存储结构

定义

数据长度和线性表长度的区别

顺序存储结构的插入与删除

获得元素操作

插入操作

删除操作

线性表顺序存储结构的优缺点

线性表的链式存储结构

顺序存储结构不足的解决方法

线性表链式存储结构定义

头指针与头结点的异同

线性表链式存储结构代码描述

单链表的读取

单链表的插入与删除

单链表的插入

单链表的删除

单链表的整表创建

单链表整表删除

单链表结构与顺序存储结构优缺点

静态链表

静态链表的插入操作

循环链表

双向链表

栈与队列

进栈出栈变化形式

栈的抽象数据结构

栈的顺序存储结构及实现

顺序存储结构-进栈操作

顺序存储结构-出栈操作

两栈共享空间

栈的链式存储结构及实现

栈的链式存储结构-进栈操作

栈的链式存储结构-出栈操作

栈的应用- 递归

递归定义

栈的应用-四则运算表达式求值

后缀（逆波兰）表示法定义

后缀表达式计算结果

中缀表达式转后缀表达式

队列的定义

队列的抽象数据结构

循环队列

队列顺序存储的不足

循环队列的定义

队列存储结构及实现

队列的链式存储结构-入队操作

队列的链式存储结构-出队操作

串

串的比较

串的抽象数据类型

串的存储结构

串的顺序存储结构