数据结构绪.ppt
《数据结构绪.ppt》由会员分享,可在线阅读,更多相关《数据结构绪.ppt(80页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构绪数据结构绪现在学习的是第1页,共80页2关于教材关于教材主教材主教材 管致锦,徐慧,陈德裕管致锦,徐慧,陈德裕管致锦,徐慧,陈德裕管致锦,徐慧,陈德裕.数据结构(数据结构(C C C C版)版)版)版).清华大学清华大学清华大学清华大学出版社出版社出版社出版社实践教材实践教材 徐慧等徐慧等.数据结构实践教程数据结构实践教程数据结构实践教程数据结构实践教程.清华大学出版社清华大学出版社习题与学习辅导习题与学习辅导陈德裕等。数据结构习题与学习指导陈德裕等。数据结构习题与学习指导陈德裕等。数据结构习题与学习指导陈德裕等。数据结构习题与学习指导.清华大学出版社清华大学出版社现在学习的是第2页
2、,共80页3如何使用教材如何使用教材主教材主教材 基本原理、学习中心基本原理、学习中心实践教材实践教材 验证实验验证实验验证实验验证实验设计实验设计实验设计实验设计实验综合实验综合实验综合实验综合实验辅导教材辅导教材 知识结构、学习要点、重点难点释疑、习题解析知识结构、学习要点、重点难点释疑、习题解析知识结构、学习要点、重点难点释疑、习题解析知识结构、学习要点、重点难点释疑、习题解析光盘光盘 验证实验源程序验证实验源程序现在学习的是第3页,共80页4第第 1 1 章章 绪论绪论现在学习的是第4页,共80页5本章目录本章目录1.1数据结构的相关概念数据结构的相关概念 1.2数据类型和抽象数据类型
3、数据类型和抽象数据类型 1.3算法与算法分析算法与算法分析 现在学习的是第5页,共80页61.1 1.1 基本概念基本概念1.1.数据结构历史沿革数据结构历史沿革2.2.数据结构研究范畴数据结构研究范畴3.3.数据结构基本概念数据结构基本概念4.4.基本的逻辑结构基本的逻辑结构5.5.基本的物理结构基本的物理结构现在学习的是第6页,共80页7 1968196819681968年美国人年美国人Donald E.KnuthDonald E.KnuthDonald E.KnuthDonald E.Knuth开创了数开创了数开创了数开创了数据结构的最初体系,他所著的据结构的最初体系,他所著的据结构的最
4、初体系,他所著的据结构的最初体系,他所著的计算机程计算机程序设计的艺术序设计的艺术第一卷第一卷基本算法基本算法是第是第是第是第一本较系统地阐述数据的逻辑结构和存储结一本较系统地阐述数据的逻辑结构和存储结一本较系统地阐述数据的逻辑结构和存储结一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。构及其操作的著作。构及其操作的著作。构及其操作的著作。19681968年,数据结构作为一门独立的课程在年,数据结构作为一门独立的课程在年,数据结构作为一门独立的课程在年,数据结构作为一门独立的课程在国外开始出现。国外开始出现。国外开始出现。国外开始出现。数据结构历史沿革数据结构历史沿革现在学习的是第7页
5、,共80页8数据结构的发展数据结构的发展 从从从从20202020世世世世纪纪纪纪6060年年年年代代代代末末末末到到到到7070年年年年代代代代初初初初,出出出出现现现现了了了了大大大大型型型型程程程程序序序序,软软软软件件件件也也也也相相相相对对对对独独独独立立立立,结结结结构构构构程程程程序序序序设设设设计计计计成成成成为为为为程程程程序序序序设设设设计计计计方方方方法法法法学学学学的的的的主主主主要要要要内内内内容容容容,人人人人们们们们越来越重视数据结构越来越重视数据结构越来越重视数据结构越来越重视数据结构从从7070年代中期到年代中期到年代中期到年代中期到80808080年代,各种
6、版本的数据结构著作相继出年代,各种版本的数据结构著作相继出年代,各种版本的数据结构著作相继出年代,各种版本的数据结构著作相继出现。目前,数据结构的发展并未终结,一方面,面向各专门现。目前,数据结构的发展并未终结,一方面,面向各专门现。目前,数据结构的发展并未终结,一方面,面向各专门现。目前,数据结构的发展并未终结,一方面,面向各专门领域中特殊问题的数据结构得到研究和发展,如多维图形数领域中特殊问题的数据结构得到研究和发展,如多维图形数领域中特殊问题的数据结构得到研究和发展,如多维图形数领域中特殊问题的数据结构得到研究和发展,如多维图形数据结构等;另一方面,从抽象数据类型和面向对象的观点来据结构
7、等;另一方面,从抽象数据类型和面向对象的观点来据结构等;另一方面,从抽象数据类型和面向对象的观点来据结构等;另一方面,从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势,越来越被人们所重视。讨论数据结构已成为一种新的趋势,越来越被人们所重视。讨论数据结构已成为一种新的趋势,越来越被人们所重视。讨论数据结构已成为一种新的趋势,越来越被人们所重视。数据结构问题起源于程序设计数据结构问题起源于程序设计 现在学习的是第8页,共80页9 数据结构的发展并未终结数据结构的发展并未终结1.1.1.1.无结构阶段无结构阶段2.2.2.2.结构化阶段:数据结构算法程序结构化阶段:数据结构算法程序结构
8、化阶段:数据结构算法程序结构化阶段:数据结构算法程序3.3.面向对象阶段:面向对象阶段:面向对象阶段:面向对象阶段:(数据结构算法)程序(数据结构算法)程序(数据结构算法)程序(数据结构算法)程序数据结构的发展阶段数据结构的发展阶段现在学习的是第9页,共80页10数据结构研究对象数据结构研究对象计算机科学是对信息进行表示和处理的科学。计算机科学是对信息进行表示和处理的科学。计算机中表示和处理的信息以数据的形式体现。计算机中表示和处理的信息以数据的形式体现。计算机中表示和处理的信息以数据的形式体现。计算机中表示和处理的信息以数据的形式体现。数据的表示和组织直接关系到计算机程序能否处理这些数据数据
9、的表示和组织直接关系到计算机程序能否处理这些数据数据的表示和组织直接关系到计算机程序能否处理这些数据数据的表示和组织直接关系到计算机程序能否处理这些数据以及处理的效率。以及处理的效率。以及处理的效率。以及处理的效率。设计高效率、高可靠性的程序需要设计高效率、高可靠性的程序需要:(1)(1)研究数据的特性、数据间的相互关系;研究数据的特性、数据间的相互关系;(2)(2)数据在计算机内部的存储表示。数据在计算机内部的存储表示。(3)(3)(3)(3)利用这些特性和关系设计出相应的算法和程序利用这些特性和关系设计出相应的算法和程序 数值计算数值计算数值计算数值计算非数值计算非数值计算现在学习的是第1
10、0页,共80页11 结构静力分析计算结构静力分析计算 -线性代数方程组线性代数方程组 -环流模式方程环流模式方程 (球面坐标系球面坐标系)全球天气预报全球天气预报 数值计算的程序设计问题数值计算的程序设计问题现在学习的是第11页,共80页12数据计算问题:百鸡问题数据计算问题:百鸡问题公元公元公元公元5 5世纪末,我国古代数据家张丘建在他所撰写的世纪末,我国古代数据家张丘建在他所撰写的算经算经算经算经中,提出了这样一个问题:中,提出了这样一个问题:“鸡翁一,值钱五;鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一。百钱买百鸡,问鸡鸡母一,值钱三;鸡雏三,值钱一。百钱买百鸡,问鸡翁、母、雏各几何?
11、即:翁、母、雏各几何?即:公鸡每只公鸡每只公鸡每只公鸡每只5 5元、母鸡每只元、母鸡每只3 3元、小鸡元、小鸡元、小鸡元、小鸡3 3 3 3只只只只1 1 1 1元,用元,用元,用元,用100100100100元钱买元钱买元钱买元钱买100100只鸡,求公鸡、母鸡、小鸡的只数。只鸡,求公鸡、母鸡、小鸡的只数。只鸡,求公鸡、母鸡、小鸡的只数。只鸡,求公鸡、母鸡、小鸡的只数。设设a a、b b、c c分别为公鸡、母鸡、小鸡的只数,则:分别为公鸡、母鸡、小鸡的只数,则:a+b+c=100a+b+c=100 5a+3b+c/3=100 5a+3b+c/3=100 c%3=0 c%3=0现在学习的是第1
12、2页,共80页13非数值计算问题:非数值计算问题:学籍管理问题学籍管理问题姓名姓名学号学号性性别别年年龄龄健康状况健康状况王好好王好好0721010107210101男男2020良好良好李平平李平平0721010207210102男男1919一般一般赵赵深深深深0721010307210103女女1818良好良好钱钱多多多多0721010407210104男男1919较较差差.现在学习的是第13页,共80页14 以上家庭成员关系之间构成了一个树状结构,结构以上家庭成员关系之间构成了一个树状结构,结构以上家庭成员关系之间构成了一个树状结构,结构以上家庭成员关系之间构成了一个树状结构,结构中的数据
13、元素之间存在一对多的关系。中的数据元素之间存在一对多的关系。中的数据元素之间存在一对多的关系。中的数据元素之间存在一对多的关系。构成家庭成员名的集合,构成家庭成员名的集合,如如 父亲,儿子,女儿,孙子,孙女父亲,儿子,女儿,孙子,孙女,这些数据有一个共,这些数据有一个共,这些数据有一个共,这些数据有一个共同特征,即他们都是家庭的成员名。同特征,即他们都是家庭的成员名。同特征,即他们都是家庭的成员名。同特征,即他们都是家庭的成员名。非数值计算问题:非数值计算问题:家庭成员的关系家庭成员的关系现在学习的是第14页,共80页15如何实现对弈如何实现对弈?各格局之间是什么关系?各格局之间是什么关系?.
14、非数值计算问题:非数值计算问题:人机对弈问题人机对弈问题现在学习的是第15页,共80页16C C C C4 4 4 4,C,C,C,C5 5 5 5,C,C,C,C6 6 6 6数据库原理数据库原理数据库原理数据库原理C C C C7 7 7 7C C C C2 2 2 2,C C C C4 4 4 4计算机原理计算机原理计算机原理计算机原理C C C C6 6 6 6C C C C3 3 3 3,C,C,C,C4 4 4 4数据结构数据结构数据结构数据结构C C C C5 5 5 5C C C C1 1 1 1,C,C,C,C2 2 2 2程序设计程序设计程序设计程序设计C C C C4 4
15、 4 4C C C C1 1 1 1离散数学离散数学离散数学离散数学C C C C3 3 3 3无无无无计算机导论计算机导论计算机导论计算机导论C C C C2 2 2 2无无无无高等数学高等数学高等数学高等数学C C C C1 1 1 1先修课先修课先修课先修课课程名称课程名称课程名称课程名称编号编号编号编号C1C2C3C4C6C5C7如何表示课程之间的先修关系?如何表示课程之间的先修关系?非数值计算问题:非数值计算问题:教学计划编排问题教学计划编排问题现在学习的是第16页,共80页17图 1-2 煤气管道的铺设示意图 以上煤气管道线之间构成了网状结构,结构中的数据元素之以上煤气管道线之间构
16、成了网状结构,结构中的数据元素之间存在多对多的关系。间存在多对多的关系。非数值计算问题:非数值计算问题:煤气管道的铺设煤气管道的铺设如下图需为城市的各小区之间铺设煤气管道,对如下图需为城市的各小区之间铺设煤气管道,对如下图需为城市的各小区之间铺设煤气管道,对如下图需为城市的各小区之间铺设煤气管道,对 n n 个小个小区只需铺设区只需铺设 n-1 n-1 n-1 n-1 条管线,由于地理环境等不同因素使各条条管线,由于地理环境等不同因素使各条条管线,由于地理环境等不同因素使各条条管线,由于地理环境等不同因素使各条管线所需投资不同管线所需投资不同管线所需投资不同管线所需投资不同(如图上所标识如图上
17、所标识如图上所标识如图上所标识),如何使投资成本最低,如何使投资成本最低?现在学习的是第17页,共80页18非数值计算问题:非数值计算问题:多叉路口的交通灯设置多叉路口的交通灯设置有连线的节点用不同有连线的节点用不同的颜色标记的颜色标记,表示不表示不能同时通行能同时通行要求使用的颜色数尽要求使用的颜色数尽可能少可能少,以使减少等以使减少等待时间待时间这是图论中的四色这是图论中的四色问题问题现在学习的是第18页,共80页19计算机处理问题的一般过程计算机处理问题的一般过程 问题数学模型建模实现求精机外表示机外表示处理要求处理要求逻辑结构逻辑结构基本运算基本运算存储结构存储结构算法算法现在学习的是
18、第19页,共80页20数据结构研究范畴数据结构研究范畴(1)(1)建立数据模型建立数据模型逻辑结构逻辑结构(2)(2)计算机中的表示计算机中的表示物理物理/存储结构存储结构(3)(3)操作在计算机中的实现操作在计算机中的实现算法算法现在学习的是第20页,共80页21表表1-1 数据结构的核心技术是数据结构的核心技术是数据结构的核心技术是数据结构的核心技术是分解分解分解分解与与抽象抽象。通过分解可以划分出。通过分解可以划分出。通过分解可以划分出。通过分解可以划分出数据的三个层次;数据的三个层次;数据的三个层次;数据的三个层次;通过通过抽象抽象抽象抽象,舍弃数据元素的,舍弃数据元素的具体内容,就得
19、到逻辑结构。具体内容,就得到逻辑结构。通过通过通过通过分解分解将处理要求划分成将处理要求划分成将处理要求划分成将处理要求划分成各种功能各种功能各种功能各种功能通过通过抽象抽象抽象抽象舍弃实现细节,就舍弃实现细节,就得到运算的定义。得到运算的定义。方面方面层层次次数据表示数据表示 数据数据处处理理抽象抽象逻辑结逻辑结构构基本运算基本运算实现实现物理物理结结构构算法算法评评价价不同数据不同数据结结构的比构的比较较及算法分析及算法分析数据结构课程内容体系数据结构课程内容体系数据结构的内容包括三个层次的数据结构的内容包括三个层次的五个五个“要素要素”,如表,如表,如表,如表1-11-1所示。所示。所示
20、。所示。现在学习的是第21页,共80页22数据结构地位数据结构地位现在学习的是第22页,共80页23有关概念和术语有关概念和术语数据数据:所有能:所有能输入输入输入输入到计算机中并能被计算机程序到计算机中并能被计算机程序识别和处识别和处理理的符号集合。的符号集合。数值数据数值数据数值数据数值数据:整数、实数等:整数、实数等:整数、实数等:整数、实数等 非数值数据非数值数据非数值数据非数值数据:图形、图象、声音、文字等:图形、图象、声音、文字等 数据元素数据元素数据元素数据元素:数据的:数据的:数据的:数据的基本基本基本基本单位,在计算机程序中通常作为一个单位,在计算机程序中通常作为一个单位,在
21、计算机程序中通常作为一个单位,在计算机程序中通常作为一个整体整体进行考虑和处理。进行考虑和处理。数据项数据项数据项数据项:构成数据元素的不可分割的最小单位。:构成数据元素的不可分割的最小单位。关键字:关键字:是指能识别一个或多个数据元素的数据项。若能是指能识别一个或多个数据元素的数据项。若能起唯一识别的作用,则称之为起唯一识别的作用,则称之为 主主 关键字,否则称之为关键字,否则称之为关键字,否则称之为关键字,否则称之为 次次 关键字。关键字。数据对象数据对象数据对象数据对象:具有相同:具有相同性质性质性质性质的数据元素的集合。的数据元素的集合。现在学习的是第23页,共80页24数据、数据元素
22、、数据项之间的关系数据、数据元素、数据项之间的关系包含关系包含关系:数据是由数据元素组成,数据元素是由:数据是由数据元素组成,数据元素是由数据项组成。数据项组成。数据元素数据元素是讨论数据结构时涉及的最小数据单位,是讨论数据结构时涉及的最小数据单位,其中的数据项一般不予考虑。其中的数据项一般不予考虑。姓名姓名学号学号性别性别班号班号出生日期出生日期入学成绩入学成绩年年月月日日现在学习的是第24页,共80页25数据结构数据结构数据结构数据结构:相互之间存在一定:相互之间存在一定:相互之间存在一定:相互之间存在一定关系关系关系关系的数据元素的集合。按照视的数据元素的集合。按照视的数据元素的集合。按
23、照视的数据元素的集合。按照视点的不同,数据结构分为逻辑结构和存储结构。点的不同,数据结构分为逻辑结构和存储结构。点的不同,数据结构分为逻辑结构和存储结构。点的不同,数据结构分为逻辑结构和存储结构。逻辑结构逻辑结构:指数据元素之间:指数据元素之间:指数据元素之间:指数据元素之间逻辑关系逻辑关系的整体。的整体。的整体。的整体。关联方式或邻接关系关联方式或邻接关系数据的逻辑结构是从具体问题抽象出来的数据模型数据的逻辑结构是从具体问题抽象出来的数据模型数据结构数据结构存储结构存储结构:又称为:又称为物理结构物理结构物理结构物理结构,是数据及其逻辑结构在,是数据及其逻辑结构在,是数据及其逻辑结构在,是数
24、据及其逻辑结构在计计算机算机中的表示。中的表示。实质上是内存分配,实质上是内存分配,在具体实现时,依赖于计算机语言。在具体实现时,依赖于计算机语言。现在学习的是第25页,共80页26典型逻辑结构典型逻辑结构2.线性表:数据元素之间存在着数据元素之间存在着一对一的线性关系;一对一的线性关系;3.树:数据元素之间存在数据元素之间存在着一对多的层次关系着一对多的层次关系ABCDEFGHIJMKL4.图:数据元素之间存在数据元素之间存在 着多对多的任意关系。着多对多的任意关系。BACDFE1.集合:数据元素之间就是数据元素之间就是 “属于同一个集合属于同一个集合”现在学习的是第26页,共80页27数据
25、结构的形式定义数据结构的形式定义 Data_Structure Data_Structure(D D,R R)(1-11-1)D D是数据元素的有限集,是数据元素的有限集,R R是是D D上关系的有限集。上关系的有限集。D=D=父亲,儿子,女儿,孙子,孙女父亲,儿子,女儿,孙子,孙女父亲,儿子,女儿,孙子,孙女父亲,儿子,女儿,孙子,孙女 R=R=R=R=(父亲(父亲,儿子)儿子),(父亲(父亲(父亲(父亲,女儿)女儿),(儿子(儿子,孙子),孙子),孙子),孙子),(儿子儿子儿子儿子,孙女)孙女)例例1.21.21.21.2中家庭成员数据结构可以中家庭成员数据结构可以中家庭成员数据结构可以中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
限制150内