数据结构教学课件市公开课金奖市赛课一等奖课件

1、信息物理工程学院测绘所 宋迎春电话箱：csusyc数据结构退出第1页数据结构:考评方式： 出勤 + 作业 + 测验第2页 开设本课程背景 数据结构是计算机相关专业一门主要专业基础课。它主要研究计算机加工对象逻辑结构、在计算机中表示形式以及实现各种基本操作算法。它是学习操作系统、编译原理、数据库原理等计算机专业关键课程基础，掌握好这门课程内容，是学习计算机其它相关课程必备条件。第3页 本课程讲述主要内容 本课程将分别讲述数据结构基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。 学习本课程基本方法l上课认真听讲； l仔细阅读教材中大量例题，

2、从而体会并最终掌握数据结构中基本概念； l独立完成每个章节后面练习题。第4页第1章 数据结构基础概论 本章主要介绍以下内容 数据结构研究主要内容 数据结构中包括基本概念 算法概念、描述方法以及评价标准第5页 1.1 数据结构研究主要内容 1.2 基本概念和术语 1.3 算法第6页1.1 数据结构研究主要内容 当今计算机应用特点： l所处理数据量大且含有一定关系； l对其操作不再是单纯数值计算，而更多地是需要对其进行组织、管理和检索。 应用举例1学籍档案管理 假设一个学籍档案管理系统应包含以下表1-1所表示学生信息。第7页表1-1第8页 特点： l每个学生信息占据一行，全部学生信息按学号次序依次

3、排列组成一张表格； l表中每个学生信息依据学号大小存在着一个前后关系，这就是我们所说线性结构； l对它操作通常是插入某个学生信息，删除某个学生信息，更新某个学生信息，按条件检索某个学生信息等等。 应用举例2输出n个对象全排列 输出n个对象全排列能够使用下列图1-1所表示形式描述。第9页图 1-1 3个对象全排列过程第10页 特点： l在求解过程中，所处理数据之间含有层次关系，这是我们所说树形结构； l对它操作有：建立树形结构，输出最低层结点内容等等。 应用举例3制订教学计划 在制订教学计划时，需要考虑各门课程开设次序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其它课程先导课程。比如

4、，计算机专业课程开设情况以下表1-2所表示：第11页表1-2第12页课程先后关系图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图 1-2 计算机专业必修课程开设先后关系第13页 特点 l课程之间先后关系用图结构描述； l经过实施创建图结构，按要求将图结构中顶点进行线性排序。 结论 计算机操作对象关系愈加复杂，操作形式不再是单纯数值计算，而更多地是对这些含有一定关系数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须搞清楚这些操作对象特点，在计算机中表示方式以及各个操作详细实现伎俩。这些就是数据结构这门课程研究主要内容。第14页1.2

5、 基本概念和术语 数据 是对客观事物符号表示。在计算机科学中其含义是指全部能够输入到计算机中并被计算机程序处理符号集合。 数据元素 是数据集合中一个实体，是计算机程序中加工处理基本单位。第15页 数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念多方面信息。 数据结构 简单地说，就是相互之间存在一个或各种特定关系数据元素集合。常见数据结构有：线性结构、树形结构和图形结构。 逻辑结构 数据结构中所说“关系”实际上是指数据元素之间逻辑关系，又称此为逻辑结构。第16页 存放

6、结构（物理结构） 是指数据结构在计算机存放器中详细实现。与孤立数据元素表示形式不一样，数据结构中数据元素不但要表示其本身实际内容，还要表示清楚数据元素之间逻辑结构。 常见存放结构 次序存放结构：特点是借助于数据元素相对存放位置来表示数据元素之间逻辑结构； 链式存放结构：特点是借助于指示数据元素地址指针表示数据元素之间逻辑结构。第17页1.3 算法 1.3.1 算法概念 算法是处理某个特定问题一个方法或一个过程。 计算机对数据操作能够分为数值性和非数值性两种类型。在数值性操作中主要进行是算术运算；而在非数值性操作中主要进行是检索、排序、插入、删除等等。第18页 设计算法基本过程 l经过对问题进行

7、详细地分析，抽象出对应数学模型； l确定使用数据结构，并在此基础上设计对此数据结构实施各种操作算法； l选取某种语言将算法转换成程序； l调试并运行这些程序。第19页 算法应该含有以下五个特征 （1）有穷性：一个算法必须在执行有穷步之后结束。 （2）确定性：算法中每一步，必须有确切含义，在他人了解时不会产生二义性。 （3）可行性：算法中描述每一步操作都能够经过已经有基本操作执行有限次实现。 （4）输入：一个算法应该有零个或多个输入。 （5）输出：一个算法应该有一个或多个输出。这里所说输出是指与输入有某种特定关系量。第20页 举例 问题：按从小到大次序重新排列x，y，z三个数值内容。 算法： （

8、1）输入x，y，z三个数值； （2）从三个数值中挑选出最小者并换到x中； （3）从y，z中挑选出较小者并换到y中； （4）输出排序后结果。第21页 1.3.2 算法描述 选择算法描述语言准则 （1）该语言应该含有描述数据结构和算法基本功效； （2）该语言应该尽可能地简捷，方便于掌握、了解； （3）使用该语言描述算法应该能够比较轻易地转换成任何一个程序设计语言。 “类C”描述语言是经过对C语言进行精心筛选保留一个关键子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言描述功效。第22页 1. 预定义常量及类型 #define TRUE 1 #define FALSE 0 #define O

9、K 1 #define ERROR 0 #define OVERFLOW -1 数据元素被约定为EntryType 类型，用户需要依据详细情况，自行定义该数据类型。第23页 2. 算法描述为以下函数形式： 函数类型 函数名（函数参数表） 语句序列； 为了简化函数书写，提升算法描述清楚度，我们要求除函数参数表中参数需要说明数据类型外，函数中使用局部变量能够不做变量说明，必要时给出对应注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解良好习惯。第24页 3. 在算法描述中能够使用赋值语句形式有： 简单赋值 变量名 = 表示式； 串联赋值 变量名1 = 变量名2 = . = 变量名n =

10、表示式； 成组赋值 （变量名1，.，变量名n）=（表示式1，.，表示式n）； 结构赋值 结构名1 = 结构名2； 结构名 =（值1，值2，.，值n）； 条件赋值 变量名 = 条件表示式 ? 表示式1：表示式2； 交换赋值 变量名1 变量名2；第25页4. 在算法描述中能够使用选择结构语句形式有：条件语句1 if （表示式） 语句；条件语句2 if （表示式） 语句； else 语句；开关语句1 switch （表示式） case 值1：语句序列1；break； case 值2：语句序列2；break； . case 值n：语句序列n；break； default：语句序列n+1； 第26页开关

11、语句2 switch case 条件1：语句序列1；break； case 条件2：语句序列2；break； . case 条件n：语句序列n；break； default：语句序列n+1； 第27页 5. 在算法描述中能够使用循环结构语句形式有： for循环语句 for （表示式1；循环条件表示式；表示式2） 语句； while循环语句 while （循环条件表示式） 语句； do-while循环语句 do 语句序列； while （循环条件表示式）； 6. 在描述算法中能够使用结束语句形式有： 函数结束语句 return 表示式； return; case或循环结束语句 break; 异常

12、结束语句 exit（异常代码）； 第28页 7. 在算法描述中能够使用输入输出语句形式有： 输入语句 scanf( 格式串，变量名1，.，变量名n)； 输出语句 printf( 格式串，表示式1，.，表示式n); 方括号（ ）中内容是能够省略部分。 8. 在算法描述中使用注释格式为： 单行注释 /文字序列 9. 在算法描述中能够使用扩展函数有： 求最大值 max（表示式1，.，表示式n）；这个函数返回参数表中n个表示式计算结果中最大值。 求最小值 min（表示式1，.，表示式n）；这个函数返回参数表中n个表示式计算结果中最小值。第29页 【算法1-1】用类C描述将三个数值排序算法。 viod

13、Three_Sort( int *x,int *y,int *z) /将x,y,z三个指针所指示内容按从小到大次序重新排列 if (*y*x&*y*z) *x*y; /挑选出最小数值并换到 x指针所指存放单元中 else if (*z*x&*z*y) *x*z; if (*z*y) *y*z; /在y和z所指示存放单元中挑选出较小者换到y中 第30页 1.3.3 算法评价 算法评价标准 (1) 正确性：要求算法能够正确地执行预先要求功效，并到达所期望性能要求。 (2) 可读性：为了便于了解、测试和修改算法，算法应该含有良好可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、读取文件统计、分配内存空间等操作结果检测，并经过与用户对话形式做出对应处理选择。 (4) 时间与空间效率：算法时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费时间及所占据空间度量。第31页 算法时间效率 算法时间效率主要由两个原因决定： l所需处理问题数据量大小，数据量大，所花费时间就多； l在处理问题过程中，基本操作执行次数。时间特征分析 假如我们将一个算法所花费时间设计成