数据结构与数据库

数据结构与数据库第1页，共42页，2023年，2月20日，星期五第一部分

数据结构第2页，共42页，2023年，2月20日，星期五教材《数据结构（c语言版）》，严蔚敏等编著,清华大学出版社，1997《数据结构题集（c语言版）》，严蔚敏等编著,清华大学出版社，1999第3页，共42页，2023年，2月20日，星期五参考书《数据结构(第二版)》，唐策善、黄刘生编著，中国科大出版社，2001

"DataStructureswithC++",WilliawFordetal.,PrenticeHallInc.,1996."DataStructures&ProgramDesigninC,2ndEd.",RobertKruseetal.,PrenticeHallInc.,1997.

第4页，共42页，2023年，2月20日，星期五什么是数据结构基本概念和术语抽象数据类型算法分析性能分析与度量第一章绪论第5页，共42页，2023年，2月20日，星期五学生成绩表格第6页，共42页，2023年，2月20日，星期五选课单学号课程号时间成绩20001DS2000SX20002001,22000,9788720002ART2000DS20002002,22001,2689020003SX2000DS20002000,92001,2877820004SX2000ART20002000,92002,28976第7页，共42页，2023年，2月20日，星期五UNIX文件系统结构图/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第8页，共42页，2023年，2月20日，星期五综上，描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现.第9页，共42页，2023年，2月20日，星期五信息？数据？知识？

？第10页，共42页，2023年，2月20日，星期五基本概念和术语数据(Data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。

数值性数据非数值性数据第11页，共42页，2023年，2月20日，星期五数据元素（DataElement）数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成。数据项是数据的不可分割的最小单位。数据元素又称为元素、结点、记录第12页，共42页，2023年，2月20日，星期五数据项(DataItem)

学号姓名出生日期年月日籍贯年级系别宿舍号第13页，共42页，2023年，2月20日，星期五数据对象(DataObject)具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}字母字符数据对象

C={‘A’,‘B’,‘C’,…‘F’}第14页，共42页，2023年，2月20日，星期五数据结构（DataStructure）形式定义：

某一数据对象的所有数据成员之间的关系。记为：

Data_Structure={D,S}

其中，D是某一数据对象，S是该对象中所有数据成员之间的关系的有限集合。第15页，共42页，2023年，2月20日，星期五序偶:

一般来说，两个具有固定次序的客体组成一个序偶，常常表示两个客体之间的关系。记作<x,y>。其中的x和y分别称为第一元素和第二元素。如：“中国地处亚洲”表示为<中国，亚洲>序偶具有确定的次序。

<x,y>=<u,v>,iffx=u,y=v第一元素本身也可是一序偶。这样，序偶的概念可推广到n元组。

如:三元组可定义为一序偶<<x,y>,z>第16页，共42页，2023年，2月20日，星期五关系：任一序偶的集合确定了一个二元关系R，R中任一序偶<x,y>可记做xRy。例如，在实数中关系>

可记作

>={<x,y>|x,y是实数且x>y}

数据结构的一个例子（例1.5)Group=(P,R)

第17页，共42页，2023年，2月20日，星期五四类基本结构集合线性结构树形结构网状结构第18页，共42页，2023年，2月20日，星期五数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；从具体问题抽象出来的数据模型；与数据元素本身的形式、内容无关；与数据元素的相对位置无关。第19页，共42页，2023年，2月20日，星期五数据的逻辑结构分类线性结构

线性表非线性结构

树图（或网络）第20页，共42页，2023年，2月20日，星期五bindevetclibuser2114131211234678910315871011998745662313155线性结构树形结构

树二叉树二叉排序树第21页，共42页，2023年，2月20日，星期五堆结构123548711102916125643125436113318146651921图结构网络结构第22页，共42页，2023年，2月20日，星期五数据的存储结构数据结构在计算机中的表示（又称映象）。包括数据元素的表示和关系的表示。数据元素的表示:位串（元素、结点）关系的表示

顺序映象非顺序映象第23页，共42页，2023年，2月20日，星期五抽象数据类型（AbstractDataType）数据类型

定义：一个值的集合和定义在这个值集上的一组操作的总称。C语言中的基本数据类型

intcharfloatdoublevoid整型字符型浮点型双精度型无值第24页，共42页，2023年，2月20日，星期五抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作数据结构+定义在此数据结构上的一组操作=抽象数据类型例如：矩阵+（求转置、加、乘、 求逆、求特征值） 构成一个矩阵的抽象数据类型第25页，共42页，2023年，2月20日，星期五抽象数据类型的描述抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

ADT抽象数据类型名{

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

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

基本操作：〈基本操作的定义〉 }ADT抽象数据类型名第26页，共42页，2023年，2月20日，星期五其中,数据对象、数据关系用伪码描述；基本操作定义格式为 基本操作名（参数表） 初始条件：〈初始条件描述〉

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

抽象数据类型可以通过固有数据类型(高级编程语言中已实现的数据类型)来实现抽象数据类型类class数据对象数据成员基本操作成员函数(方法)在C++中，类的成分(数据成员和成员函数)可以有三种访问级别Private私有成分（只允许类的成员函数进行访问）

protected保护成分（只允许类的成员函数及其子孙类进行访问）public公有成分（允许类的成员函数、类的实例及其子孙类、子孙类的实例进行访问）第28页，共42页，2023年，2月20日，星期五算法和算法分析定义：为了解决某类问题而规定的一个有限长的操作序列。特性：有穷性算法在执行有穷步后能结束确定性每步定义都是确切、无歧义可行性每一条运算应足够基本输入有0个或多个输入输出有一个或多个输出第29页，共42页，2023年，2月20日，星期五算法设计例子：

选择排序问题：递增排序解决方案：逐个选择最小数据算法框架：

for(inti=0;i<n-1;i++){

//n-1趟 从a[i]检查到a[n-1];

若最小整数在a[k],交换a[i]与a[k];}细化：SelectSort第30页，共42页，2023年，2月20日，星期五voidselectSort(inta[],intn){

//对n个整数a[0],a[1],…,a[n-1]按递增顺序排序

for(inti=0;i<n-1;i++){ intk=i;

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

if(a[j]<a[k])k=j;//从a[i]查到a[n-1],找最小整数,在a[k]

inttemp=a[i];a[i]=a[k];a[k]=temp;}}

第31页，共42页，2023年，2月20日，星期五性能分析与度量算法的性能标准正确性可读性健壮性效率（时间、空间）第32页，共42页，2023年，2月20日，星期五算法的事后统计（后期测试）在算法中的某些部位插装时间函数time

(),

测定算法完成某一功能所花费时间

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;printf(”%d%d\n",n,runTime);第33页，共42页，2023年，2月20日，星期五intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索x

inti=0;

while(i<n&&a[i]!=x)

i++;

if(i==n)return

-1;

returni;}

第34页，共42页，2023年，2月20日，星期五算法的事前估计时间复杂度度量运行时间=算法中每条语句执行时间之和。每条语句执行时间=该语句的执行次数（频度）*语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。第35页，共42页，2023年，2月20日，星期五举例1矩阵相乘算法

for(i=1;i<=n;++i)//n+1for(j=1;j<=n;++j){//n(n+1)c[i][j]=0;//n2for(k=1;k<=n;++k)//n2(n+1)c[i][j]+=a[i][k]*b[k][j];//n3}

则算法执行时间T(n)为所有语句的频度之和。

T(n)=n+1+n(n+1)+…+n3

=2n3

+3n2+2n+1第36页，共42页，2023年，2月20日，星期五渐进时间复杂度

引入“O”记号，以体现随问题规模n的增长率。

T(n)=n+1+n(n+1)+…+n3

=2n3

+3n2+2n+1＝O(n3)，其中n3

为增长最快的项。最坏时间复杂度vs.平均时间复杂度

有时算法基本操作重复执行次数还随问题的输入数据集不同而不同（如一些排序算法）。这时可分析最坏时间复杂度（最坏情况下的时间复杂度）和平均时间复杂度（平均情况下的时间复杂度）第37页，共42页，2023年，2月20日，星期五

估计算法时间的通常做法：

根据问题（或算法类型），从算法中选取一种原操作（指固有数据类型的操作）作为基本操作。其重复执行次数应与算法执行时间成正比；一般为最深层循环内的语句中的原操作；用该基本操作重复执行的次数作为算法的时间度量。即统计包含该操作的所有语句的频度之和。如：上例中选取乘法为基本操作；算法执行时间T(n)则正比于乘法所在语句的