数据结构1-1绪论.ppt

通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。 … bat cat eat … 起始地址 例：（bat, cat, eat） * 通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素。 例：（bat, cat, eat） 0200 0208 0300 0325 … … … … bat 0200 cat 0325 eat ∧ * 2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。 数据元素之间的逻辑关系由元素的存储位置来表示。 存放学生表的结构体数组Stud定义为： struct { int no; /*存储学号*/ char name[8]; /*存储姓名*/ char sex[2]; /*存储性别*/ char class[4]; /*存储班号*/ } Stud[7]={{1,“张斌”,“男”,“9901”},…, {5,王萍,女,9901}}; * 结构体数组Stud各元素在内存中顺序存放,即第i(1≤i≤6)个学生对应的元素Stud[i]存放在第i+1个学生对应的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。 9901 女 王萍 5 … 9901 男 张斌 1 Stud[0] Stud[6] Stud数组起始地址 * 存放学生表的链表的结点类型StudType定义为： typedef struct studnode { int no; /*存储学号*/ char name[8]; /*存储姓名*/ char sex[2]; /*存储性别*/ char class[4]; /*存储班号*/ struct studnode *next; /*存储指向下一个学生的指针*/ } StudType； * 链表首结点地址head 1 张斌 男 9901 8 刘丽 女 9902 34 李英 女 9901 20 陈华 男 9902 12 王奇 男 9901 26 董强 男 9902 5 王萍 女 9901 ∧ 学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。 学生表构成的链表 * 顺序存储方法 定义：逻辑上相邻的结点存储在物理位置上也相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来表示 特点： 结点中只有自身信息域，没有连接信息域,存储密度大，存储空间利用率高 通过计算直接确定数据结构的中的第i个结点的存储地址Li， Li=L0+（i-1）*m ,其中L0为第一个结点的存储位置，m为每个结点所占用的存储单元个数。 插入和删除都会引起大量的结点移动 * 链式存储方法 定义：链式存储方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的关系由附加的指针来表示，指针指向结点的邻接结点 结点 特点： 存储结构的存储密度小，存储空间利用率低。 逻辑上相邻的结点，物理上不必邻接 删除和插入操作灵活方便，不必移动结点，只要改变结点中的指针值 数据域：存储结点本身的值 指针域：后继结点的存储单元地址 * 索引存储方法 建立一个附加的索引表，利用索引表中索引想的值确定时间存储单位地址。 散列存储方法 根据结点的关键字值，通过散列函数H（key）直接计算出结点的存储地址。 * 数据的运算 查找 插入 删除 修改 排序 * 数据结构的基本概念（小结） 数据的操作：插入、删除、修改、检索、排序等 数据的逻辑结构 数据的存储结构 顺序存储 链式存储 集合 线性结构 树结构 图结构 数据表示 * 数据结构的研究对象 计算机求解问题: 问题→抽象出问题的模型→求模型的解 问题——数值问题、非数值问题 数 值 问 题→数学方程 非数值问题→数据结构 * 学籍管理问题——表结构 学号 姓名 性别 出生日期 政治面貌 0001 王 军 男 1983/09/02 团员 0002 李 明 男 1982/12/25 党员 0003 汤晓影 女 1984/03/26 团员 … … … … … 数据结构的研究对象 * 例: 人机对弈问题——树结构 数据结构的研究对象 如何实现对弈?各格局之间是什么关系？ …… …….. …….. …… …... …… *