数据结构课堂用-第1章绪论

第一章绪论第一章 绪论（Introduction）内容提要数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析开发的过程:系统分析系统实现系统设计确定系统所要达到的目标确定实现方案并生成系统实地安装调试系统修整完善1.1数据结构程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型1.1

数据结构Niklaus

WirthAlgorithm

+

Data

Structures

=

Programs数值问题非数值问题1.1

数据结构两类问题数值问题的求解，如:鸡兔同笼问题二元一次代数方程组结构静力分析问题全球天气预报高次线性代数方程组球面坐标系下的环流模式方程1.1数据结构非数值计算问题的求解，如：例一 对一组(n个)整数进行排序例二 交叉路口的交通 问题例三 煤气管道的铺设问题例四

海外华侨 的族谱问题1.1数据结构①建立问题的数学模型（如，线性模型、树状模型、网状模型等）②按照数学模型设计解决问题的算法③根据算法编写程序，运行程序得到问题的解答1.1

数据结构非数值性问题的求解方法：举例：检索系统----线性模型问题棋类对弈--------树状模型问题煤气管道铺设--------网状模型问题1.1数据结构书库登录号书名分类作者单价……………0011数据结构CS26.000012C程序设计CS25.00……………0035数据结构CS善16.00……………0125BASIC语言CS13.000126C程序设计CS宽复旦26.00……………0200高等数学MA高教18.00……………书名索引表1数据结构2C程序设计3BASIC语言4高等数学…00110035

∧00120126∧0125∧0200∧作者索引表1234善…00120125∧0011∧0200∧0035∧一个结点线性模型问题树状模型问题井字棋的对弈树煤气管道铺设问题：1.1

数据结构非数值问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。1.1数据结构数据结构？数据结构是一门 “描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示 ”的学科。1.1数据结构第一章 绪论内容提要1.1数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析所有能被输入到计算机中，且能被计算机处理的符号的总称，它是计算机程序加工的

“原料”。如，文字、字符、图形、图像、声音等等。1.数据（Data)1.2

基本概念和术语是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。如， 检索系统中的一本书的书目信息；井棋弈对弈树中的一个棋盘格局；煤气管道铺设图中的一个圆圈等等。2.数据元素(Data

Element)1.2

基本概念和术语一个具体的实体，

一个数据元素一般如一个学生，一本书等。在数据模型中， 往往不考虑数据元素的具体含义，而抽象成一个结点。数据元素的同义词是：结点、顶点、记录、元素1.2

基本概念和术语3.数据项(Data

Item)数据元素的分量，数据项是数据的不可分割的最小单位。4.数据对象(Data

Object)同类型数据元素的集合，如一个系的全体学生等。1.2

基本概念和术语②

全体数据元素以及数据元算机 的表达----数据的间的特定关系在计结构③

为解决问题而对数据施加的一组操作----数据的运算集合1.2

基本概念和术语5.数据结构(Data

Structure)的含义没有被一致公认的定义。具有三个层面的含义：①

问题所涉及的数据对象，以及数据对象

各个数据元 间的特定关系----数据的逻辑结构其中,

D:一个数据对象D={di

|i=1,2,…,n,

n≥0}S:

D内数据元 间存在的关系的集合S={sj

|j=1,2,…,m,

m≥1}关系sj——数据元素序偶的集合逻辑结构面向问题，与计算机无关1.2

基本概念和术语数据的逻辑结构可以用一个二元组来描述:DS=(D,

S)序偶:两个数据元素X和Y之间存在某种特定关系(如图a所示)称为一个序偶，记为<X,

Y>。这里，X称为Y的直接前驱；Y称为X的直接后继。如果这种关系是对称的，也就是说如果存在<X,Y>,就必然有<Y,X>,则记为(X,Y),图b表示。X图a图bYXY1.2

基本概念和术语<x,

y>（x,

y）举例：描述6个城市之间的关系DS=(D,

S)D={

A,

B,

C,

D,

E,

F}S={

s1,

s2,

s3}s1={<A,

B>,

<A,

C>,

<B,

D>,

<B,

E>,

<C,

F>}s2={(A,

B),

(A,

C),

(A,

D),

(B,

C),

(C,

F),

(B,

E)}s3={(A,

B),

(A,

C),

(E,

F),

(B,

D),

(C,

F),

(B,

E)}AFDEs1的图示CBDs2的图示CA

B

FE--行政隶属关系--公路交通关系--地理邻接关系ADB

CEFs3的图示几种常用的数据结构（逻辑结构）：线性结构树形结构图状结构集合结构1.2

基本概念和术语据元

间存在的关系。常用的

技术有：顺序 、链式 、散列、索引结构面向计算机数据的

结构将问题所涉及的数据对象中的所有数据元素存入计算机，并且在计算机

表达出数1.2

基本概念和术语既面向问题又面向计算机：操作集合的定义由问题决定；

操作的实现与数据在计算机内的方式有关。数据的运算集合对数据进行加工和处理的一组算法1.2

基本概念和术语6.数据类型(Data

Type)高级语言的数据类型涉及两个层面的含义：值的集合——数据的特征，取值范围等如int，float操作的集合——对值集定义的一组运算int型：

+,

-,

*,

/,

%

…float型：+,

-,

*,

/…高级语言中已经实现的数据类型称为固有数据类型，只能 简单的数据1.2

基本概念和术语高级语言提供的数据类型使在编程时不用考虑每种数据在计算机的细节和运算的实现细节，直接按照数据类型的外部抽象数学特性来使用数据，大大方便了程序设计。1.2

基本概念和术语7.抽象数据类型

ADT( Data

Type)一个数学模型以及定义在该模型上的一组操作；本课程用ADT来描述数据结构ADT可用三元组表示：(D,S,P

)其中： D——

数据对象S

——

D中数据元 间的关系P——对D的基本操作的集合1.2

基本概念和术语1.2

基本概念和术语

高级语言中的固有数据类型（如int、float等）只能

简单的数据。用户在解决实际问题时往往需要构建一些复杂的数据类型——描述该数据类型的数学特性，为它定义一组操作。这正是抽象数据类型的建模方法。1.2

基本概念和术语抽象数据类型的定义只涉及数学模型的逻辑特性，而不涉及该模型的具体实现细节。不管采用什么技术方法来实现这个抽象数据类型，只要模型的数学特性不变，都不会影响它的外部使用。从而使外部使用和实现分离。“抽象”的目的就是让人们集中精力把握问题的本质，研究解决问题的算法，抛开繁琐的实现细节，从而使问题得到简化。“抽象”可以按一定的层次逐步提高抽象的程度。层次越高，细节就越少，使用就越方便。本课程中定义ADT的格式为：ADT抽象数据类型名{数据对象：<对数据对象的定义>数据关系：<对数据关系的定义>基本操作：<对基本操作的定义>}ADT抽象数据类型名1.2

基本概念和术语基本操作的定义格式为：基本操作名(参数表)初始条件：<初始条件的描述>

——描述了操作执行之前数据结构和参数应满足的条件。初始条件可以为空。操作结果：<操作结果的描述>

—出口—说明了操作正常完成之后，数据结构的变化状况和应返回的结果。1.2

基本概念和术语举例:抽象数据类型复数的定义ADTComplex{数据对象：D＝{e1,e2|eiRealSet}数据关系：R1＝{<e1,e2>|e1是实部，e2是虚部}基本操作：plex(&Z,v1,v2)操作结果：构造了复数Z,实部和虚部分别赋予参数v1和v2的值GetReal(Z，&RealPart)初始条件：复数Z已经存在操作结果：用参数RealPart返回实部值GetImag(Z，&ImagPart)初始条件：复数Z已经存在操作结果：用参数ImagPart返回虚部值e1

e2Add(z1,z2,&sum)初始条件：复数z1和z2已经存在操作结果：用参数sum返回z1与z2的和值Subtract(z1,z2,&sub)初始条件：复数z1和z2已经存在操作结果：用参数sub返回z1与z2的差值Multiply(z1,z2,&mult)初始条件：复数z1和z2已经存在操作结果：用参数mult返回z1与z2的积值Division(z1,z2,&div)初始条件：复数z1和z2已经存在操作结果：用参数div返回z1，z2的商值}ADT

Complex小结：数据(Data)数据元素

(Data Element

)数据项(DataItem)数据对象

(

Data Object

)数据结构

(

Data

Structure)数据类型

(

Data Type

)抽象数据类型

( Data

Type

)1.2

基本概念和术语第一章 绪论内容提要1.1数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。言的虚拟层次上在高级程序设计语抽象数据类型的，采用类C语言作为描述表示

工具。1.3

抽象数据类型的表示与实现类C语言采用了标准C语言的语法结构，同时对

一些语法细节进行了简化，并添加了一些描述方法。用类C写的代码是伪代码。因为不完全符合C语言的规范，所以不能被C编译器编译。类C语言简介1.3

抽象数据类型的表示与实现类C语言简介和本 中的一些约定：1.

本 中约定的一些预定义常量和类型constTRUE=1;真constFALSE=0;假constOK=1;算法正常完成的状态constERROR=0算法执行出错的状态constINFEASIBLE=-1;算法不可实现的状态constOVERFLOW=-2;溢出的状态typedef

int

Status

;Status作为类型名，专门用来说明函数返回值的类型，其值是函数执行结果的状态代码。1.3

抽象数据类型的表示与实现2.结构用类型定义(typedef)描述数据元素（结点）的类型名约定为ElemType1.3

抽象数据类型的表示与实现3.操作算法用以下形式的函数描述函数返回值类型 函数名(参数表){//对算法的文字说明函数语句序列}//函数名1.3

抽象数据类型的表示与实现4.赋值语句的格式变量名=表达式;变量名1=变量名2=

...=变量名k=表达式;简单赋值:串联赋值:成组赋值:结构体名=结构体名;{变量名1,

...

,

变量名k

}={值1,

...

,值k};

数组名[]=表达式;

—对整个数组赋值数组名[起始下标..终止下标]=数组名[起始下标..终止下标];交换赋值:

变量名变量名;

条件赋值:

条件表达式?表达式T:表达式F;

1.3

抽象数据类型的表示与实现5.选择语句条件语句1:if(条件表达式)语句T;条件语句2:if(条件表达式)else

语句F;语句T;1.3

抽象数据类型的表示与实现开关语句:格式1:switch(表达式){语句序列1;

break;语句序列2;

break;语句序列n;

break;语句序列n+1;case

值1:case

值2:...case

值n:default:}格式2:switch

{case

条件1:语句序列1;break;case

条件2:语句序列2;break;...case

条件n:语句序列n;break;default:

语句序列n+1;}1.3

抽象数据类型的表示与实现6.循环语句for语句

:for(

赋初值句;条件;修改句)语句;while语句:while(条件)语句;do-while语句:do

{语句序列;while(条件);1.3

抽象数据类型的表示与实现7.结束语句函数结束语句:return;

或

return(表达式);case结束语句:break;异常结束语句:exit(错误代码);1.3

抽象数据类型的表示与实现8.输入输出语句输入语句:cin>>变量1>>变量2>>...>>变量n;scanf(“格式串”,变量1,...,变量n);scanf(变量1,...,变量n);输出语句:cout<<变量1<<变量2<<...<<变量n;printf(“格式串”,变量1,...,变量n);printf(变量1,...,变量n);1.3

抽象数据类型的表示与实现9.注释语句单行注释://注释文字1.3

抽象数据类型的表示与实现10.基本函数求最大值:求最小值:求绝对值:min(表达式1,...,abs(表达式)求不足整数值:求进位整数值:判定文件结束:判定行结束:floor(表达式)

或

表达式ceil(表达式)

或

表达式

eof(文件变量)

或

eofeoln(文件变量)

或

eolnfloor(5.8)=5或

5.8

=5max(表达式1,...,ceil(5.1)=6或

5.1

=61.3

抽象数据类型的表示与实现11.逻辑运算约定与运算&&:条件表达式A

&&

条件表达式B当条件表达式A为假时,不再对条件表达式B求值或运算

||

:条件表达式A

||

条件表达式B当条件表达式A为真时,不再对条件表达式B求值1.3

抽象数据类型的表示与实现12.内存的动态分配与分配空间：指针变量=new

数据类型;指针变量=(强制指针类型)malloc(分配长度);指针变量=(强制指针类型)realloc(老基址，新分配的长度);空间：delete

指针变量; delete

[]

指针变量;free(指针变量);1.3

抽象数据类型的表示与实现realloc函数的使用：改变数组空间的大小（增或减）int

*a=(int*)malloc(sizeof(int)*10),*b;……b=(int*)realloc(a,

sizeof(int)*15);申请新数组空间2468a5

6

7

8

9b0

1

2

3

4

5

6

7

8

9

10

11

12

13

14老数组的内容老数组的空间1.3

抽象数据类型的表示与实现12.

关于“

参数”在函数参数表中，参数的前面可以加符号“&”修饰，表示该参数为

参数(变参)。在函数体内，如果对

参数的值进行了修改，这个变化能够传递到相应的实参。没有用“&”修饰的参数是值参。参数可以用来作为传递运算结果的管道1.3

抽象数据类型的表示与实现例:

void add(int

x,

int

&y)

{x++;

y++;}void

main(void

){

int

a=0, b=0

;add

(a,

b);printf(“a=%d,

b=%d”,

a,

b);}打印：a=0,b=1Demos:指针的与指向指针的指针.cpp1.3

抽象数据类型的表示与实现举例：ADT

Complex的类C表示typedef

struct{

//复数类型定义float

real,imag;}complex;status//复数初始化z.real=v1;return

OK;}plex(complex

&z,

float

v1,

float

v2){z.imag=v2;1.3

抽象数据类型的表示与实现抽象数据类型的表示与实现Status

GetReal(complex

z,

float

&RealPart)

{//取得已知复数z的实部RealPart，并返回OKRealPart=z.real;return

OK;}Status

GetImag(complex

z,

float

&ImagPart)

{//取得已知复数z的虚部ImagPart，并返回OKImagPart=z.imag;return

OK;}1.3

抽象数据类型的表示与实现Status

Add(complex

z1,

complex

z2,

complex

&sum)

{//求得两个复数z1和z2的和sum，并返回OKsum.real=z1.real

+

z2.real;sum.imag=z1.imag

+

z2.imag;return

OK;}Status

Subtract(complex

plex//求得两个复数z1和z2的差sub，并返回OKsub.real=z1.real

-

z2.real;sub.imag=z1.imag

-

z2.imag;return

OK;plex

&sub){}1.3

抽象数据类型的表示与实现Status

Multiply(complex

z1,

complex

z2,complex

&mult){//求得两个复数z1和z2的积mult，并返回OKmult.real=z1.real*z2.real-z1.imag*z2.imag;mult.imag=z1.real*z2.imag+z2.real*z1.imag;return

OK;}1.3

抽象数据类型的表示与实现Status

Division(complex

z1,

complex

z2,complex

&div){//求得复数z1除以复数z2的商div，并返回OK//float

temp;if(z2.real==0&&z2.imag==0)

return

ERROR;temp=z2.real*z2.real+z2.imag*z2.imag;div.real=(z1.real*z2.real+z1.imag*z2.imag)/temp;div.imag=(z2.real*z1.imag-z1.real*z2.imag)/temp;return

OK;}1.3

抽象数据类型的表示与实现第一章 绪论本章内容提要用数据结构方法解决的问题基本概念和术语类C语言简介算法和算法分析算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。1.4

算法和算法分析算法（Algorithm）的定义算法必须满足的五个重要特性：(P13)有穷性：算法必须能在执行有穷步骤之后结束，每一步骤都能在有限时间内完成；确定性：算法的每一个步骤必须是确切定义的。并且，对于一种输入，算法只有一条执行路径，即对于相同的输入只能得到相同的输出；可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现；

(4)有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。(5)有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。1.4

算法和算法分析算法的描述:本书采用类C语言描述－－比C语言的细

节简单，可读性强，而且做简单的修改就可以转换成可以编译调试的C程序。算法的要求：正确性，可读性，健壮性，高效率1.4

算法和算法分析算法效率分析：时间耗费：(渐进)时间复杂度空间耗费：(渐进)空间复杂度1.4

算法和算法分析算法的时间分析：语句的频度：算法中某条语句重复执行的次数称为该语句的频度。算法的时间耗费:i

1其中，ti—语句i执行一次所耗费的时间m—算法中可执行语句的个数mT

语句i的频度

ti1.4

算法和算法分析m语句执行的时间ti与机器的性能有关，与编译程序的代码质量有关，与语句的种类有关。为了排除这些与算法无关的因素，取ti＝单位1。这样算法的时间耗费T就简化为统计算法中所有语句的执行次数：T

语句i的频度i

1—算法的时间复杂度在很多情况下，T是问题规模n的函数：T(n)1.4

算法和算法分析计算n阶方阵的乘积C＝A×Bfor(i=1;

i<=n;

i++)(n+1)次for(j

=1;

j<=n;

j++){n(n+1)次C[i][j]=0;n2次for(k=1;

k<=n;k++)n2(n+1)次C[i][j]+=A[i][k]*B[k][j];n3次}T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+11.4

算法和算法分析希望用一个与T(n)同阶的简单函数表示算法的时间耗费：设f(n)是一个已知的简单函数，且满足lim

T

(n)

常数Cf

(n)n则T(n)与f(n)同阶，记为T(n)=O(f(n))。O是Order（数量级）的第一个字母，它允许用“＝”代替“≈”。如：n3+3n2+2n=O(n3)1.4

算法和算法分析1.4

算法和算法分析用O(f(n))来做为算法时间耗费的度量，称为算法的渐进时间复杂度，简称为算法的时间复杂度。对于前面的T(n)=2n3+3n2+2n+1,可记为:T