数据结构(清华大学课件)-清华大学

第一章1.1数据结构讨论的范畴1.2与数据结构相关的概念1.3算法和算法的量度软件开发的过程:系统分析系统实现系统维护系统设计系统设计确定系统所要达到的目标确定实现方案并生成系统实地安装调试系统修整完善NiklausWirth

Algorithm

+DataStructures=Programs程序设计:算法:

数据结构:

为计算机处理问题编制一组指令集

处理问题的策略问题的数学模型例如:鸡兔同笼问题二元一次代数方程组结构静力分析问题全球天气预报高次线性代数方程组球面坐标系下的环流模式方程非数值计算的程序设计问题例一求一组(n个)整数中的最大值例二交叉路口的交通管制问题例三煤气管道的铺设问题例四数据库中表格管理问题概括地说，

数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。一、基本概念和术语二、数据结构三、数据类型和抽象数据类型

所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合。数据是计算机操作的对象的总称。

是计算机处理的信息的某种特定的符号表示形式。

是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。数据元素例如，整数“5”,字符“N”等。

----是不可分割的“原子”它是数据结构中讨论的最小单位。又如,描述一个学生的数据元素由多个款项构成，其中每个款项称为一个“数据项”。称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项关键字能识别一个或几个数据元素的数据项。若能起唯一识别作用，则被称为“主”关键字，否则称为“次”关键字。数据对象具有相同特性的数据元素的集合。如:整数、实数等。数据结构带结构的数据元素的集合有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系例如，可用三个

4位的十进制数表示一个含

12位数的“长整数”。3214,6587,9345

─

a1(3214),a2(6587),a3(9345)对长整数进行运算的程序中的操作对象是一个含三个数据元素{a1,a2,a3}的集合，且三者之间存在下列

“次序”关系:

{a1,a2、a2,a3}

。又如，在2行3列的二维数组中六个元素

{a1,a2,a3,a4,a5,a6}之间存在着两个关系:“行”的次序关系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}“列”的次序关系:a1a2a3a4a5a6

在含

6个数据元素{a1,a2,a3,a4,a5,a6}的集合上存在如下的次序关系:{<ai,ai+1>|i=1,2,3,4,5}

“数据结构”

是相互之间存在着某种逻辑关系的数据元素的集合。可见，不同的“关系”构成不同的“结构”则构成“一维数组”

。可用如下的数据结构描述“班集体”:{班主任，班长1，班长2，舍长1，……，舍长p,

学生1，学生2，……，学生n}{<班主任，班长1>，<班主任，班长2>，<班长1，舍长1>，

……，<班长2，舍长p>,<舍长1，学生1>，

<舍长1，学生2>，……，<舍长p，学生n>}班主任班长1班长2舍长1舍长k舍长k+1舍长p学生1学生2学生3学生4学生n-3学生n-2学生n-1学生n…………数据结构的形式定义描述为:数据结构是一个二元组

Data_Structures=

(D,S)其中:D

是数据元素的有限集，

S

是D上关系的有限集。从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构包括“逻辑结构”

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

是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;物理结构

是逻辑结构在计算机中的表示和实现，故又称“存储结构”。存储结构是逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2

A=(101)8=(001000001)2“关系”的两种映象方法：（表示x,y的方法）顺序映象以x和y之间相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间相差一个预设常量C，而C是一个隐含值，存储结构中只包含数据元素本身的信息

xy链式映象以附加信息(指针)表示后继关系需要用一个和x绑定在一起的附加信息(指针)指示y的存储位置yx以“由数据元素x的存储映象和附加的指针合成的结点”表示数据元素。存储结构的描述方法随编程环境的不同而不同，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。

typedef

int

Long_int[3]例如，当以“顺序映象”表示长整数时，可定义为:定义“日期”为:

typedef

struct{

inty;//年号Year

intm;//月号Month

intd;//日号Day}

DateType;//日期类型定义“学生”为:

typedef

struct{charid[8];//学号

charname[16];//姓名

charsex;//性别‘M/F’:男/女

DateType

bdate;//出生日期}Student;//学生类型何谓“数据类型”？在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C++

语言中的基本数据类型有:逻辑型

bool、字符型

char、整型

int

和实型(浮点型

float和双精度型

double)

数据类型是一个“值”的集合和定义在此集合上的“一组操作”的总称。对程序员而言，各种语言中的整数类型都是一样的，因为它们的数学特性相同。从这个意义上可称“整数”是一个抽象数据类型。抽象数据类型和数据类型的实质相同，范畴更广，不局限于语言中的数据类型。抽象数据类型

(AbstractDataType

简称ADT)

是指一个数学模型以及定义在该模型上的一组操作。通常称语言中已经实现的数据类型为固有数据类型。抽象数据类型有两个重要特征:“数据抽象”和“数据封装”数据抽象数据封装

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节抽象数据类型的描述方法ADT=（D，S，P）其中:D

是数据对象，

S

是D上的关系集，

P

是对D的基本操作集。

数据对象是特性相同的数据元素的集合，是数据的一个子集。例如,抽象数据类型“复数”的定义:R1＝{<e1,e2>|e1是复数的实数部分,

|e2

是复数的虚数部分}ADTComplex{数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：基本操作：

AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数Z已存在。操作结果：用realPart

返回复数Z的实部值。

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart

返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。

}ADTComplex……#include<iostream.h>#include"complex.h"voidmain(){

}……complexz1,z2,z3,z4,z;floatRealPart,ImagPart;InitComplex(z1,8.0,6.0);InitComplex(z2,4.0,3.0);Add(z1,z2,z3);Multiply(z1,z2,z4);if(Division(z4,z3,z)){

GetReal(z,RealPart);

GetImag(z,ImagPart);}//ifADT

抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉}ADT

抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉

赋值参数

只为操作提供输入值；引用参数

以&打头，除可提供输入值外，还将返回操作结果。初始条件

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

说明在操作正常完成之后，数据结构的变化状况和应返回的结果。初始条件可以为空，并可省略。抽象数据类型的表示和实现

抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。例如，对之前定义的复数类型typedef

struct{

float

realpart；

float

imagpart；}complex；//-----存储结构的定义//-----基本操作的函数原型说明void

Assign(complex&Z,

float

realval,float

imagval)；//

构造复数Z,其实部和虚部分别被赋以参数//realval

和imagval

的值float

GetReal(cpmplexZ)；

//返回复数Z的实部值float

Getimag(cpmplexZ)；

//返回复数Z的虚部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回两个复数z1,z2的和……//-----基本操作的实现voidadd(complexz1,complexz2,complex&sum){

//以sum返回两个复数z1,z2的和

sum.realpart=z1.realpart+z2.realpart;

sum.imagpart=z1.imagpart+z2.imagpart;}

……一、算法的定义二、算法设计的原则三、算法效率的衡量方法和准则四、算法的存储空间需求是为了解决某类问题而规定的一个有限长的操作序列。3．可行性一个算法必须满足以下五个重要特性：算法1．有穷性2．确定性5．有输出4．有输入有穷性

对于任意一组合法输入值，在执行有穷步骤之后一定能结束。算法中的每个步骤都能在有限时间内完成。确定性

对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。可行性

算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。有输入

作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。有输出

它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。设计算法时，通常应考虑达到以下目标：1．正确性2.

可读性3．健壮性4．高效率与低存储量需求正确性

首先，算法应当满足以特定的“规格说明”方式给出的需求。

其次，对算法是否“正确”的理解可以有以下四个层次：a．不含语法错误；b．对于某几组输入数据能够得出满足要求的结果；

c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第

c层意义的正确性作为衡量一个算法是否合格的标准。

d．程序对于一切合法的输入数据都能得出满足要求的结果；可读性

算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；健壮性

当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。高效率与低存储量需求存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。效率指的是算法执行时间；通常有两种衡量算法效率的方法:事后统计法事前分析估算法缺点：1.必须执行程序

2.

其它因素掩盖算法本质优点：可以预先比较各种算法，以便均衡利弊从中选优。和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度算法选用的策略问题的规模

一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。

假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))称

T(n)

为算法的(渐近)时间复杂度如何估算算法的时间复杂度？算法=控制结构+原操作（固有数据类型的操作）算法的执行时间

=∑(原操作(i)的执行次数×原操作(i)的执行时间)

算法的执行时间

与

原操作执行次数之和

成正比

从算法中选取一种对于所研究的问题来说是

基本操作

的原操作，以该基本操作

在算法中重复执行的次数

作为算法运行时间的衡量准则。“基本操作”指的是，该操作重复执行次数和算法的运行时间成正比。例一两个矩阵相乘voidmult(inta[],intb[],int&c[]){//以二维数组存储矩阵元素，c为a和b的乘积

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

for(j=1;j<=n;++j)

{c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作时间复杂度:

O(n3)forforfor*

void

select_sort(int&a[],intn){

//将a中整数序列重新排列成自小至大有序的整数序列。

}//select_sortfor(i=0;i<n-1;++i){

}例二选择排序基本操作:

比较(数据元素)操作时间复杂度:

O(n2)j=i;//

选择第i个最小元素for

(k=i+1;k<n;++k)

if

(a[k]<a[j]

)

j=k;if(j!=i)a[j]←→a[i];例三起泡排序void

bubble_sort(int&a[],intn){

//将a中整数序列重新排列成自小至大有序的整数序列。for(i=n-1,change=TRUE;i>1&&change;--i)}//bubble_sort基本操作:

赋值操作时间复杂度:

O(n2){change=FALSE;//change为元素进行交换标志

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{a[j]←→a[j+1];change=TRUE;}}//一趟起泡←→forfor算法的空间复杂度定义为:

表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。S(n)=O(g(n))算法的存储量包括:1．输入数据所占空间2．程序本身所占空间；3．辅助变量所占空间。若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是个常量，则称此算法为原地工作。

若所需存储量依赖于特定的输入，则通常按最坏情况考虑。1.

熟悉各名词、术语的含义，掌握基本概念。2.

理解算法五个要素的确切含义。本章学习要点3.掌握计算语句频度和估算算法时间复杂度的方法。提几点要求:1.课前预习，了解本堂课内容;2.课后复习，在理解教学内容的基础上做练习题;3.独立完成作业;4.勤答疑，多问“为什么”。(n-1)+(n-2)+……+1=n(n-1)/2=n2/2+n/2312597132357912357519732159793915297372715352513231297532第二章

线性结构的基本特征:1．集合中必存在唯一的一个“第一元素”2．集合中必存在唯一的一个“最后元素”3．除最后元素在外，均有唯一的后继4．除第一元素之外，均有唯一的前驱线性结构是一个数据元素的有序（次序）集2.1

线性表的类型定义2.3线性表类型的实现

链式映象2.4一元多项式的表示2.2线性表类型的实现

顺序映象ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

{称

n

为线性表的表长;

称

n=0

时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),

称i为ai

在线性表中的位序。}

基本操作：

结构初始化操作结构销毁操作

引用型操作

加工型操作

}ADTList

{结构初始化}

InitList(&L)

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

CreateList(&L,A[],n)

初始条件：A[]中存在线性表的n个数据元素。操作结果：构造一个含n个数据元素的线性表L。

{销毁结构}

DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。

ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit()){引用型操作}

ListEmpty(L)（线性表判空）初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。ListLength(L)（求线性表的长度）初始条件：操作结果：线性表L已存在。返回线性表L

中元素个数。

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无定义。

GetElem(L,i,&e)（求线性表中某个元素）初始条件：操作结果：线性表L已存在以e

带回L

中第i

个数据元素值。LocateElem(L,e,compare())（定位函数）初始条件：操作结果：线性表L已存在,compare()为判定函数。返回L中第1个与e满足关系

compare()的元素的位序，若不存在这样的元素，则返回

0。且1≤i≤LengthList(L)。

ListTraverse(L,visit())（遍历线性表）初始条件：操作结果：线性表L已存在,visit()为数据元素的访问函数。依次对L

的每个数据元素调用函数visit()，一旦visit()失败，则遍历操作失败。ClearList(&L)

(线性表置空)ListInsert(&L,i,e) (插入数据元素)PutElem(&L,i,&e) (改变数据元素的值)ListDelete(&L,i,&e) (删除数据元素){加工型操作}

ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为空表。PutElem(&L,i,e)初始条件：操作结果：L中第i个元素赋值和e相同。线性表L已存在，且1≤i≤LengthList(L)。

ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在在L的第i个元素之前插入新的元素e,L的长度增1。

ListDelete(&L,i,e)初始条件：操作结果：线性表L已存在删除L中第i个元素，并以e带回其值,L的长度减1。,1≤i≤LengthList(L)+1。,1≤i≤LengthList(L)。例2-1

假设有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。

现要求一个新的集合A＝A∪B。即:需对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．取得线性表LB中一个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。ListDelete(Lb,1,e);

LocateElem(LA,e,equal());

ListInsert(LA,n+1,e);(n表示线性表LA当前长度)操作步骤：ListDelete(Lb,1,e);

//删除Lb中第1个数据元素赋给eif(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和

e相同的数据元素，则插入之La_len=ListLength(La);

//求线性表La的长度while(!ListEmpty(Lb)){}//while}//unionvoidunion(List&La,ListLb){

//将线性表Lb中所有在线性表La中不存在的数据元素

//插入到线性表La中例2-2

已知一个“非纯集合”B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。若仍然以线性表表示集合，则算法的策略应该和例一基本相同,差别是什么？1.集合A的初态是“空集”2.不破坏集合Bvoidpurge(List&La,ListLb){

La_len=0;Lb_len=ListLength(Lb);}//pugre

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e

if(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和

e相同的数据元素，则插入之for(i=1;i<=Lb_len;i++){}//forInitList(La);//构造(空的)线性表LA例2-3判别两个集合是否相等。集合相等的条件是:两者所含元素个数相同，且所有对应元素都相等。仍以线性表表示集合，并假设这两个集合是“纯集合”。则算法的策略为:在两个线性表的长度相等的前提下，只要判别一个表中的元素在另一个表中都存在即可。bool

isEqual(ListLA,ListLB){

//若线性表LA和LB不仅长度相等，且所含数据

//元素也相同，则返回TRUE,否则返回FALSE

}//isEqual

La_len=Listlength(LA);Lb_len=Listlength(LB);if(La_len!=Lb_len)

returnFALSE;//两表的长度不等else{

}

………while(i<=La_len

&&found){

}//whilereturnfound;

GetElem(LA,i,e);//取得LA中一个元素if(LocateElem(LB,e,equal())i++;//依次处理下一个elsefound=FALSE;

//LB中没有和该元素相同的元素i=1;found=TRUE;一、顺序表

---线性表的顺序映象二、顺序表中基本操作的实现三、顺序表的其它操作举例最简单的一种顺序映象方法是：

令y的存储位置和x的存储位置相邻。顺序映象——

以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>

用一组地址连续的存储单元

依次存放线性表中的数据元素线性表的起始地址，称作线性表的基地址

a1a2

…ai-1

ai

…an以“存储位置相邻”表示有序对<ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置

LOC(ai)=

LOC(a1)

+(i-1)×C基地址顺序表的C语言描述//存储结构typedef

struct{}SqList;//俗称顺序表ElemType

*elem;//存储空间基址int

length;//当前长度int

listsize;//当前分配的存储容量

//(以sizeof(ElemType)为单位)//基本操作接口void

purge(SqList

&La,SqListLb){//构造顺序表La，使其只包含Lb中所有值不

//相同的数据元素,算法不改变顺序表Lb

boolb;

int

Lb_len=Listlength(Lb);//求线性表Lb的长度

InitList(La,Lb_len);//创建一个空的线性表La

int

La_len=0;

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

{

//依次处理Lb中每个元素}//for}//purge

b=GetElem(Lb,i,e);

//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()){++La_len;b=ListInsert(La,La_len,e);//

当

La中不存在和

e值相同的数据

//元素时进行插入

}线性表的基本操作在顺序表中的实现InitList(&L)//结构初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//删除元素Status

InitList(SqList&L,int

maxsize){//构造一个最大容量为maxsize

的顺序表

}//InitList算法时间复杂度：O(1)L.elem=newElemType[maxsize];

//

为顺序表分配大小为maxsize

的数组空间if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=maxsize;returnOK;例如：顺序表23754138546217L.elemL.length=7L.listsize假设e=38pppppi=12341850p可见，基本操作是，将顺序表中的元素逐个和给定值e相比较。

int

LocateElem(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在顺序表中查询第一个满足判定条件的数据元素，

//若存在，则返回它的位序，否则返回0}//LocateElem

O(ListLength(L))if(i<=L.length)returni;

elsereturn0;算法的时间复杂度为：i=1;//i的初值为第1元素的位序p=L.elem;

//p的初值为第1元素的存储位置while(i<=L.length&&!(*compare)(*p++,e))++i;(*compare)(*p++,e)//找到满足条件的元素//没有找到满足条件的元素线性表操作

ListInsert(&L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？

(a1,…,ai-1,ai,…,an)改变为a1a2

…ai-1

ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的长度增加(a1,…,ai-1,e,ai,…,an)

Status

ListInsert(SqList

&L,inti,ElemTypee){//

在顺序表L的第i个元素之前插入新的元素e,

//i的合法范围为1≤i≤L.length+1}//ListInsert

算法时间复杂度为:for(j=L.length-1;j>=pos-1;--j)L.elem[j+1]=L.elem[j];

//插入位置及之后的元素右移L.elem[pos-1]=e;//插入e++L.length;//表长增1returnTRUE;O(ListLength(L))……元素右移考虑移动元素的平均情况:

假设在第

i个元素之前插入的概率为pi

，

则在长度为n

的线性表中插入一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：if(L.length>=L.listsize)returnOVERFLOW;//当前存储空间已满

if(i<1||i>L.length+1)

returnERROR;

//

插入位置不合法2118307542568721183075例如：ListInsert(L,5,66)

L.length-10j87564266for(j=L.length-1;j>=pos-1;--j)L.elem[j+1]=L.elem[j];4jj线性表操作

ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？

(a1,…,ai-1,ai,ai+1,…,an)改变为ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a1a2

…ai-1

ai

ai+1

…ana1a2

…ai-1

(a1,…,ai-1,ai+1,…,an)Status

ListDelete(SqList

&L,inti,ElemType

&e){}//ListDelete算法时间复杂度为:

O(ListLength(L))for(j=pos;j<L.length;++j)L.elem[j-1]=L.elem[j];//被删除元素之后的元素左移--L.length;//表长减1return

TRUE;if((i<1)||(i>L.length))returnERROR;

//删除位置不合法元素左移考虑移动元素的平均情况:

假设删除第

i个元素的概率为qi,则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：211830754256876321183075L.length-10j8756for(j=pos;j<L.length;++j)L.elem[j-1]=L.elem[j];例如：ListDelete(L,5,e)635jj试设计一个算法，用尽可能少的辅助空间将顺序表中前m个元素和后n个元素进行互换，即将线性表

(a1,a2,…,am,b1,b2,…,bn)改变成

(b1,b2,…,bn,a1,a2,…,am)。

从

b1开始，从原地删除之后插入到a1之前直至bn。例2-4算法1

进行三次“逆转顺序表”的操作。算法2abcdefg123451gggfffeeedddcccbbbaaa23123jijijiabcdefg12345abcdeeffg123445cbga251voidinvert(ElemType

&R[]，ints，

intt)//本算法将数组R中下标自s到t的元素逆置，

//即将（Rs,Rs+1,…,Rt-1,Rt

）

//改变为（Rt,Rt-1,…,Rs+1,Rs

）

voidexchange(SqList

&A;intm){

//本算法实现顺序表中前m个元素

//和后n个元素的互换

n=A.length–m;invert(A.elem,0,A.length);invert(A.elem,0,n-1);invert(A.elem,n,m+n-1);}//exchange

算法的时间复杂度为:O(m+n)voidexchange(SqList

&A,intm){//实现顺序表A中前m个元素和后n个元素互换}exchangefor(i=0;j=m;

j<A.length;i++,j++){}x=A.elem[j];for(k=j;k>i;k--)

A.elem[j]=A.elem[j-1];A.elem[i]=x;算法的时间复杂度为:O(mn)试编写算法，删除顺序表中“多余”的数据元素。例2-5

从

a1开始，检查在它之后的数据元素，如有和它相等的，则从表中删除之。算法1

回顾例2-2的算法，试按“构造”一个新的顺序表的思想来进行，设想这两个表“共享”一个存储空间。算法2525334257543ij3342557437543jj3i4L.length-1L.length-1L.length-1L.length-1j525334257543ki523iiiiiiiiiiikkkk47kivoidpurge(SqList&L){//删除顺序表L中冗余元素

for(i=0;i<L.length-1;++i){//顺序考察表中每个元素

j=i+1;while(j<L.length)}//for}//purgeif(L.elem[j]!=L.elem[i])++j;else

{

for(k=j+1;k<L.length;++k)L.elem[k-1]=L.elem[k];//移动元素

--L.length;//修改表长}//else算法的时间复杂度为:O(L.length3)voidpurge(SqList&L){//删除顺序表L中的冗余元素

k=-1;//k指示新表的表尾

for(i=0;i<L.length;++i)

{

//顺序考察表中每个元素

}//forL.length=k+1;//修改表长}//purge算法的时间复杂度为:O(L.length2)j=0;while(j<=k&&L.elem[j]!=L.elem[i])++j;

//

在新表中查询是否存在

//和L.elem[i]相同的元素if(k==-1||j>k)//k=-1

表明当前考察的是第一个元素

L.elem[++k]=L.elem[i];一、单链表

---线性表的链式映象二、单链表中基本操作的实现三、单链表的其它操作举例四、其它形式的链表结构

用一组地址任意的存储单元存放线性表中的数据元素。一、单链表以元素(数据元素的映象)

+指针(指示后继元素存储位置)=结点

(表示数据元素或数据元素的映象)以“结点的序列”表示线性表

称作单链表

以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针头结点

a1a2…...an^头指针头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空

//存储结构Typedef

struct

LNode

{

ElemType

data;

//

数据域

struct

LNode

*next;

//

指针域}

*LinkList;

单链表的C语言描述LinkListL；//L为单链表的头指针二、单链表操作的实现GetElem(L,i,e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,e)//删除数据元素ClearList(&L)//重置线性表为空表CreateList(&L,n)

//生成含n个数据元素的链表L

线性表的操作

GetElem(L,i,&e)在单链表中的实现:211830754256∧pppj123

因此，查找第i个数据元素的基本操作为：移动指针，比较j和i

单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。

令指针p

始终指向线性表中第j

个数据元素

Status

GetElem(LinkListL,inti,ElemType

&e){//L是带头结点的链表的头指针，以e返回第

i个元素}//GetElem算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，j为计数器while(j<i){p=p->next;++j;}

//

顺指针向后查找，直到p指向第i个元素

e=p->data;//取得第i个元素returnOK;

p&&//

或p为空if(!p||j>i)

returnERROR;//第i个元素不存在ai-1

线性表的操作

ListInsert(&L,i,e)

在单链表中的实现：

有序对<ai-1,ai>

改变为<ai-1,e>和<e,ai>eaiai-1

因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。

Status

ListInsert(LinkListL,inti,ElemTypee){

//L为带头结点的单链表的头指针，本算法

//在链表中第i个结点之前插入新的元素e

}//LinstInsert算法的时间复杂度为:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}//寻找第i-1个结点if(!p||j>i-1)

returnERROR;//

i大于表长或者小于1s=new

LNode;//生成新结点if(s==NULL)returnERROR;s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>ai-1aiai+1ai-1

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;delete(q);pq

Status

ListDelete(LinkListL,inti,ElemType

&e){

//删除以L为头指针(带头结点)的单链表中第i个结点

}//ListDelete算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i个结点，并令p指向其前趋q=p->next;p->next=q->next;

//删除并释放结点e=q->data;

delete(q);returnOK;if(!(p->next)||j>i-1)

returnERROR;//删除位置不合理操作ClearList(&L)在链表中的实现:void

ClearList(&L){//将单链表重新置为一个空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListdelete(p);算法时间复杂度：O(ListLength(L))如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。例如：逆位序输入n个数据元素的值，建立带头结点的单链表。操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，

建立结点并插入；四、依次类推，直至输入a1为止。L∧∧epdpcpbpap∧p=new

LNode;scanf(&p->data);//输入元素值p->next=L->next;L->next=p;//插入L=new

LNode;L->next=NULL;

//先建立一个带头结点的单链表void

CreateList(LinkList

&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=new

LNode;L->next=NULL;

//先建立一个带头结点的单链表for(i=n;i>0;--i){

p=new

LNode;

scanf(&p->data);//输入元素值

p->next=L->next;L->next=p;

//插入}试设计算法，将单链表中前m个结点和后n个结点进行互换，即将线性表(a1,a2,…,am,b1,b2,…,bn)改变成(b1,b2,…,bn,a1,a2,…,am)。例2-6算法设计:

将(b1,b2,…,bn)从链表的当前位置上删除之后再插入a1到之前，并将am设为表尾。a1a2amb1b2bnL……∧tahbtb∧∧ta->next=NULL;tb->next=L->next;L->next=hb;voidexchange(SLink

&L,intm){//互换链表中前m个和后n个结点

ta=L;i=0;

while(ta

&&i<m){//查询结点am

ta=ta->next;i++;

}//while}//exchange算法的时间复杂度为:O(ListLength(L))if(ta

&&

ta->next){//m<表长

hb=ta->next;tb=hb;while(tb->next)tb=tb->next;//查询表尾bn

}//if修改指针例2-7试编写算法，删除单链表中“多余”的数据元素。算法一对链表中当前考察的每个元素，删除它之后的“值相同”的结点;算法二将新表中尚未存在的“值相同”的结点插入到新的链表中。voidpurge(SLink

&L){//删除链表中的“冗余”元素

p=L->next;

while(p){//p指向当前被考察的结点

q=p;

while(q->next)//考察q所指后继结点

if(q->next->data<>p->data)q=q->next;

else//修改指针并释放结点空间

{

s=

q->next;q->next=s->next;deletes;} p=p->next;

}//whilep}//purge算法时间复杂度:O(ListLength2(n))voidpurge(SLink

&L){

//删除链表中“冗余”元素

p=L->next;L->next=NULL;//设新表为空表

while(p){//p指向当前被考察的结点

q=L->next;succ=p->next;//指向*p的后继

while(q&&q->data<>p->data) q=q->next;//查询是否已存在值相同的结点

if(q)deletep;

else//插入新表(倒插)，修改指针

{p->next=L->next;L->next=p;}

p=succ; //继续考察下一个结点

}//whilep}//purge算法时间复杂度:O(ListLength2(n))

最后一个结点的指针域的指针又指回第一个结点的链表

循环链表

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。

a1a2…...an

有时还可以将头指针设成指向尾结点。voidexchange(SLink

&L,intm){//互换链表中前m个和后n个结点

ta=L;i=0;

while(ta

&&i<m){//查询结点am

ta=ta->next;i++;

}//while

if(ta

&&

ta->next){//m<表长

hb