数据结构-使用C语言 朱战立课件.pptVIP

教材：朱战立编著，数据结构——使用C语言（第3版），西安交通大学出版社，2003年;*;*;*;*;*;*;*;数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述;*;*;*;*;*;*;*;*;*;*;*;(5)抽象数据类型（Abstruct Data Type，简称ADT）：是指一个数学模型以及定义在模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。 (6)抽象数据元素：抽象定义的、没有实际含义的数据元素。 ;*;*;*;*;*;*;*;练习 1、设有数据逻辑结构为：line=(D,R);其中D={01，02，03，04，05，06}； R={r}； r={01，02，02，05,05,04,04,06,06,03}. 试分析数据结构属于哪种逻辑结构。 01-02-05-04-06-03 线性结构 ;2、设有数据逻辑结构为tree={D,R},其中D={01,02,03,04,05,06,07,08}; R={r}； r={01,02,01,03,01,04,02,05, 02,06,03,07,07,08}.试分析数据结构属于哪种逻辑结构. 树型 ;作业;;;*;*;*;*;队列的抽象数据类型定义 ADT Queue{数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D, i=1,2, …,n }?????????? 约定a1为队列头，an为队列尾。?? 基本操作：??? InitQueue( Q )????? 操作结果：构造一个空队列Q。??? DestroyQueue ( Q )????? 初始条件：队列Q已存在。????? 操作结果：销毁队列Q。 QueueLength( Q )????? 初始条件：队列Q已存在。????? 操作结果：返回Q的数据元素个数，即队列的长度。;*;*;有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。 确定性：每条指令必须有确切的含义 可行性：算法是能行得通的 必有输出 ;正确性：算???应当满足具体问题的需求 可读性：算法的可读性有利于人们对算法的理解 健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的结果。 效率与低存储需求：时间短，存储空间少（两者不能兼得）;1.3.3 算法效率的度量;时间复杂度 (time complexity);时间复杂度表示法 记作T(n)=O(f (n)) （称为大O表示法)，表示随问题规模n 的增大，算法执行时间的增长率和f(n) 的增长率相同。 时间复杂度往往不是精确的执行次数，而是估算的数量级，它着重体现的是随着问题规模n的增大，算法执行时间的变化趋势 时间复杂度的数量级 O (1) O (log2n) O (n ) O( nlog2n) O (n2) O (n3) O (2n) O (3n) O (n!) ;例如在下列三个程序段中： (a) x=x+1； (b) for(i=1;i=n;i++) x=x+1; (c) for(j=1;j=n;j++) for(k=1;k=n;k++) x=x+1; 基本语句均为 x=x+1; 程序段(a) 中频度为1，则T(n)= O(1)； 程序段(b)中频度为n，则T(n)= O(n)； 程序段(c)中频度为n2，则T(n)= O(n2)。;;加法规则 (针对并列程序段 ) T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m))) 乘法规则 (针对嵌套程序段) T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)) 算法1.1中既有并列程序段又有嵌套程序段 并列程序段： T(n) = O(max(n2,n))= O(n2) 嵌套程序段： T(n) = O(f (n)*g (n))= O(n2) ;有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如： Void bubble-sort(int a[