数据结构与算法分析课件

数据结构与算法分析

第一章导论1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的量度1.4算法的描述工具1.1数据结构讨论的范畴

Algorithm+DataStructures=Programs程序设计:计算机处理问题编制一组指令集

算法:处理问题的策略数据结构:问题的数学模型

Object+Message=Programs数学模型到类对象的建模Algorithm+DataStructures=ProgramsObject+Message=ProgramsObject=InstanceoftheClassClass=Properties+Methods1.2

基本概念一、数据与数据结构二、数据类型三、抽象数据类型ADT四、Java的接口与ADT一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”数据元素:数据结构中讨论的基本单位数据结构：带结构的数据元素的集合

假设用三个

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

12位数的十进制数。例如:3214,6587,9345─a1(3214),a2(6587),a3(9345)则在数据元素

a1、a2

和

a3

之间存在着“次序”关系：

a1,a2

、

a2,a3

3214，6587，9345

a1

a2

a3

6587，3214，9345

a2

a1

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>}

a1a3a5a2a4a6

a1a2a3a4a5a6

数据结构：带结构的数据元素的集合数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构的形式定义为:数据结构是一个二元组

Data_Structures=(D,S)其中:D是数据元素的有限集，

S是D上关系的有限集。数据的存储结构

——

逻辑结构在存储器中的映象“数据元素”的映象

？“关系”的映象

？关系的映象方法：（表示

x,y

的方法）顺序映象

以相对的存储位置表示后继关系

例如:令y

的存储位置和x

的存储位置之间差一个常量C

而C是一个隐含值，整个存储结构中只含数据元素本身的信息

xyC链式映象以附加信息(指针，或引用)表示后继关系

需要用一个和x

在一起的附加信息指示y

的存储位置y

xclassEmployeeCell{Objectemployee;EmployeeCellnext;publicEmployeeCell(Objecto){employee=o;}}structEmployeeCell{employeecell;EmployeeCell*next;};

C语言的指针对应Java语言中的引用二、数据类型

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

数据类型是一个值的集合和定义在此集合上的一组操作的总称。三、抽象数据类型

(Abstract

Data

Type

简称ADT)

是指一个数学模型以及定义在此数学模型上的一组操作ADT抽象数据类型名

{

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

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

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

ADT

抽象数据类型名

其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名（参数表）

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

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

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。抽象数据类型的表示和实现

抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现,具体是：

非面向对象的语言工具抽象数据类型定制为语言的数据类型数据对象数据类型

数据关系

变量关系（指针、数组元素）

基本操作

一组相互依存的函数

抽象数据类型通过类的设计可直接构造出来：面向对象的语言工具数据对象属性（数据成员）

数据关系

变量关系（引用、数组元素）

基本操作

方法（成员函数）

四、Java的接口与ADTADT在

Java中表现为由抽象的方法组成的接口Interface。1.3算法和算法的衡量

算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下几个重要特性：一算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.

可读性3．健壮性4．高效率与低存储量需求5．可重性考虑二、算法效率的衡量方法和准则通常有两种衡量算法效率的方法:

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

2．其它因素掩盖算法本质

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

假如，随着问题规模

n

的增长，算法执行时间的增长率和

f(n)

的增长率相同，则可记作：T(n)=O(f(n))称T(n)

为算法的(渐近)时间复杂度

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

基本操作

的原操作，以该基本操作

在算法中重复执行的次数

作为算法运行时间的衡量准则。

算法中重复执行的次数也称为频度(frequency)F(n)例一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];}基本操作:

乘法操作时间复杂度:

O(n3)例二

voidselect_sort(inta[],intn){//

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

for(i=0;i<n-1;++i){j=i;for(k=i+1;k<n;++k)if(a[k]

<

a[j])j=k;if(j!=i)a[j]←→a[i];}}//select_sort

T(n)与f(n)有相同的数量级，但f(n)更清晰揭示了算法基于时间优劣的本质趋势算法的(渐近)时间复杂度本质含义三、算法的存储空间需求算法的空间复杂度

表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。S(n)=O(g(n))1.4算法的描述工具

使用C/C++语言的核心子集[3]

使用Java(C#)语言ADT的程序级实现的技术要求：point.hpointApp.cpp#include“point.h”point.javapointApp.javaimportpoint;packagepoint;ADTPoint{}……DesignImplementationApplicationsTestpublicstaticvoidmain(){….}主

要

参

考

书：[1]《数据结构（C语言版）》（含CD）

2002.9第一版

严蔚敏

吴伟民

清华大学出版社[2]《数据结构习题集（C语言版）》

严蔚敏

吴伟民

清华大学出版

[3]《数据结构与及应用算法教程》（含CD）

2002.8第三次印刷

严蔚敏

陈文博

清华大学出版社

[4]《算法设计与分析》

王晓东

清华大学出版社2.1线性表的类型定义2.3线性表类型的实现

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

顺序映象2.1线性表的类型定义在实际的问题中:(北京,上海,天津,重庆

)(清华,北大,浙大,…北工大,….)(286,386,486,P-MMX,PII,PIII,P4)

一般的:(a1,a2,…ai,…an)F4,抽象数据类型线性表的定义如下：ADT

List{

数据对象：D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}

{称

n

为线性表的表长;

称

n=0

时的线性表为空表。}数据关系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为

(a1，a2,...，ai，...，an),

称

i为

ai在线性表中的位序。}

基本操作：结构初始化操作结构销毁操作引用型操作加工型操作

}ADTList

InitList(&L)操作结果：构造一个空的线性表L。初始化操作在Java中初始化由构造方法List()取代

结构销毁操作DestroyList(&L)初始条件：操作结果：线性表L

已存在。销毁线性表L。在Java中有自动垃圾搜集机制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())引用型操作:public

interface

LinearList{

publicbooleanisEmpty();

publicintsize();

publicObjectget(intindex);

publicintindexOf(ObjecttheElement);

publicObjectremove(intindex);

publicvoidadd(intindex,ObjecttheElement);

publicStringtoString();}Java通过接口在实现的层面提供对ADT直接的支持

已知一个非纯集合

B，试构造一个纯集合

A，使

A中只包含

B

中所有值各不相同的数据元素。

仍选用线性表表示集合例集合

B集合

A从集合B

取出物件放入集合A要求集合A中同样物件不能有两件以上因此，算法的策略应该和例2-1相同voidunion(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);}//union

GetElem(Lb,i,e);//取Lb中第

i个数据元素赋给

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

)

ListInsert(La,++La_len,e);

//La中不存在和

e相同的数据元素，则插入之for(i=1;i<=Lb_len;i++){}InitList(La);

//构造(空的)线性表LApurge2.2线性表类型的实现

顺序映象最简单的一种顺序映象方法是：

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

以

x的存储位置和

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

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

依次存放线性表中的数据元素

a1a2

…ai-1ai

…an线性表的起始地址，称作线性表的基地址顺序映像的

C语言描述typedefstruct{

}SqList;//俗称

顺序表#define

LIST_INIT_SIZE80

//线性表存储空间的初始分配量#defineLISTINCREMENT10

//线性表存储空间的分配增量ElemType*elem;//存储空间基址int

length;//当前长度int

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

//(以ElemType为单位)

考虑移动元素的平均情况:

假设在第

i

个元素之前插入的概率为

，

则在长度为n

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

若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：考虑移动元素的平均情况:

假设删除第

i

个元素的概率为

,则在长度为n

的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：

使用实用类Vector的变长功能实现ListVector

element;3.1栈的类型定义ADTStack

{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定an

端为栈顶，a1端为栈底。

基本操作：

}ADTStackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)

Push(&S,e)

Pop(&S,&e)StackTravers(S,visit())Astackisacontainerofobjectsthatareinsertedandremovedaccordingtothelast-in-first-out(LIFO)principle.

例一、

数制转换

算法基于原理：

N=(Ndivd)×d+Nmodd

3.2栈的应用举例

例如：（1348)10=(2504)8

，其运算过程如下：

NNdiv8Nmod8

13481684

168210

2125

202计算顺序输出顺序voidconversion(){InitStack(S);

cin>>N;

while(N){

Push(S,N%8);N=N/8;

}

while(!StackEmpty(S)){

Pop(S,e);

cout<<e;

}}//conversion

在实际问题中全进全退是特殊情况，一般进栈和退栈往往是交错进行的。例二、

括号匹配的检验假设在表达式中

（［］（））或［（［

］［

］）］等为正确的格式，

［（

］）或（［（

））或

(()])均为不正确的格式。则

检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;例如：考虑下列括号序列：

[([][])]12345678到来的是“不速之客”;直到结束，也没有到来所“期待”的括弧;算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余Statusmatching(string&exp){

intstate=1;

while(i<=Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOT

StackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}

else{state=0;}

break;}

case”]”:...}

if(StackEmpty(S)&&state)returnOK;…...

进退栈的次序是由问题决定的例三、

迷宫求解通常用的是“试探与回溯求解”的方法求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。

删除意味着退回到搜索过的点，亦称为回溯，它以“后进先出”方式运作。（进栈）（退栈又进栈）（退栈）###########

#

###

#

###

####

######

#####

#######

####

Q###########120345789601234567891234111121121122

静态跟踪与栈的变化221

限于二元运算符的表达式定义:

表达式

::=(操作数)(运算符)(操作数)

操作数

::=

简单变量

|表达式

简单变量

::=

标识符

|无符号整数例四、

表达式求值例如:Exp=a

b

+

(7

d/e)

fExp=a

b

+

(7

d/e)

f表达式的运算规则是“算符优先法”算符优先法的规则:1.

/优先

+

2.括号优先

3.从左至右三种符号:操作数运算符界限符（

）##算符21：>><<<>>>><<<>>>>>><>>>>>><>><<<<<=

>>>>

>><<<<<

=++——

//

（

（

）

）

#

#算符优先关系表

a

b

+

(7

d/e)

f

算法思想：1.置操作数栈OPND为空，运算符栈OPTR的栈底压入#２.扫描表达式:

凡操作数进操作数栈OPND

运算符则与运算符栈OPTR的栈顶元素比优先级并作相应操作3.3 栈类型的实现

顺序栈

链栈//-----栈的顺序存储表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*elem;

inttop;

intstacksize;

}

SqStack;

类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。

StatusInitStack(SqStack&S){//构造一个空栈SS.elem=newSElemType[STACK_INIT_SIZE];

if(!S.elem)exit(“OVERFLOW”);

//存储分配失败

S.top=-1;S.stacksize=STACK_INIT_SIZE;

returnOK;}StatusPush(SqStack&S,SElemTypee){if(S.top==S.stacksize-1){//栈满，追加存储空间

icrementStacksize(S);

if(!S.elem)exit(“OVERFLOW”);

//存储分配失败

}S.top[++S.top]=e;

returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，

//用e返回其值，并返回OK；

//否则返回ERROR

if

(S.top

==

-1)

returnERROR;

e=S.elem[S.top––];

returnOK;}栈顶指针链栈∧a1an注意:链栈中指针的方向an-1…toptypedefLinklistLinkStack;InitStack_L(LinkStack&S)Push_L(LinkStack&S,SElemTypee)Pop_L(LinkStack&S,SElemType&e)//constructorspublic

ArrayStack(intinitialCapacity){

if(initialCapacity<1)

thrownewIllegalArgumentException("initialCapacitymustbe>=1");

stack=newObject[initialCapacity];

top=-1;}Java的接口与实现3.1栈的类型定义3.2栈的应用举例3.3栈类型的实现3.4队列的类型定义3.5队列类型的实现ADTQueue{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定其中a1

端为队列头，an

端为队列尾基本操作：3.4队列的类型定义}

ADTQueue队列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())3.5队列类型的实现

链队列——链式映象

循环队列——顺序映象

循环队列的使用实例

typedefstructQNode{//结点类型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;链队列——链式映象typedefstruct{//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列01234567abcQ.rearQ.frontQ.reard按循环机制使用数组空间Q.rear=(Q.rear+1)Q.front=(Q.front+1)

通过头尾指针的循环使用,顺序空间即可当循环空间来使用，称循环队。循环使用指针在技术上是由取模实现的：%

MAXQSIZE;%

MAXQSIZE;

队列的上机大作业:

离散事件模拟（银行的排队事例）请先阅读材料[1]P65~69[3]P250~2594.1串的抽象数据类型的定义如下：ADTString{

数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R＝{<ai-1,ai>|ai-1,ai

∈D,i=2,...,n}串是有限长的字符序列，由一对引号相括，如:"astring"

基本操作：

StrAssign(&T,chars)

StrCopy(&T,S)

DestroyString(&S)

StrEmpty(S)

StrCompare(S,T)

StrLength(S)

Concat(&T,S1,S2)SubString(&Sub,S,pos,len)

Index(S,T,pos)

Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)

ClearString(&S)}ADTString

对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。

gets(str)输入一个串；

puts(str)

输出一个串；

strcat(str1,str2)串联接函数；

strcpy(str1,str2)串复制函数；

strcmp(str1,str2)串比较函数；

strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：Java语言中String是最常用的类型JDK1.2String有24个方法

（还不包括重载）

构造函数就多达11个例如常用的方法：

S.charAt(i)

0<=i<=S.length-1

S.valueOf(T)whereTisanyprimitivetype

S.indexOf(T)T

is

thesubstringofabiggerstring

S.concat(T)S=S+T

OtheroperationmethodsarefoundinclassStringinjava.lang.*;在ADT抽象数据类型定义的13种操作中，

串赋值StrAssign、串复制Strcopy、

串比较StrCompare、求串长StrLength、

串联接Concat以及求子串SubString

等六种操作构成串类型的最小操作子集。

即：这些操作不可能利用其他串操作来实现，

反之，其他串操作（除串清除ClearString和串

销毁DestroyString外）可在这个最小操作子

集上实现。

在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2串的表示和实现一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示

类似于线形表的顺序存储表示法,即用一组连续的存储单元存放串的字符序列.(以‘\0’为结束标志)

例如:charstr[10];//字符串最大串长为9

一、串的定长顺序存储表示

#defineMAXSTRLEN255//用户可在255以内定义最大串长

typedef

unsignedcharSstring[MAXSTRLEN+1];//0号单元存放串的长度串的定长顺序存储表示(在系统级完成)void

concat(char

s1[],char

s2[],char

t[]){

int j=0,k=0;

while(s1[j]!='\0')t[k++]=s1[j++];j=0;

while(s2[j]!='\0')t[k++]=s2[j++];t[k]='\0';}串的拼接操作concat

typedefstruct{char*ch;

//若是非空串，则按串长分配存储区，

//否则ch为NULL

intlength;//串长度

}HString;二、串的堆分配存储表示(在系统级完成)

通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数new和delete为用户进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。

C语言中的串以一个空字符为结束符,串长是一个隐含值，Java语言中串长是一个属性。

这类串操作实现的算法为:

先为新生成的串分配一个存储空间，然后进行串值的复制。voidconcat(char*s1,char*s2,char*&t){

inti=0,j=0;

t=newchar[strlen(s1)+strlen(s2)+1];//为t分配堆空间

while((t[i]=s1[i])!='\0')i++;

while((t[i]=s2[j])!='\0'){i++;j++;}}voidmain(){char*s1="china";char*s2="beijing";char*t1;//仅说明类型而不申请空间

concat(s1,s2,t1);cout<<t1<<endl;}三、串的块链存储表示

(在用户级完成)也可用链表来存储串值，由于串的数据元素是一个字符，它只有

8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。存储密度

=数据元素所占存储位实际分配的存储位

#defineCHUNKSIZE80//可由用户定义的块大小

typedefstructChunk{//

结点结构

charch[CUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{//串的链表结构

Chunk*head,*tail;//串的头和尾指针

intcurlen;//串的当前长度

}LString;chunkheattailDATASTRUCTURES#curlen=15

这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。4.3 串的模式匹配算法INDEX(S,T,pos)初始条件：串S和T存在，T是非空串，

0≤pos≤StrLength(S)-1。操作结果：若主串S中存在和串T值相

同的子串返回它在主串S中

第pos个字符之后第一次出

现的位置;否则函数

值为0。

首先，回忆一下串匹配(查找)的定义:ij5.1数组的类型定义ADTArray{

数据对象：

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}

数据关系：

R＝{R1,R2,...,Rn}

Ri＝{<aj1,...ji,...jn

,aj1,...ji

+1,...jn

>|0

jk

bk-1,1

k

n且k

i,0

ji

bi-2,i=2,...,n}

}ADTArray基本操作:二维数组的定义:数据对象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:

R={ROW,COL}

ROW={<ai,j,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}

COL={<ai,j,ai,j+1>|0≤i≤b1-1,0≤j≤b2-2}5.2数组的顺序表示和实现

类型特点:1)只有引用型操作，没有加工型操作;2)数组是多维的结构，而存储空间是

一个一维的结构。

有两种顺序映象的方式:1)以行序为主序(低下标优先);2)以列序为主序(高下标优先);ai,jai,j例如：

称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

b2

推广到一般情况，可得到

n维数组数据元素存储位置的映象关系

称为

n维数组的映象函数。数组元素的存储位置是其下标的线性函数其中

cn=L，ci-1=bi

×ci,1<i

n。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n假设

m行

n列的矩阵含

t个非零元素，则称为稀疏因子通常认为

0.05

的矩阵为稀疏矩阵5.3稀疏矩阵的压缩存储何谓稀疏矩阵？1)尽可能少存或不存零值元素;解决问题的原则:2)尽可能减少没有实际意义的运算;3)操作方便;即:

能尽可能快地找到与

下标值(i,j)对应的元素;

能尽可能快地找到同

一行或同一列的非零值元素;随机稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑联接的顺序表三、十字链表

#defineMAXSIZE12500

typedefstruct{

inti,j;//该非零元的行下标和列下标

ElemTypee;

//该非零元的值

}

Triple;//三元组类型一、三元组顺序表typedefstruct{

Tripledata[MAXSIZE+1];

intmu,nu,tu;}TSMatrix;//稀疏矩阵类型121415-522-73136342812345原稀疏矩阵三元组表示的稀疏矩阵

三元组表示的稀疏矩阵节省了空间，便于实现矩阵运算吗？如何求转置矩阵？

首先应该确定每一列的非零元个数,然后求每一列第一非零元在三元组中的位置。

col12345Num[col]12011Cpot[col]12445

cpot[1]=1;for(col=2;col<=M.nu;++col)

cpot[col]=cpot[col-1]+num[col-1];StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu)

{

for(col=1;col<=M.nu;++col)num[col]=0;

for(t=1;t<=M.tu;++t)++num[M.data[t].j];

cpot[1]=1;

for(col=2;col<=M.nu;++col)

cpot[col]=cpot[col-1]+num[col-1];

for(p=1;p<=M.tu;++p){}

}//if

returnOK;}//FastTransposeSMatrix

转置矩阵元素Col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];

分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu+M.tu)for

(col=1;col<=M.nu;++col)…

…for

(t=1;t<=M.tu;++t)…

…for(col=2;col<=M.nu;++col)……for

(p=1;p<=M.tu;++p)…

…

#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

intmu,nu,tu;}RLSMatrix;//行逻辑链接顺序表类型

修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos（各行第一非零元的位置）,其值在稀疏矩阵的初始化函数中确定。例如：给定一组下标，求矩阵的元素值ElemTypevalue(RLSMatrixM,intr,intc){

p=M.rpos[r];

while(M.data[p].i==r&&M.data[p].j<c)

p++;

if(M.data[p].i==r&&M.data[p].j==c)

returnM.data[p].e;

elsereturn0;}//value行逻辑联接的顺序表的Java设计方案讨论TripleUnitinti,j,eTripleUnit(i,j,e)TripleUnit()MatrixTripleintmu,nu,tu;TripleUnit[]elementint[]numMatrixTriple(…)addTripleUnit(…)toSring()value(..)int[]rposcreateMatrixTriple(.)三、

十字链表M.cheadM.rhead30050-100200011314522-1312^^^^^^^5.4广义表的类型定义ADTGlist{

数据对象：D＝{ei|i=1,2,..,n;n≥0;

ei∈AtomSet

或

ei∈GList,

AtomSet为某个数据对象

}

数据关系：

R＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}}ADTGlist基本操作:北京亚洲足球邀请赛（日本，韩国，中国，朝鲜）（日本，韩国，（申花，实德，现代），（））在现实中：广义表是递归定义的线性结构，LS=(

1,

2,

,

n)其中：

i

或为原子

或为广义表例如:A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,

,)))广义表

LS=(

1,

2,…,

n)的结构特点:1)广义表中的数据元素有相对次序;2)广义表的长度定义为最外层包含元素个数;3)广义表的深度定义为所含括弧的重数;

注意:“原子”的深度为

0

;

“空表”的深度为

1

。4)广义表可以共享;5)广义表可以是一个递归的表;

递归表的深度是无穷值，长度是有限值。5.5

广义表的表示方法通常采用头、尾指针的链表结构表结点:原子结点：tag=0datatag=1hptp1)表头、表尾分析法:构造存储结构的两种分析方法:若表头为原子，则为空表

ls=NIL非空表

lstag=1指向表头的指针指向表尾的指针tag=0data否则，依次类推。Java的引用L=(a,(x,y),((x)))a(x,y)(

)

1LL=()0a

1

1

1

10x

()x

1

10x0y2)子表分析法:若子表为原子，则为空表

ls=NIL非空表1指向子表1

的指针tag=0data否则，依次类推。1指向子表2

的指针1指向子表n

的指针ls…

5.6广义表操作的递归函数递归函数

一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件:1)在每一次调用自己时，必须是(在某种意义上)更接近于解;2)必须有一个终止处理或计算的准则。广义表从结构上可以分解成广义表=表头+表尾或者广义表=

子表1+子表2+···+子表n

因此常利用分治法求解之。算法设计中的关键问题是，如何将k个子问题的解组合成原问题的解。广义表的头尾链表存储表示：typedef

enum{ATOM,LIST}ElemTag;

//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//标志域

union{AtomTypeatom;//原子结点的数据域

struct{structGLNode*hp,*tp;}ptr;

};}*GListtag=1

hp

tpptr表结点广义表的深度=Max{子表的深度}+1例一求广义表的深度可以直接求解的两种简单情况为:

空表的深度

=1

原子的深度

=0

将广义表分解成

n个子表，分别(递归)求得每个子表的深度,

int

GlistDepth(GlistL){

//返回指针L所指的广义表的深度

for(max=0,

pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);if(dep>max)max=dep;

}

returnmax+1;}//GlistDepthif(!L)return1;if(L->tag==ATOM)return0;tag=1

hp

tpptrpp111L…

for(max=0,

pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);if(dep>max)max=dep;

}例如:pppp->ptr.hppppppp->ptr.hppp->ptr.hpabstractclass

GListNode{

boolean

tag;

publicGListNode(){}}C语言union的Java的方案publicclassAtomNodeextends

GListNode{

char

atom;

publicAtomNode(){

super.tag=false;}}6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码6.1树的类型定义数据对象

D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树；

否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互

不相交的有限集T1,T2,…,Tm,其中每一

棵子集本身又是一棵符合本定义的树，

称为根root的子树。

数据关系

R：

基本操作：查

找

类

插

入

类删

除

类Root(T)//求树的根结点

查找类：Value(T,cur_e)//求当前结点的元素值

Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子

RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树

TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历InitTree(&T)//初始化置空树

插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1,第l

层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点，

F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF6.2二叉树的类型定义

二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树

二叉树的主要基本操作：查

找

类插

入

类删

除

类Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());查

找

类

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插

入

类ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删

除

类二叉树的重要特性

性质1：

在二叉树的第i

层上至多有2i-1

个结点。(i≥1)用归纳法证明：

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点，

2i-1=20=1；假设对所有的

j，1≤

j

i，命题成立;二叉树上每个结点至多有两棵子树，则第

i层的结点数

=2i-2

2=2i-1

。

性质2：

深度为k

的二叉树上至多含2k-1个结点（k≥1）证明：

基于上一条性质，深度为

k的二叉树上的结点数至多为

20+21+

+2k-1=2k-1

性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为

2

的结点，则必存在关系式：n0=n2+1证明：设

二叉树上结点总数

n=n0+n1+n2又

二叉树上分支总数

b=n1+2n2

而

b=n-1=n0+n1+n2-1由此，

n0=n2+1两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的

n个结点和满二叉树中编号为

1至

n的结点一一对应。123456789101112131415abcdefghij

具有

n个结点的完全二叉树的深度为

log2n

+1证明：设

完全二叉树的深度为

k则根据第二条性质得

2k-1≤n<2k

即

k-1≤log2n<k

因为

k只能是整数，因此，

k=

log2n

+1

性质4：

性质5：

若对含

n个结点的完全二叉树从上到下且从左至右进行

1

至

n

的编号，则对完全二叉树中任意一个编号为

i

的结点：

(1)若

i=1，则该结点是二叉树的根，无双亲,否则，编号为

i/2

的结点为其双亲结点;

(2)若

2i>n，则该结点无左孩子，

否则