计算机数据结构第一章绪言

计算机数据结构第一章绪言第一页，共五十八页，编辑于2023年，星期一与相关课程联系线性代数数据结构离散数学程序设计概率论编译原理操作系统算法设计与分析人工智能数据库原理

……第二页，共五十八页，编辑于2023年，星期一学习目标及方法

了解数据的特性，学会数据的组织及其在计算机内部的表示方法掌握基本的算法原理和设计

训练基本的、良好的程序设计技能注重实践，项目驱动学习继续保持“研学小组”学习方式课程有一定难度，要重视第三页，共五十八页，编辑于2023年，星期一教材与参考书：严蔚敏，吴伟民编．《数据结构》（C语言版）．北京：清华大学出版，2007年．吴艳等．《数据结构与算法实验教程》．北京：科学出版社，2006年．

严蔚敏吴伟民.数据结构题集(C语言版),清华大学出版社第四页，共五十八页，编辑于2023年，星期一第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析

1.4.1算法

1.4.2算法设计的要求

1.4.3算法效率的度量

1.4.4算法的存储空间的需求第五页，共五十八页，编辑于2023年，星期一计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。第六页，共五十八页，编辑于2023年，星期一

对于数值计算问题，其数学模型通常是数学方程；而对于更多的非数值计算问题，其数学模型通常无法用数学方程加以描述。数据结构重点研究此类问题的处理。第七页，共五十八页，编辑于2023年，星期一过去我们知道：程序=算法+数据结构本课程将深刻理解该问题。程序:计算机处理问题编制一组指令集.

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

.第八页，共五十八页，编辑于2023年，星期一1.1什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。

例1.1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：

(a1，b1)(a2，b2)…(an，bn)

其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。第九页，共五十八页，编辑于2023年，星期一算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n

数据结构还要提供每种结构类型所定义的各种运算的算法。第十页，共五十八页，编辑于2023年，星期一例１.2图书馆书目检索系统（表）（１）问题目标：自动检索（２）操作对象：书目信息（登录号、书名、作者名、分类号、出版单位、出版时间等）（３）对象关系：顺序排列（４）数学模型：线形数据结构类似问题有：查号系统、仓库帐户系统等第十一页，共五十八页，编辑于2023年，星期一001高等数学樊映川S01……002理论力学罗远祥L01……003高等数学华罗庚S01……004线性代数栾汝书S02……..………………………………………高等数学001,003,…理论力学002,…线性代数004,…樊映川001,…华罗庚003,…栾汝书004,…L002,…S001,003,…图1.1图书目录文件示例书名索引表作者索引表分类号索引表第十二页，共五十八页，编辑于2023年，星期一例1.3人机对弈问题

（１）问题目标：计算机不仅要会看格局，还能预测棋局发展，做出决策。（２）操作对象：格局（３）对象关系：一个格局可派生出多个格局（４）数学模型：树形数据结构第十三页，共五十八页，编辑于2023年，星期一例1.3计算机和人对弈问题（树）○○××○××○××○××○××○×××××××○○○○○第十四页，共五十八页，编辑于2023年，星期一例1.4多叉路口交通灯的管理（１）问题目标：设计交通灯方案，使车辆相互不冲突，且流量最大CBAED第十五页，共五十八页，编辑于2023年，星期一（２）操作对象：顶点（表示通路，用两个字母表示，前者为出发点，后者为到达点）（３）对象关系：连线（表示通路之间的冲突关系）（４）数学模型：图第十六页，共五十八页，编辑于2023年，星期一例1.3多叉路口交通灯的管理问题（图）EABCD(b)表示通路的图11111112223344(a)五叉路口EDABACADBABCBDDADBDCEAEBEC第十七页，共五十八页，编辑于2023年，星期一

通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。第十八页，共五十八页，编辑于2023年，星期一1.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。第十九页，共五十八页，编辑于2023年，星期一数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构结构中的数据元素之间存在一对一的关系。树型结构结构中的数据元素之间存在一对多的关系。图状结构或网状结构结构中的数据元素之间存在多对多的关系。

第二十页，共五十八页，编辑于2023年，星期一

集合

线性树

图数据的逻辑结构示例第二十一页，共五十八页，编辑于2023年，星期一数据结构的形式定义为：数据结构是一个二元组：

Data-Structure=(D，R)

其中：D是数据元素的有限集，R是D上关系的有限集。例复数的数据结构定义如下：

Complex=(C，R)

其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。第二十二页，共五十八页，编辑于2023年，星期一

数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。第二十三页，共五十八页，编辑于2023年，星期一abcd例

线性表L=(D,R),D={a,b,c,d},R={(a,b),(b,c),(c,d)}顺序存储结构链式存储结构（单链表）Labcd^第二十四页，共五十八页，编辑于2023年，星期一指针项可以有多个,以指示多个后继.例如,S=(D,R),D={a,b,c,d,e,f},R={(a,b),(a,c),(b,d),(b,e),(c,f)}abcfedd1d2d3d4d5d6ΛΛΛΛΛΛΛ第二十五页，共五十八页，编辑于2023年，星期一1.3抽象数据类型的表示和实现

数据类型(DataType)一般的高级语言都提供了一些数据类型,如整数型,字符型等.数据类型是一个值的集合和定义在此集合上的一组操作的总称.用户还可以定义自己的数据类型.数据类型可分为原子类型(不可分解的,如int,bool,char等)和结构类型(由其他类型构成)数据类型为程序员提供了极大的方便:它将数据集合及其上的操作与其实现细节分离开来,或者说将数据的逻辑表示和运算与它们的实现相分离。程序员只需要了解此集合由哪些值构成,可以进行那些运算.第二十六页，共五十八页，编辑于2023年，星期一抽象数据类型

抽象数据类型(AbstractDataType

简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作.抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。用三元组描述如下：（Ｄ，R，Ｐ）

D

是数据对象(性质相同的数据元素的有限集)。

R

是D上关系的有限集。

P是对D的基本操作的有限集。

第二十七页，共五十八页，编辑于2023年，星期一抽象数据类型描述：ADT{

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

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

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

ADT

抽象数据类型名

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

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

第二十八页，共五十八页，编辑于2023年，星期一

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

“操作结果:说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。第二十九页，共五十八页，编辑于2023年，星期一例1.4

定义一个抽象数据类型——三元组ADTTriplet{

数据对象：D={e1,e2,e3|e1,e2,e3ElemSet}

数据关系：R1={<e1,e2>,<e2,e3>}

基本操作：

InitTriplet(&T,v1,v2,v3)

操作结果：构造了三元组T，元素e1,e2,e3分别被赋以参数v1,v2,v3的值。

DestroyTriplet(&T)

操作结果：三元组T被销毁。

Get(T,i,&e)

初始条件：三元组T已存在，1i3

操作结果：用e返回T的第i元的值。…………第三十页，共五十八页，编辑于2023年，星期一

抽象数据类型的表示与实现通常采用类语言（类程序设计语言，如类C，类PASCAL等）作为描述工具，和程序设计语言相比，类语言具有以下特点：1.抽象性

类语言抽象而简洁，描述算法时可忽略许多细节问题。2.可读性类语言算法忽略细节而突出了解题的思路和方法。3.适应性用类语言写的算法可以方便地转换为各种程序设计语言的程序。第三十一页，共五十八页，编辑于2023年，星期一类C语言简介//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型，其值是函数结果状态代码typedefintStatus;(1)

预定义常量和类型：第三十二页，共五十八页，编辑于2023年，星期一(2)数据结构的表示(即存储结构)用类型定义(typedef)描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。(3)基本操作的算法都用以下形式的函数描述:函数类型函数名（函数参数表）{

//算法说明语句序列

}//函数名第三十三页，共五十八页，编辑于2023年，星期一(3)．赋值语句简单赋值：〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量；〈变量〉++，它表示变量加1后赋值给变量；〈变量〉--，它表示变量减1后赋值给变量；第三十四页，共五十八页，编辑于2023年，星期一成组赋值：1.（〈变量1〉,〈变量2〉,〈变量3〉,…〈变量k〉）

=（〈表达式1〉，〈表达式2〉,〈表达式3〉,…〈表达式k〉）;2.〈数组名1〉[下标1…下标2]=〈数组名2〉[下标1…下标2]；第三十五页，共五十八页，编辑于2023年，星期一串联赋值：〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉；条件赋值：〈变量名〉=〈条件表达式〉？〈表达式1〉：〈表达式2〉；交换赋值：〈变量1〉←→〈变量2〉，表示变量1和变量2互换；第三十六页，共五十八页，编辑于2023年，星期一(5)．条件选择语句if（〈表达式〉）语句；if（〈表达式〉）语句1；else语句2；情况语句

switch（〈表达式〉）{case判断值1；语句组1；break；case判断值2；语句组2；break；

……case判断值n；语句组n；break；[default：语句组n+1；]}注意：switchcase语句是先计算表达式的值，然后用其值与判断值相比较，若它们相一致时，就执行相应的case下的语句组；若不一致，则执行default下的语句组；其中的方括号代表可选项。第三十七页，共五十八页，编辑于2023年，星期一(7)．输入、输出语句输入语句：用函数scanf实现，特别当数据为字符时，用getchar函数实现。输出语句：用printf函数实现，特别当要输出字符数据时，用putchar函数实现。(6)循环语句：for（赋初值表达式；条件；修改表达式序列）语句；while（条件）语句；do{语句序列}while（条件）；第三十八页，共五十八页，编辑于2023年，星期一(8)．其他一些语句（1）return表达式或return：用于函数结束。（2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。（3）exit语句：表示出现异常情况时，控制退出语句。(9)．注释形式

可用/*字符串*/或者单行注释或//文字序列。第三十九页，共五十八页，编辑于2023年，星期一(10)逻辑运算约定与运算&&

对于A&&B，当A的值为0时，不再对B求值。例：

inta[N];……i=0;while(i<N&&a[i]!=x)i++;

或运算||

对于A||B，当A的值为非0时，不再对B求值。

第四十页，共五十八页，编辑于2023年，星期一例1.4(续):

抽象数据类型Triplet的表示和实现//-----采用动态分配的顺序存储结构typedefElemtype*Triplet;//-----基本操作的函数原型说明StatusInitTriplet(Triplet&T,Elemtypev1,Elemtypev2,Elemtypev3);//操作结果：构造了三元组T，元素e1,e2,e3分别被

//赋以参数v1,v2,v3的值。StatusDestroyTriplet(Triplet&T);//操作结果：三元组T被销毁。Status

Get(TripletT,inti,Elemtype&e)//初始条件：三元组T已存在，1i3

//操作结果：用e

返回T的第i元的值。…………第四十一页，共五十八页，编辑于2023年，星期一//-----基本操作的实现StatusInitTriplet(Triplet&T,Elemtypev1,Elemtypev2,Elemtypev3);{T=(Elemtype

*)malloc(3*sizeof(Elemtype));if(!T)exit(OVERFLOW);T[0]=v1;T[1]=v2;T[2]=v3;returnOK;}//InitTripletStatusDestroyTriplet(Triplet&T);{free(T);T=NULL;returnOK;}//DestroyTriplet第四十二页，共五十八页，编辑于2023年，星期一Status

Get(TripletT,inti,Elemtype&e){//1i3,用e

返回T的第i元的值。

if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}//GetStatus

Put(Triplet&T,inti,Elemtypee){//1i3,置T的第i元的值为e。

if(i<1||i>3)returnERROR;T[i-1]=e;returnOK;}//Put第四十三页，共五十八页，编辑于2023年，星期一1.4算法和算法分析1.4.1算法算法：是对特定问题求解步骤的一种描述。算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。第四十四页，共五十八页，编辑于2023年，星期一(4)输入:

一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。(5)输出:

一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.4.2算法设计的要求评价一个好的算法有以下几个标准:(1)正确性(Correctness)：算法应满足具体问题的需求。(2)可读性(Readability)：算法应该好读。以有利于阅读者对程序的理解。(3)健状性(Robustness)：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。第四十五页，共五十八页，编辑于2023年，星期一(4)效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4.3算法效率的度量

对一个算法要作出全面的分析可分成两用人才个阶段进行，即事后测试和事先分析。事后测试

收集此算法的执行时间和实际占用空间的统计资料。事先分析

求出该算法的一个时间界限函数第四十六页，共五十八页，编辑于2023年，星期一事后测试法缺点：1.必须编制程序且上机执行；

2.其它因素可能掩盖算法本身的质量

算法的效率通过依据该算法编制的程序在计算机上运行所消耗的时间来度量，不同算法的程序可通过一组或若干组相同的测试数据以分辨优劣。第四十七页，共五十八页，编辑于2023年，星期一事前分析法

从算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法执行时间的度量基准。原操作——

固有数据类型的操作

固有数据类型——

计算机系统中已定义并实现的数据类型,如高级语言中的整型、实型、字符型、布尔型、指针型等。第四十八页，共五十八页，编辑于2023年，星期一T(n)=O(f(n))其中：

n——

问题的规模，如：矩阵的阶，线性表的长度，树中的结点数，图中的顶点数等。算法的时间复杂度:

f(n)——

n的某个函数，通常表示算法中基本操作的重复执行次数。定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n)︳≦c｜g(n)，则记作f(n)=O(g(n))第四十九页，共五十八页，编辑于2023年，星期一O(1)O(n)O(n2)O(n3)常量阶线性阶平方阶立方阶指数阶对数阶O(2n)O(log2n)O(nlog2n)O(f(n)+g(n))=O(max(f(n),g(n)))O(cf(n))=O(f(n))运算法则：第五十页，共五十八页，编辑于2023年，星期一//计算n阶矩阵的乘积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]=c[i][j]+a[i][k]*b[k][j];

}原操作基本操作的重复执行次数：f(n)=n3例:矩阵相乘算法第五十一页，共五十八页，编辑于2023年，星期一矩阵相乘算法的时间量度记作：

T(n)=O(n3)称O(n3)为该算法的(渐近)时间复杂度。

asymptotictimecomplexity它表示：当n较大时，T(n)与