第1周绪论第2讲-什么是数据结构.pdf

《第1周绪论第2讲-什么是数据结构.pdf》由会员分享，可在线阅读，更多相关《第1周绪论第2讲-什么是数据结构.pdf（29页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第1章章 绪绪 论论 数据结构中的几个概念数据结构中的几个概念 Word文档文档 图像文档图像文档 都是数据都是数据 而数据结构中主要而数据结构中主要讨论讨论结构化数据结构化数据。 学号学号姓名姓名性别性别班号班号 1张斌张斌男男9901 8刘丽刘丽女女9902 34李英李英女女9901 20陈华陈华男男9902 12王奇王奇男男9901 26董强董强男男9902 5王萍王萍女女9901 结构化数据结构化数据示例示例 一个学生表一个学生表 数据项数据项( (用于用于 描述数据元素描述数据元素) ) 数 据 元 素 数 据 元 素 数据结构数据结构数据对象数据对象结构结构 数据元素之间数据元素

2、之间 的关系构成结的关系构成结 构构 相同性质的相同性质的 数据元素的数据元素的 集合集合 数据元素之间的关系数据元素之间的关系 结构结构, ,现实世界的结构是现实世界的结构是纷繁复杂的纷繁复杂的 数据结构中数据结构中讨论讨论的元素关系的元素关系主要是指主要是指相邻相邻关系关系或或邻接关系邻接关系。 学号学号姓名姓名性别性别班号班号 1张斌张斌男男9901 8刘丽刘丽女女9902 34李英李英女女9901 20陈华陈华男男9902 12王奇王奇男男9901 26董强董强男男9902 5王萍王萍女女9901 相 邻 相 邻 不 相 邻 不 相 邻 一个数据结构的构成：一个数据结构的构成： 逻辑结

3、构逻辑结构 存储存储结构结构 数据运算数据运算 数据元素之间的数据元素之间的逻辑逻辑关系关系 数据数据的的逻辑结构逻辑结构。 数据元素及其关系在计算机存储器中的数据元素及其关系在计算机存储器中的存储存储方式方式 数据数据 的的存储存储结构结构（或或物理结构物理结构）。 施加在该数据施加在该数据上上的操作的操作 数据数据运算运算。 1、数据数据的逻辑结构表示的逻辑结构表示 数据的逻辑结构是面向用户的，它有多种表示形式。数据的逻辑结构是面向用户的，它有多种表示形式。 学号学号姓名姓名性别性别班号班号 1张斌张斌男男9901 8刘丽刘丽女女9902 34李英李英女女9901 20陈华陈华男男9902

4、 12王奇王奇男男9901 26董强董强男男9902 5王萍王萍女女9901 学生学生表的逻辑结构表的逻辑结构表示表示1 1- -表格表格 直 接 来 源 于 现 实 世 界 直 接 来 源 于 现 实 世 界 一个二元组表示为：一个二元组表示为： B=(D，R) 其中，其中，B是一种数据结构，它由数据元素的集合是一种数据结构，它由数据元素的集合D和和D上二元关系上二元关系 的集合的集合R所组成。其中：所组成。其中： D= di| 1in，n0：数据元素的集合数据元素的集合 R= rj| 1jm，m0：关系的集合关系的集合 二元组二元组是是一种通用的逻辑结构表示方法一种通用的逻辑结构表示方法

5、学生学生表的逻辑结构表的逻辑结构表示表示2 2- -二元组二元组 序偶序偶（x，y D） x为第一元素为第一元素，y为第二元素为第二元素。 x为为y的的前趋元素前趋元素。 y为为x的的后继元素后继元素。 若某个元素没有前趋元素若某个元素没有前趋元素，则称该元素为则称该元素为开始元素开始元素；若某个元；若某个元 素没有后继元素素没有后继元素，则称该元素为则称该元素为终端元素终端元素。 每个关系每个关系的的用若干个序偶来表示用若干个序偶来表示： 序偶序偶表示表示x、y是有向的，序偶是有向的，序偶(x，y)表示表示x、y是无向的是无向的 二元组逻辑表示：二元组逻辑表示： ， ， 学号学号姓名姓名性别

6、性别班号班号 1张斌张斌男男9901 8刘丽刘丽女女9902 34李英李英女女9901 20陈华陈华男男9902 12王奇王奇男男9901 26董强董强男男9902 5王萍王萍女女9901 每个学生记录用学号标识每个学生记录用学号标识 例如，如下数据为一例如，如下数据为一个矩阵：个矩阵： 对应的二元组表示为对应的二元组表示为B=(D，R)，其中：，其中： D=2,6,3,1,8,12,7,4,5,10,9,11 R=r1，r2 其中，其中，r1表示表示行关系行关系，r2表表示列关系示列关系 r1=，, ， r2=，, ， 2631 81274 510911 在在学生表中，用学号标识每个学生记录

7、，其逻辑结构学生表中，用学号标识每个学生记录，其逻辑结构用用 图形图形表示如下：表示如下： 18342012265 学生学生表的逻辑结构表的逻辑结构表示表示3 3- -图形图形 2、数据数据的存储结构表示的存储结构表示 数据数据在计算机存储器中的存储方式就是在计算机存储器中的存储方式就是存储存储结构结构。它是面向它是面向 程序员的程序员的。 逻辑结构逻辑结构 映射映射 设计存储结构的这种设计存储结构的这种映射应满足两映射应满足两个要求：个要求： 存储所有元素存储所有元素 存储数据元素间的关系存储数据元素间的关系 学生学生表存储结构表存储结构1 结构体数组结构体数组 存放学生表的结构体数组存放学

8、生表的结构体数组Stud定义如下：定义如下： Stud数组起始地址数组起始地址 学号学号姓名姓名性别性别班号班号 1张斌张斌男男9901 8刘丽刘丽女女9902 34李英李英女女9901 20陈华陈华男男9902 12王奇王奇男男9901 26董强董强男男9902 5王萍王萍女女9901 存储结构建立完毕存储结构建立完毕 学生表的逻辑结构学生表的逻辑结构 Stud0 1张斌张斌男男9901 Stud1 8刘丽刘丽女女9902 Stud6 5王萍王萍女女9901 映射过程：映射过程： 这种存储结构的这种存储结构的特点特点： 所有元素占用一整块内存空间。所有元素占用一整块内存空间。 逻辑上相邻的元

9、素，物理上也相邻。逻辑上相邻的元素，物理上也相邻。 顺序存储结构顺序存储结构 StudiStudi+1 直接映射直接映射 两个逻辑上相两个逻辑上相 邻元素邻元素 存储空间也相存储空间也相 邻邻 存放学生表的链表的节点类型存放学生表的链表的节点类型StudType声明如下：声明如下： 学生学生表存储结构表存储结构2 链表链表 1张斌张斌男男9901 链表首节链表首节 点 地 址点 地 址 head8刘丽刘丽女女9902 5王萍王萍女女9901 学号学号姓名姓名性别性别班号班号 1张斌张斌男男9901 8刘丽刘丽女女9902 34李英李英女女9901 20陈华陈华男男9902 12王奇王奇男男99

10、01 26董强董强男男9902 5王萍王萍女女9901 映射过程：映射过程： 学生表的逻辑结构学生表的逻辑结构 存 储 结 构 建 立 存 储 结 构 建 立 完 毕 完 毕 这种存储结构的特点：这种存储结构的特点： 一一个逻辑元素个逻辑元素用一个节点存储，每个节点单独分配，所有用一个节点存储，每个节点单独分配，所有 节点的地址不一定是连续的。节点的地址不一定是连续的。 用用指针来表示指针来表示逻辑关系。逻辑关系。 链式存储结构链式存储结构 3、数据数据运算运算 数据数据运算是对数据的操作。分为两个层次：运算是对数据的操作。分为两个层次：运算描述运算描述和和运算实现运算实现。 对于对于“学生表

11、学生表”这种数据结构这种数据结构，可以进行一系列的运算：可以进行一系列的运算： 查找序号为查找序号为2的学生姓名的学生姓名 增加增加一个学生记录；一个学生记录； 删除一个学生记录；删除一个学生记录； 查找性别为查找性别为“女女”的学生记录；的学生记录； 查找班号为查找班号为“9902”的学生记录；的学生记录； 运 算 描 述 运 算 描 述 顺序顺序存储结构中存储结构中实现实现“查找序号为查找序号为2的学生姓名的学生姓名” Stud数组起始地址数组起始地址 Stud0 1张斌张斌男男9901 Stud1 8刘丽刘丽女女9902 直接找到直接找到Stud1 记录，记录， 返回返回刘丽刘丽 hea

12、d 链式链式存储结构中存储结构中实现“查找序号为实现“查找序号为2的学生姓名”的学生姓名” 1张斌张斌男男9901 8刘丽刘丽女女9902 34李英李英女女9901 20陈华陈华男男9902 5王萍王萍女女9901 12王奇王奇男男9901 26董强董强男男9902 i=1，p i 2 i=2，p i=2 找 到 序 号 为 找 到 序 号 为 2 的 记 录 ， 返 的 记 录 ， 返 回回 刘 丽 刘 丽 结论结论： 同一逻辑结构可以对应多种存储结构同一逻辑结构可以对应多种存储结构。 同样的运算同样的运算，在不同的存储结构中在不同的存储结构中，其实现过程是不同的其实现过程是不同的。 本讲完本讲完