数据结构-清华大学严蔚敏2课件.pptx

数据结构在计算机内存中的存储包括数据元素的 存储和元素之间的关系的表示。 元素之间的关系在计算机中有两种不同的表示方 • 顺序存储结构：用数据元素在存储器中的相对位 置来表示数据元素之间的逻辑结构(关系)。 1. 数据结构的存储方式 法：顺序表示和非顺序表示。由此得出两种不同的存储 结构：顺序存储结构和链式存储结构。 • 链式存储结构：在每一个数据元素中增加一个存 放另一个元素地址的指针(pointer )，用该指针来 表示数据元素之间的逻辑结构(关系)。 {3.0,2.3,5.0,-8.5,11.0} ， • 顺序结构：数据元素存放的地址是连续的； 的的存存储储结结构构 数数据据集集合合AA 同同 有有 不不 设设 种种 ：： 两两 例例 • 链式结构：数据元素存放的地址是否连续没有要 求。 数据的逻辑结构和物理结构是密不可分的两个方 面，一个算法的设计取决于所选定的逻辑结构，而算法 的实现依赖于所采用的存储结构。 D 2= (D ， 2) _ 存储结构： 数据元素在计算机中的存储及其逻辑 关系的表现称为数据的存储结构或物理结构。 数据操作： 对数据要进行的运算。 数据结构的三个组成部分： 数据元素之间逻辑关系的描述 逻辑结构 ： 性表是一种典型的线性结构。其基本特点是线性表中的 数据元素是有序且是有限的。在这种结构中： ① 存在一个唯一的被称为“第一个”的数据元素； ② 存在一个唯一的被称为“最后一个”的数据元素； ③ 除第一个元素外，每个元素均有唯一一个直接前 驱； 2. 线性表 ④ 除最后一个元素外，每个元素均有唯一一个直接 线性结构是最常用、最简单的一种数据结构。而线 后继。 用l个存储单元，以所占的第一个单元的存储地址作为 数据元素的存储位置。则线性表中第i+1个数据元素的 存储位置LOC(ai+1)和第i个数据元素的存储位置 LOC(ai)之间满足下列关系： Loc(a1) Loc(ai)+(i- 1)* l … a1 a2 … ai … an … 在具体的机器环境下：设线性表的每个元素需占 LOC(ai+1)=LOC(ai)+l 图2-1 线性表的顺序存储表示 存储链表中结点的一组任意的存储单元可以是连续 的，也可以是不连续的，甚至是零散分布在内存中的任 意位置上的。 链表中结点的逻辑顺序和物理顺序不一定相同。 2.3 线性表的链式存储 2.3.1 线性表的链式存储结构 链式存储 ：用一组任意的存储单元存储线性表中 的数据元素。用这种方法存储的线性表简称线性链表。 1305 单链表是由表头唯一确定，因此单 链表可以用头指针的名字来命名。 例1、线性表L=(bat ，cat ，eat ，fat ， hat) 其带头结点的单链表的逻辑状态和物理 存储方式如图2-3所示。 3700 3695 eat 3700 …… bat 1300 fat 1100 …… head hat NULL …… cat 1305 图2-3 带头结点的单链表的逻辑状态、物理存储方式 hat ⋀ fat head eat bat cat 1300 1100 …… 循环链表(Circular Linked List)：是一种 头尾相接的链表。其特点是最后一个结点的指针域指向 链表的头结点，整个链表的指针域链接成一个环。 2.3.3 循环链表 a1 a2 head 从循环链表的任意一个结点出发都可以找到链表 中的其它结点，使得表处理更加方便灵活。 图2-6是带头结点的单循环链表的示意图。 图2-6 单循环链表示意图 a n head 非空表 空表 双向链表(Double Linked List) :指的是构 成链表的每个结点中设立两个指针域：一个指向其直接 前趋的指针域prior，一个指向其直接后继的指针域 next 。这样形成的链表中有两个方向不同的链，故称 链表上的某些运算变得方便。 将头结点和尾结点链接起来也能构成循环链表，并 称之为双向循环链表。 双向链表是为了克服单链表的单向性的缺陷而引入 和单链表类似，双向链表一般增加头指针也能使双 2.4 双向链表 为双向链表。 的。 1 双向链表的结点及其类型定义 其结点形式如图2-7所示，带头结点的双向链表的形式 如图2-8所示。 prior data next 图2-8 带头结点的双向链表形式 图