数据结构与算法 第一章 绪论

1、数据结构与算法课程简介课程内容 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。 数据结构课程的主要目的是介绍一些常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论对它们实行的各种运算的实现算法。 课程简介课时安排 理论：48学时 实践：24学时学习方法 书面练习 + 上机实验考核方式：考试 平时成绩 + 实验成绩 + 期考成绩课程简介参考书目1 严蔚敏、吴伟民，数据结构（第二版），清华大学出版社，1992。2 William Ford & Willi

2、am Topp, 数据结构-C+语言描述，清华大学出版社，（中译本），1998。3 Sartaj Sahni 数据结构算法与应用，机械工业出版社，（中译本），1999。4 王晓东 算法设计与分析，清华大学出版社，20035齐德昱,数据结构与算法,清华大学出版社,2003 (21世纪大学本科计算机专业系列教材)6 胡学钢, 数据结构算法设计指导, 清华大学出版社,19997 熊岳山等, 数据结构-典型题解与实战模拟, 国防科技大学出版社, 2004(第二版)第一章 绪论 数据结构与算法的意义 数据结构概述 算法 算法分析1.1 数据结构与算法的意义 Nikiklaus Wirth(1976) D

3、ata Structure + Algorithm = Program.程序设计：为计算机处理问题编制一组指令集算 法：处理问题的策略数据结构：问题的数学模型例1 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例2 人机对奕问题树.例3 最短路径问题图 从油田铺设管道，把原油运到加工厂，求使管道总长最短的铺设方案。 例4 古老的七桥问题图ABDCADCB小结 数据结构描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中的表示和实现。 有了数据结构知识，可以帮助我们分析数据的特征和数据之间的关系，尤其是对非数值

4、计算问题，从而更好地组织数据，更加有效地使用计算机，充分发挥计算机的功能。算法的意义选择问题。设有一组N个数，确定其中的第k个最大者。学习算法设计的方法和算法分析的技术后，可以帮助我们设计较好的算法，分析算法的优、缺点，从而找出解决某一问题的最好方法。1.2 数据结构概述数据（data) ：所有能输入到计算机中去的描述客观事物并被计算机程序处理的符号的总称，分为两类：数值型数据和非数值型数据。数据元素（data element）：数据的基本单位，也称节点或记录，如“树”中的一个棋盘格局，“图”中的一个圆圈一个数据元素可由不可分割的若干个数据项级成。数据项（data item）：有独立含义的数据

5、最小单位，也称域(field)，是不可分割的，如书目信息中的书名、作者等。数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集。数据结构（data structure)：是指相互之间存在着一种或多种关系的数据元素的集合。四种基本的数据结构集合：数据元素间除“同属于一个集合”外，无其它关系。线性结构：一个对一个，如线性表、栈、队列。树形结构：一个对多个，如树。图状结构：多个对多个，如图。Group=（P，R）其中：P=T，G1，Gn，S11Snm 1n 3，1m2R=R1，R2R1=| 1 i n，1 n 3R2=| 1in，1jm，1 n3，1m2数据结构的形式定义为

6、:数据结构是一个二元组Data_Structure=（D，S）其中：D是数据元素的有限集，S是D上关系的有限集。例 假设我们需要编制一个事务管理的程序，管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象课题小组设计一个数据结构。假设每个小组由一位教师、一至三名研究生及一至六名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。则可以如下定义数据结构：数据结构的形式定义数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构存储结构分为：顺序存

7、储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系数据结构的两层次元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容顺序存储1536元素21400元素11346元素3 元素4h存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 1346 链式存储 1.3 抽象数据类型 抽象数据类型（Abstract Data Type,ADT）是指一个数学模型以及定义在此数学模型上的一组操作。 抽象数

8、据类型由元素、关系及操作3种要素来定义。抽象数据类型用三元组来表示： （D、R、P）数据对象关系集基本操作集1.4 算法算法（algorithm）：解决某一特定问题的具体步骤的描述，是指令的有限序列。算法的特性算法的评价正确性(correctness)： 1、不含语法错误 2、对于几组输入数据能够得出满足规格说明要求的结果 3、对于精心选择的典型、苛刻而带有刁难性的数据能够得出满足规格说明要求的结果 4、对于一切合法的输入数据都能产生满足规格说明要求的结果可读性(readability)：人的阅读与交流健壮性(robustness)：当输入非法数据时，算法能够适当的做出反应或进行处理，不会产生

9、莫名其妙的结果效率与低存储量：算法的执行时间和所需的最大存储空间算法与数据结构间的关系例：求3个数中的最大者算法1：int Max1(int a3) if(a0 a1) if(a0 a2) return a0; else return a2; else if(a1 a2) return a1; else return a2; 算法2：int Max2(int a3) c = a0; for(int I = 1 ; I c) c = ai; return ai;不需要额外的空间需要额外的空间算法的度量时间复杂度运行算法时所需要消耗的时间资源。一般：算法中基本操作重复执行的次数是问题规模n的某个函

10、数f(n)时间复杂度：随问题规模n的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的（渐近）时间复杂 度，记作 T(n)=o(f(n)例1：nXn矩阵相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; 例2：for(i=0;in;i+) for(j=0;jm;j+) Aij=0; 常见的时间复杂度，按数量级递增排列，有O(1),O(log2n),O(n),O(nlog2n),O(n2),O(2n) 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该操作在算法中重复执得的次数作

11、为算法运行时间的衡量准则。 算法的度量空间复杂度算法在计算机内挂靠时所需存储空间的度量。 程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间 空间复杂度：算法所需存储空间的量度 S(n)=o(f(n)例：交换两数void swap(int &a,int &b) int temp; temp = a; a = b; b = temp;例：交换两数void swap(int &a,int &b) a = a + b; b = a - b; a = a - b;需要额外的空间不需要额外的空间运行时间计算法则法则1：赋值语句的运行时间为1。法则2：一次for循环的运行时间至多是该for循环内 语句的运行时间乘以迭代的次数。法则3：嵌套for循环。每一层循环