C语言数据结构_第01讲 绪论.ppt

绪论 知 识 点 数据结构中常用的基本概念和术语 算法描述和分析方法 难 点 算法时间复杂度 要 求 了解数据的逻辑结构和物理结构； 了解算法对于程序设计的重要性 ； 掌握算法时间复杂度的分析方法 。 目录 1-1 数据结构研究的内容 1-2 数据的逻辑结构 1-3 数据的存储结构 1-4 算法和算法分析 小 结 实验1 习题1 1-2 数据的逻辑结构 1-2-1 基本概念 1．数据（Data） 数据是信息的载体，是对客观事物的符号表示。通俗的说，凡是能被计算机识别、存取和加工处理的符号、字符、图形、图像、声音、视频信号等一切信息都可以称为数据。 2. 数据元素（Data Element） 数据元素是对现实世界中某独立个体的数据描述，是数据的基本单位。 数据元素也称为结点（Node），在计算机中，常作为一个整体来处理。 1-2-2 逻辑结构的描述 数据元素之间的逻辑关系，称为数据的逻辑结构。 一个数据的逻辑结构可以用二元组来表示： G=(D,R) 其中：D是数据元素的集合； R是D上所有数据元素之间关系的有限集合。 【例1-4】一种数据结构Line=（D，R），其中: D={01,02,03,04,05,06,07,08,09,10} R={r} r={05,01,01,03,03,08,08,02,02,07, 07,04,04,06,06,09,09,10} 1-3 数据的存储结构 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。 四种不同的存储结构: 1. 顺序存储 顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 例如，一个字母占一个字节，输入A、B、C、D、E，并存储在2000起始的连续的存储单元，如图1-8为顺序存储结构。 2. 链式存储 借助指示元素存储地址的指针（Pointer）来表示数据元素之间的逻辑关系。 例如，图1-9为表示复数z=2.0+4.8i的链式存储结构。 其中地址2000存放实部，地址2100存放虚部，实部与虚部的关系用值为”2100”的指针来表示（本例仅仅是为了简化讨论而作的一个引例，实际应用中，像复数这样简单的结构并不需要采用链式存储结构）。 3. 索引存储 索引存储是在原有存储数据结构的基础上，附加建立一个索引表，索引表中的每一项都由关键字（能唯一标识一个结点的数据项）和地址组成。索引表反映了按某一个关键字递增或递减排列的逻辑次序，主要作用是为了提高数据的检索速度。 4. 散列存储 散列存储是通过构造散列函数来确定数据存储地址或查找地址的。 1-4 算法和算法分析 1-4-1 算法特性 1．算法（Algorithm） 算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。 2. 算法的特性： （1）有穷性 （2）确定性 （3）正确性 （4）输 入 （5）输 出 3. 算法与程序的区别 （1）一个算法必须在有穷步之后结束；一个程序不一定满足有穷性。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 （3）算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特定的程序设计语言来描述，就成了程序。 （4）算法与数据结构是相辅相承的。 1-4-3 算法效率的评价 算法效率的评价用时间复杂度（所需运算时间）和空间复杂度（所占存储空间）表示，重点是时间复杂度 。 一个算法所需的运算时间通常与所解决问题的规模大小有关。 用n表示问题规模的量 ，把算法运行所需的时间T表示为n的函数，记为T(n)。 不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。 一个算法所需的执行时间就是该算法中所有语句执行次数之和。 渐进时间复杂性：当n逐渐增大时T(n)的极限情况，一般简称为时间复杂度。 时间复杂度： 时间复杂度常用数量级的形式来表示， 记作T(n)=O(f(n))。 其中，大写字母O为Order(数量级)的字头，f(n)为函数形式，如T(n)=O(n2)。 当T(n)为多项式时,可只取其最高次幂项,且它的系数也可略去不写。 一般地，对于足够大的n，常用的时间复杂性存在以下顺序： O(1) O(lgn) O(n) O(n*lgn) O