资源描述：
《数据结构概述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第1章数据结构概述数据结构课程的重要地位考研必考：数据结构（DataStructure）操作系统（OperationSystem）计算机行业中的作用应用程序的开发底层开发程序=算法+数据结构1.1什么是数据结构数据类型：intfloatchar43.5‘a’数组：inta[5]floatb[3]charc[7]a[0]1a[1]2a[2]3a[3]4a[4]5b[0]3.5b[1]4.1b[2]7.9c[0]Hc[1]ec[2]lc[3]lc[4]0c[5] c[6]1.1什么是数据结构数据类型：结构体：一个学生的基本信息包括学号，姓名，性别，年龄，籍贯线性表：结构体数组表中的每一行
2、是一个结点，除了第一个结点和最后一个结点以外，其余的结点都有且仅有一个直接前驱结点和一个直接后续结点,称为线性结构。0101张三男19河北省0101张三男19河北省0102李四女18辽宁省0103王五男19北京市0104赵六男20江苏省1.1什么是数据结构数据类型：树：网站中经常有树形结构的结点信息大外软件学院计算机教研室日语教研室英语教研室日语学院树中除了根结点以外，其余的结点都有且仅有一个直接前驱结点和一到多个直接后续结点，称为树形结构。1.1什么是数据结构数据类型：图：旅行家旅行问题图中每个结点都有多个直接前驱结点和多个直接后续结点，称为图形结构。图中主要涉及到最短路径问题和最优
3、路径问题。1.2数据的逻辑结构数据结构分为逻辑结构和存储结构例如：点名册上学生姓名的顺序和座位上学生的位置计算机资源管理器和文件具体存放的位置存储结构：数据在计算机内部，在硬盘或内存的存储方式，也称为物理结构。1.2.1基本概念和术语数据：能被计算机识别、存取和加工处理的符号、字符、图形、图像、声音和视频等一切信息都可以称为数据。数值型数据---整数、浮点数、复数、双精度数。非数值型数据---字符、字符串，以及文字、声音、图形、图像。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。每一个学生的信息1.2.1基本概念和术语数据项：是数据不可分割的、具有独
4、立意义的最小数据单位，是对数据元素属性的描述。学号、姓名、性别数据对象：是性质相同的数据元素的集合，是数据的一个子集。整数的数据对象是集合N={0,±1,±2,…}四季的数据对象是集合S={春，夏，秋，冬}在学校中，学生是数据对象，每个数据元素就是一个学生记录，每个学生记录包括：学号，姓名，性别，出生年月，家庭住址等数据项，以表明学生在某方面的属性。数据项大连市男1551987李明0001家庭住址性别出生时间姓名学号沈阳市男631986王庆0002日月年数据数据元素1.2.1基本概念和术语1.2.1基本概念和术语数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。集合：数据元素
5、之间除了“同属于一个集合”的关系之外，别无其他关系。线性结构：数据元素之间存在着“一对一”的关系。树形结构：数据元素之间存在着“一对多”的关系。图形结构：数据元素之间存在着“多对多”的关系。1.2.1基本概念和术语集合线性结构树形结构图形结构1.2.2逻辑结构的描述二元组表示法：G=（D,R）G表示数据逻辑结构的名称；D表示数据元素的有限集合；R表示D上所有元素之间关系的有限集合。1.2.2逻辑结构的描述【例1-4】一种数据结构Line=（D,R）D={1,2,3,4,5,6,7,8},R={r},r={<3,2>,<2,1>,<1,5>,<5,6>,<6,4>,<4,7>,<7,8>
6、}r是关系集合，尖括号表示数据元素的关系是有向的，如<3,2>表示从3指向2。1.2.2逻辑结构的描述【例1-5】一种数据结构Tree=（D,R）D={a,b,c,d,e,f,g,h,i},R={r}，r={,,,,,,,}1.2.2逻辑结构的描述【例1-6】一种数据结构Graph=（D,R）D={A,B,C,D,E,F},R={r}，r={(A,B),(A,C),(A,D),(B,E),(B,F),(C,E),(D,F),(E,F)}圆括号表示数据元素之间的关系是无向的，如(A,B)表示从A到B之间的边是
7、双向的。1.2.2逻辑结构的描述练习：下面给出几种逻辑结构，S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构（线性or非线性）。D={A，B，C，D，E，F},R={r1,r2,r3}(1)r1={〈A，B〉，〈B，C〉，〈C，D〉，〈D，E〉，〈E，F〉}(2)r2={〈A，B〉，〈B，C〉，〈B，D〉，〈D，E〉，〈D，F〉}(3)r3={〈A，B〉，〈B，C〉，〈D，A〉，〈D，B〉，〈D，E〉}1.2.2逻辑结构的
