数据结构-绪论

本课程教学内容第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章动态存储管理第九章查找第十章内部排序第十一章外部排序第十二章文件本课程内容结构数据结构线性结构非线性结构线性表栈队列串数组和广义表顺序表链表单链表双向链表循环链表两种存储结构顺序存储链式存储树图二叉树的遍历树和森林哈夫曼树及哈夫曼编码图的存储图的遍历最小生成树拓扑排序和关键路径最短路径查找排序静态动态哈希表内部外部第一章绪论1.1数据结构的研究对象1.2数据结构的基本概念1.3抽象数据类型的表示与实现1.4算法和算法分析计算机的发展仅能进行数值计算能处理各种非数值数据数据处理的种类数值数据

非数值数据

数(整数,实数)字符字符串文字图形图象声音1.1数据结构的研究对象

数值问题与非数值问题1）数值问题例1已知：游泳池的长len和宽wide，求面积area问题涉及的对象：游泳池的长len

宽wide，面积area；

对象之间的关系：area=lenwide1.1数据结构的研究对象例2线性方程组求解

学号姓名性别出生日期籍贯入学成绩所在班级 00201

杨润生男

82/06/01广州56100计算机2

00102石磊男83/12/21汕头51200计算机1

00202李梅女83/02/23阳江53200计算机200301马耀先男

82/07/12广州

50900计算机32）非数值问题例1已知某年级学生情况,要求分班并按入学成绩排列顺序。在这类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,这类数学模型称为线性模型。1.1数据结构的研究对象例2迷宫问题。1.1数据结构的研究对象入口出口例3多岔路口交通灯的管理问题。1.1数据结构的研究对象CDEAB数据结构研究的问题：非数值数据之间的结构关系及如何表示，如何存储，如何处理。1.1数据结构的研究对象1.2数据结构的基本概念一、基本概念二、数据结构的分类三、数据结构的存储四、数据类型1.数据能被输入计算机且能被计算机处理的一切对象。(是信息的载体，是客观事物的符号表示。)

例如：整数，实数，字符串、图象、声音等都是数据。一、基本概念2.数据元素是现实世界中某独立实体的数据描述。是数据结构讨论的基本单位，有时称为结点、或记录。一般由若干数据项组成。1.2数据结构的基本概念3.数据项具有独立意义的最小数据单位，是相对数据元素的，有时称域或字段。一、基本概念姓名性别年龄专业班级

数据项4.数据对象具有相同特征的数据元素的有限集合。例如：某个学生信息(数据元素)1.2数据结构的基本概念5.数据结构结构是数据元素之间的关系。数据结构是带结构的数据元素的集合。

一、基本概念例如一个12位的十进制数可以用三个4位十进制数表示：3214，6587，9345——a1(3214),a2(6587),a3(9345)在a1,a2,a3之间存在“次序”关系<a1,a2>,<a2,a3>3214,6587,9345≠6587,3214,9345a1a2a3a2a1a31.2数据结构的基本概念数据结构的数学定义形式：

B=(D,R)二元组

D:数据元素的集合(数据对象)R:D上关系的集合，表示数据元素之间的前驱、后继关系。一、基本概念1.2数据结构的基本概念如：B=(D,R)D={a,b,c,d,e,f,g}R={<a,b>,<a,c>,<b,d>,<b,e>,<c,f>,<c,g>}cfbedag6.数据的逻辑结构上述定义中“关系”描述的是数据元素之间的逻辑关系，即数据的逻辑结构。通常简称为数据结构。一、基本概念7.数据的存储结构数据结构在计算机中的表示，又称物理结构。是逻辑结构在存储器中的映像。1.2数据结构的基本概念1.集合二、数据结构的分类2.线性结构3.树型结构4.图状结构1.2数据结构的基本概念某班学生基本情况登记表，记录了每个学生的学号姓名专业政治面貌，表中的记录是按学生的学号顺序排列的。学号姓名 专业 政治面藐

001 王洪 计算机党员

002孙文计算机团员

003 谢军 计算机团员

004 李辉 计算机团员

005 沈祥福计算机党员

006 余斌 计算机团员

007 巩力 计算机团员

008 孔令辉计算机团员学生基本情况登记表的图示

001003002004006005008007学生间学号顺序关系是一种线性结构关系例一常用的数据结构

1）线性结构

2）非线性结构

如树、图等二、数据结构的分类家族的族谱

假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE例二、数据结构的分类树形结构三、数据结构的存储数据结构包括结点的值及结点之间的关系。1.顺序存储(顺序映像)只存储结点(数据元素)的值。结点之间的关系：由存储单元的相邻关系隐含地表示。适合于线性结构。在高级语言中常用数组表示顺序存储结构。1.2数据结构的基本概念地址数据3142331566316783173431887例：23，66，78，34，87三、数据结构的存储2.链接存储（非顺序映像）存储结点的值和结点之间的关系。用指针表示结点之间的关系，是各结点的后继结点的地址。两部分数据域：存储结点自身的值指针域：存储该结点的各后继结点的存储单元的地址1.2数据结构的基本概念地址

datalink0001630002000254000500038200040004660001000550^00030004000100020005存储结构8266546350三、数据结构的存储逻辑表示例1-1：有一线性结构结点集合：

D={63，54，82，66，50}

关系为结点值的降序：

R={<82,66>,<66,63>,<63,54>,<54,50>}1.2数据结构的基本概念例1-2：有一树型结构：

B=（D，R）

D={A，B，C，D，E，F，G}R={<A,B>,<A,C>,<B,D>,<B,E>,<C,F>,<F,G>}

逻辑表示：存储结构：三、数据结构的存储adddataLlinkRlink0000A000100020001B000300040002C0005^0003D^^0004E^^0005F0006^0006G^^1.2数据结构的基本概念四、数据类型1.定义数据类型是一个值的集合和定义在这个值集上的一组操作的总称。具体到高级语言中，例如整型、字符型等。整形上的加、减、乘、除操作。2.分类非结构类型：原子类型结构型：由一组原子类型或结构类型按某种结构组成1.2数据结构的基本概念数据类型是和数据结构密切相关的一个概念，最早出现在高级语言中，用以刻画程序操作对象的特性。用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的数据类型。四、数据类型抽象数据类型-ADT(AbstractDataType)

是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型和数据类型实质上是一个概念。1.2数据结构的基本概念抽象数据类型的描述抽象数据类型定义用三元组表示：（D，S，P），

其中，D是数据对象，

S是D上的关系集，

P是对D的基本操作集。定义格式：ADT抽象数据类型名{数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>（相当于声明若干函数)}ADT抽象数据类型名

四、数据类型1.2数据结构的基本概念如：用三元组定义出抽象数据类型复数ADTList{

数据对象：D={e1,e2|e1,e2∈实数,e1,e2分别代表实部与虚部}

数据关系：R1={<e1,e2>|}

基本操作：复数相加复数相减

}四、数据类型1.2数据结构的基本概念抽象数据类型的表示与实现我们通过固有的数据类型（高级语言中已实现的数据类型）来表示和实现抽象数据类型。

1.3抽象数据类型的表示与实现1.2数据结构的基本概念1.4算法和算法的衡量数据结构+算法=程序程序：为计算机处理问题编制的一组指令集数据结构：问题的数学模型算法：处理问题的策略，是对特定问题求解步骤的一种描述，是有限长的操作序列。

1.4算法和算法的衡量一、算法和算法的五个重要特性二、算法的设计原则三、时间复杂度和空间复杂度一、算法和算法的五个重要特性

算法有五个重要特性：1.有穷性2.确定性3.可行性4.输入5.输出1.3算法和算法的衡量一、算法和算法的五个重要特性1.有穷性：执行有穷步后结束，且每一步在有穷时间内完成。2.确定性：每一条指令必须有确切的含义，不会产生二义性。并且在任何条件下，算法都只有一条执行的路径。3.可行性：算法中描述的操作都是可以通过基本运算执行有

限次实现。4.输入：有0个或多个输入。作为算法加工对象的量值，通常体现为算法中的一组变量值，有些是算法执行过程中输入的，有些已被嵌入在算法中。5.输出：有一个或多个输出。是一组与输入有确定关系的量值，是算法加工信息对象后得到的结果。这种确定关系即为算法的功能。

1.3算法和算法的衡量二、算法的设计原则衡量算法性能的标准。设计算法时，通常应考虑达到以下目标：1.正确性2.可读性3.健壮性4.高效率与低存储量的需求1.3算法和算法的衡量1.正确性（有效性）首先，算法能够正确地实现预先规定的功能。其次，对正确性理解的四个层次：

(1)程序中不含语法错误

(2)程序对几组输入数据能够得出满足要求的结果

(3)程序对精心选择的典型、苛刻而带有刁难性的几组输入数据能得出满足要求的结果

(4)对一切合法的输入数据都能产生满足要求的结果二、算法的设计原则1.3算法和算法的衡量2.可读性可读性好。算法的逻辑必须是清晰的、简单的和结构化的。有助于人对算法的理解，为了人的阅读与交流。3.健壮性很好的容错性，即提供例外处理，对不合理的数据作出反应或进行处理，而不会产生莫明其妙的结果或出现异常中断、死机等现象，对于出错应报告出错信息。三、算法的设计原则1.3算法和算法的衡量二、算法的设计原则4.高效率与低存储量的需求

效率：指的是算法执行的时间；

存储量：指的是算法执行过程中所需的最大存储空间。通常，用时间复杂度来度量效率；用空间复杂度来试题存储量。1.3算法和算法的衡量三、时间复杂度和空间复杂度1.时间复杂度(1)和算法执行时间相关的因素：1.问题性质

2.问题规模3.算法选用的策略4.编写程序的语言5.编译程序6.计算机执行指令的速度(2)算法的时间复杂度与运行算法的目标计算机及描述算法的工具无关。取决于以下三方面：问题性质问题规模算法性质1.3算法和算法的衡量算法=控制结构+原操作

三、时间复杂度和空间复杂度以基本操作重复执行的次数作为算法的时间量度。重复执行的次数是一个函数f(n)。自变量n称做此算法的问题规模时间复杂度(渐进时间复杂度)记作：

T(n)=O(f(n))

算法执行时间的增长率和f(n)的增率相同。所研究的基本操作

1.3算法和算法的衡量例1-3

两个n阶矩阵相加，即C=A+B，其算法如下：#defineMAX20voidmatrixadd(int

n,int

a[MAX][MAX],int

b[MAX][MAX],int

c[MAX][MAX]){inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)

c[i][j]=a[i][j]+b[i][j];

//重复执行的次数为n2}

此时f(n)=n2

因此：

T(n)=O(f(n))=O(n2)

三、时间复杂度和空间复杂度1.3算法和算法的衡量

基本操作大多在循环和递归中。时间复杂度通常具有的形式：

O(1)、O(log2n)、O(n)、O(n*log2n)、O(n2)、O(n3)、O(2n)、O(n!)

不同数量级对应的值的关系：

O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)三、时间复杂度和空间复杂度1.3算法和算法的衡量

（1）有些算法，基本操作执行次数难以确定，只考虑它的阶数。（2）有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑

算法平均时间复杂度

（3）算法在最坏情况下的时间复杂度三、时间复杂度和空间复杂度2．空间复杂度空间复杂度是算法在执行过程中占用存储容量的度量。算法的存储量包含：输入数据、程序和辅助变量所占的存储空间。

空间复杂度是问题规模的函数，记为g(n)。

表示为：S(n)=O(g(n))

其中：n为问题的规模，g(n)与解决问题所用的存储