01 第1章 数据结构与算法绪论.pptx

第1页：数据结构与算法课程封面

数据结构与算法

第2页：GIS专业为什么要学数据结构

GIS专业为什么要学数据结构?

• 《数据结构》是计算机及其相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法
• 通俗地讲，GIS就是利用计算机技术手段来管理各种空间数据，并为各种分析决策提供科学依据和服务

第3页：空间数据比事务数据复杂

空间数据比一般的事务处理数据要复杂的多，例如

• 图书管理系统涉及的数据是图书信息，是结构化的数据
• 而GIS管理的空间数据，如DEM、矢量形式的点线面数据是比较复杂的，且是非结构化的并存在复杂的拓扑关系，要正确组织好复杂的空间数据是GIS数据库管理、各种算法设计的关键
• 今后从事GIS工作，无任是从事GIS底层开发、还是对GIS进行二次开发，都涉及到空间数据组织、算法与程序设计问题，而数据结构是解决这类问题的基础

第4页：课程对后续课程的支撑

开设本课程将为后续课程，尤其是空间数据结构与分析、地理信息系统工程、GIS二次开发等课程，打下理论和实践基础；为同学们提供必要的程序设计、数据分析等技能方面的训练，以便提高同学们在利用计算机解决数据处理方面的的抽象思维与逻辑推理能力、分析问题与解决问题能力，以及软件设计和编程能力

• 数据结构课程在地理信息系统专业中具有举足轻重的作用

第5页：本课程目的与教学安排

本课程目的：

• 掌握数据结构的概念与类型，掌握各种类型数据结构的定义、特点、存储结构、相关算法和应用实例
• 掌握算法的概念、描述方法及算法的性能分析方法
• 掌握各种内部排序算法课程类别：
• 专业基础课（必修）教学过程：
• 理论课时48学时+实验16学时

第6页：考核方式与教材

考核方式：

• （作业+实验报告+点名）+（闭卷考试）教材：
• 严蔚敏，吴伟民，数据结构（C语言版），清华大出版社，1997第1版参考文献：
• 李保春，数据结构习题与分析，清化大学出版社，
• 谭浩强，C语言，清华大学出版社
• 余绍军，数据结构，中南大学出版社
• ……

第7页：课程主要内容与章节

主要内容：第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第九章查找第十章内部排序

第8页：第一章绪论

第一章绪论

第9页：第一章内容提要

内容提要:

• 1.1什么是数据结构
• 1.2基本概念和术语
• 1.3抽象数据类型的表示与实现
• 1.4算法和算法分析

第10页：1.1什么是数据结构

1.1什么是数据结构

• 计算机的程序是对信息进行加工处理
• 信息包括事务处理信息、空间信息等方面
• 信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构要研究的内容

第11页：例1：书目自动检索系统

例1：书目自动检索系统作者名：分类号：出版单位：出版时间：价格：书目卡片登录号：书名：高等数学樊映川001002理论力学罗远祥S01L01003高等数学华罗庚S01004线性代数栾汝书S02……………………书目文件按书名按作者名按分类号001,…樊映川001，003……高等数学002,….华罗庚002，……..理论力学004,….栾汝书004，……线性代数…….…….……..……002,…L001,003,S…………索引表线性表

第12页：书目检索系统的线性结构特点

特点：

• 每本书的信息占据一行，所有书的信息按书号顺序依次排列构成一张表格；
• 表中每本书的信息依据书号的大小存在着一种前后关系，这就是我们所说的线性结构；
• 对它的操作通常是插入某本书的信息，删除某本书的信息，更新某本书的信息，按条件检索某本书的信息等等。

第13页：例2：人机对奕问题

例2：人机对奕问题树……..……..程朋根…...…...…...…...东华理工学院

第14页：人机对奕的树形结构特点

特点：

• 在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；
• 对它的操作有：建立树形结构，输出最低层结点内容等等。

第15页：例3：多叉路口交通灯管理

例3：多叉路口交通灯管理问题图CEDAB单行道交叉路口的一条通道相连的两条道路不能同时通行1号灯2号灯3号灯4号灯EAABACADBABCBDDADBDCEBECED

第16页：交通灯问题的图结构特点

特点：

• 用一个顶点来表示一条通道，而道路之间互相矛盾的关系以两个顶点之间的连线表示，即图结构；
• 设置交通灯的问题等价为对图的顶点染色问题，要求对图上的每个顶点染色，并且要求有连线的两个顶点不能具有相同的颜色，而总的颜色种类尽可能少（等待时间短）

第17页：例4：制定教学计划

华理工学院程朋根需要的先导课程编号课程名称课程编号无程序设计基础C1C1离散数学C2C1，C2数据结构C3C1汇编语言C4C3，C4算法分析与设计C5C11计算机组成原理C6C5，C3编译原理C7C3，C6操作系统C8无高等数学C9C9线性代数C10C9普通物理C11C9，C10，C1数值分析C12东例4：制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序；有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表

第18页：课程先后关系图

O课程先后关系的图形描形式：c1c9c4c2c10c11计算机专业必修课程开设先后关系c5c3c12c6c7c8

第19页：教学计划问题的图结构特点

特点

• 课程之间的先后关系用图结构描述；
• 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。

第20页：非数值性处理与数据结构

从上面的几个实例可以看出：

• 计算机的操作不再局限于单纯的数值计算（根据具体问题抽象数学模型、设计解算数学模型的算法、编程实现）
• 计算机的操作对象的关系更加复杂，更多地是对那些具有一定关系的数据进行组织管理，我们将此称为非数值性处理
• 要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点、在计算机中的表示方式以及各个操作的具体实现手段，这就是《数据结构》的主要内容

第21页：1.2基本概念和术语

1.2基本概念和术语

数据(Data)

是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。例如，整数、字符、图象、声音等

数据元素(DataElement)

是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位。例如，一本书的书目信息可以是一个数据元素，一个空间定位点的（X,Y,Z）坐标

第22页：数据对象与数据结构定义

数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N={0,1,2,3,…}

数据结构(DataStructure)

是相互之间存在一种或多种特定关系的数据元素的集合。DataStructure=(D,S)，其中，D是数据元素的有限集，S是D上关系的有限集

第23页：四种基本数据结构

四种基本数据结构

• 集合：数据元素间除“同属于一个集合”外，无其它关系
• 线性结构：一个对一个，如线性表、栈、队列
• 树形结构：一个对多个，如树
• 图状结构：多个对多个，如图

第24页：逻辑结构与存储结构

数据结构的两种形式

• 数据的逻辑结构：只抽象反映数据元素的逻辑关系
• 数据的存储（物理）结构：数据的逻辑结构在计算机存储器中的实现

第25页：顺序存储与链式存储结构

存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系

第26页：顺序存储结构示意图

元素1Lo元素2Lo+m……..Lo+(i-1)*m元素i……..Lo+（n-1)*m元素n存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储

第27页：链式存储结构示意图

13451536元素21400元素11346元素3∧元素4指针存储内容存储地址1400元素11345∧元素41346…….……..…….1536元素21400…….……..…….1346元素31536链式存储h

第28页：数据结构的三个方面

数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：

第29页：数据类型

数据类型（Datatype）：高级语言中指数据的取值范围及其上可进行的操作的总称。也可以是一个值的集合和定义在这个值集上的一组操作的总称。例如：C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;

第30页：抽象数据类型ADT

抽象数据类型（AbstractDatatype）：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示与实现无关。定义形式：抽象数据类型的定义由三元组来定义：(D,S,P)D是数据对象，S是D上的关系集，P是对D的基本操作集

第31页：ADT定义格式与示例

定义格式：ADT抽象数据类型名{数据对象：<数据对象定义>数据关系：<数据关系定义>基本操作：<基本操作定义>}ADT抽象数据类型名例如：ADTBox{floatx1,y1,x2,y2//数据元素（x1,y1）,(x2,y2)//数据关系，构成点对voidDraw();//基本操作voidDelete();voidMove(floatx,floaty);}

第32页：抽象数据类型分类

抽象数据类型分类：

• 原子类型(AtomicDataType):变量值不可再分，例如，int,float
• 固定聚合类型(Fixed-AggregateDataType):由确定数目的成分按某种结构组成，例如，Box
• 可变聚合类型(Variable-AggregateDataType):数的成分数目不定，例如，多边形点串
• 多型数据类型(PolymorphicDataType):值的成分不确定，例如，ElementSetE；E可以是数值，可以是字符；VirtualDraw()；虚拟函数Draw()可以是绘点、线或面

第33页：1.3类C语言描述约定

采用介于伪码和C语言之间的类C语言作为描述工具，是C的一个核心子集1）预定义常量及类型

• #define
• #define
• #define
• #define
• #defineTRUE1FALSE0OK1ERROR0OVERFLOW-12）数据元素被约定为ElemType类型，用户需要根据具体情况，自行定义该数据类型
• 1.3抽象数据类型的表示与实现

第34页：算法描述的函数形式

3）算法描述为以下的函数形式

• 函数类型函数名（函数参数表）{//算法说明语句序列；}
• 为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可；另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。

第35页：赋值语句形式

4）算法描述中使用的赋值语句形式有

• 简单赋值变量名=表达式；
• 串联赋值变量名1 =变量名2= ... =变量名n =表达式；
• 成组赋值（变量名1，...，变量名n）=（表达式1，...，表达式n）；
• 结构名=（值1，值2，...，值n）；
• 结构赋值结构名1=结构名2；
• 条件赋值变量名=条件表达式?表达式1：表达式2；
• 交换赋值变量名1变量名2；

第36页：选择结构语句形式

5）算法描述中使用的选择结构语句形式有

• 条件语句1if（表达式）语句；
• 条件语句2if（表达式）语句；else语句；
• 开关语句1switch（表达式）{case值1：语句序列1；break；case值2：语句序列2；break；...case值n：语句序列n；break；default：语句序列n+1；}

第37页：开关语句2形式

开关语句2switch{case条件1：语句序列1；break；case条件2：语句序列2；break；...case条件n：语句序列n；break；default：语句序列n+1；}

第38页：循环与结束语句形式

6）算法描述中使用的循环结构语句形式有

• for循环语句for（表达式1；循环条件表达式；表达式2）语句；
• while循环语句while（循环条件表达式）语句；
• do-while循环语句do{语句序列；}while（循环条件表达式）；7）描述算法中使用的结束语句形式有
• 函数结束语句return表达式；return;
• case或循环结束语句break;异常结束语句exit（异常代码）；

第39页：输入输出语句与扩展函数

7）算法描述中使用的输入输出语句形式有

• 输入语句scanf( [格式串]，变量名1，...，变量名n)；printf( [格式串]，表达式1，...，表达式n);方括号（[ ]）中的内容是可以省略的部分
• 输出语句8）在算法描述中使用的注释格式为
• 单行注释//文字序列9）在算法描述中可以使用的扩展函数有
• 求最大值max（表达式1，...，表达式n）；这个函数返回参数表中n个表达式计算结果中的最大值
• 求最小值min（表达式1，...，表达式n）；这个函数返回参数表中n个表达式计算结果中的最小值

第40页：算法实例：三个数排序

viodThree_Sort(int*x,int*y,int*z){

• //将x,y,z三个指针所指示的内容按从小到大的顺序重新排列
• if(*y<*x&&*y<*z)*x*y;
• //挑选出最小的数值并换到x指针所指的存储单元中
• elseif(*z<*x&&*z<*y)*x*z;
• if(*z<*y)*y*z;
• //在y和z所指示的存储单元中挑选出较小者换到y中
• }【算法实例】用类C描述将三个数值排序的算法

第41页：1.4算法和算法分析

1.4算法和算法分析

算法（Algorithm）

是指对特定问题求解步骤地一种描述。它是指令的有限序列，其中一条指令代表一个或多个操作。

第42页：算法的特性

算法的特性：

• 有穷性：当执行一个算法时，不论是何种情况，在经过了有限步骤后，这个算法一定要终止；
• 确定性：算法中的每条指令都必须是清楚的，指令无二义性；
• 可行性：每条指令都充分基本，原则上可由人仅用笔和纸在有限的时间内也能完成；
• 输入：具有0个或0个以上由外界提供的量；
• 输出：产生1个或多个结果。

第43页：算法设计的要求

算法设计的要求

• 正确性(Correctness):不存在语法错误，对合法数据都能得到合乎要求的结果；
• 可读性(Readability)：可读性好，有助于人的理解、调试和修改；
• 健壮性(Robustness)：输入非法数据时，能做出适当的反映，而不致产生莫名其妙的结果；
• 效率与低存储量：执行时间短，占用存储空间少。

第44页：算法效率的度量方法

算法效率的度量

• 方法:
• 事后统计的方法：依赖于计算机软、硬件环境
• 事前分析估计方法：从算法中选择一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行次数作为算法的时间度量
• 标准：
• 时间复杂度T(n)
• 空间复杂度S(n)

第45页：时间复杂度的基本操作

有关时间复杂度讨论

• 基本操作的原操作
• 应该是执行次数和算法的执行时间成正比例的原操作
• 多数情况下它是最深层循环内的语句中的原操作
• 例如：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];}O原操作是:c[i][j]+=a[i][k]*b[k][j];

第46页：时间复杂度的统计方法

统计方法

• 有时只选择一种基本操作来讨论算法的时间复杂度
• 有时可以同时考虑几种基本操作，并对不同操作赋予不同的权
• 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同，例如，冒泡法排序，当序列的初始集为自小到大有序时，基本操作执行次数为零；当序列的初始集为自大到小排列时，基本操作执行次数为:n(n-1)/2,对此可以采用平均值的方法
• 更为常用的方法是采用最坏情况的时间复杂度

第47页：例1：矩阵乘法时间复杂度

例１：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];}

• 由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3
• 时间复杂度为T(n) =O(n3)

第48页：例2：二重循环语句频度

例2：for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}

• 语句频度为：f(n)=2n2
• 其时间复杂度为：O(n2)，即时间复杂度为平方阶

第49页：例3：冒泡法排序时间复杂度

例3：冒泡法排序Voidbubble-sort(inta[]，intn){for(i=n-1;change=TURE;i>1&&change;--i){change=false;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE}}}

• 最好情况：0次(正序排列，比较n-1次，交换0次)
• 最坏情况：1+2+3+…+n-1=n(n-1)/2
• 平均时间复杂度为：O(n2)

第50页：例4：对数阶时间复杂度

例4：分析以下程序的时间复杂度i=1while(i<=n)i=i*2①②

• 本段程序语句①的频度是1，设语句②的频度为f(n)，则有2f(n)<=n，即f(n) <= log2n
• 该段程序的时间复杂度为：T(n)=1+f(n)=1+log2n=O(log2n)

第51页：例5：累加循环时间复杂度

例5：分析以下程序的时间复杂度i=s=0while(s<n){i++;s+=i;}

• 本段程序的基本操作是while，设语句while的频度为T(n)，则有:s=1+2+3+…+T(n) <n，即222nO(n)T2(n)T2(n)T(n)2nT(n)T(n)(1T(n)nn（1T(n))*T(n)T2(n)T(n)n)
• 该段程序的时间复杂度为：O(

第52页：例6：双层循环m的值

例6：设n为偶数，试计算运行下列程序段后m的值，给出该程序的时间复杂度m=0for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;解：外循环i=1时，内循环j从2到n，语句m++执行n-2+1次外循环i=2时，内循环j从4到n，语句m++执行n-4+1次……外循环i=n/2时，内循环j从n到n，语句m++执行n-n+1次当i>n/2时，内循环不执行实际上m的值就是内循环执行的次数m(n1)(n3)(n5)...1(共n/2项)O(n2)422((n1)1)n2n

第53页：本章重点

本章重点：

• 掌握数据结构定义、类型
• 抽象数据类型概念与描述
• 算法概念、算法特性与衡量标准并能分析各种算法的时间复杂度

第54页：习题（一）

习题：

• 1、数据结构课程是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的科学。
• 2、数据结构含义是相互之间存在一种或多种特定关系的数据元素的集合。
• 3、数据结构的形式定义为（D,S），其中S是数据元素的集合，S是D上的关系的集合。
• 4、数据结构的类型通常分为：集合、线性结构、树形结构、图状结构或网状结构；从逻辑上可以把它们分成：线性结构和非线性结构

第55页：习题（二）

5、数据的逻辑结构只抽象反映数据元素的逻辑关系；数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现

• 6、算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是空间复杂度和时间复杂度
• 7、计算机算法是解决问题的有限运算序列，它必须具备输入、输出、确定性、有穷性和稳定性等5个方面的特性
• 8、线性结构中元素之间的关系存在一对一关系，树形结构中元素之间的关系存在一对多关系，图形结构中元素之间的关系存在多对多关系

第56页：问答题：算法与算法评价

9、什么是算法？算法的主要特点是什么？10、如何评价一个算法？

第57页：

第58页：时间复杂度分析例题图

i=1While(i<=n)i=i*2本段程序①②③③④⑤⑥⑦⑧⑨⑩