大学数据结构课件-第1章绪论

1

1.1什么是数据结构

1.2基本概念和术语

1.3抽象数据类型的表示和实现

1.4算法和算法分析第1章绪论2一、数据结构课程的研究内容电子计算机的主要用途：早期：主要用于数值计算。后来：

处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）数学模型→选择计算机语言→编出程序→测试→最终解答数据元素之间的相互关系一般无法用数学方程加以描述1.1什么是数据结构3非数值计算问题例1.1

电话号码查询问题。例1.2

田径赛的时间安排问题：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）。要求设计比赛日程表，使得在尽可能短的时间内完成比赛。1.1什么是数据结构4（1）设用如下六个不同的编码代表不同的项目：

跳高跳远标枪铅球100米200米

AB CDE F姓名项目1项目2项目3丁一ABE马二CD

张三CEF李四DFA王五BF（2）用顶点（圆圈）代表比赛项目

不能同时进行比赛的项目之间连上一条边。AEBFDC比赛时间比赛项目1A，C2B，D3E4F1.1什么是数据结构5因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。由此可见：对于解决非数值计算的问题首先要考虑对相关的各种信息如何表示、组织和存储？1.1什么是数据结构61.许卓群，张乃孝，杨冬青，唐世渭，《数据结构》，国防科技大学计算机研究所，1985年“按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做一个数据结构。”特点：从三个方面来看数据结构。2.李春葆，《数据结构（C语言篇）习题与解析》，清华大学出版社，2000年“数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构又可以分为下述三个组成部分，它们分别是数据的逻辑结构、数据的存储结构和数据的运算。”特点：明确强调“关系”，且细分“关系”。1.1什么是数据结构73.黄国瑜，叶乃菁，《数据结构》，清华大学出版社，2001年“在程序语言中，“数据类型”是指程序语言中变量所能表示并存储的数据种类，“数据实体”则是指在一种数据类型中的所有可能元素的集合。而“数据结构”，大致上说来，就是数据实体中元素之间的关系，包括数据的表示法和运算。”特点：指出“关系”为表示法和运算。4.陈慧南，《数据结构——C语言描述》，西安电子科技大学出版社，2003年“从数学概念上讲，一个数据结构是由数据元素依据某种逻辑联系组织起来的。研究数据结构是为了解决应用问题，所以讨论数据结构必须同时讨论在数据结构上执行的相关运算及其算法才有意义。”特点：从逻辑联系入手，兼顾其它方面。1.1什么是数据结构8计算机内的数值运算依靠方程式，而非数值运算则要依靠数据结构。同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。程序设计实质=好算法+好结构二、学习数据结构课程的用处1.1什么是数据结构9是介于数学、计算机硬件和计算机软件三者之间的一门核心课程数学硬件软件三、数据结构课程的地位1.1什么是数据结构10数据--是对客观事物的符号表示，在计算机科学中是指所有（Data）

能输入到计算机中并被计算机程序处理的符号的总称(整数、实数、字符串、图像、声音等)。数据元素--是数据的基本单位，具有完整确定的实际意义，（DataElement）在计算机程序中通常作为一个整体进行考虑和处理(又称记录、结点等)。数据项--

一个数据元素可由若干个数据项组成，是数据的（DataItem）不可分割的最小单位(又称字段等)。三者之间的关系：数据>数据元素>数据项例：学生档案>个人记录>姓名、性别、籍贯…1.2基本概念和术语11数据对象（DataObject）--是性质相同的数据元素的集合，是数据的一个子集。数据结构（DataStructure）--是相互之间存在一种或多种特定关系的数据元素的集合。

表示为：

Data_Structure=(D,S)元素有限集关系有限集例1：用数据结构表示一周中的七天。Data_Structure=(D,S),其中，D={}S={}Mon,Tue,Wen,Thu,Fri,Sat,Sun<Mon,Tue>,<Tue,Wen>,<Wen,Thu>…1.2基本概念和术语12（1）Data_Structure=(D,S)，其中，

D={01，02，03，04，05}S={}（2）S=(D,R)D={a,b,c,d,e,f

}R={<a,e>,<

b,c>,<

c,a>,<

e,f>,<

f,d>}解:

上述表达式可用图形表示为：aebcfd例2：将下述表达式用图形的形式表示出来集合结构线性结构1.2基本概念和术语13（3）

Data_Structure=(D,S),其中，

D={01，02，03，04，05，06，07}S={(01,02)，(01,03)，(01,04)，(02,05)，(02,06)，(03,07)}（4）S=(D,R)

D={di|1≤i≤5,1≤j≤5}

R={<di,dj>,i<j}d1d2d3d4d501020304050607树形结构图状结构1.2基本概念和术语14逻辑结构--数据元素之间的逻辑关系，即结构中定义的“关系”。逻辑结构可细分为4类：集合结构线性结构树形结构图状结构一对一关系一对多关系多对多关系非线性结构1.2基本概念和术语1501000101物理结构--也称存储结构，是数据的逻辑结构在计算机存储器内的表示（映像）。顺序映像非顺序映像特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。例：复数3.0-2.3i

的存储形式3.0-20-2.3算法的设计取决于选定的数据（逻辑）结构算法的实现依赖于采用的存储结构----顺序存储结构----链式存储结构1.2基本概念和术语16数据类型--是一个值的集合和定义在这个值集上的一组操作

的总称。抽象数据类型—由用户定义，用以表示应用问题的数据模型。它由基本的数据类型组成，并包含一组相关的操作。抽象数据类型可用ADT=（D，S，P）三元组表示数据对象D上的关系集D上的操作集ADT

抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉}ADT

抽象数据类型名ADT常用定义格式1.3抽象数据类型的表示与实现17例：给出自然数（NaturalNumber）的抽象数据类型定义。IsZero(x):Booleanif(x==0)返回Trueelse返回FalseAdd(x,y):NaturalNumberif(x+y<=MaxInt)返回x+yelse返回MaxIntSubtract(x,y):NaturalNumberif(x<y)返回0else返回x-yEqual(x,y):Booleanif(x==y)返回Trueelse返回FalseADTNaturalNumber

{}NaturalNumber数据对象:数据关系:数据操作:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数。1.3抽象数据类型的表示与实现18一、算法：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。二、算法的5个特性：

有穷性、确定性、可行性、输入和输出三、算法设计的要求：

正确性、可读性、健壮性、效率与低存储需求时间复杂度空间复杂度1.4算法和算法分析19时间复杂度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中语句的执行次数称为语句频度或时间频度，记为T(n)。算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作

T（n）=O（f（n））随着问题规模的增大，算法执行时间的增长率和f（n）的增长率相同，称为算法的渐近时间复杂度，简称时间复杂度。1.4算法和算法分析20①{++x;s=0;}②for(i=1;i<=n;++i){++x;s+=x;}③for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}O

（1）O

（n）O

（n2）算法的时间复杂度由嵌套最深的语句的频度决定的④i=1;while(i<=n)i=i*2;O

（log2n）1.4算法和算法分析21常数阶O(1)对数阶O(log2n)线性阶O(n)线性对数阶O(nlog2n)平方阶O(n2)立方阶O(n3)……K次方阶O(nk)指数阶O(2n)1.4算法和算法分析22

教学要求：

1、了解数据结构的相关术语:数据、数据元素、数据对象、数据类型、数据结构、数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系。

2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价。

3、掌握计算语句频度和估算算法时间复杂度的方法。第1章总结231、把矩形定义及其运算设计成一种抽象数据类型，其数据部分包括矩形的长度和宽度，操作部分包括初始化矩形的尺寸、求矩形的周长和面积。2、试用图形的形式表示下列二元组表示的数据结构，并指出它们分别属于何种结构。

(1)A=(K,R)，其中K={a1,a2,a3……an}