《绪论(网络版)》由会员分享，可在线阅读，更多相关《绪论(网络版)（70页珍藏版）》请在金锄头文库上搜索。
1、 2007-2008学年第二学期上课安排n上课时间： 第1周开始，星期二第3大节信息楼 3006n学时安排： 课堂教学：24学时 上机实验：8学时（课内）n主讲教师： 信息科学技术学院：高飞教学参考书、实验及考试n教 材：C+与数据结构北京理工大学出版社 高飞等编著n实验教材：C+与数据结构实验教程 北京理工大学出版社 苏京霞等编著n上机环境：Visual C+ 6.0n考试成绩:上机20%，期末80%。教学目标n建立数据结构的基本概念，掌握常见的处理 非数值问题的算法。n提高编程能力。n能够完成一般问题的算法设计，为今后使用 计算机解决本专业实际问题奠定基础。对学生的要求n保持课堂纪律，可以
2、自主选择适合自己的学 习方式进行学习。n听课请不要迟到，课上不要影响其他同学。n独立完成上机实验。学习建议n上课认真听讲，课后看书复习，多上机多编 程多练习。适当增加课外上机时间。n掌握有效的学习方法：n学习算法的基本思想，掌握如何将现实世界中的 问题抽象为计算机内部的描述，设计并描述出高 效的算法。n通过编程实现，将描述的算法变为实际的程序。n提前复习C+程序设计中的相关内容。让 我 们 开 始 吧 一、什么是数据结构二、基本概念和术语主要内容：三、抽象数据类型四、算法和算法分析一、什么是数据结构Algorithm + Data Structures = Programs程序设计:算法: 数
3、据结构: 为计算机处理问题编制一组指令集 处理问题的策略 问题的数学模型结构静力分析计算 例如: 数值计算的程序设计问题 线性代数方程组 环流模式方程(球面坐标系)全球天气预报 非数值计算的程序设计问题例一: 求一组(n个)整数中的最大值算法: ?模型： ？基本操作是“比较两个数的大小”取决于整数值的范围例二：计算机对弈算法：?模型：?对弈的规则和策略棋盘及棋盘的格局例三：足协的数据库管理算法：?模型：?需要管理的项目？如何管理？ 用户界面？各种表格概括地说：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。二、基本概念和术语所有能被输入
4、到计算机中，且能被 计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的 符号表示形式。是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个运动员的数据元素可以是称之为组合项年 月 日姓名俱乐部名称出生日期参加日期职务业绩数据结构： 带结构的数据元素的集合假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。3214,6587,9345 a1(3214),a2(6587),a3(9345)则在数据元素 a1、a2 和 a3 之间存在着 “次序”关系 a1,a2、a2
5、,a33214，6587，9345 a1 a2 a3 6587，3214，9345a2 a1 a3例如:又例，在2行3列的二维数组a1, a2, a3, a4, a5, a6中六个元素之间 存在两个关系:a1 a2 a3a4 a5 a6 行的次序关系:列的次序关系: col = ,a1 a3 a5a2 a4 a6 a1 a2 a3 a4 a5 a6数据结构： 带结构的数据元素的集合row = ,再例，在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系:| i=1, 2, 3, 4, 5或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据结构
6、： 带结构的数据元素的集合可见，不同的“关系”构成不同的“结构”逻辑结构和物理结构(存储结构)对每种数据结构，主要讨论如下两方 面的问题：1) 数据的逻辑结构，数据结构的基 本操作2) 数据的存储结构，数据结构基本 操作的实现逻辑结构和物理结构(存储结构) 数据结构定义中的关系描述的是数据 元素之间的逻辑关系，因此，又称为 数据的逻辑结构。n数据结构在计算机中的表示称为数据的物理结构，又称为存储结构，它包括数据元素的表示和关系的表示。数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构n线性结构 学生基本情况登记表，记录了每个学生的学号、姓名、 专业、政治面貌，记录按学生的学号顺序
7、排列。001003002004006005008007学生间学号顺序关系 是一种线性结构关系线性结构：除第一个元 素和最后一个元素外， 其他元素都有且仅有一 个直接前趋，有且仅有 一个直接后继。学号 姓名 专业 政治面貌 001王洪 计算机 党员 002 孙文 计算机 团员 003谢军 计算机 团员 004李辉 计算机 团员 005沈祥福 计算机 党员 006余斌 计算机 团员 007巩力 计算机 团员 008孔令辉 计算机 团员n树形结构 假设某家族有10个成员A、B、C、D、E、F、G、H、I、 J，他们之间的血缘关系可以用图表示。JIACBDHGFE树形结构：每一个元素只有一个直接前趋，
8、 有0个或多个直接后继。n图形结构工程进度图。图形结构：每一个元素可以有0个或多个直 接前趋，有0个或多个直接后继。V1V0V2V3V4V5V6数据结构的表示 图示表示图示表示是由顶点和边构成的图，其中顶 点表示数据，边表示数据之间的结构关系。 二元组表示二元组表示是用一个二元组（D，S）表示 数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。例：学生基本情况表的二元组表示（D，S ）001003002004006005008007D = 001，002，003，004，005，006，007，008 S = R R = , , , , , , 例：家族树的二元组表示（D，S）D
9、= A，B，C，D，E，F，G，H，I，J S = R R = , , , , , , , , JIACBDHGFE数据的存储结构 逻辑结构在存储器中的映象“数据元素”的映象 ？“关系”的映象 ？数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10 = (501)8 = (101000001)2A = (101)8 = (001000001)2关系的映象方法：（表示x, y的方法） 数据元素之间的关系在计算机中有两种不同的 表示方法:顺序映象和非顺序映象。1 顺序映象 对应的存储结构：顺序存储结构。 顺序映象的特点是借助元素在存储器中的相对位置 来表示数据元素之间的逻辑关系
10、。 2 非顺序映象 对应的存储结构：链式存储结构。 非顺序映象的特点是借助指示元素存储地址的指针 表示数据元素之间的逻辑关系。（表示x, y的方法）顺序映象 以相对的存储位置表示后继关系例如:令 y 的存储位置和 x 的存储位置 之间差一个常量 C而 C 是一个隐含值，整个存储结构中只 含数据元素本身的信息x y关系的映象方法：链式映象以附加信息(指针)表示后继关系需要用一个和 x 在一起的附加信息 指示 y 的存储位置y xn数据的存储结构 逻辑结构：从操作对象抽象出来的数学模型。 存储结构：逻辑结构在计算机中的表示。n常见的存储结构 顺序存储结构，链式存储结构。n顺序存储结构：借助元素在存
11、储器中的相对位置来表 示数据元素之间的逻辑关系（一维数组描述）。n链式存储结构：借助指示元素存储地址的指针来表示 数据元素之间的逻辑关系（指针类型描述）。n注意：算法的设计取决于所选定的逻辑结构，算法的 实现则依赖于采用的存储结构。n顺序存储结构元素n元素i元素2元素1LoLo+CLo+(i-1)*CLo+（n-1)*C存储地址存储内容Loc(元素i) = Lo +（i-1) * Cn链式存储结构1536元素21400元素11346元素3 元素41345 h存储地址 存储内容 指针1345 元素1 14001346 元素4 . .1400 元素2 1536. .1536 元素3 1346 数据
12、结构研究的主要内容 逻辑结构 研究数据之间固有的客观联系 存储结构 研究数据在计算机内部的存储方法 算法 研究如何在数据的各种结构（逻辑的和物理的）上实施有效的操作或处理1 数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。三、抽象数据类型例如，C 语言中提供的基本数据类型有:整型 int浮点型 float字符型 char逻辑型 bool （ C+语言）双精度型 double实型（ C+语言）数据类型 是一个 值的集合和定义在此集合上的 一组操作的总称。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。2 抽象数据类型是指一个
13、数学模型以及定义在此数学模型上的一组操作。抽象数据类型 有两个重要特征:数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成 的功能以及它和外部用户的接口（即外 界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D 是数据对象；S 是 D 上的关系集；P 是对 D 的基本操作集。 四、算法和算法分析 1 算法算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：（1）有穷性 （2）确定性 （3）可行性（4）有输入 （5）有输出（
14、1）有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即： 算法中的每个步骤都能在有限时间内完成 。（2）确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算 法的执行者或阅读者都能明确其含义及如 何执行。并且在任何条件下，算法都只有 一条执行路径。（3）可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操 作运算有限次实现之。（4）有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输 入量需要在算法执行过程中输入，而有的 算法表面上可以没有输入，实际上已被嵌 入算法之中。（5）有输出 它是一组与“输入”有确 定关系的量值，是算法进行信息加
15、工 后得到的结果，这种确定关系即为算 法的功能。2 算法设计的原则设计算法时，通常应考虑达到以下目标：（1）正确性（2）可读性（3）健壮性（4）高效率与低存储量需求（1）正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出 满足要求的结果；c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足 要求的结果；通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。d程序对于一切合法的输入数据都能得出满足要求的结果；（2） 可读性算法主要是为了人的阅读与交流，其次才是为
16、计算机执行，因此算法应该易于人的理解；晦涩难读的程序易于隐藏较多错误而难以调试。（3）健壮性当输入的数据非法时，算法应当恰当地作出反应或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。（4）高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。3 算法效率的衡量方法和准则 通常有两种衡量算法效率的方法:事前分析估算法缺点：1必须执行程序2其他因素掩盖算法本质事后统计法和算法执行时间相关的因素：（1）算法选用的策略（2）问题的规模（3）编写程序的语言（4）编译程序产生的机器代码的质量（5）计算机执行指令的速度一个特定算法的“
