1、说明：说明：1、本课程的先修课程是、本课程的先修课程是程序设计程序设计和和离散数学离散数学 2、本课程是、本课程是操作系统、编译原理操作系统、编译原理和和数据库数据库的基础的基础程序=算法+数据结构数据结构是程序设计的基础。算法是在数据结构的基础上建立的。如：每个学生的信息、棋盘中每个格局、比赛中每个项目如：每个学生的信息、棋盘中每个格局、比赛中每个项目3158710119613987456231a1a2a3a4 a510141312112345678911012354871110291641012115123698712564312543611331814665161921数据的存储结构是逻
2、辑结构用计算机语数据的存储结构是逻辑结构用计算机语言的实现；言的实现；数据的存储结构数据的存储结构 的主要方法的主要方法:顺序存储方法顺序存储方法 链式存储方法链式存储方法(索引存储方法索引存储方法 散列存储方法散列存储方法)a1 a2 a3 a4 a5 a6 1 2 3 4 5 6顺序存储表示顺序存储表示结点间的逻辑关系由存储单元的邻接关系来体现结点间的逻辑关系由存储单元的邻接关系来体现链式存储表示链式存储表示a0a1a2a3a4 结点间的逻辑关系由附加的指针字段来表示结点间的逻辑关系由附加的指针字段来表示 学学 号号 姓姓 名名 性别性别 籍籍 贯贯 出生年月出生年月 98131 刘激扬刘
3、激扬 男男 北北 京京 1979.12 98164 衣春生衣春生 男男 青青 岛岛 1979.07 98165 卢声凯卢声凯 男男 天天 津津 1981.02 98182 袁秋慧袁秋慧 女女 广广 州州 1980.10 98224 洪洪 伟伟 男男 太太 原原 1981.01 98236 熊南燕熊南燕 女女 苏苏 州州 1980.03 98297 宫宫 力力 男男 北北 京京 1981.01 98310 蔡晓莉蔡晓莉 女女 昆昆 明明 1981.02 98318 陈陈 健健 男男 杭杭 州州 1979.12 姓姓 名名 1 蔡晓莉蔡晓莉 2 陈陈 健健 3 宫宫 力力 4 洪洪 伟伟 5 刘激
4、扬刘激扬 6 卢声凯卢声凯 7 熊南燕熊南燕 8 衣春生衣春生 9 袁袁秋慧秋慧 索引存储表示索引表索引表数据的数据的逻辑结构逻辑结构 与数据的与数据的存储结构存储结构之间的关系之间的关系 同一种逻辑结构可以映象成同一种逻辑结构可以映象成 不同的存储结构不同的存储结构数据的存储结构一定要正确数据的存储结构一定要正确 反映出数据元素之间的逻辑关系反映出数据元素之间的逻辑关系抽象数据类型（抽象数据类型（abstract data type,abstract data type,简称简称ADT)ADT)是指一个数学模型以及定义在该模型上的一组操作。是指一个数学模型以及定义在该模型上的一组操作。抽象数
5、据类型可以用三元组表示：抽象数据类型可以用三元组表示：（D，S，P)其中，其中，D D是数据对象，是数据对象，S S是是D D上的关系集，上的关系集，P P是对是对D D的基本操作集。的基本操作集。ADT抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本运算：基本运算的定义基本运算：基本运算的定义 ADT抽象数据类型名抽象数据类型名算法分析就是衡量算法质量的优劣。算法分析的目在于改进算法。算法分析主要从三方面考虑：执行算法所耗费的时间（时间性能）执行算法所耗存储空间（空间性能）算法应易于理解，易于编码，易于调试
6、等等算法中所有语句的频度之和是算法中所有语句的频度之和是矩阵阶数矩阵阶数n的函数的函数 T(n)=2n3+2n2+2n+1一般地，称一般地，称 n 是问题的规模。则时间复是问题的规模。则时间复杂度杂度 T(n)是问题规模是问题规模 n 的函数。的函数。当当n-时，把时间复杂度的数量级（阶）时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度称为算法的渐进时间复杂度 T(n)=O(n3)T(n)=T1(n)+T2(n)=O(max(f(n),g(n)T(n)=T1(n)*T2(n)=O(f(n)*g(n)常见时间复杂度：常见时间复杂度：（按数量级递增排列）按数量级递增排列）（1）、）、（log
7、2n）、n）、）、（nlog2n）、）、n2）、）、（n3）、）、2n）、）、（3n）例：设有两个算法在同一机器上运行，例：设有两个算法在同一机器上运行，其执行时间分别为其执行时间分别为 100n2 和和 2n，问：要问：要使前者快于后者，使前者快于后者，n 至少要取多大？至少要取多大？解答：解答：问题是找出满足问题是找出满足 100n2 2n=8192 n=14时，时，100n2=19600 2n=16384 n=15时，时，100n2=22500=0&Ai!=k)i-;return i;i-n A 中各元素的取值中各元素的取值 k 本本 章章 小小 结结数据组织的三个层次：数据、数据元素和数据项数据组织的三个层次：数据、数据元素和数据项数据结构主要研究的三方面内容：数据结构主要研究的三方面内容：（1）数据的逻辑结构）数据的逻辑结构 （线性结构和非线结构）（线性结构和非线结构）（2）数据的存储结构）数据的存储结构 （顺序方式、链式方式、索引方式和散列方式）（顺序方式、链式方式、索引方式和散列方式）（3）对数据实施的基本运算）对数据实施的基本运算算法分析：时间性能和空间性能算法分析：时间性能和空间性能
