2003-2004(夏)9 讲陈光喜 ●数据结构类型:线性结构,非线性结构 ●线性结构:1)有且仅有一个根结点2)每个结点 最多只有一个根前件一个后件 两种不同的存储结构:顺序存储结构和链式 存储结构 ●顺序存储结构用数据元素在存储器中的相对 位置来表示数据元素之间的逻辑关系。 ●链式存储结构:在每一个数据元素中增加 个存放地址的指针,用此指针来表示数据元素 之间的逻辑关系
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 数据结构类型: 线性结构，非线性结构。 ⚫ 线性结构: 1)有且仅有一个根结点 2)每个结点 最多只有一个根前件一个后件 ⚫ 两种不同的存储结构：顺序存储结构和链式 存储结构 ⚫ 顺序存储结构:用数据元素在存储器中的相对 位置来表示数据元素之间的逻辑关系。 ⚫ 链式存储结构：在每一个数据元素中增加一 个存放地址的指针，用此指针来表示数据元素 之间的逻辑关系
2003-2004(夏)9 陈光喜 ●数据类型:在一种程序设计语言中,变量所具 有的数据种类。 ●例如C语言,变量的数据类型有基本类型(整型 浮点型、字符型和构造类型(数、结构、 联合、指针、枚举型、自定义) ●数据对象:某种数据类型元素的集合。 ●例如整数的数据对象是{…-3,2,-1,0,1, 2,3,,}英文字符类型的数据对象是{A,B, C,D,E,F,…}
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 数据类型：在一种程序设计语言中，变量所具 有的数据种类。 ⚫ 例如C语言，变量的数据类型有基本类型 (整型、 浮点型、字符型)和构造类型(数组、结构、 联合、指针、枚举型、自定义) ⚫ 数据对象：某种数据类型元素的集合。 ⚫ 例如:整数的数据对象是{…-3，-2，-1，0，1， 2，3，…} 英文字符类型的数据对象是{A，B， C，D，E，F，…}
2003-2004(夏)9 讲陈光喜 1.3算法与分析 ●算法:是对特定问题求解步骤的一种描述 算法是有限长的操作序列 ●算法具有以下五个特性: ●1有穷性一个算法必须总是在执行有穷步之后 结束,且每一步都在有穷时间内完成 ●2确定性算法中每一条指令必须有确切的含义 不存在二义性。且算法只有一个入口和一个出口 ●3可行性一个算法是可行的。即算法描述的操作 都是可以通过已经实现的基本运算执行有限次来 实现的
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 算法：是对特定问题求解步骤的一种描述 算法是有限长的操作序列 ⚫ 算法具有以下五个特性： ⚫ 1有穷性 一个算法必须总是在执行有穷步之后 结束，且每一步都在有穷时间内完成。 ⚫ 2确定性 算法中每一条指令必须有确切的含义。 不存在二义性。且算法只有一个入口和一个出口。 ⚫ 3可行性 一个算法是可行的。即算法描述的操作 都是可以通过已经实现的基本运算执行有限次来 实现的。 1.3 算法与分析
2003-2004(夏)9 陈光喜 4输入一个算法有零个或多个输入,这些输入 取自于某个特定的对象集合。 ●5输出一个算法有一个或多个输出,这些输出 是同输入有着某些特定关系的量 1.3.2算法设计的要求 ●(1)正确性( orrectness)算法应满足具体问题 的需求。 ●(2)可读性( Readability)算法应该好读。以有利 于阅读者对程序的理解。 (3)健状性( Robustness)算法应具有容错处理 当输入非法数据时,算法应对其作出反应,而 不是产年莫名其妙的输出结果
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 4 输入 一个算法有零个或多个输入，这些输入 取自于某个特定的对象集合。 ⚫ 5 输出 一个算法有一个或多个输出，这些输出 是同输入有着某些特定关系的量。 ⚫ 1.3.2 算法设计的要求 ⚫ (1) 正确性(Correctness ) 算法应满足具体问题 的需求。 ⚫ (2)可读性(Readability) 算法应该好读。以有利 于阅读者对程序的理解。 (3)健状性(Robustness) 算法应具有容错处理。 当输入非法数据时，算法应对其作出反应，而 不是产年莫名其妙的输出结果
2003-2004(夏)9 陈光喜 ●(4)效率与存储量需求效率指的是算法执行的 时间;存储量需求指算法执行过程中所需要的 最大存储空间。一般,这两者与问题的规模有 关 133算法的复杂度 ●算法分析可分成两个阶段进行,即事先分析和 事后测试 ●事先分析求出该算法的一个时间界限函数 ●事后测试收集此算法的执行时间和实际占用 空间的统计资料 定义:如果存在两个正常数c和n,对于所有的 n≡no, 有|fn)|sclg(n) ●则记作f(n)=O(g(n
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ (4)效率与存储量需求 效率指的是算法执行的 时间；存储量需求指算法执行过程中所需要的 最大存储空间。一般，这两者与问题的规模有 关。 ⚫ 1.3.3 算法的复杂度 ⚫ 算法分析可分成两个阶段进行，即事先分析和 事后测试 ⚫ 事先分析 求出该算法的一个时间界限函数 ⚫ 事后测试 收集此算法的执行时间和实际占用 空间的统计资料。 ⚫ 定义：如果存在两个正常数c和n0，对于所有的 n≧n0，有︱f(n) ︳≦c｜g(n) ︳ ⚫ 则记作 f(n)=O(g(n))