数据结构-第一章2

1、 Software College Northeastern University Autumn 2005数据结构Data Structure东北大学软件学院 董傲霜本课程学习的目的通过本课程的学习掌握常用数据结构的逻辑结构特征、存储结构及相关算法。学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。 学会书写符合软件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。 本课程学习要求要求掌握线性表、栈、队列、串、数组、广义表、树、图及文件等常用的一些数据结构的逻辑形式、存

2、储形式以及实现各种操作的算法。掌握在上述各种数据结构上经常实现的查找和排序的基本方法。能对工作中遇到的一些算法的时间复杂性和空间复杂性进行分析。能根据用户的要求及系统提供的数据，设计或选择合适的数据结构并能编写正确的算法解决实际问题。 教材及参考书(1) 教材严蔚敏，吴伟民编著：数据结构（C语言版），清华大学出版社，2004.11 严蔚敏，吴伟民，米宁编著：数据结构题集（C语言版） 清华大学出版社，2004.7教材及参考书(2) 参考书算法与数据结构-C语言描述,张乃孝主编,高等教育出版社。Mark Allen Weiss, Data Structures and Problem Solvin

3、g Using C+, published by Addison Wesley Longman, 2000.5。学时分配及考核方式学时分配：授课 60学时 上机实验 20学时课程成绩： 平时成绩 期末考试成绩 平时成绩 20 书面作业、上机练习 期末考试 80 闭卷笔试教师答疑方式Email： dongaoshuang固定答疑 时间：周二下午13：0016：00 地点：易购425课件及实验报告格式下载 邮箱：sjkxt- 密码：sjkxtsjkxt内容安排(1) 常用数据结构第章：绪论第章：线性表第章：栈和队列第章：串第章：数组和广义表第章：树和二叉树内容安排(2)第章：图 常用查找和排序算法

4、第章：动态存储管理第章：查找第章：内部排序第章：外部排序第章：文件学时安排教学内容讲课上机时间小计第1章 绪论44第3章 线性表8412第4章 栈与队列44第5章 字符串33第6章 数组、广义表和递归算法448第7章 树与二叉树10414第8章 图88第9章 查找8412第10章 内部排序7411第11章 文件44总 计602080上机实验内容上机实验内容 实验1：顺序表和链表的应用 （4学时） 实验2：堆栈和队列、串和数组的应用 （4学时） 实验3：树和图的应用 （4学时） 实验4：查找的应用 （4学时） 实验5：排序的应用 （4学时） 上机软件Visual C+ 6.0 第一章 绪论 第一

5、章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法及其分析 本章教学要求： (1) 了解数据结构的基本概念，理解常用术语. (2) 了解抽象数据类型的定义、表示和实现方法. (3) 掌握算法的定义及特性，算法设计的要求. 重点: (1) 了解数据结构的基本概念，理解常用术语。 (2) 抽象数据类型表示法、类C语言语法。 (3) 算法的特性，算法设计要求，算法分析。 难点: (1) 数据元素间的四种结构关系。 (2) 抽象数据类型表示法。 (3) 算法分析。 1.1 什么是数据结构一、计算机解决问题 步骤程序原始数据结果数据(1)、分析阶段-从问题抽象出

6、模型(分析问题,建模)(2)、设计阶段-依模型找出解法(重点是数据结构的设计和算法的设计)(3)、编码阶段依设计要求，用适当的程序语言编写出可执行的程序(4)、测试与维护-发现和排除前几个阶段的错误1.1 什么是数据结构二、 数值问题与非数值问题1）数值问题1.1 什么是数据结构主要特点是其数学模型可以用数学方程来表示。 2）非数值问题主要特点是其数学模型不再是数学方程，而是表、树或图之类的数据结构。 非数值问题的一些示例 学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级 00201 杨润生 男 82/06/01 广州 561 00计算机200102 石磊 男 83/12/21 汕头 51

7、2 00计算机100202 李梅 女 83/02/23 阳江 532 00计算机200301 马耀先 男 82/07/12 广州 509 00计算机3 已知某年级学生情况 , 要求分班按入学成绩排列顺序。 1.1 什么是数据结构 在这类文档管理的数学模型中, 计算机处理的对象之间通常存在着一种最简单的线性关系 , 这类数学模型称为线性模型 -表，线性的数据结构例1.1 图书馆信息管理系统书目表按书名按作者名按分类号索引表登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片例1.2 1.1 什么是数据结构1.1 什么是数据结构 迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。

8、计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树” 入口 出口例1.3 人机对奕树.例1.4 1.1 什么是数据结构 多叉路口交通灯问题CEBDAC和E是单行线,其他是双行线。要求：设计交通信号灯管理(“图”结构)1.1 什么是数据结构例1.5 多叉路口交通灯问题CEDABABACADBABCBDDADBDCEAEBECED 1.1 什么是数据结构1.1 什么是数据结构数据结构的研究问题： 非数值型数据之间的结构关系，及如何表示，如何存储，如何处理。数据结构 讨论描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。 12

9、基本概念和术语一、数据和数据结构 1、数据：所有能被输入到计算机中，且被计算机处理的符号的集合 ； 是计算机操作的对象的总称； 是计算机处理的信息的某种特定的符号表示形式 。 2、数据元素：数据中的一个“个体”，也称 “数据记录” 。是数据结构中讨论的基本单位 。 3、数据项: 相当于记录的“域”, 是数据的不可分割的最小单位。是数据结构中讨论的最小单位 。 (原子项、组合项) 1.2 基本概念和术语举例：数据、数据元素、数据项及其关系12 基本概念和术语4、数据对象：性质相同的数据元素的集合. 5、数据处理：指对数据进行检索、插入、删除、合并、拆分、排序、统计和转换等的操作。6、数据结构：是

10、相互间存在关系的数据元素集合。例如：一个含12位数的十进制数可以用三个4位的十进制数表示 3214,6587,9345 记 a1(3214),a2(6587),a3(9345) 在a1、a2和a3 之间存在“次序”关系 a1,a2、a2,a3 12 基本概念和术语二、数据结构的三方面 1） 数据的逻辑结构 2） 数据的存储结构 3） 数据的运算 数据的逻辑结构： 是数据元素之间的逻辑关系。形式化描述： Data_structure=(D,S) D数据元素的有限集合；SD上关系的有限集合。12 基本概念和术语 数据的存储结构 (物理结构)： 数据的各元素及其之间的关系在计算机中的存储表示。 数据

11、运算： 定义于逻辑结构、实现于存储结构，对数据的检索、插入、删除、更新、排序等操作。 1） 线性结构 2） 树形结构 3） 图结构 4） 集合 某班学生基本情况登记表，记录了每个学生的学号、姓名 、专业、政治 面貌 ，表中的记录是按学生的学号顺序排列的。 学号 姓名 专业 政治面藐 001 王洪 计算机 党员 002 孙文 计算机 团员 003 谢军 计算机 团员 004 李辉 计算机 团员 005 沈祥 计算机 党员 006 余斌 计算机 团员 007 巩力 计算机 团员 008 孔辉 计算机 团员学生基本情况登记表的图示 001003002004006005008007学生间学号顺序关系是

12、一种线性结构关系例1.6(1)常用的数据(逻辑)结构 线性结构：元素之间是一对一的关系。 12 基本概念和术语 家族的族谱 假设某家族有10个成员A， B， C， D， E， F， G， H，I， J，他们之间的血缘关系可以用如右图表示。12 基本概念和术语例1.7 树形结构：元素之间是一对多的关系。 JIACBDHGFE 图结构: 元素之间是多对多的关系。 如交通网、计算机网络等。 集合: 元素间为松散的关系。例如： 12 基本概念和术语数据(逻辑)结构的二种常用表示方法 图示表示 图示表示是由顶点和边构成的图，其中顶点表示数据 ，边表示数据之间的结构关系； 0010030020040060

13、05008007例如：学生基本情况表的图示表示JIACBDHGFE再如：家族树的图示表示12 基本概念和术语例如：学生基本情况表的二元组表示（D，S） 二元组表示 二元组表示是用一个二元组（D，S）表示数据结构， 其中 D 是数据元素集合，S 是 D 上关系的集合。D = 001，002，003，004，005，006，007，008S = R R= , , 再如：家族树的二元组表示（D，S） D = A，B，C，D，E，F，G，H，I，J S = R R = A,B, 12 基本概念和术语JIACBDHGFE 00100300200400600500800712 基本概念和术语(2)数据的存

14、储(物理)结构-逻辑结构在存储器中的映象 数据元素的映象方法：用二进制位(bit)的位串表示数据元素 。 例如： (321)10 (101000001)2 A (001000001)2 关系的映象方法：有以下 4种 顺序结构 链接结构 索引结构 散列结构 链接结构： 使用附加的 指针表示元素间的关系。 顺序结构： 以计算机存储器中存储单元之间的相邻关系表示元素间的相邻关系。xyz 特点：使用连续存储空间，整个存储结构中只含数据元素本身的信息。 x y z顺序结构与链接结构的比较： 可以从空间利用率和运算两方面进行比较。12 基本概念和术语12 基本概念和术语 索引结构： 使用索引表和基本表实现

15、数据结构。 散列结构： 根据结点的值确定结点存储地址。 说明： 4种存储方法可结合使用。12 基本概念和术语 三、数据类型和抽象数据类型的概念 数据类型（Data Type） 在高级语言中指数据的一个值的集合及其上可进行的一组操作的总称。 例:C语言中 提供int基本数据类型，可以进行+，*，/，%等操作 按值的类型划分： 原子类型 结构类型12 基本概念和术语 抽象数据类型（Abstract Data Type） 是指一个数学模型以及定义在该模型上的一组操作抽象数据类型和数据类型的区别 数据类型注重运算，忽略了数据元素（值）之间的关系 抽象数据类型注重数据元素的关系 抽象的是数据元素本身的值

16、的类型14 算法与算法分析 1.3 抽象数据类型13 抽象数据类型一、抽象数据类型的定义(ADTAbstract Data Type)： ADT是指一个数学模型以及定义在此数学模型上的一组操作。 例如： 矩阵 +（求转置、加、乘、求逆、求特征值） 构成一个矩阵的抽象数据类型 数据结构+定义在此数据结构上的一组操作 = 抽象数据类型 二、抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示其中，D是数据对象，S是D上的关系集，P是对D的基本操作集 ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 数据对象和数

17、据关系用伪码描述 基本操作名（参数表） 初始条件：（初始条件描述） 操作结果：（操作结果描述）13 抽象数据类型名称线性表数据对象D=ai| aiElemSet,i=1,2,.,n,n=0任意数据元素的集合数据关系R1=| ai-1,ai D,i=2,.,n除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作ListInsert(&L,i,e)ListDelete(&L,i,e)L为线性表，i为位置，e为数据元素。例：线性表抽象数据类型的表示13 抽象数据类型13 抽象数据类型三、类C语言语法(1)1、预定义常量和类型#define TRUE 1#define FALSE 0

18、#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status; /Status是函数的类型，其值是函数结果状态代码。2、数据结构的存储结构typedef ElemType first;3、基本操作的算法函数类型 函数名（函数参数表）/算法说明语句序列/函数名 13 抽象数据类型类C语言语法(2)4、赋值语句简单赋值：变量名=表达式； 串联赋值：变量名1=变量名2=.=变量名k=表达式； 成组赋值: （变量名1，.,变量名k）=（表达式1，.,表达式k);结构名=结构名；结构名=（值1，

19、.，值k);变量名=表达式；变量名起始下标.终止下标=变量名起始下标.终止下标； 交换赋值：变量名变量名；条件赋值：变量名=条件表达式？表达式T：表达式F13 抽象数据类型类C语言语法(3)5、选择语句1、if（表达式） 语句；2、if（表达式） 语句；else 语句；3、switch(表达式） case 值1：语句序列1；break; . case 值n：语句序列n；break; default:语句序列n+1；break; 4、switchcase 条件1：语句序列1；break;.case 条件n：语句序列n；break; default:语句序列n+1；break; 类C语言语法(4)

20、13 抽象数据类型6、循环语句for（赋初值表达式；条件；修改表达式序列）语句；while（条件）语句；do 语句序列 while（条件）；7、结束语句return 表达式；return; /函数结束语句break; /case结束语句exit(异常代码); /异常结束语句8、输入和输出语句scanf（格式串，&变量1，.,&变量n）；printf(格式串,表达式1,表达式n);9、注释/文字序列10、基本函数max（表达式1，.，表达式n）min,abs,floor,ceil,eof,eoln 11、逻辑运算&与运算；|或运算ADT List /线性表的类C表示数据对象: D=ai| ai(

21、-ElemSet,i=1,2,.,n,n=0 数据关系: R1=| ai-1,ai(- D,i=2,.,n 基本操作：InitList(&L)；DestroyList(&L)；ListInsert(&L,i,e)；ListDelete(&L,i,&e)；ADT ListListInsert(List &L,int i,ElemType e)if (iL.length+) return ERROR;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p;*q=e;+L.length;return OK;13 抽象数据类型14 算法与算

22、法分析 1.4 算法及其分析一、算法的概念 算法是描述求解问题的操作序列的有穷规则集合。 算法的5个基本特征：1）输入：0个或多个输入；2）输出：1个或多个输出；3）有穷性：算法必须在有限步内结束；4）确定性：组成算法的操作必须清晰无二义性。5）可行性：组成算法的操作必须能够在计算机上实现。 求两个正整数 m，n 中的大者MAX的算法。 （1）若 m n 则 max=m （2）若 m = n 则 max=n 例1.814 算法及其分析 算法的描述流程图自然语言伪代码高级语言14 算法及其分析例1.7从n个整数中查找最大数算法的描述描述方法一 ： 使用流程图开始输入n个整数a1anxa1,i2i

23、xii+1输出x结束NYYN14 算法及其分析描述方法二：使用自然语言给n个元素a1an输入数值把第一个元素a1值赋给用于保存最大值元素的变量x把2赋给表示下标的变量i如果ix，则把ai赋给x，否则不改变x的值使下标i增加1转向第(4)步继续执行14 算法及其分析描述方法三：使用伪语言-类C语言 DataType Max(int n) /设n个数已存于数组A x=A0; i=1; while (ix) x=Ai; i+; return x; 14 算法及其分析描述方法四：使用高级语言-C语言#define N 10 #include void Max() int i,x,AN; for (i=

24、0;iN;i+) scanf(“%d”,&ai); x=A0; i=1; while (ix) x=Ai; i+; printf(“max=%dn”,x); 14 算法及其分析二、算法的设计14 算法及其分析“自顶向下,逐步求精”，使算法层次化、模块化。三个阶段：数学模型非形式化算法抽象数据类型伪语言算法数据类型高级语言源程序算法设计的要求14 算法及其分析1正确性2. 可读性 3健壮性 4高效率与低存储量需求 int sign(int x)int y; if(x 0) y = 1; else if(x = 0) y = 0; else y = -1; return y;第一个层次程序不包含语

25、法错误int sign(int x)int y; if(x 1) y = 1; else if(x = 0) y = 0; else y = -1; return y;第二个层次输入100 输出1输入0 输出0输入100 输出1int sign(int x)int y; if(x = 1) y = 1; else if(x = 0) y = 0; else y = -1;return y;第三个层次输入100 输出1输入1 输出1输入0 输出0输入-1 输出-1输入-100 输出-1int sign(int x)int y; if(x 0) y = 1; else if(x = 0) y =

26、0; else y = -1; if(x =0 x1234) y= 0; return y;第四个层次所有可能的输入14 算法及其分析三、算法的分析 好算法的特性： 正确性、可读性、健壮性、高效率和低存储量等。 1、算法效率的度量-算法时间复杂度1) 两种衡量算法效率的方法: 事后统计方法 :例如Visual C+ 中的Profiler 缺点：不利于较大范围内的算法比较。 （异地，异时，异境） 事前分析估算方法：评估方法 可克服事后统计方法的缺点。 14 算法及其分析程序在计算机上运行所需时间的影响因素算法本身选用的策略问题的规模：输入量的数目规模越大，消耗时间越多书写程序的语言语言越高级，消

27、耗时间越多编译产生的机器代码质量机器执行指令的速度为便于比较算法本身的优劣，应排除其它影响算法效率的因素。 14 算法及其分析例1.8计算下列算法的执行时间(包含的简单操作个数)int sum(int A,int n) int s=0; for (i=0;in;i+) s+=Ai; return s;假设以语句为单位进行统计：T(n)=1+1+n+1+n+n+n+1=4n+4 14 算法及其分析 s=0; i=0;Loop: if(in) s+=Ai; i+; goto loop; return s;一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），即它是问题规模的

28、函数。 算法 = 控制结构 + 原操作 （固有数据类型的操作） 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的度量。 14 算法及其分析例1.8原操作：加法操作的次数int sum(int A,int n) int s=0; for (i=0;in;i+) s+=Ai; return s;T(n) = n 14 算法及其分析 多数情况下只要求出最深层次循环语句中原操作量级2) 算法时间复杂度的估算 - 大“O”记号算法的渐进时间复杂度，简称算法时间复杂度记作： T(n) = O(f(n) 表示随问题规模n的增大，算法执行时间的增长率

29、与f(n) 的增长率相同。-算法执行时间的数量级 14 算法及其分析例1.9 两个n 阶矩阵相乘的算法 矩阵相乘的基本运算：乘法、 加法；for ( i = 1; i=n; i+ ) for (j = 1; j=n; j+ ) c i j = 0 ; for (k = 1; k= n; k+ ) c i j += a i k * b k j ; 乘法 加法执行次数均为 n3 O（n3） 称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与n3成正比, 即O（n3）与n3 同一数量级； 14 算法及其分析例1.10选择排序void sele_sort(int A,int n) for

30、 (i=0;in-1;i+) index=i; for (j=i+1;jn;j+) if (AjAindex) index=j; if (index!=i) temp=Aindex; Aindex=Ai; Ai=temp; T(n)=? 请思考! 14 算法及其分析原操作：比较(n-1)+(n-2)+1=n(n-1)/2算法时间复杂度：O(n2) 常见算法时间复杂度表示及增长速度排序：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)说明：logn指log2n常用公式： n n n 1=n , i=n(n+1)/2 , i2=n(n+1)(2n+1)/6 1

31、 1 1 14 算法及其分析各种数量级的T(n) 14 算法及其分析算法时间复杂度的表示： 算法执行时间的数量级数量级的含义： 忽略这个数量级的系数 低于这个数量级的其他项问题： T(n) = 5n2+100n 什么情况下会考虑系数和低数量级项的因素？ 14 算法及其分析 最好、最坏、平均时间复杂度例1.11对一维数组进行顺序查找。int search(int a,int n,int key) for (i=0;in;i+) if (ai= =key) return i; return -1;最好情况：?最坏情况：?平均情况：? 14 算法及其分析算法执行的时间: 和数据集的具体值和值的分布有关系 概念：最好时间复杂度：指算法对所有可能的输入集的最小执行时间最坏时间复杂度：指算法对所有可能的输入集的最大执行时间平均时间复杂度：指算法对所有可能的输入集的执行时间的数 学期望值。 14 算法及其分析 14 算法及其分析例1.122 算法空间复杂度 -算法存储空间的度量 用执行算法所需的辅助空间的大小作为算法所需空间的度量。 S（n）= O(g(n)