第三章数据结构与算法_线性结构(二)合编.ppt

广义表与多重链表 1.广义表(Generalized List) 特点：一种特殊的线性表，元素的值并非原子类型，可以再分解，表中元素也是一个广义表（即广义的线性表）。 对于线性表而言， n个元素都是基本的单元素； 广义表中，这些元素不仅可以是单元素也可以是另一个广义表。 抽象数据类型 ADT Glist { 数据对象： D＝{ei | i=1,2,..,n; n≥0; ei∈AtomSet 或 ei∈GList, AtomSet为某个数据对象 } 数据关系： LR＝{ei-1, ei | ei-1 ,ei∈D, 2≤i≤n} } ADT Glist 广义表的存储结构 由于广义表通常用链式结构，每个元素用一个结点表示。广义表结点可按结构不同分成两种，1.单元素 2.广义表。 1 2 原因：广义表的元素可以是不同结构（原子或列表） ? typedef struct GNode *GList; struct GNode{ int Tag; /*标志域：0表示结点是单元素，1表示结点是广义表 */ /*子表指针域Sublist与单元素数据域Data复用，即共用存储空间*/ union { ElementType Data; GList SubList; } URegion; GList Next; * 指向后继结点 */ }; Tag Data SubList Next 示例 （1）B=（a，（b, c ）,d） 0 1 ∧ 0 a 0 d 0 b 0 c 0 1 ∧ 1 2.多重链表 多重链表：链表中的节点可能同时隶属于多个链， 多重链表中结点的指针域会有多个， 如前面例子包含了Next和SubList两个指针域； 但包含两个指针域的链表并不一定是多重链表，比如在双向链 表但包含两个指针域的链表并不一定是多重链表。 ? ? 多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。 堆栈 1. 定义（stack） 是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。 与一般线性表的区别：仅在于运算规则不同。 2. 构成 栈顶（top）：在表中只允许进行插入和删除的一端； 栈底(bottom)：不允许进行插入和删除另一端。 举例： 特殊情况空栈 a b c 栈顶 栈底 逻辑结构 a b c 3. 运算规则 只能在栈顶运算，且访问结点时按照后进先出（LIFO，last in first out）原则。 练习： 一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则不可能得到的出栈序列是什么？ 分析：不可能的出栈顺序为312。 6 5 4 A B C B Top D C B Top 5 A Top A A 6 Top CreatStack( ); Push(S,A); Push(S,B); Push(S,C); D C B A 3 5 2 C B A Top B A Top A Top 6 1 Top x=Pop(S); x=Pop(S); x=Pop(S); IsEmpty (S) 4. 逻辑结构 与线性表相同，仍为一对一( 1:1)关系。 5. 主要运算 （1）入栈—插入元素到栈顶的操作； （2）出栈—从栈顶删除最后一个元素的操作。 6. 存储结构 顺序栈：栈的数组表示，但以顺序栈更常见； 链栈：栈的链式表示。 7.堆栈的抽象数据类型描述 类型名称: 堆栈（Stack） 数据对象集：一个有0个或多个元素的有穷线性表。 操作集：长度为MaxSize的堆栈S∈Stack，堆栈元素item∈ElementType 1、Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为MaxSize； 2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满； 3、void Push( Stack S, ElementType item )：将元素item压入堆栈； 4、int IsEmpty ( Stack S )：判断堆栈S是否为空； 5、ElementType Pop( Stack S )：删除并返回栈顶元素； 8.栈的顺序存储实现 栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。假设用一维数组Data[MaxSize]表示一个栈，MaxSize为栈中可存储数据元素的最大个数。习惯上将栈底放在数组下标小的那端，栈顶位置用一个整型变量Top记录