绪论学时精要.pptx

数据结构网工13级;课程学时安排;;;答疑安排;数据结构;;讲课主要内容;第1章 绪 论;背景;数据结构课程需要研究的问题;; ;例1：电话号码查询系统;例2：磁盘目录文件系统 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推： 本问题是一种典型的树型结构问题，如图1-2 ，数据与数据成一对多的关系，是一种典型的非线性关系结构—树形结构。;例3：交通网络图 从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。;;实际例子;;举例;;元素之间的基本逻辑结构关系;;请尝试上面的关系图画出来;逻辑结构与物理结构;;顺序存储结构与链式存储结构; 例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ，两种不同的存储结构。 顺序结构：数据元素存放的地址是连续的； 链式结构：数据元素存放的地址是否连续没有要求。 ;数据结构的三个组成部分 逻辑结构： 数据元素之间逻辑关系的描述 存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。 数据操作： 对数据要进行的运算。 本课程中将主要讨论的三种逻辑结构（线性结构、树结构、图结构）所采用的存储结构（如图1-4所示）及操作运算。;;; 数据类型(Data Type)：指的是一个值的集合和定义在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。 在C语言中数据类型有：基本类型和构造类型。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。; 数据结构的主要运算包括： ⑴ 建立(Create)一个数据结构； ⑵ 消除(Destroy)一个数据结构； ⑶ 从一个数据结构中删除(Delete)一个数据元素； ⑷ 把一个数据元素插入(Insert)到一个数据结构中； ⑸ 对一个数据结构进行访问(Access)； ⑹ 对一个数据结构(中的数据元素)进行修改(Modify)； ⑺ 对一个数据结构进行排序(Sort)； ⑻ 对一个数据结构进行查找(Search)。;;; 初始条件：描述操作执行之前数据结构和参数应满足的条件;若不满足，则操作失败，返回相应的出错信息。 操作结果：描述操作正常完成之后，数据结构的变化状况和 应返回的结果。;;1.4.1 算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下五个特性 ① 有穷性： 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ② 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 ③ 可行性： 一个算法是能被执行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。 ④ 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 ⑤ 输出： 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 ;;① 正确性(Correctness )： 算法应满足具体问题的需求。 ② 可读性(Readability)： 算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。 ③ 健壮性(Robustness)： 算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。 通用性(Generality)： 算法应具有一般性 ，即算法的处理结果对于一般的数据集合都成立。 ⑤ 效率与存储量需求： 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。;; 算法效率相关因素有： 依据算法选用何种策略； 问题的规模； 程序设计的语言； 编译程序所产生的机器代码的质量； 机器执行指令的速度； 撇开软硬件等有关部分因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用n表示），或者说，它是问题规模的函数。;;;;;;;;;;第1章 绪论习题 ;⑴ Sum1( int n ) { int p=1, sum=0, m ; for (m=1; m=n; m++) { p*=m ; sum+=p ; } return (sum) ; }