数据结构与软件工程

数据结构与软件工程信息科学与技术学院郝矿荣E-mail:krhao@

1数据结构与软件工程教材及参考书目：数据结构（C语言版）严蔚敏等编清华高校出版社数据结构习题集（C语言版）严蔚敏等编清华高校出版社数据结构C++语言描述刘卫东等译清华高校出版社2数据结构与软件工程预备学问：C语言程序设计的基本技术离散数学概率论3数据结构与软件工程计算机三级偏硬：计算机原理60%数据结构30%Internet等10%探讨生入学考试的核心课程4数据结构与软件工程“数据结构”所处的地位5数据结构与软件工程要求：上课细致听课作业按时完成上机实习细致，按质按量完成6数据结构与软件工程第一章绪论第六章树与二叉树其次章线性表第七章图第三章栈和队列第八章动态存储管理第四章串第九章查找第五章数组与广义表第十章内部排序7第一章绪论目的：了解数据结构的背景驾驭一些基本概念和术语驾驭抽象数据类型的定义、表示与实现描述算法的类C语言驾驭算法分析的一些基本方法8第一章绪论重点：有关数据结构的基本概念和术语驾驭抽象数据类型ADT的定义、表示与实现熟悉类C语言的书写规范理解算法五个要素的精确含义驾驭估算时间困难度的方法，了解空间困难度的度量方法9第一章绪论难点：抽象数据类型ADT的表示与实现算法困难度的分析方法10第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求11一、数据结构形成和发展背景计算机是一门探讨用计算机进行信息表示和处理的科学两个问题：1）信息的表示和组织：干脆关系到处理信息的程序的效率；2）信息的处理：面对系统程序和应用程序的大规模和困难结构1.1什么是数据结构12一、数据结构形成和发展背景计算机的飞速发展及其应用范围的快速扩展计算机处理的对象由纯粹的数值发展到字符、表格和图像等各种具有确定结构的数据编制“好”的程序要求分析待处理的对象以及各处理对象之间存在的关系1.1什么是数据结构13二、数据结构1、用计算机解决问题的步骤：具体问题—建立数学模型—设计算法—编制程序—测试和调整—最终答案建立数学模型（关键）：分析问题、提取操作对象、找出对象间关系，对此用数学语言加以描述算法设计：利用建立的数学模型，依据具体问题，设计出解决问题的方法1.1什么是数据结构14二、数据结构

NiklausWirth：

Algorithms+DataStructures=Programs

程序设计:为计算机处理问题编制一组指令集算法：处理问题的策略数据结构：问题的数学模型1.1什么是数据结构15二、数据结构从数学模型上分：数值问题（数学方程），如：桥梁结构的应力分析模型——线性方程组人口增长模型——微分方程全球天气预报——环流模式方程非数值问题（集合、线性表、树、图等）无法用数学方程加以描述1.1什么是数据结构16二、数据结构非数值计算的程序设计问题例1:求一组(n个)整数中的最大值算法:基本操作是“比较两个数的大小”例2：计算机对弈算法：对弈的规则和策略例3：协会会员注册系统算法：须要管理的项目？如何管理？用户界面？模型：？1.1什么是数据结构17二、数据结构2、数据结构主要关切的：结构中各元素之间逻辑关系（数学模型） 线性结构：如图书馆的书目索引 树形结构：见后面例子 图形结构：见后面例子结构中各元素的存储方式结构具有的行为特征（其上的操作）在计算机中的表示和实现1.1什么是数据结构18例1.电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式支配：(a1,b1)(a2,b2)…(an,bn)其中，ai,bi(i=1,2,…,n)分别表示某人的名字和对应的电话号码要求：设计算法，给定某人的名字，打印出此人的电话号码；假如无此人，则报告无此人的标记1.1什么是数据结构19算法的设计，依靠于计算机如何存储人的名字和对应的电话号码，或者说依靠于名字和其电话号码的结构数据的结构，干脆影响算法的选择和效率上述问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量1)假定名字和其电话号码逻辑上已支配成N元向量的形式，它的每个元素是一个数对(ai,bi)，1≤i≤n2)数据结构还要供应每种结构类型所定义的各种运算的算法1.1什么是数据结构20例2.图书馆的书目检索系统自动化问题（线性结构）图书馆的一本图书由书名、作者、出版社等数据来描述，依据须要我们选择其中的若干项组成一个数据元素来对应一本书图书馆的编目表反映了书与书之间的关系，是数据元素之间的结构。当然我们还应留意到书是具体地放在某个书架上的，它是编目表的物理实现图书馆从两方面管理图书：物理的藏书和逻辑的编目表。这就是图书馆的结构。和图书馆一样计算机管理数据，也有两个方面：即物理的存储和逻辑的关系1.1什么是数据结构211.1什么是数据结构22例3：学生选课系统模型（图结构）1.1什么是数据结构23例3：学生选课系统模型（图结构）

课程编号

课

程

名

学时024002

程序设计基础64024010

汇编语言48024016

计算机原理64024020

数据结构64024021

微机技术64024024

操作系统48024026

数据库原理481.1什么是数据结构24例3：学生选课系统模型（图结构）选课单包含如下信息

学号课程编号成绩时间

学生选课系统中实体构成的网状关系1.1什么是数据结构25例4：下棋问题1.1什么是数据结构26例5.多叉路口交通灯的管理（图结构）11112223344111.1什么是数据结构27问题模型结构分析——线性方程组人口预报——微分方程优化问题——线性规划、非线性规划振动问题——矩阵分析；特征值、特征向量信息管理——二维数据表下棋——树型结构城市路径——图型结构DOS书目——树型结构家谱——树型结构排队——队列（线性）1.1什么是数据结构28数据的逻辑结构按关系分为线性结构（关系是线性的）和非线性结构（关系是非线性的）1.1什么是数据结构29数据结构是一门探讨非数值计算的程序设计问题中计算机的操作对象以及它们之间相互关系和操作等的学科对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构照旧是原来的结构类型1.1什么是数据结构301.2基本概念和术语数据：数据是信息的载体，是描述客观事物的数、字符以及全部能输入到计算机中，被计算机程序识别和处理的符号的集合数值性数据/非数值性数据数据元素：数据基本单位，通常作为一个整体来考虑，如：“树”中的一个棋盘格局；学生信息表，一个数据元素（记录）含若干个数据项等数据项是数据的不行分割的最小单位311.2基本概念和术语数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。数据对象可以是有限的，也可以是无限的整数数据对象:N={0,1,2,…}英文字符类型的数据对象:{A，B，C，D，E，F，…}

学生数据对象：数据表数据、数据元素和数据对象之间的关系：

数据数据元素数据项32集合元素间为松散的关系

线性结构元素间为严格的一对一关系树形结构元素间为严格的一对多关系

图状结构（或网状结构）元素间为多对多关系

示例特征1.2基本概念和术语331.2基本概念和术语数据结构与数据对象之间的区分和联系？数据对象仅仅是数据元素的集合，不涉及这些元素之间的关系描述数据结构不仅要描述数据对象，而且要描述元素彼此之间的关系341.2基本概念和术语数据结构描述Data-Structure=(D,S)D——数据集；S——关系集例：学科探讨课题小组Group=(P,R)其中：P={T,G1,G2,…Gn,S11,S12,…Snm}R={R1,R2}R1={<T,Gi>|i=1,2,3}R2={<Gi,Sij>|i=1,2,3,j=1,2}351.2基本概念和术语数据结构描述例：复数的数据结构定义如下：

Complex=(C，R)

其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}361.2基本概念和术语数据的逻辑结构逻辑结构：数据结构描述的元素间的逻辑“关系”，独立于计算机按集合的观点，数据的逻辑结构有两个要素：一是数据元素，二是关系数据元素间的关系表示1）依次映象：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系2）非依次映象：借助指示元素存储地址的指针表示数据元素之间的逻辑关系371.2基本概念和术语数据的逻辑结构依次映象：x和y存储位置的相对关系表示有序对<x,y>最简洁的方法就是使y和x的存储位置之间差一个常量C,例如：(a1,a2,a3)381.2基本概念和术语数据的逻辑结构链式映象：x和y的存储位置随意，则须要用一个和x在一起的附加信息指示y的存储位置，这个附加信息和x绑定在一起，此时，两者合在一起作为x的存储映象391.2基本概念和术语数据的物理（存储）结构物理结构：数据结构中数据元素间的关系在存储器中的存储方法（表现和实现）物理结构中的基本定义：

1）位：二进制中的一位；信息表示的最小单位

2）元素（结点）：由若干位组合起来形成的一个位串，可看成是数据元素在计算机中的映象

3）数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串401.2基本概念和术语依据物理结构的不同分为：1）依次存储结构：利用在存储器中的物理关系来表示逻辑关系。逻辑上相邻的数据元素存储在物理位置上相毗邻的存储单元里，元素的关系由存储单元的邻接关系来体现2）链式存储结构：数据元素可以在计算机内随意位置上存放（它不要求逻辑上相邻的元素在物理位置上也相邻)，用在存储器中附加指针的方式来表示逻辑关系。将数据元素存放的存储单元分为两个部分，分别存放数据和指针，称为数据域和指针域411.2基本概念和术语数据的逻辑结构和物理结构的关系：逻辑结构只抽象地描述数据元素逻辑关系（简称数据结构）物理结构是一个逻辑结构映像到计算机中所得到的存储表示算法的设计：取决于选定的数据逻辑结构算法的实现：依靠于接受的存储结构421.2基本概念和术语数据类型用以刻画（程序）操作对象的特性。一个值的集合（整型变量）+该集合上定义的一组操作(不体现值间关系)（加、减等操作）类型明显或隐含地规定了：在程序执行期间变量或表达式全部可能的取值范围以及在这些值上允许进行的操作431.2基本概念和术语数据类型例1.在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义例2.在FORTRAN语言中变量的数据类型有整型、实型、和复数型441.2基本概念和术语数据类型按“值”的不同特性可分为：1）非结构的原子类型：其值是不行分解的；2）结构类型：其值是由若干成分按某种结构组成的，是可分解的；且它的成分可以是非结构的，也可以是结构的。451.2基本概念和术语抽象数据类型：数据结构+定义在此结构上的一组操作（和其在计算机上的表示和实现无关）。不再局限于前述各处理器中已定义并实现的数据类型，还包括用户自定义的数据类型按“值”的不同特性可分为：1）原子类型：其值是不行分解的；2）固定聚合类型：其值由给定数目的成分按某种结构组成；3）可变聚合类型：其值的成分的数目不确定。461.2基本概念和术语抽象数据类型1）一个含抽象数据类型的软件模块包含：定义、表示和实现2）三元组表示（D,S,P）D：数据对象，S：D上的关系集，P：D上的基本操作集471.2基本概念和术语抽象数据类型定义：

ADT抽象数据类型名{

数据对象：<数据对象定义>

数据关系：<数据关系定义>

基本操作：<基本操作定义>}ADT抽象数据类型名其中：1）数据对象和数据关系的定义用伪码表示；481.2基本概念和术语抽象数据类型定义：2）基本操作的定义：基本操作名（参数表）初始条件：（初始条件描述）操作结果：（操作结果描述）基本操作有两种参数：赋值参数：为操作供应输入值引用参数：以&打头，除供应输入值外，还将返回操作结果491.2基本概念和术语抽象数据类型定义：2）基本操作的定义：初始条件：描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息操作结果：说明白操作正常完成之后，数据结构的变更状况和应返回的结果。若初始条件为空，则省略之501.2基本概念和术语抽象数据类型的两个特征:数据抽象对程序处理的实体的描述强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界运用它的方法)数据封装将实体的外部特性和其内部实现微小环节分别，并且对外部养护隐藏其内部实现微小环节511.2基本概念和术语抽象数据类型三元组的定义:（P9，例1-6）ADTTriplet{

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

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

基本操作：

InitTriplet(&T)

DestroyTriplet(&T) Get(T,i,&e) Put(&T,i,e) …}ADTTriplet521.3抽象数据类型的表示与实现可以通过固有数据类型表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作利用类C语言（C语言的一个核心子集）作为描述工具类C语言描述：P10-13

typedef数据类型定义

ElemType数据元素类型

Status函数结果状态的整数描述与运算&&,或运算||53类C语言描述：P10-13内存的动态支配与释放指针变量=new数据类型delete指针变量基本操作的算法：函数描述函数结果主要状态代码：TURE,OK=1FALSE,ERROR=0OVERFLOW=-21.3抽象数据类型的表示与实现54类C语言描述：P10-13几组特殊的赋值形式：交换赋值，数组赋值，条件赋值选择语句：条件语句，开关语句循环语句：for,while,do-while输入和输出语句：三种结束语句return,break,exit注释：基本函数：max,min,abs,floor,ceil,eof,eoln1.3抽象数据类型的表示与实现55例1-7抽象数据类型Triplet的表示和实现（P11-13）基本操作的函数原型：

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3);//操作结果：构造了三元组T，e1,e2和e3被赋以参数v1,v2,v3的值

StatusDestroyTriplet(Triplet&T)；//操作结果：三元组T被销毁。

StatusGet(TripletT,inti,ElemType&e);//初始条件：三元组T已存在，1i3//操作结果：用e返回T的第i元的值。1.3抽象数据类型的表示与实现56例1-7抽象数据类型Triplet的表示和实现（P11-13）基本操作的实现：

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){//构造三元组T，依此置T的三个元素的初值为v1,v2,v3 T=(ElemType*)malloc(3*sizeof(ElemType));if(!T)exit(OVERFLOW);T[0]=v1;T[1]=v2;T[2]=v3;returnOK;}1.3抽象数据类型的表示与实现57例1-7抽象数据类型Triplet的表示和实现（P11-13）基本操作的实现：

StatusDestroyTriplet(Triplet&T){//销毁三元组T free(T);T=null;returnOK;}StatusGet(TripletT,inti,ElemType&e){//1i3,用e返回T的第i元的值。

if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}1.3抽象数据类型的表示与实现58例：复数抽象数据类型示例ADTComplex{ 数据对象：D={c1,c2|c1,c2R(R为实数集）} 数据关系：S={<c1,c2>（c1为实部，c2为虚部）} 基本操作： voidAssign(&A,c1,c2） voidAdd(&A,B) voidMinus(&A,B) voidMultiply(&A,B) voidDivide(&A,B) ...}ADTComplex1.3抽象数据类型的表示与实现591.4算法和算法分析算法：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作算法的五个重要特性：1）有穷性：一个算法必需总是在执行有穷步之后结束，且每一步都在有穷时间内完成2）确定性：算法中每一条指令必需有精确的含义，不存在二义性。且算法只有一个入口和一个出口601.4算法和算法分析算法的五个重要特性：

3）可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的

4）输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合

5）输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量611.4算法和算法分析算法设计的要求：1）正确性：算法应满足具体问题的需求a）程序不含语法错误；b）程序对于一般输入数据的正确性；c）程序对于苛刻、刁难输入数据的正确性；d）程序对于一切合法输入数据的正确性2）可读性：算法应当好读。以有利于人对程序的理解3）健壮性：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年稀里糊涂的输出结果621.4算法和算法分析算法设计的要求：4）效率与低存储量需求效率：算法执行时间存储量需求：算法执行过程中所须要的最大存储空间一般，这两者与问题的规模有关631.4算法和算法分析算法效率的度量算法执行时间的度量方法：1）事后统计的方法：收集此算法的执行时间和实际占用空间的统计资料缺陷：a）必需先运行依据算法编制的程序；b）依靠于计算机的硬件、软件等环境因素2）事前分析估算的方法：求出该算法的一个时间界限函数算法运行所消耗的时间取决于：a）依据的算法选用何种策略；b）问题的规模；c）书写程序的语言；d）编译程序所产生的机器代码的质量；e）机器执行指令的速度641.4算法和算法分析算法的时间度量1）原操作：基本操作2）算法的时间度量：原操作重复执行的次数3）算法的渐近时间困难度：原操作重复执行的次数是问题规模n的某个函数f(n)T(n)=O(f(n))4）频度：原操作重复执行的次数5）在难以精确计算基本操作执行次数的状况下，只需求出它关于n的增长率或阶即可6）当基本操作执行次数随问题的输入数据集变更时，计算平均时间困难度或最坏状况下的上界651.4算法和算法分析算法的时间度量常用的计算规则：1）加法准则 T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))=O(max(f1(n),f2(n)))2）乘法准则 T(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=O(f1(n)×f2(n))常见的时间困难度：1）O(1)常量阶2）O(n)线性阶3）O(n2)平方阶4）O(n3)立方阶5）O(logn)对数阶6）O(2n)指数阶661.4算法和算法分析算法的时间度量六种常用计算算法时间的多项式的关系为：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：O(2n)<O(n!)<O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上特殊悬殊。因此，若能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个宏大的成就671.4算法和算法分析算法的时间度量例1.{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间困难度为Ｏ(1)假如将s=0也看成是基本操作，则语句频度为２，其时间困难度仍为Ｏ(1)，即常量阶例2.for(i=1;i<=n;++i){++x;s+=x;}语句频度为：2n其时间困难度为：O(n)即时间困难度为线性阶681.4算法和算法分析算法的时间度量计算累加和程序程序步数计算工作表格691.4算法和算法分析算法的时间度量例3.for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}语句频度为：2n2其时间困难度为：O(n2)即时间困难度为平方阶。701.4算法和算法分析算法的时间度量例4.两个N*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]; /*原操作*/ }问题规模：n原操作：c[i][j]+=a[i][k]*b[k][j];基本操作重复执行的次数：f(n)=n3该算法时间度量记作T(n)=O(f(n))=O(n3)时间困难度：O(n3)711.4算法和算法分析算法的时间