高等数据结构与算法

高等数据结构与算法第1页，共26页，2023年，2月20日，星期四教材：数据结构(C语言版)严蔚敏清华大学出版社参考书：数据结构——使用C语言朱战立西安交通大学出版社数据结构与算法齐德昱清华大学出版社数据结构与算法——C++版(第2版)AdamDrozdek清华大学出版社课程与考试安排：第8、11、12章不作要求有**号的小节不作要求期末成绩和平时成绩各占60％和40％第2页，共26页，2023年，2月20日，星期四第一章绪言1.1.1什么是数据结构程序设计=数据模型+算法程序设计：为计算机处理问题编制的一组指令集数据模型：现实问题的抽象算法：处理问题的策略数值计算问题——数学模型是一组线性或非线性的代数方程组或微分方程组非数字计算问题(包括管理、控制、数据处理等)——数学模型是数据结构第3页，共26页，2023年，2月20日，星期四例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表第4页，共26页，2023年，2月20日，星期四例2人机对奕问题树……..……..…...…...…...…...第5页，共26页，2023年，2月20日，星期四多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图第6页，共26页，2023年，2月20日，星期四数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科1.1.2为什么要学数据结构程序设计的需要计算机专业基础课编译程序、操作系统、数据库系统和大型应用程序第7页，共26页，2023年，2月20日，星期四1.1.3学什么掌握各种类型的数据结构掌握查找和排序操作学会用算法去处理问题学会用C语言去实现算法1.1.4怎么学重视实践环节，包括编程和上机第8页，共26页，2023年，2月20日，星期四1.2基本概念和术语数据(data)——所有能输入到计算机中去的描述客观事物的符号，数据是信息的载体数据元素(dataelement)——数据的基本单位，数据中的一个“个体”数据项(dataitem)——数据的最小单位，数据元素是数据项的组合，有组合项和原子项之分数据对象(dataobject)——性质相同的数据元素的集合，如整数、所有书目信息等数据结构(datastructure)——数据元素和数据元素关系的集合，数据元素相同而关系不同的数据结构是不同的数据结构第9页，共26页，2023年，2月20日，星期四根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图数据结构的形式定义为：数据结构是一个二元组

Data_Structures=(D,S)

其中：D是数据元素的有限集，

S是D上关系的有限集。第10页，共26页，2023年，2月20日，星期四数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系数据元素的实现数值"321"可用位串101000001表示，字母"A"可用位串001000001表示关系的实现第11页，共26页，2023年，2月20日，星期四元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储第12页，共26页，2023年，2月20日，星期四1536元素21400元素11346元素3∧元素41345h存储地址

存储内容

指针1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

链式存储

h第13页，共26页，2023年，2月20日，星期四不同的编程环境中，数据存储结构可有不同的描述方法：以上用的是计算机的编码及内存来描述还可用高级程序语言提供的数据类型来描述关系顺序存储结构

intLong_int[3];[链式存储结构

int

*Long_int[3];数据元素Long_int[0]=4234;第14页，共26页，2023年，2月20日，星期四1.3抽象数据类型数据类型(datatype)——一个值的集合和定义在此集合上的一组操作的总称抽象数据类型(abstractdatatype,ADT)——一个数学模型以及定义在此数学模型上的一组操作抽象不同语言不同处理器相同的数学特征（即已定义的数据类型）设计软件时自定义的数据类型ADT有两个重要特征：数据抽象：用ADT描述程序处理的实体时，强调的是其本质特征和外界使用它的方法数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节第15页，共26页，2023年，2月20日，星期四抽象数据类型包含定义、表示和实现三部分。抽象数据类型的形式描述为：

ADT=(D，S，P)

其中：D是数据对象，

S是D上的关系集，

P是D的基本操作集。typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;第16页，共26页，2023年，2月20日，星期四1.抽象数据类型的定义ADT形式定义为：

ADT

抽象数据类型名{

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

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

基本操作：基本操作的定义

}

ADT

抽象数据类型名

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

基本操作名

（参数表）

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

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

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。

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

"操作结果"说明了操作正常完成之后，数据结构的变化状况和应返回的结果。第17页，共26页，2023年，2月20日，星期四例：抽象数据类型"复数"的定义为：ADTComplex{

数据对象：D={e1,e2|e1,e2∈RealSet}

数据关系：R1={<e1,e2>|e1是复数的实部，e2是复数的虚部}

基本操作：

InitComplex(&Z,v1,v2)

操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)

初始条件：复数已存在。

操作结果：复数Z被销毁。

GetReal(Z,&realPart)

初始条件：复数已存在。

操作结果：用realPart返回复数Z的实部值。

GetImag(Z,&ImagPart)

初始条件：复数已存在。

操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)

初始条件：z1，z2是复数。

操作结果：用sum返回两个复数z1，z2的和值。

}ADTComplex第18页，共26页，2023年，2月20日，星期四2.抽象数据类型的表示和实现抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之谓固有数据类型）来实现。第19页，共26页，2023年，2月20日，星期四例：利用C语言实现的"复数"类型如下描述：

//

存储结构的定义

typedefstruct{

floatrealpart;

floatimagpart;

}complex;

//

基本操作的函数原型说明

voidAssign(complex&Z,floatrealval,floatimagval);

//

构造复数Z，其实部和虚部分别被赋以参数realval和imagval的值

voidadd(complexz1,complexz2,complex&sum);

//

以sum返回两个复数z1，z2的和

//

基本操作的实现

…………

voidadd(complexz1,complexz2,complex&sum)

{//

以sum返回两个复数z1，z2的和

sum.realpart=z1.realpart+z2.realpart;

sum.imagpart=z1.imagpart+z2.imagpart;

}

…………第20页，共26页，2023年，2月20日，星期四1.4算法的描述和算法分析简介算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性—算法的描述—采用类C语言算法的评价—衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量第21页，共26页，2023年，2月20日，星期四算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量

1.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣

2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适第22页，共26页，2023年，2月20日，星期四时间复杂度：基本操作重复执行的次数的阶数T(n)=O(f(n))，表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同例1：NXN矩阵相乘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];} 语句的频度：该语句重复执行的次数第23页，共26页，2023年，2月20日，星期四除特别指明，若算法的执行时间依赖于特定的输入，则按最坏情况考虑对时间复杂度而言，只需要取最高项，并忽略常数系数

voidbubble_sort(inta[],intn)

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

for(i=n-1,change=TRUE;i>1&&change;--i){

change=FALSE;

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{w=a[j];a[j]=a[j+1];a[j+1]=w;change=TRUE}

}

}//bubble_sort

算法执行次数随输入数据不同而不同，概率相等时考虑平均值，概率不明时考虑最坏情况。#include<stdio.h>main(){inta[11],i,j,t;p