《第三章 数据结构与算法_线性结构(二)》由会员分享，可在线阅读，更多相关《第三章 数据结构与算法_线性结构(二)（31页珍藏版）》请在金锄头文库上搜索。
1、,广义表与多重链表,1.广义表(Generalized List) 特点：一种特殊的线性表，元素的值并非原子类型，可以再分解，表中元素也是一个广义表（即广义的线性表）。 对于线性表而言， n个元素都是基本的单元素； 广义表中，这些元素不仅可以是单元素也可以是另一个广义表。,抽象数据类型 ADT Glist 数据对象：Dei | i=1,2,n; n0; eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：LR| ei-1 ,eiD, 2in ADT Glist,广义表的存储结构,由于广义表通常用链式结构，每个元素用一个结点表示。广义表结点可按结构不同分成两种，1.单
2、元素 2.广义表。,1,2,原因：广义表的元素可以是不同结构（原子或列表）, typedef struct GNode *GList; struct GNode int Tag; /*标志域：0表示结点是单元素，1表示结点是广义表 */*子表指针域Sublist与单元素数据域Data复用，即共用存储空间*/ union ElementType Data; GList SubList; URegion; GList Next; * 指向后继结点 */ ;,示例,（1）B=（a，（b, c ）,d）,2.多重链表,多重链表：链表中的节点可能同时隶属于多个链， 多重链表中结点的指针域会有多个， 如前
3、面例子包含了Next和SubList两个指针域； 但包含两个指针域的链表并不一定是多重链表，比如在双向链 表但包含两个指针域的链表并不一定是多重链表。,多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。,堆栈,1. 定义（stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。 与一般线性表的区别：仅在于运算规则不同。 2. 构成 栈顶（top）：在表中只允许进行插入和删除的一端； 栈底(bottom)：不允许进行插入和删除另一端。,举例：,特殊情况空栈,逻辑结构,3. 运算规则只能在栈顶运算，且访问结点时按照后进先出（LIFO，
4、last in first out）原则。 练习：一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则不可能得到的出栈序列是什么？,分析：不可能的出栈顺序为312。,6,5,4,A,B,C,B,Top,D,CB,Top,5,A,Top,A,A,6,TopCreatStack( ); Push(S,A);,Push(S,B);,Push(S,C);,D,C,B,A,3,5,2,CBA,Top,BA,Top,A,Top,6,1,Top,x=Pop(S);,x=Pop(S);,x=Pop(S);,IsEmpty (S),4. 逻辑结构与线性表相同，仍为一对一( 1:1)关系。 5. 主要运算（
5、1）入栈插入元素到栈顶的操作；（2）出栈从栈顶删除最后一个元素的操作。 6. 存储结构顺序栈：栈的数组表示，但以顺序栈更常见；链栈：栈的链式表示。,7.堆栈的抽象数据类型描述,类型名称: 堆栈（Stack）,数据对象集：一个有0个或多个元素的有穷线性表。,操作集：长度为MaxSize的堆栈SStack，堆栈元素itemElementType,1、Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为MaxSize；,2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；,3、void Push( Stack S, E
6、lementType item )：将元素item压入堆栈；,4、int IsEmpty ( Stack S )：判断堆栈S是否为空；,5、ElementType Pop( Stack S )：删除并返回栈顶元素；,8.栈的顺序存储实现 栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。假设用一维数组DataMaxSize表示一个栈，MaxSize为栈中可存储数据元素的最大个数。习惯上将栈底放在数组下标小的那端，栈顶位置用一个整型变量Top记录当前栈顶元素的下标值，当Top指向-1时，表示空栈；当Top指向MaxSize-1时，表示满栈。 顺序栈类型Stack如下：#defi
7、ne MaxSize typedef struct SNode Stack;struct SNodeElementType DataMaxSize;int Top;,（1）入栈操作Push 首先判别栈是否满，若不满，Top加1，并将新元素放入Data数组的Top分量中。 void Push( Stack PtrS, ElementType item ) if ( PtrS-Top = MaxSize-1 ) printf(“堆栈满”); return;elsePtrS-Data+(PtrS-Top)=item;return;,（2）出栈操作Pop 首先判别栈是否空；若不空，返回DataTop，
8、同时将Top减1。 ElementType Pop( Stack PtrS ) if ( PtrS-Top = -1 ) printf(“堆栈空”);return ERROR; elsereturn ( PtrS-Data(PtrS-Top)- ); ,例 请用一个数组实现两个堆栈，要求最大地利用数组空间，使 数组只要有空间入栈操作就可以成功。 【分析】 一种比较聪明的方法是使这两个栈分别从数组的两头开始 向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。#define MaxSize struct DStack ElementType DataMaxSize;int Top1; /*
9、堆栈的栈顶指针 */int Top2; /* 堆栈的栈顶指针*/ S; 两个堆栈的初始化方法是： S.Top1 = -1; S.Top2 = MaxSize;,void Push( struct DStack *PtrS, ElementType item, int Tag ) /* Tag作为区分两个堆栈的标志，取值为1和2 */if ( PtrS-Top2 PtrS-Top1 = 1) /*堆栈满*/printf(“堆栈满”);return;if ( Tag = 1 ) /* 对第一个堆栈操作 */PtrS-Data+(PtrS-Top1) = item;elsePtrS-Data-(Pt
10、rS-Top2) = item;,ElementType Pop( struct DStack *PtrS, int Tag ) /* Tag作为区分两个堆栈的标志，取值为1和2*/if ( Tag = 1 ) /* 对第一个堆栈操作*/if ( PtrS-Top1 = -1 ) /*堆栈1空*/printf(“堆栈1空”);return NULL; else return PtrS-Data(PtrS-Top1)-; else /* 对第二个堆栈操作 */if ( PtrS-Top2 = MaxSize ) /*堆栈2空 */printf(“堆栈2空”); return NULL; else
11、 return PtrS-Data(PtrS-Top2)+; ,9.堆栈的链式存储实现 栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删 除操作只能在链栈的栈顶进行。栈顶指针Top就是链表的头指针。typedef struct SNodeElementType Data;struct SNode *Next;LinkStack; LinkStack *Top;,为了表示方便，链栈附带一空的表头结点，表头结点后面的第一个结点就是链栈的栈顶结点，栈中的其他结点通过它们的指针Next链接起来，栈底结点的Next为NULL。 (1) 堆栈初始化（建立空栈） LinkStack CreateSt
12、ack() /* 构建一个堆栈的头结点，返回指针 */Stack S;S =(Stack)malloc(sizeof(struct SNode);S-Next = NULL;return S;,(2) 判断堆栈S是否为空 int IsEmpty(LinkStack S) /*判断堆栈S是否为空，若为空函数返回整数1，否则返回0 */ return ( S-Next = NULL ); (3)入栈 void Push( ElementType item, LinkStack *S) /* 将元素item压入堆栈S */ struct SNode *TmpCell; mpCell=(struct
13、SNode *)malloc(sizeof(struct SNode); TmpCell-Element = item; TmpCell-Next = S-Next; S-Next = TmpCell; ,（4）出栈 ElementType Pop(Stack S) /* 删除并返回堆栈S的栈顶元素 */struct SNode *FirstCell;ElementType TopElem;if( IsEmpty( S ) ) printf(“堆栈空”); return NULL; else FirstCell = S-Next; S-Next = FirstCell-Next; TopEle
14、m = FirstCell -Element; free(FirstCell); return TopElem; ,10.堆栈应用：表达式求值 例 算术表达式5+6/2-3*4。正确理解： 5+6/2-3*4 = 5+3-3*4 = 8-3*4 = 8-12 = -4 由两类对象构成的： 运算数，如2、3、4 运算符号，如+、-、*、/ 不同运算符号优先级不一样 中缀表达式：运算符号位于两个运算数之间。 后缀表达式：运算符号位于两个运算数之后。 例题的后缀形式：562/+34*-,中缀表达式如何转换为后缀表达式 从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理 运算数：直接输出；
15、左括号：压入堆栈； 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）； 运算符： 若优先级大于栈顶运算符时，则把它压栈； 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈； 若各对象处理完毕，则把堆栈中存留的运算符一并输出。,1,8,9,中缀转换为后缀示例： （ 2*（9+6/3-5）+4）,步骤,待处理表达式,堆栈状态,输出状态,（底顶） 2*（9+6/3-5）+4,2,*（9+6/3-5）+4,2,3456710 11 12 13 14 15,（9+6/3-5）+4 9+6/3-5）+4 +6/3-5）+4 6/3-5）+4 /3-5）+4 3-5）+4 -5）+4 5）+4 ）+4 +4 4,* *（ *（ *（ + *（ + *（ + / *（ + / *（ - *（ - * + +,2 2 29 29 296 296 2963 2963/+ 2963/+5 2963/+5- 2963/+5-* 2963/+5-*4 2963/+5-*4+,应用堆栈实现后缀表达式求值的基本过程： 从左到右读入后缀表达式的各项（运算数）；1. 运算数：入栈；2. 运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈；3. 最后，堆栈顶上的元素就是表达式的结果值。,
