[互联网]第01章 算法与数据结构基础.ppt

第 1 章　算法与数据结构基础 1.1 算法的基本概念 1.2 数据结构基础 1.3 线 性 表 1.4 栈 和 队 列 1.5 树 1.6 排序 1.7 查找 1.1 算法的基本概念 算法的定义：一个有穷的指令集，这些指令为解决某一特定问题规定了一个运算序列，即方法和步骤，在计算机学科中，算法就是计算机解决问题的过程或步骤。 结构化程序算法的特性如下。 （1）输入 （2）输出 （3）确定性 （4）有穷性 （5）有效性 算法复杂度通常采用由德国数学家Paul Bachmann在1892年提出的“大O表达式”表述，该符号以大写字母O带一对小括号括起的一个表达式构成。一般描述算法复杂度时括号里用N的简单函数表示，如O(N2)（读作：ON大平方）。 算法的时间复杂度指算法的时间耗费，算法时间是由控制结构和原操作的决定的。算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，记作： T(n) = O(f(n)) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。 算法的空间复杂度 算法的空间复杂度描述算法的存储空间需求，运行完一个程序所需要的内存大小是问题规模n的某个函数g(n)，记作： S(n) = O(g(n)) 它表示随着问题规模n的增大，算法运行所需存储空间的增长率S(n)与g(n)的增长率相同。 2009年9月4. 算法的空间复杂度是指（???? ）。 A.算法在执行过程中所需要的计算机存储空间??? B.算法所处理的数据量 C.算法程序中的语句或指令条?????????????????????? D.算法在执行过程中所需要的临时工作单元数 1.2 数据结构基础 数据：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据包括数值性数据和非数值性数据。 数据元素（也称为元素、接点、顶点、记录）：数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成。 数据项：数据项是具有独立含义的最小标识单位。 数据对象：数据的子集，是具有相同性质的数据成员（数据元素）的集合。 数据结构的定义：数据结构是指数据之间的相互关系，即数据的组织形式，由某一数据对象及该对象中所有数据成员之间的关系组成，记为： Data_Structure={D,R}，其中D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。它包括逻辑结构、存储结构和数据的运算3个方面的内容。 数据的逻辑结构：用来描述数据元素之间的逻辑关系。 数据的存储结构：用来描述数据元素及数据元素之间的关系在存储器中的存储形式。 数据的运算：即对数据元素施加的操作。 数据结构的图形表示：用图形来直观地表示数据及其之间的关系。 数据的逻辑结构分为线性结构和非线性结构两类： 线性结构：数据元素之间构成一种顺序的线性关系，如图1-2所示。线性结构包括线性表、堆栈、队列和串。 线性结构的特征有： （1）集合中必存在惟一的一个“第一元素”； （2）集合中必存在惟一的一个“最后元素”； （3）除最后的元素之外，均有惟一的后继； （4）除第一元素之外，均有惟一的前驱。 非线性结构是指不满足以上条件的存储结构。非线性结构包括树、二叉树、 图（或网络）和广义表。 2009年9月 1．下列数据结构中，属于非线性结构的是（???? ）。 A.???? 循环队列 B.带链队列C.二叉树? D.带链栈 答案 C 解析 树均是非线性结构 1.3 线 性 表 1.3.1 线性表的顺序存储结构 线性表是最常用且最简单的一种数据结构。 采用顺序存储结构的线性表也叫做顺序表，如n个元素的线性表可以记为：L=（a1，a2，…，an）。 顺序表有插入和删除两种基本操作。 1.3.2 线性表的链式存储结构 链式存储是指用一组地址任意的存储单元存放线性表中的数据元素。 链式存储采用结点来表示数据元素。一个结点由两个部分构成：数据域和指针域。 （1）单链表及其基本操作 2009年3月(1)下面叙述中正确的是 A）栈是“先进先出”的线性表 B）队列是“先进后出”的线性表 C）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。 答案: D （2）双向链表及其基本操作 1.4 栈 和 队 列 1.4.1 栈及其基本操作 栈是规定只能在表的一端进行插入和删除的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。当表中没有元素时称为空栈。由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先被删除，所以又把栈称为后进先出（Last_In_First_Out，简称LIFO）表。栈有插入