d01-数据结构.ppt

第 * 页 1.4 算法与算法分析：算法的空间复杂度 void bubble_sort (int a[ ], int n ) { //起泡排序 for (i = n-1,change=TRUE; i 0change; - -i ) { change= FALSE; for ( j = 0; j= i; ++j ) if ( a[j] a[ j+1] ) { temp = a[j]; a[j]= a[ j+1]; a[j+1]=temp; change = TRUE; } } } S(n) = O(1) 第 * 页 数据的逻辑结构 数据的存储结构 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队列 树形结构 图形结构 数据结构：带有结构和操作的数据元素集合 绪论—必须掌握的基本概念 散列存储 索引存储 结构 操作 数据操作的定义（功能） 数据操作的实现(在计算机上) 算法效率 * * * 注意：算法的设计取决于所选定的逻辑结构，算法的实现则依赖于采用的存储结构。 * 注意：算法的设计取决于所选定的逻辑结构，算法的实现则依赖于采用的存储结构。 * 注意：算法的设计取决于所选定的逻辑结构，算法的实现则依赖于采用的存储结构。 * 注意：算法的设计取决于所选定的逻辑结构，算法的实现则依赖于采用的存储结构。 * 注意：算法的设计取决于所选定的逻辑结构，算法的实现则依赖于采用的存储结构。 * * * * * * 一个应用问题，如果你所设计的算法不能在用户可以忍受的时间内结束。否则你所编的算法就没有意义。 O(logn)、 O(n) O(nlog n)：快速排序 O(nlog n)：快速排序 O(n2)：冒泡排序 如：HANIO问题：的递归算法执行时间是指数级的2n,这里n是需要搬动的盘子数。当n多大运行时间 程序段功能：依次求出给定数组的所有子数组中各元素之和。即：求a[0]+a[1]; a[0]+a[1]+a[2],....a[0]+...+a[n-1] * 第 * 页 1.2 基本概念和术语：数据的存储结构 链式存储结构 1536 元素2 1400 元素1 1386 元素3 ∧ 元素4 1345 h 存储地址 存储内容 指针 1345 元素1 1400 1386 元素4 ∧ ……. …….. ……. 1400 元素2 1536 ……. …….. ……. 1536 元素3 1386 第 * 页 1.2 基本概念和术语：数据的存储结构 索引方式 索引法是顺序存储法的一种推广，也是使用整数编码来访问数据结点位置。 37 42 52 73 98 73 52 42 98 37 线性索引 存储区域的数据 第 * 页 1.2 基本概念和术语：数据的存储结构 散列方式 散列方法是索引方法的一种延伸和扩展。 利用散列函数（hash functions）的机制来进行索引值的计算，然后通过索引表求出结点的指针地址。 散列函数是将字符串 s 映射到非负整数（作为存储地址/下标）。 第 * 页 1.3 抽象数据类型 模块化思想的发展，为模块的划分提供了理论依据，简称ADT (Abstract Data Type) ADT是定义了一组操作的一个抽象模型 例如，集合与集合的并、交、差运算就可定义为一个的抽象数据类型 一个抽象数据类型要包括哪些操作，由设计者根据需要确定 例如，对于集合，如果需要，也可以把判别一个集合是否为空集或两个集合是否相等作为集合上的操作 第 * 页 1.3 抽象数据类型 使用ADT的优势 用数学方法定义对象集合和运算集合，仅通过运算的性质刻画数据对象。 ADT的定义仅取决于它的逻辑特性，与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不会影响外部的使用。 完全独立于计算机中可能的表示方法，目的在于隐藏运算实现的细节和内部数据结构。 第 * 页 1.3 抽象数据类型 ADT是一种描述用户与数据之间接口的抽象模型。它定义了一个数据模型和在该数据模型上的一组操作。 ADT抽象数据类型名 { 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 } 第 * 页 1.3 抽象数据类型 ADT List { 数据对象：D = { a1, a2, ... , ai-