讲数据结构概述

讲数据结构概述1第一页，共四十一页，编辑于2023年，星期一

第1讲数据结构概述

1.1数据结构的基本概念与术语

1.2数据类型和抽象数据类型

1.3算法和算法分析2第二页，共四十一页，编辑于2023年，星期一

1.1数据结构的基本概念与术语

一、为什么要学习数据结构？电子计算机的主要用途：早期：

主要用于数值计算。后来：

处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。3第三页，共四十一页，编辑于2023年，星期一非数值计算的程序设计问题

算法+数据结构=程序设计算法即处理问题的策略，而数据结构即为问题的数学模型。寻求数学模型的实质提取操作的对象找出这些操作对象之间含有的关系用数学模型加以描述4第四页，共四十一页，编辑于2023年，星期一非数值计算的程序设计问题例1:求一组(n个)整数中的最大值算法:基本操作是“比较两个数的大小”模型：线性表581379025第五页，共四十一页，编辑于2023年，星期一例2：计算机对弈算法：对弈的规则和策略模型：树6第六页，共四十一页，编辑于2023年，星期一例3田径赛的时间安排问题：

设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。算法:染色模型:无向图7第七页，共四十一页，编辑于2023年，星期一（1）用顶点代表比赛项目，设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米

A B CDE F（2）不能同时进行比赛的项目之间连上一条边。某选手比赛的项目必定有边相连（不能同时比赛）（3）对图上的每个顶点染一种颜色，并且要求有线相连的两个顶点不能具有相同颜色，而总的颜色种类应尽可能地少。同色可以同时比赛----田径赛的时间安排问题解法8第八页，共四十一页，编辑于2023年，星期一姓名项目1项目2项目3丁一ABE马二CD

张三CEF李四DFA王五BFAEBFDC比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛（无向图）9第九页，共四十一页，编辑于2023年，星期一

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科数据结构的定义(从研究对象来看):10第十页，共四十一页，编辑于2023年，星期一《数据结构课程》所处的地位：介于数学、计算机硬件和计算机软件三者之间的一门核心课程。11第十一页，共四十一页，编辑于2023年，星期一二、数据结构的基本概念与术语1、数据(Data):

描述客观事物的存在计算机中的并可为计算机处理的符号的总称，是计算机程序加工的”原料”。（分两类：数值型数据和非数值型数据）2、数据元素(DataElement):

是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

或称：元素、结点、顶点、记录

对于文件，每个记录就是它的数据元素对于数组，每个数组元素就是数据元素对于字符串，字符就是数据元素

12第十二页，共四十一页，编辑于2023年，星期一3、数据项(DataItem)：

是具有独立意义的不可分割的最小数据单位。一个数据元素可由若干个数据项组成。数据元素:运动员数据项:姓名俱乐部名称出生日期参加日期职务业绩数据元素与数据项的例子：13第十三页，共四十一页，编辑于2023年，星期一4、数据对象(DataObject)：

具有相同性质的数据元素的集合。是数据的一个子集。整数数据对象：N＝{0，±1，±2…….}，字母字符数据对象：C={‘A’,’B’,…’Z’}学生成绩数据对象:Cj={(‘101’,‘jane’,80),(‘102’,‘jack’,90),(‘103’,‘jerry’,75)}数据对象的例子：14第十四页，共四十一页，编辑于2023年，星期一5、逻辑结构

客观事物中数据元素之间的关系，与计算机无关分两大类：线性结构集合非线性结构树型结构图型结构（网状结构）（1）集合：结构中的数据元素除了同属于一种类型外，别无其它关系。（2）线性结构：结构中的数据元素之间存在一对一的关系。（3）树型结构：结构中的数据元素之间存在一对多的关系。（4）图型结构：结构中的数据元素之间存在多对多的关系。15第十五页，共四十一页，编辑于2023年，星期一

（a）集合结构

（b）线性结构

（c）树型结构（d）图型结构四类基本结构的示意图16第十六页，共四十一页，编辑于2023年，星期一数据的逻辑结构二元组表示：

B=(K，R)其中：K：数据元素的有限集合（数据对象）

R：K上的关系的有限集合，用<ai,aj>表示.ai称为直接前驱或弧尾,aj称为直接后继或弧头.图示为:aiaj弧aiaj边有向关系无向关系17第十七页，共四十一页，编辑于2023年，星期一数据结构二元组表示法示例：

例如，有5个人，分别记为a,b,c,d,e,其中a是b的父亲，b是c的父亲，c是d的父亲,d是e的父亲，如果只讨论他们之间所存在的父子关系，则可以用下面的二元组形式化地予以表达:B=（K，R）其中：K={a,b,c,d,e}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>}18第十八页，共四十一页，编辑于2023年，星期一

说明：a是b的直接前驱，b是a的直接后继a是开始结点，e为终端结点，b、c、d为内部结点

abcde线性逻辑结构

用图形方式表示如下：19第十九页，共四十一页，编辑于2023年，星期一6、存储结构（物理结构）

数据结构在计算机中的表示(或称映象）称为数据的存储结构，与计算机密切相关。四种基本的存储结构：（1）顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。（2）链式存储结构：在每一个数据元素中增加一个存放地址的指针（→），用此指针来表示数据元素之间的逻辑关系。（3）索引存储结构（4）散列存储结构20第二十页，共四十一页，编辑于2023年，星期一数据结构：B=（K，R）其中K={k1,k2,k3,k4,k5,k6,k7,k8,k9}R={r}r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>,<k7,k8>,<k8,k9>}这是一个线性结构，它的顺序存储方式如图所示:顺序存储结构示例：21第二十一页，共四十一页，编辑于2023年，星期一k1k2k3k6k5k4k7k8k9存储地址M100110021003100410051006100710081009特点：逻辑上相邻的元素物理位置上也相邻22第二十二页，共四十一页，编辑于2023年，星期一数据结构：B=（K，R）其中K={k1,k2,k3,k4,k5}R={r}r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}这是一个线性结构，它的链式存储如图所示。链式存储结构示例：23第二十三页，共四十一页，编辑于2023年，星期一100010011002100310041005100610071008存储地址infonextk41006k21007k11003k5∧k31005特点:逻辑上相邻物理上不一定相邻。24第二十四页，共四十一页，编辑于2023年，星期一

7、数据的运算集合注意：数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现就依赖于数据的存储结构。

数据的运算集合要视情况而定，一般而言，数据的运算包括插入、删除、检索、输出、排序等。插入：在一个结构中增加一个新的结点。删除：在一个结构删除一个结点。检索：在一个结构中查找满足条件的结点。输出：将一个结构中所有结点的值打印、输出。排序：将一个结构中所有结点按某种顺序重新排列。25第二十五页，共四十一页，编辑于2023年，星期一

8、数据结构定义的术语描述

按一定的逻辑结构组成的一批数据（或称带结构的数据元素的集合），使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。

注：同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。26第二十六页，共四十一页，编辑于2023年，星期一

数据的逻辑结构

数据的存储结构运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队列树型结构图型结构数据结构研究的三个方面：

散列存储索引存储串及数组27第二十七页，共四十一页，编辑于2023年，星期一1.2数据类型和抽象数据类型

数据的抽象经历了三个发展阶段：从无类型的二进制数到基本数据类型的产生从基本数据类型到用户自定义类型的产生从用户自定义类型到抽象数据类型的出现28第二十八页，共四十一页，编辑于2023年，星期一1.2数据类型和抽象数据类型

1、数据类型(DataType)

数据对象和在该集合上的一组操作。（如C中的int型，它的值是[-MAXINT,MAXINT]区间上的整数，操作为：加、减、乘、除、取余等运算）原子数据类型

C语言中基本类型：整型、实型、字符型等结构数据类型

C语言中数组和结构类型等29第二十九页，共四十一页，编辑于2023年，星期一2、抽象数据类型（

AbstractDataTypes）由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的运算信息隐蔽和数据封装，使用与实现相分离对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。30第三十页，共四十一页，编辑于2023年，星期一抽象数据类型描述的一般形式如下：ADT抽象数据类型名称{

数据对象：

……

数据关系：

……

操作集合：操作名1：

…………

操作名n：}ADT抽象数据类型名称31第三十一页，共四十一页，编辑于2023年，星期一练习：指出下列二元组表示法的数据结构是属于何种逻辑结构。（1）B=(K,R)K={a,b,c,d,e,f}R={<a,e>,<b,c>,<c,a>,<e,f>,<f,d>}（2）B=(K,R)

K={di|1≤i≤5}

R={<di,dj>,i<j}32第三十二页，共四十一页，编辑于2023年，星期一1.3算法和算法分析一、算法的概念和描述：1、什么是算法？求解问题的方法和步骤。

2、算法的特性（1）有穷性（2）确定性（3）可行性（4）输入（有或没有）（5）输出（一定有）33第三十三页，共四十一页，编辑于2023年，星期一3、判断算法好坏的标准(1)正确性(2)可读性(3)健壮性(4)时空效率时间效率空间效率4、算法的描述程序流程图伪代码自然语言(中文)

类高级语言（如：a<=>b）程序语言5、算法的实现本课程采用C语言34第三十四页，共四十一页，编辑于2023年，星期一二、算法的效率算法随问题的规模变大时效率变化情况。一个算法效率的评价主要从时间复杂度和空间复杂度来考虑。1、时间复杂度（着重评价）计算算法中主要语句执行的次数——语句频度时间复杂度—T(n)当问题规模n→∞时，算法执行时间增长率。用大“O”表示法。记作T(n)=O(f(n))（f(n)：为语句频度之和的最高次项的数量级阶）问题规模—n

算法求解问题的输入量（或初始数据量）。35第三十五页，共四十一页，编辑于2023年，星期一例：分析以下程序段的时间复杂度（1）A、B两数交换

C=A;A=B;B=C；时间复杂度：T(n)=1+1+1=O(1)——常量阶频度是：1频度是：1频度是：136第三十六页，共四十一页，编辑于2023年，星期一（2）二重循环for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;

时间复杂度：

T(n)=1+2+3+…+n=

——平方阶频度是：1+2+3+…+