数据结构.ppt
《数据结构.ppt》由会员分享,可在线阅读,更多相关《数据结构.ppt(433页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机专业教研室计算机专业教研室 刘娜刘娜数据结构数据结构3/2/20233/2/2023学时数:72学时(16学时实验)+课程设计(一周)教 材:数据结构C语言版严蔚敏、吴伟民 -清华大学出版社(配题集)教学参考书:1殷人昆等,数据结构(用面向对象方法与殷人昆等,数据结构(用面向对象方法与C+描述),清华描述),清华大学出版社大学出版社2数据结构数据结构C语言篇语言篇习题与解析,李春葆,清华大学出版社习题与解析,李春葆,清华大学出版社3丁宝康等,数据结构自学考试指导,清华大学出版社丁宝康等,数据结构自学考试指导,清华大学出版社课程介绍课程介绍2第1章 绪论第2章 线性表第3章 栈和队列第4章
2、 串 第5章 数组和广义表 第6章 树和二叉树第7章 图第9章 查找第10章 内部排序 数据结构31.1什么是数据结构什么是数据结构1.2基本概念和术语基本概念和术语1.3抽象数据类型的表示和实现抽象数据类型的表示和实现1.4算法和算法分析算法和算法分析第1章绪论4一、数据结构课程的研究内容一、数据结构课程的研究内容 电子计算机的主要用途:电子计算机的主要用途:早期:早期:主要用于数值计算。主要用于数值计算。后来:后来:处理逐渐扩大到非数值计算领域(能处理处理逐渐扩大到非数值计算领域(能处理 多种复杂的具有一定结构关系的数据)多种复杂的具有一定结构关系的数据)数学模型数学模型选择计算机语言选择
3、计算机语言编出程序编出程序测试测试最终解答最终解答数据元素之间的相互关系一般无法用数学方程加以描述数据元素之间的相互关系一般无法用数学方程加以描述1.1什么是数据结构5 非数值计算问题 例1.1 电话号码查询问题。例1.2 田径赛的时间安排问题:设有六个比赛项目,规定每个选手至多可参加三个项目,有设有六个比赛项目,规定每个选手至多可参加三个项目,有五人报名参加比赛(如下表所示)。要求设计比赛日程表,五人报名参加比赛(如下表所示)。要求设计比赛日程表,使得在尽可能短的时间内完成比赛。使得在尽可能短的时间内完成比赛。1.1什么是数据结构6(1)设用如下六个不同的编码代表不同的项目:跳高跳高 跳远跳
4、远 标枪标枪 铅球铅球 100100米米 200200米米 A BA B C D E C D E F F姓名姓名项目项目1项目项目2项目项目3丁一丁一ABE马二马二CD张三张三CEF李四李四DFA王五王五BF(2)用顶点(圆圈)代表比赛项目 不能同时进行比赛的项目之间连上一条边。不能同时进行比赛的项目之间连上一条边。A AE EB BF FD DC C比赛比赛时间时间比赛比赛项目项目1A,C2B,D3E4F1.1什么是数据结构7因此,可以认为:数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。由此可见:对于解决非数值计算的问题首先要考虑对相关的各种信
5、息如何表示、组织和存储?对相关的各种信息如何表示、组织和存储?1.1什么是数据结构81.许卓群,张乃孝,杨冬青,唐世渭,许卓群,张乃孝,杨冬青,唐世渭,数据结构数据结构,国防科技大学计,国防科技大学计算机研究所,算机研究所,1985年年“按某种逻辑关系组织起来的一批数据,按一定的存储表示方式把它存按某种逻辑关系组织起来的一批数据,按一定的存储表示方式把它存储在计算机的存储器中,并在这些数据上定义了一个运算的集合,就叫储在计算机的存储器中,并在这些数据上定义了一个运算的集合,就叫做一个数据结构。做一个数据结构。”特点:从三个方面来看数据结构。特点:从三个方面来看数据结构。2.李春葆,李春葆,数据
6、结构(数据结构(C语言篇)习题与解析语言篇)习题与解析,清华大学出版社,清华大学出版社,2000年年“数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构又可以分为下述三个组成部分,它们分别是数据的逻辑结构、数据的存储又可以分为下述三个组成部分,它们分别是数据的逻辑结构、数据的存储结构和数据的运算。结构和数据的运算。”特点:明确强调特点:明确强调“关系关系”,且细分,且细分“关系关系”。1.1什么是数据结构93.黄国瑜,叶乃菁,黄国瑜,叶乃菁,数据结构数据结构,清华大学出版社,清华大学出版社,2001年年“在程序语言中,在
7、程序语言中,“数据类型数据类型”是指程序语言中变量所能表示并存储的是指程序语言中变量所能表示并存储的数据种类,数据种类,“数据实体数据实体”则是指在一种数据类型中的所有可能元素的集则是指在一种数据类型中的所有可能元素的集合。而合。而“数据结构数据结构”,大致上说来,就是数据实体中元素之间的关系,大致上说来,就是数据实体中元素之间的关系,包括数据的表示法和运算。包括数据的表示法和运算。”特点:指出特点:指出“关系关系”为表示法和运算。为表示法和运算。4.陈慧南,陈慧南,数据结构数据结构C语言描述语言描述,西安电子科技大学出版社,西安电子科技大学出版社,2003年年“从数学概念上讲,一个数据结构是
8、由数据元素依据某种逻辑联系组织起从数学概念上讲,一个数据结构是由数据元素依据某种逻辑联系组织起来的。来的。研究数据结构是为了解决应用问题,所以讨论数据结构必须同时讨论在数研究数据结构是为了解决应用问题,所以讨论数据结构必须同时讨论在数据结构上执行的相关运算及其算法才有意义。据结构上执行的相关运算及其算法才有意义。”特点:从逻辑联系入手,兼顾其它方面。特点:从逻辑联系入手,兼顾其它方面。1.1什么是数据结构10计算机内的数值运算依靠方程式,而非数值运算则计算机内的数值运算依靠方程式,而非数值运算则要依靠数据结构。要依靠数据结构。同样的数据对象,用不同的数据结构来表示,运算同样的数据对象,用不同的
9、数据结构来表示,运算效率可能有明显的差异。效率可能有明显的差异。程序设计实质程序设计实质=好算法好算法+好结构好结构二、学习数据结构课程的用处二、学习数据结构课程的用处1.1什么是数据结构11是介于数学、计算机硬件和计算机软件三者之间的一门核心课程数学数学硬件硬件软件软件三、数据结构课程的地位三、数据结构课程的地位1.1什么是数据结构12数据数据-是对客观事物的符号表示,在计算机科学中是指所有是对客观事物的符号表示,在计算机科学中是指所有(Data)能输入到计算机中并被计算机程序处理能输入到计算机中并被计算机程序处理的符号的总的符号的总称称(整数、实数、字符串、图像、声音等整数、实数、字符串、
10、图像、声音等)。数据元素数据元素-是数据的是数据的基本基本单位,具有完整确定的实际意义,单位,具有完整确定的实际意义,(DataElement)在计算机程序中通常作为一个整体进行考虑和在计算机程序中通常作为一个整体进行考虑和处理处理(又称记录、结点等又称记录、结点等)。数据项数据项-一个数据元素可由若干个数据项组成,一个数据元素可由若干个数据项组成,是数据的是数据的(DataItem)不可分割的不可分割的最小最小单位单位(又称字段等又称字段等)。三者之间的关系:数据三者之间的关系:数据数据元素数据元素数据项数据项例:例:学生档案学生档案 个人记录个人记录 姓名、性别、籍贯姓名、性别、籍贯1.2
11、基本概念和术语13数据对象数据对象(Data ObjectData Object)-是性质相同的数据元素的集合,是性质相同的数据元素的集合,是数据的一个子集。是数据的一个子集。数据结构数据结构(Data StructureData Structure)-是相互之间存在一种或多种是相互之间存在一种或多种 特定特定关系关系的的数据元素数据元素的集合。的集合。表示为:表示为:Data_Structure=(D,S)元素有限集元素有限集关系有限集关系有限集例例1:用数据结构表示一周中的七天。用数据结构表示一周中的七天。Data_Structure=(D,S),其中,其中,D=S=Mon,Tue,Wen
12、,Thu,Fri,Sat,Sun,1.2基本概念和术语14(1)Data_Structure=(D,S),其中,其中,D=01,02,03,04,05S=(2)S=(D,R)D=a,b,c,d,e,fR=,解解:上述表达式可用图形表示为:上述表达式可用图形表示为:aebcfd例2:将下述表达式用图形的形式表示出来集合结构线性结构1.2基本概念和术语15(3)Data_Structure=(D,S),其中,其中,D=01,02,03,04,05,06,07S=(01,02),(01,03),(01,04),(02,05),(02,06),(03,07)(4)S=(D,R)D=di|1i5,1j5
13、R=,ijd1d2d3d4d501020304050607树形结构图状结构1.2基本概念和术语16逻辑结构逻辑结构-数据元素之间的逻辑关系,即结构中定义的数据元素之间的逻辑关系,即结构中定义的“关系关系”。逻辑结构可细分为逻辑结构可细分为4类:类:集合结构集合结构线性结构线性结构树形结构树形结构图状结构图状结构一对一关系一对一关系一对多关系一对多关系多对多关系多对多关系非线性非线性结构结构1.2基本概念和术语1701000101物理结构物理结构-也称存储结构,是也称存储结构,是数据的逻辑结构在计算机存数据的逻辑结构在计算机存储器内的表示(映像)。储器内的表示(映像)。顺序映像顺序映像非顺序映像
14、非顺序映像特点是借助元素在存储器中的特点是借助元素在存储器中的相对位置相对位置来表示数来表示数据元素之间的逻辑关系。据元素之间的逻辑关系。特点是借助指示元素存储地址的特点是借助指示元素存储地址的指针指针表示数据表示数据元素之间的逻辑关系。元素之间的逻辑关系。例:例:复数复数 3.0-2.3i 的存储形式的存储形式3.0-2.301000201010102013.0-2.3算法的设计取决于选定的数据(逻辑)结构算法的设计取决于选定的数据(逻辑)结构算法的实现依赖于采用的存储结构算法的实现依赖于采用的存储结构-顺序存储结构顺序存储结构-链式存储结构链式存储结构1.2基本概念和术语18数据类型数据类
15、型-是一个是一个值的集合值的集合和定义在这个值集上的和定义在这个值集上的一组操作一组操作的总称。的总称。抽象数据类型抽象数据类型由用户定义,用以表示应用问题的数据模由用户定义,用以表示应用问题的数据模型。它由基本的数据类型组成,并包含一组相关的操作。型。它由基本的数据类型组成,并包含一组相关的操作。抽象数据类型抽象数据类型可用可用ADT=(D,S,P)三元组表示三元组表示数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集ADT 抽象数据类型名 数据对象:数据对象的定义 数据关系:数据关系的定义 基本操作:基本操作的定义 ADT 抽象数据类型名ADT常用常用定义定义格式格式1.3抽
16、象数据类型的表示与实现19例:例:给出自然数(给出自然数(Natural NumberNatural Number)的抽象数据类型定义。的抽象数据类型定义。IsZero(x):Boolean if(x=0)返回True else 返回FalseAdd(x,y):NaturalNumber if(x+y=MaxInt)返回 x+y else 返回MaxIntSubtract(x,y):NaturalNumber if(x y)返回 0 else 返回 x-yEqual(x,y):Boolean if(x=y)返回True else 返回 FalseADT NaturalNumber Natura
17、lNumber数据对象数据对象:数据关系数据关系:数据操作数据操作:一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0,结束于机器能表示的最大整数。结束于机器能表示的最大整数。1.3抽象数据类型的表示与实现20一、算法:一、算法:算法是对特定问题求解步骤的一种描述,它是指令的有限算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。序列,其中每一条指令表示一个或多个操作。二、算法的二、算法的5 5个特性:个特性:有穷性、确定性、可行性、输入和输出有穷性、确定性、可行性、输入和输出有穷性、确定性、可行性、输入和输出有穷性、确定性、可行性、输入和输出三
18、、算法设计的要求:三、算法设计的要求:正确性、可读性、健壮性、效率与低存储需求正确性、可读性、健壮性、效率与低存储需求时间复杂度时间复杂度空间复杂度空间复杂度1.4算法和算法分析21时间复杂度:一一个个算算法法花花费费的的时时间间与与算算法法中中语语句句的的执执行行次次数数成成正正比比例例,哪哪个个算算法法中中语语句句执执行行次次数数多多,它它花花费费时时间间就就多多。一一个个算算法法中中语语句的执行次数称为语句频度或时间频度,记为句的执行次数称为语句频度或时间频度,记为T(nT(n)。算法中基本操作重复执行的次数是算法中基本操作重复执行的次数是问题规模问题规模n的某个函数,算的某个函数,算法
19、的时间量度记作法的时间量度记作T(n)=O(f(n)随着问题规模的增大,算法执行时间的增长率和随着问题规模的增大,算法执行时间的增长率和f(n)的增的增长率相同,称为长率相同,称为算法的渐近时间复杂度算法的渐近时间复杂度,简称,简称时间复杂度时间复杂度。1.4算法和算法分析22 +x;sx;s=0;=0;for(ifor(i=1;i=1;i=n;+in;+i)+x;sx;s+=x;+=x;for(jfor(j=1;j=1;j=n;+jn;+j)for(kfor(k=1;k=1;k=n;+kn;+k)+x;sx;s+=x;+=x;OO(1)OO(n)OO(n2)算法的时间复杂度由嵌套最深的语句的
20、频度决定的 i=1;i=1;while(iwhile(i=n)i=i*2;=n)i=i*2;OO(log2n)1.4算法和算法分析23常数阶常数阶O O(1)对数阶对数阶O O(log2n)线性阶线性阶O O(n)线性对数阶线性对数阶O O(nlog2n)平方阶平方阶O O(n2)立方阶立方阶O O(n3)K K次方阶次方阶O O(nk)指数阶指数阶O O(2n)1.4算法和算法分析24 教学要求:教学要求:1 1、了解数据结构的相关术语、了解数据结构的相关术语:数据、数据元素、数据对象、数据、数据元素、数据对象、数据类型、数据结构、数据的逻辑结构与物理结构概念数据类型、数据结构、数据的逻辑结
21、构与物理结构概念 及逻辑结构与物理结构间的关系。及逻辑结构与物理结构间的关系。2 2、了解算法的定义、算法的特性、算法的时间代价、算法、了解算法的定义、算法的特性、算法的时间代价、算法 的空间代价。的空间代价。3 3、掌握计算语句频度和估算算法时间复杂度的方法。、掌握计算语句频度和估算算法时间复杂度的方法。第1章总结251 1、把矩形定义及其运算设计成一种抽象数据类型,其数据部、把矩形定义及其运算设计成一种抽象数据类型,其数据部 分包括矩形的长度和宽度,操作部分包括初始化矩形的尺分包括矩形的长度和宽度,操作部分包括初始化矩形的尺 寸、求矩形的周长和面积。寸、求矩形的周长和面积。2 2、试用图形
22、的形式表示下列二元组表示的数据结构,并指出、试用图形的形式表示下列二元组表示的数据结构,并指出 它们分别属于何种结构。它们分别属于何种结构。(1)A=(K,R),其中其中K=a1,a2,a3anR=(2)B=(K,R),其中,其中K=a,b,c,d,e,f,g,hR=rr=,(3)C=(K,R),其中,其中K=a,b,c,d,e,f,g,hR=,(4)D=(K,R),其中,其中K=1,2,3,4,5,6R=,作业作业26记录27线性结构的定义:线性结构的定义:若结构是非空有限集,则有且仅有一个开始结点和一个终端结若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一
23、个直接前驱和一个直接后继。点,并且所有结点都最多只有一个直接前驱和一个直接后继。线性结构的表达式线性结构的表达式(a1,a2,a3,an)线性结构的特点:线性结构的特点:有且仅有一个有且仅有一个首结点和尾结点首结点和尾结点 除首尾结点以外,其它结点除首尾结点以外,其它结点有且仅有一个有且仅有一个前驱结点前驱结点 和一个后继结点和一个后继结点线性结构包括:线性结构包括:线性表、栈、队列、数组和广义表线性表、栈、队列、数组和广义表结点间的逻辑关系是一对一的结点间的逻辑关系是一对一的线性结构线性结构282.1线性表的类型定义线性表的类型定义2.2线性表的顺序表示和实现线性表的顺序表示和实现2.3线性
24、表的链式表示和实现线性表的链式表示和实现2.4一元多项式的表示和相加一元多项式的表示和相加第2章线性表29一、线性表的定义一、线性表的定义 L=(a1,a2,ai-1,ai,ai+1,an)由由n个元素构成的有限序列,记为个元素构成的有限序列,记为n n为线性表的为线性表的长度长度,当当n=0n=0时时L L为空表为空表ai的直接前驱的直接前驱ai的直接后继的直接后继 同一线性表中的元素必定具有相同特性,即属同一线性表中的元素必定具有相同特性,即属同一线性表中的元素必定具有相同特性,即属同一线性表中的元素必定具有相同特性,即属 同一数据对象,且相邻元素具有序偶关系同一数据对象,且相邻元素具有序
25、偶关系同一数据对象,且相邻元素具有序偶关系同一数据对象,且相邻元素具有序偶关系 n n是有限大是有限大是有限大是有限大2.1线性表的类型定义30例例1:26个英文字母组成的英文表个英文字母组成的英文表(A,B,C,D,Z)例例2:学生情况登记表学生情况登记表学号学号姓名姓名性别性别年龄年龄班级班级0205210102052101于春梅于春梅女女2020计计0210210205210202052102林苹林苹女女2020计计0210210205210302052103康强康强男男2121计计0210210205210402052104黄一爽黄一爽女女2020计计0210212.1线性表的类型定义
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
限制150内