数据结构与算法

数据结构与算法

同学们好！现在我们学习数据结构与算法数据结构的基本概念及术语算法线性表栈和队列二叉树查找与排序两类问题：第一类.数值计算问题求解线性方程组；求解高次方程组；模型（问题描述）：算法：数学方程计算公式特点：数据简单。侧重于建立程序，以程序为中心

第1节数据结构的基本概念及术语第二类非数值计算问题例一:

将一组数据按大小进行排序。模型:算法:基本操作是“比较两个数的大小”一组数据的列表（线性表）特点：程序简单，数据规模可能很大，程序设计以数据为中心主要解决过程控制，决策和数据处理等问题。例二：计算机对弈对弈的规则和策略棋盘及棋盘的（变化）格局特点：需要有交互过程。棋盘格局的变化是树型结构

模型：算法：例三：铺设城市间的天然气管道模型：算法：图优化策略归纳：

对于非数值计算，程序设计的本质是：对需要解决的问题选择一种好的数学模型（数据结构），并加上一种好的算法。

程序＝数据结构＋算法程序:数据结构:算法:为计算机处理问题编制一组指令集

处理问题的策略问题的数学模型定位：

数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。第1小节为什么学习数据结构

计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理。要使计算机能更有效地进行这些非数值性理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。目的：合理织数据，提高程序效益。能被计算机处理的符号(数值、字符、声音、图形、图像等)的集合。1.数据:2.数据元素:

如果把数据作为一个集合，则集合中的每一个独立“个体”称为数据元素。数据元素是数据结构中讨论的基本单位。数据集合中的所有数据元素的属性相同。第2小节数据结构的基本术语例如：描述一个学生信息的数据元素称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项数据元素也可以由若干数据项构成。3.数据对象数据对象是性质相同的数据元素的集合。无限集：整数数据对象是集合N={0，±1，±2，…}，有限集：大写字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’}，多个数据项组成的复合数据元素集：

10020741班学生基本情况也可看作一个数据对象。

4.数据结构带结构的数据元素的集合

1）数据结构：一个有相同特性的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为数据结构。指的是数据元素之间存在的关系不同的“关系”构成不同的“结构”例如：IP地址（IPv4）是一个用四个3位的十进制数表示一个数据结构。如：166.111.102.128─a1(166),a2(111),a3(102),a4(128)则：在数据元素a1、a2、a3和a4之间存在着“次序”关系

a1,a2、a2,a3、a3,a4166.111.102.128a1a2a3a4111.166.102.128a2a1a3a4≠注意：又如：在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:注意：row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6

a1a2a3a4a5a6

a1a2a3a4a5a6≠2）数据结构的形式定义:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，

S是D上关系的有限集。例如:定义“班集体”为一个数据结构Class=(D,S)D={a,b1,…,bn,c1,…cn,d1,…dn

}S={R1,R2}R1={<a,b1>,<a,c1>,<a,d1>}R2={<b1,bj>,<c1,cj>,<d1,dj>|j=2,3,…,n}从数据间的关系来看，数据关系可归结为以下四种结构:线性结构树形结构图状结构集合结构3）数据结构分类分类数据结构包括“逻辑结构”

和“物理结构”两个方面(层次):逻辑结构：

是对数据元素之间的逻辑关系的描述。它对应一个数据元素的集合和定义在此集合上的若干关系;物理结构：

是逻辑结构在计算机中的表示和实现，故又称“存储结构”。4）逻辑结构和物理结构数据的存储结构

—逻辑结构在存储器中的映象“数据元素”的映象：所有数据元素都映象为二进制位串(321)10=(501)8=(101000001)2

A=(101)8=(001000001)2数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。常见的存储结构：顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。“关系”的映象：①

顺序存储结构：(1)连续存放;逻辑上相邻,物理上也相邻。

(2)结构简单，易实现。

(3)插入、删除操作不便（需大量移动元素）。②链式存储结构：(1)非连续存放,借助指针来表示元素间的关系;

(2)插入、删除操作简单，只要修改指针即可；

(3)结构较复杂，需要额外存储空间。逻辑结构和物理结构的关系(1)数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。(2)数据的存储结构是逻辑结构在计算机中的实现，依赖于计算机；离开了机器，则无法进行任何操作。(3)任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。5）抽象数据类型抽象数据类型（简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的描述方法：ADTname{

数据对象：D={……}

数据关系：R={……}

基本操作：创建；输出；插入；删除；等等;}ADTname;【例】复数的抽象数据类型描述ADTComplex{

数据对象：D={c1,c2|c1,c2∈float}

数据关系：R={<c1,c2>|c1,c2分别代表复数的实部和虚部}

基本操作：创建一个复数；输出一个复数；求两个复数的和；求两个复数的积；等等;}ADTComplex;第2节算法第1小节算法的基本概念①算法：

是对特定问题求解步骤的一种描述。②算法和数据结构的关系：对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。③设计算法的步骤：通过对问题进行详细地分析，确定方案；确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；选用某种语言将算法转换成程序；调试并运行这些程序。④算法的特性（1）有穷性：一个算法必须在执行有穷步之后结束。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。

（4）输入：一个算法应该有零个或多个输入。

（5）输出：一个算法应该有一个或多个输出。⑤算法设计的要求（1）正确性（Correctness）有4个层次：

A.程序不含语法错误；

B.程序对几组输入数据能够得出满足规格要求的结果；

C.程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果；

D.程序对一切合法的输入数据都能产生满足规格要求的结果。（2）可读性（Readability）

算法的第一目的是为了阅读和交流;可读性有助于对算法的理解;可读性有助于对算法的调试和修改。

（3）健壮性（Robustness）

当输入非法数据时，算法也能适当地作出反应或进行处理；并且，处理出错的方法应该是返回一个表示错误或错误性质的值并中止程序的执行，以便在更高的抽象层次上进行处理。

（4）高效率与低存储量

处理速度快;存储容量小;时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。第2小节算法评价的标准（效率的度量）①评价算法好坏的标准

求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？

选用的算法首先应该是“正确”的。此外，主要考虑如下三点：

第一：执行算法所耗费的时间；

第二：执行算法所耗费的存储空间，其中主要考虑辅助存储空间；

第三：算法应易于理解，易于编码，易于调试②算法效率的衡量方法和准则通常有两种衡量算法效率的方法:

事后统计法事前分析估算法缺点：1。必须执行程序

2。其它因素掩盖算法本质算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度③时间复杂度（指在计算机上运行该算法所花费的时间。）

一般情况下，算法中的基本操作重复操作执行的次数是问题规模n的某个函数f(n)。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。

算法的时间复杂度记做

T(n)=O(f(n))用"O（数量级）"来表示，称为"阶"。

对算法效率分析问题的简化：【例】求两个n阶方阵的乘积C=A×B

constintn=100

;voidMatrixMultiply(intA[n][n]，intB[n][n]，intC[n][n])

{//红色为各语句的频度

inti,j,k;

(1)for(i=0;i＜n;j++)n+1

(2)

for(j=0;j＜n;j++)n(n+1)

(3)

{C[i][j]=0;n2

(4)

for(k=0;k＜n;k++)n2

(n+1)

(5)

C[i][j]=C[i][j]+A[i][k]*B[k][j];n3

}

}}该算法中所有语句的频度之和(即算法的时间耗费)为：

T(n)=2n3+3n2+2n+1

这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同。记作T(n)=O(n3)是算法的渐近时间复杂度。

for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}例选择排序

void

select_sort(inta[],intn){

}//select_sort基本操作:比较操作时间复杂度:O(n2)j=i;//

选择第i个最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;

n+1

nn(n-1)/2

nn(n+1)/2【例】（a）x=x+1；O（1）（c）for(i=0;i<n;i++)

（b）for(i=0;i<n;i++)for(j=0;j<n;j++)

x=x+1；O（n）x=x+1；O（n2）

（d）i=1;

while(i<n) i=i*2;O（log2n）常见的时间复杂度有：O（1）常数阶

O（log2n）对数阶

O（n）线性阶

O（n2）平方阶

O(2n）指数阶102030405020040060080010001200140010n20n5nlogn2n22n④空间复杂度（数据、程序、辅助）

一个算法的空间复杂度(SpaceComplexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

⑤算法性能选择

要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重：

①若该程序使用次数较少，则力求算法简明易懂；

②对于反复多次使用的程序，应尽可能选用快速的算法；

③若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。

线性表是最简单且最常用的一种数据结构。掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。

第3节线性表

线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。1.线性表的定义

线性表L是n（n≥0）个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。当n=0时称为空表，即不含有任何元素。常常将非空的线性表(n>0)记作：(a1，a2，…an)

这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。第1小节线性表的基本概念及运算

例1、26个英文字母组成的字母表（A，B，C、…、Z）

例2、从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、线性表的逻辑特征：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；

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

其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。

线性表是一种典型的线性结构。2.线性表的基本运算(1)初始化线性表(2)求线性表的长度(3)按序号取元素(4)按值查找(5)插入元素(6)删除元素3.线性表的抽象数据类型ADTLinear_list{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0；}

数据关系：R={<ai-1，ai>|ai-1,ai∈D,i=2,3,…,n}

基本操作：初始化空线性表；求线性表表长；取线性表的第i个元素；在线性表的第i个位置插入元素x；删除线性表的第i个元素；修改线性表中的第i个元素；按某种要求重排线性表中各元素的顺序；按某个特定值查找线性表中的元素；

……}ADTLinear_list；第2小节线性表的顺序结构及运算实现线性表的顺序存储结构又称顺序表1.具有以下两个基本特点：

(1)线性表的所有元素所占的存储空间是连续的。用物理的连续表示逻辑的连续(2)在确定顺序表起始位置后，线性表中各数据元素可随机存取。可随机存取的存储结构

2.顺序表类定义及运算实现：typedef

int

ElemType; constintMAXSIZE=100; classSqList{private:

ElemType

elem[MAXSIZE];intlength;public:

SqList(void);~SqList(){};voidCreat(intn);

voidPrintOut();

int

GetLength();

int

Locate(ElemTypex);

ElemType

GetElme(inti);voidInsert(inti,ElemTypex);voidDelete(inti); };

①初始化线性表：使用构造函数实现SqList::SqList(){length=0;}

②得到线性表长度：int

SqList::GetLength(){returnlength;}③创建线性表：voidSqList::Creat(intn){

cout<<"输入"<<n<<"元素:\n";

for(intk=0;k<n;k++)cin>>elem[k]; length=n;}④输出线性表：voidSqList::PrintOut() {

cout<<"length="<<length;

cout<<"\nPrintOutData:\n";

for(intk=0;k<length;k++)

cout<<setw(6)<<elem[k];

cout<<endl;}⑤查找值为x的元素：int

SqList::Locate(ElemTypex){

inti;

i=0;

while(i<length&&elem[i]!=x)

i++;

if(i<length)returni+1;

elsereturn0;}⑥得到第i个元素：ElemType

SqList::GetElme(inti){

if(i<1||i>length){cout<<"error\n";exit(1);}returnelem[i-1];}⑦第i个插入值为x的元素：voidSqList::Insert(inti,ElemTypex){

intj;if(i<1||i>length+1) {cout<<"error\n";exit(1);}

if(length==MAXSIZE) {cout<<"overflow!\n";exit(1);}

for(j=length;j>=i;j--)

elem[j]=elem[j-1];

//数据元素后移

elem[i-1]=x; //插入x

length++; //表长度加1}

⑧删除第i个元素：voidSqList::Delete(inti){intj;if(i<1||i>length)

{cout<<"不存在第i个元素\n";exit(0);}for(j=i;j<length;j++)elem[j-1]=elem[j];//向前移动元素length--;}voidmain(){

SqListl;l.Creat(3);

cout<<"初始的线性表:\n";

l.PrintOut();

cout<<“\n查找值为x的元素:"<<l.Locate(2)<<endl;

cout<<"\n查找第i个元素:"<<l.GetElme(1);

cout<<"\n第i个位置插入值为x的元素:\n";l.Insert(1,10);

l.PrintOut();

cout<<"\n删除第i个位置的元素:\n";l.Delete(2);

l.PrintOut();}【例】利用线性表的基本运算，编写在线性表A中删除线性表B中出现的元素的算法。

【解】本题的算法思路是：依次检查线性表B中的每个元素，看它是否在线性表A中。若在线性表A中，则将其从A中删除。本题的算法如下：

voiddelbina(SqList&A,SqList&B){int

i,k;

ElemTypex;

for(i=1;i<=B.GetLength();i++){x=B.GetElme(i);k=A.Locate(x);

if(k>0)A.Delete(k);}}【例】将顺序表(a1，a2，a3，…，an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大（这里假设数据元素的类型具有可比性，可设为整型）。

【解】基本思路：从第二个元素开始到最后一个元素，逐一向后扫描，当数据元素ai比a1大时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个；当数据元素ai比a1小时，表明它应该在a1的前面，此时将它前面的元素依次向下移动一个位置，然后将它置入最上方。算法如下：voidSqList::part(){

int

i,j;

ElemType

x,y;x=elem[0];//将基准元素a1置入x中

for(i=1;i<length;i++)

if(elem[i]<x)//当前元素小于a1{y=elem[i];

for(j=i-1;j>=0;j--)//移动

elem[j+1]=elem[j];elem[0]=y;}}顺序存储结构缺点主要表现在：（1）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间；（2）插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和删除操作时需移动大量数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提高。（3）存储空间不便于扩充。当一个线性表分配顺序存储空间后，若线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。第3小节线性表的链式存储和运算实现

为避免大量结点的移动，可以使用另一种存储方式:链式存储结构，简称链表(LinkedList)。

线性表的链式存储结构中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。

1链表的存储结构C++语言采用结构数据类型描述结点如下：typedef

structnode{ElemTypedata;//结点值

structnode*next;//存储下一个结点的地址}

NodeType

;

假设有一个线性表为（A,B,C,D,E），存储空间具有10个存储结点，该线性表在存储空间中的存储情况如下图所示。

2单向链表每个结点只有一个指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾，而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。对于空链表，头结点的指针域为空。（a）为带头结点的空链(b)为带头结点的单链表单链表类定义及运算实现：classLinkList{private:

NodeType*Head;//链表头指针public:

LinkList(void);~LinkList(){};voidCreat(intn); voidPrintOut();

int

GetLength();

NodeType*Locate(ElemTypex);

NodeType*GetElme(inti);voidInsert(inti,ElemTypex);

voidInsert(inti,NodeType*s)

voidDelete(inti);};①初始化单链表：使用构造函数实现LinkList::LinkList(){Head=new

NodeType;Head->next=0;}

②得到链表长度：int

LinkList::GetLength(){

intnum=0;

NodeType*p;p=Head->next;

while(p!=NULL){num++;p=p->next;}

return(num);}③创建单链表表：voidLinkList::Creat(intn){

inti;

NodeType*p,*pup;

if(n>0)

for(i=0;i<n;i++) { p=newNodeType;

cin>>p->data; p->next=NULL;

if(i==0)Head->next=p;elsepup->next=p; pup=p; }}④输出单链表：voidLinkList::PrintOut() {

NodeType*p;p=Head->next;

while(p!=NULL){cout<<setw(6)<<p->data;p=p->next;}

cout<<endl;}⑤查找值为x的节点：NodeType*LinkList::Locate(ElemTypex){

NodeType*p;p=Head->next;

while(p!=NULL&&p->data!=x)p=p->next;returnp;}⑥得到第i个节点：NodeType*LinkList::GetElme(inti){

NodeType*p;

intpos=1;p=Head->next;

if(i<1||i>GetLength())exit(1);

while(pos<i){p=p->next;pos++;}returnp;}s=(LNode*)malloc(sizeof(LNode))；s->data=x；(b)申请新结点s，数据域置xxsheada1a2...ai-1p...aian∧xsheada1a2×...ai-1p...aian∧②①(a)找到插入位置s->next=q->nextq->next=s(c)修改指针域，将新结点s插入关键语句：qq⑦第i个插入值为x的元素：voidLinkList::Insert(inti,ElemTypex){

NodeType*p,*q,*s;

intpos=1;p=Head;

if(i<1||i>GetLength()+1)exit(1);s=newNodeType;s->data=x;

while(pos<=i){q=p;p=p->next;pos++;}s->next=q->next;q->next=s;}

如果插入的某节点：voidLinkList::Insert(inti,NodeType*s){

NodeType*p,*q;

intpos=1;

if(i<1||i>GetLength()+1)exit(1);p=Head;

while(pos<=i){q=p;p=p->next;pos++;}s->next=q->next;q->next=s;}x=p->data；(b)返回被删除结点数据xxpheada1a2...ai-1q...aian∧(a)找到删除位置pheada1...(c)修改指针域，将结点p删除qai-1pai...an∧ai+1①②关键语句：q->next=p->next；free(p)⑧删除第i个元素：voidLinkList::Delete(inti){

intpos=1;

NodeType*q=Head,*p;

if(i<1||i>GetLength())exit(1);

while(pos<i){q=q->next;pos++;}p=q->next;q->next=p->next;deletep;}

voidmain(){

LinkListl;l.Creat(3);

cout<<"初始的线性表:\n";

l.PrintOut();

cout<<endl<<l.GetLength()<<endl;

NodeType*p;p=l.GetElme(2);

cout<<endl<<"第2个元素："<<p->data<<endl;p=l.Locate(2);

cout<<endl<<"值为2个元素："<<p->data<<endl;l.Delete(1);

l.PrintOut();}【例】利用前面定义的基本运算函数，编写将一已知的单链表H倒置的程序。如图的操作。(a)为倒置前，(b)为倒置后。图

单链表的倒置【解】算法基本思路：不另外增加新结点，而只是修改原结点的指针。设置指针p，令其指向head->next，并将head->next置空，然后依次将p所指链表的结点顺序摘下，插入到head之后即可。具体算法如下：voidLinkList::reverse(){NodeType*p,*q;

if(Head->next!=NULL){p=Head->next;Head->next=NULL;

while(p!=NULL){q=p;p=p->next;Insert(1,q);}}}3循环链表

在单链表中，最后一个结点的指针域为空（NULL）。访问单链表中任何数据只能从链表头开始顺序访问，而不能进行任何位置的随机查询访问。如要查询的结点在链表的尾部也需遍历整个链表。所以单链表的应用受到一定的限制。循环链表(CircularLinkedList)是另一种形式的链式存储结构。它将单链表中最后一个结点的指针指向链表的头结点，使整个链表头尾相接形成一个环形。这样，从链表中任一结点出发，顺着指针链都可找到表中其它结点。循环链表的最大特点是不增加存储量，只是简单地改变一下最后一个结点的指针指向，就可以使操作更加方便灵活。图循环链表结构示意图带头结点的单循环链表的操作算法和带头结点的单链表的操作算法很相似，差别仅在于算法中的循环条件不同。在循环单链表上实现上述基本运算的改动如下：1）．初始化链表创建的头结点指针域next不为空，而是指向自身，Head->next=Head2）．求线性表长度GetLength()函数、查找运算locate(x)函数、链表元素输出运算PrintOut()函数中，循环遍历是否进行的条件由p!=NULL改为p!=L;其余函数运算没有变化，请自行写出相关函数的定义。在循环链表中，除了有头指针head外，有时还可加上一个尾指针tail。尾指针tail指向最后一结点，沿最后一个结点的指针又可立即找到链表的第一个结点。在实际应用中，使用尾指针来代替头指针进行某些操作往往会更简单。【例】将两个循环链表首尾相接进行合并【解】算法思路：对两个单循环链表La，Lb进行的连接操作，是将Lb的第一个数据结点接到La的尾部。操作时需要从La的头指针开始找到La的尾结点，其时间复杂性为O(n)。而在循环链表中若采用尾指针La，Lb来标识，则时间性能将变为O(1)。其连接过程如下图所示。图两个循环链表首尾相接进行合并

4双向链表

单链表只有一个指向后继的指针来表示结点间的逻辑关系。故从任一结点开始找其后继结点很方便，但要找前驱结点则比较困难。双向链式是用两个指针表示结点间的逻辑关系。即增加了一个指向其直接前驱的指针域，这样形成的链表有两条不同方向的链，前驱和后继，因此称为双链表。在双链表中，根据已知结点查找其直接前驱结点可以和查找其直接后继结点一样方便。

下面也仅讨论带头结点的双链表。

双向链表结点的定义如下：

typedef

struct

DNode{

ElemTypedata;

struct

DNode*prior;

struct

DNode*next;}Dnode,*DuLinkList;图双向链表结点结构图

在双向链表中也可采用与单链表类似的方法，用头指针标识链表的开头，也可以带头结点。在双向链表中，每个结点都有一个指向直接前驱结点和一个指向直接后继结点的指针。链表中第一个结点的前驱指针和最后一个结点的后继指针可以为空，不做任何指向，这是简单的双向链表。图带头结点的双向链表

图中，如果某指针变量p指向了一个结点，则通过该结点的指针p可以直接访问它的后继结点，即由指针p->next所指向的结点；也可以直接访问它的前驱结点，由指针p->prior指出。这样在需要查找前驱的操作中，就不必再从头开始遍历整个链表。这种结构极大地简化了某些操作。结点的插入过程如下图所双向链表示：

注意：在图中，关键语句指针操作序列既不是唯一也不是任意的。操作①必须在操作③之前完成，否则*p的前驱结点就丢掉了。

在双向链表中找到删除位置的前一个结点，由p指向它，q指向要删除的结点。删除操作如下：①将*p的next域改为指向待删结点*q的后继结点；②若*q不是指向最后的结点，则将*q之后结点的prior域指向*p。

注意：在双向链表中进行插入和删除时，对指针的修改需要同时修改结点的前驱指针和后继指针的指向。

结点的删除过程如下图所双向链表示：

5循环双链表与循环单链表一样，也可以使用循环双链表。循环单链表和循环双链表可通过尾结点找到头结点，也常作为编辑器的数据结构，尤其是循环双链表。

图

带头结点且有n个结点的循环双链表

链式存储结构小结：

克服了顺序存储结构的缺点,它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，进行数据插入或删除时不需要移动数据元素。但是链式存储结构也有不足之处：①每个结点中的指针域需额外占用存储空间，当每个结点的数据域所占字节不多时，指针域所占存储空间的比重就显得很大；②链式存储结构是一种非随机存储结构。对任一结点的操作都要从指针链查找到该结点，这增加了算法的复杂度。第4节栈和队列第1小节栈1.栈的定义

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：

进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图的形式描述：a1,a2,a3,...,an插入和删除端图栈示意图特性：后进先出（LastInFirstOut），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。栈结构的基本操作：（1）初始化栈

（2）入栈

（3）出栈

（4）获取栈顶元素内容

（5）判断栈是否为空2.栈的抽象数据类型ADTStack{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0;}

数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}

基本操作：初始化一个空栈；判栈空，空栈返回True,否则返回False；进栈，在栈顶插入一个元素；出栈，在栈顶删除一个元素；取栈顶元素值；置栈为空状态；求栈中数据元素的个数；销毁栈；

……}ADTStack；3.顺序栈类定义及运算实现typedef

int

ElemType; constintMAXSIZE=100;classSqstack{private:

ElemType

elem[MAXSIZE];

inttop;public:public:

Sqstack(){top=-1;}

~Sqstack(){}; voidSetEmpty(){top=-1;}

int

IsEmpty(); voidPush(ElemTypee);

ElemTypePop();

ElemType

GetTop(); voidPrintOut();

};①初始化顺序栈：使用构造函数实现Sqstack::

Sqstack(){top=-1;}③入栈：voidSqstack::Push(ElemTypee){if(top==MAXSIZE-1)cout<<“\n栈满溢出"<<endl;elseelem[++top]=e;}②判断是否空栈：int

Sqstack::

Sqstack(){if(top==-1)return1;elsereturn0;}④出栈：ElemType

Sqstack::Pop(){

if(top==-1){cout<<“\n栈为空，不能进行出栈操作"<<endl;exit(0);//return(0);}returnelem[top--];}⑤获取栈顶元素：ElemType

Sqstack::GetTop(){if(top==-1){cout<<“\n栈为空，不能进行出栈操作"<<endl;exit(0);}returnelem[top];}⑥输出栈的所有元素：voidSqstack::PrintOut() {cout<<"\nPrintOutData:\n";

if(top==-1)cout<<"\n已是空栈！";else{for(intk=top;k>=0;k--)

cout<<setw(6)<<elem[k];

cout<<endl;}}^若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构--“链栈”。链栈通常用一个无头结点的单链表表示。结点的类型定义：typedef

int

ElemType;struct

Lsnode

{ElemTypedata;

Lsnode*next;};将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针4.栈的链式存储

top链栈类定义及运算实现typedef

int

ElemType; classSqstack{private:

Lsnode*top;public:public:

Sqstack(){top=NULL;}

~Sqstack(){};

int

IsEmpty(); voidPush(ElemTypee);

ElemTypePop();

ElemType

GetTop();

voidPrintOut();

};①初始化顺序栈：使用构造函数实现Sqstack::

Sqstack(){top=0;}③入栈：voidSqstack::Push(ElemTypee){Lsnode*p;p=newLsnode;p->data=e;

p->next=top;top=p;

}②判断是否空栈：int

Sqstack::

Sqstack(){if(top==NULL)return1;elsereturn0;}④出栈：ElemType

Sqstack::Pop(){

Lsnode*p;

ElemTypex;if(top==0)cout<<"Stackisempty!\n";else{x=top->data;p=top;top=top->next;deletep;

returnx;}}⑤获取栈顶元素：ElemType

Sqstack::GetTop(){if(top==0)cout<<"Stackisempty!\n";returntop->data;}⑥输出栈的所有元素：voidSqstack::PrintOut() { Lsnode*p; p=top;

cout<<"\nPrintOutData:\n";

if(p==NULL)cout<<"\n已是空栈！";else{while(p!=NULL) {cout<<setw(6)<<p->data;p=p->next;}

cout<<endl;}

}5栈的应用举例【举例1】将从键盘输入的字符序列逆置输出

比如：从键盘上输入：

tsetasi

sihT算法将输出：Thisisatest完整算法：

typedefcharStackEntry;voidReverseRead(){

Sqstacks;charch;

cout<<"输入一串字符:\n"; while((ch=getchar())!='\n')s.Push(ch);while(s.IsEmpty()==0)

cout<<s.Pop();

cout<<endl;}【举例2】十进制数值转换成二进制

使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。

完整算法：voidDecimal_Binary(){Sqstacks;intdata;cin>>data;while(data){s.Push(data%2);data/=2;}while(!s.IsEmpty())

cout<<s.Pop();cout<<endl;}【举例3】检验表达式中的括号匹配情况

假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，并且这三种括号可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。

算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。

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

第2小节队列1队列的定义

队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。a1a2a3...ai...an-1an删除端插入端

插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。结论：先进先出（FirstInFirstOut），简称为FIFO线性表。

举例：在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。队列结构的基本操作：（1）初始化队列（2）入队（3）出队（4）获取队头元素内容（5）判断队列是否为空2.队列的抽象数据类型ADTQueue{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0;}

数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n

基本操作：初始化一个空队列；判队空入队，在队尾插入一个元素；出队，在队头删除一个元素；取队头数据元素值；置队列为空状态；销毁队列；

……}ADTQueue;2队列的顺序存储队列的顺序存储结构如下图所示：问题1：当队空时，队头和队尾指针都为-1，队列将处于下图所示的状态：此时若进行入队操作，就需要让队头和队尾指针都增1，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队与非空队状态所需要执行的操作不完全一样。解决方法：在算法中，需要对这两种情况加以区分，这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图所示。

问题2：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。如下图出现

“假溢出”现象。

解决方法：将存储队列元素的一维数组首尾相接，形成一个环状---“循环队列”。a8a7a6a576543210rearfront①循环的效果的实现

假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算实现。如下所示：

front=(front+1)%MAX_QUEUE；

rear=(rear+1)%MAX_QUEUE；当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。这样，就使得指针自动由后面转到前面，形成循环的效果。

a7a876543210rearfront76543210rearfront(a)(b)队列变为空，队头和队尾指针相等。②队空和队满的标志问题：rearfrontrearfronta6a5a4a3a1a276543210a6a5a4a3a1a2a8a776543210(a)(b)队列变为满，队头和队尾指针也相等。解决队列变满方法：假设队列只剩下一个单元时认为队满。顺序队列类定义及运算实现typedef

int

ElemType; constintMAXSIZE=4;classSqueue{private:

ElemType

data[MAXSIZE];

int

front,rear;public:

Squeue(){front=-1;rear=-1;} ~Squeue(){};

int

Empty(){if(front==rear)return1;elsereturn0;}voidDisplay(); voidEnQueue(ElemTypex);

ElemType

DelQueue();

ElemType

GetFront();};①初始化顺序队列：使用构造函数实现Squeue

::

Squeue(){front=-1;rear=-1;}③入队：voidSqueue::EnQueue(ElemTypex){if((rear+1)%MAXSIZE==front)cout<<“队满"<<endl;else{rear=(rear+1)%MAXSIZE;data[rear]=x;}}

②判断是否空队列：int

Squeue

::

Empty(){if(front==rear)return1;elsereturn0;}④出队：ElemType

Squeue::DelQueue(){ if(Empty()){cout<<“对空"<<endl;exit(0);}else{front=(front+1)%MAXSIZE;returndata[front];}}⑤获取对头元素：ElemType

Squeue::GetFront(){if(Empty()){cout<<"对空"<<endl;exit(0);}elsereturndata[(front+1)%MAXSIZE];}⑥输出队列的所有元素：voidSqueue::Display(){

inti; if(Empty()){cout<<"对空

"<<endl;return;}

for(i=(front+1)%MAXSIZE;

i!=(rear+1)%MAXSIZE;

i=(i+1)%MAXSIZE)

cout<<setw(6)<<data[i];

cout<<endl;}

在用链式存储结构表示队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。3队列的链式存储队列的顺序存储结构如下图所示：^frontrearstruct

quenode{ElemTypedata;

quenode*next; 域

};

链式队列类定义及运算实现classSqueue{private:

quenode*front,*rear;public:

Squeue(){front=newquenode;rear=front;} ~Squeue(){deletefront;}

int

Empty(){if(front==rear)return1;elsereturn0;}voidDisplay(); voidEnQueue(ElemTypex);

ElemType

DelQueue();

ElemType

GetFront();};①初始化链式队列：使用构造函数实现Squeue

::

Squeue(){front=newquenode;

rear=front;

}③入队：voidSqueue::EnQueue(ElemTypex){

quenode*s=newquenode;s->data=x;s->next=NULL;

rear->next=s；rear=s;}

②判断是否空队列：int

Squeue

::

Empty(){if(front==rear)