数据结构 清华大学出版社 第1篇 绪论-1.ppt

逻辑结构和物理结构 逻辑结构: 数据元素之间的逻辑关系描述 物理结构: 数据逻辑结构在计算机中的表示,又称存储结构（元素的表示：位串，关系的表示：顺序与非顺序映像） 算法的设计取决于选定的逻辑结构 算法的实现依赖于采用的存储结构 原则上，一种逻辑结构可以采用任一种存储结构来存储（表示） 存储结构分：顺序、链接、索引和散列 考 数据的存储结构 —— 逻辑结构在存储器中的映象 “数据元素”的映象 ？ “关系”的映象 ？ 数据元素的映象方法： 用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 如用一个字长的位串表示一个整数， 用8位二进制数表示一个字符。 关系的映象方法： （表示?x, y?的方法） 1.顺序映象 以相对的存储位置表示后继关系 例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C 而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息 x y 元素n …….. 元素i …….. 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(a)=Lo+（i-1)*m 顺序存储 每个元素所占用 的存储单元个数 元素n …….. 元素i …….. 元素2 元素1 存储内容 顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 顺序存储结构的三个弱点： 1.作插入或删除操作时，需移动大量元数。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。 2.链式映象 以附加信息(指针)表示后继关系 需要用一个和 x 在一起的附加信息指示 y 的存储位置 y x 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 1345 h 链式存储 每个节点都由两部分组成：数据域和指针域。 数据域存放元素本身的数据， 指针域存放指针。 数据元素之间逻辑上的联系由指针来体现。 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 head 1346 元素3 1536 ……. …….. ……. 1536 元素2 1400 ……. …….. ……. ∧ 元素4 1346 1400 元素1 1345 指针 存储内容 存储地址 链式存储 1345 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 1345 h 链式存储 1.比顺序存储结构的存储密度小 (每个节点都由数据域和指针愈组成)。 2.逻辑上相邻的节点物理上不必相邻。 3.插入、删除灵活 (不必移动节点，只要改变节点中的指针)。 链接存储结构特点： 在不同的编程环境中， 存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。 例如： 顺序存储结构---一维数组 链式存储结构---指针 学号 姓名 性别 班号 1 张斌 男 9901 8 刘丽 女 9902 34 李英 女 9901 20 陈华 男 9902 12 王奇 男 9901 26 董强 男 9902 5 王萍 女 9901 例1.1 有一个学生表如表1.1所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。 例1.1中的记录顺序反映了数据元素之间的逻辑关系,我们用学号标识每个学生记录,这种逻辑关系可以表示为：1,8,8,34,34,20,20,12, 12,26,26,5 其中尖括号“ai,ai+1”表示元素ai和ai+1之间是相邻的,即ai在ai+1之前,ai+1在ai之后。 例如,采用二元组表示例1.1的学生表。 学生表中共有7个结点,依次用k1～k7表示,则对应的二元组表示为B=(D,R),其中： D={k1,k2,k3,k4,k5,k6,k7} R={r} r={k1,k2,k2,k3,k3,k4,k4,k5,k5,k6, k6,k7} 学号 姓名 性别 班号 1 张斌 男 9901 8 刘丽 女 9902 34 李英 女 9901 20 陈华 男 9902 12 王奇 男 9901 26 董强 男 9902 5 王萍 女 9901 表1.1中这些数据在计算机存储器中的存储方式就是存储结构。通常可以采用C/C++语言中的结构体数组和链表两种方式实现其存储结构。 存放学生表的结构体数组Stud定义为： struct { int no;