数据在计算机内部的组织-下.ppt

* * 第九章（下） 数据在计算机内部的组织 本部分将主要讨论：将以恰当的形式对在内存中拥有独立地址且物理上相互独立的存储单元进行组织，并考虑如何模拟这种抽象数据组织。目的是让用户以抽象的组织形式来考虑数据，并不关心数据在计算机内存中的实际组织方式。 学生信息管理 计算机和人对弈问题 交通灯管理问题 数据结构基础 抽象：将用户从实际数据存储的细节中抽象出来，允许用户以更方便的方法访问信息。 静态结构与动态结构：取决于结构的外形与大小是否随时间变化； 指针：就是包含有其他存储单元地址的一个存储单元，用来记录存储数据的位置。 数组 数组：将数据按照矩形排列存储到一个同质数组中。 0点 1点 2点 3点 …… 22点 23点 如果第一个读数所在的位置为x，则第n条数据在x+(n-1)的存储单元中。 数组（2） 行优先； 列优先； D E C 1700 2100 1200 1300 800 B 2000 1500 1100 1200 1000 A 周五 周四 周三 周二 周一 人员 某公司一周销售量 二维数组的行优先存储 数组（3） 在二维数组中，假设一个数组中列的数目为 c，第一行第一列所在的单元地址为 x，则数组中第 i 行第 j 列所在的位置为： 地 址 多 项 式 x+15 x+13 x+10 x+5 x x+13=x+(3-1)*5+(4-1) 表结构——邻接表（contiguous list） 在计算机内存中存储姓名表时，一种策略是将它保存在一片独立的地址连续的存储空间中。假设每一个名字最多有8个字符组成，可以把整个一大块空间划分为一组子块，每一块子块包含8个存储单元。 缺点：删除与添加时的处理方法； 表结构——链接表（linked list） 适用于：表中的不同单元存储在内存的不同位置而非一大块连续的空间。 姓 名1 指针 姓 名2 指针 姓 名3 NIL 头指针 姓 名 1 姓 名 2 姓 名 3 姓 名1 指针 姓 名2 指针 姓 名3 NIL 头指针 表结构——链接表（2） 链接表的删除 姓 名1 指针 姓 名2 指针 姓 名3 NIL 头指针 表结构——链接表（3） 链接表的插入 表结构——抽象概念表 （1）确定选用邻接表还是链接表； （2）写出通用过程：插入新条目、删除旧条目、有哪些信誉好的足球投注网站条目、输出条目等； 姓 名1 指针 姓 名2 指针 姓 名3 NIL 头指针 CurrentPointer←头指针； While (CurrentPointer不是NIL) do Begin 输出指针指向的条目的名字； 将当前结点的指针域的值赋给CurrentPointer； End 顺序输出链表中的姓名序列 堆栈 特点：插入和删除操作均在表结构的同一端进行。 其中，可以进行操作的端称为栈顶，另一端称为栈底。向堆栈中插入元素称为入栈，从栈中删除元素称为出栈。 姓 名1 指针 姓 名2 指针 姓 名3 NIL 头指针 CurrentPointer←头指针； While (CurrentPointer不是NIL) do Begin 指针指向的条目的名字入栈； 将当前结点的指针域的值赋给CurrentPointer； End While (栈非空) do 将栈中的名字弹出并且输出； 逆序输出链表中的姓名序列 先进后出 张 三 指针 李 四 指针 王 五 NIL 头指针 张 三 李 四 王 五 堆栈（2） 队列 特点：插入和删除操作在表结构的两端进行。 其中，可以进行插入操作的端称为队尾，另一端称为队头。向队列中插入元素称为入队，从队列中删除元素称为出队。 先进先出 头 尾 A B C 头 尾 C D E F G H I J 树 结点：树中的一个位置； 根结点：顶端的结点； 叶结点：与树的根结点相对应的另一终极端结点，又称末端结点； 子树：结点和它下面的结点组成的结构； 深度：从根结点到叶结点经过的结点数目； 二叉树：树的每一个结点最多有两个子结点； 二叉树的存储 包含数据的单元 左子结点 右子结点 根结点 A B C NIL D NIL NIL E NIL NIL F NIL NIL 二叉树的存储（2） A B C D E F 根结点 树的第二级结点 树的第三级结点 1 2 3 4 5 6 7 第 n 个结点的左右孩子结点可以在第 2n 个存储单元和第 2n+1 个存储单元中找到。 第 n 个结点的双亲结点可以在第 ?n/2? 个存储单元中找到。 二叉树的存储（3） A B C D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 E 15 特点：对空