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

1、 广义表与广义表与多重链表多重链表1.1.广义表广义表(Generalized List)特点：一种特殊的线性表，元素的值并特点：一种特殊的线性表，元素的值并非原子类型非原子类型，可以再分解，表中可以再分解，表中元素元素也也是一个广义表是一个广义表（即广义的线即广义的线性表性表）。对于线性表而言，对于线性表而言， n n个元素都是基本的单元素；个元素都是基本的单元素；广义表中，这些元素不仅可以是单元素也可以是另一广义表中，这些元素不仅可以是单元素也可以是另一个广义表。个广义表。抽象数据类型抽象数据类型ADT Glist 数据对象数据对象： Dei | i=1,2,.,n; n0; eiAtom

2、Set 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in ADT Glist广义表的存储结构v由于广义表通常用链式结构，每个元素用一个结点表示。广由于广义表通常用链式结构，每个元素用一个结点表示。广义表结点可按结构不同分成两种，义表结点可按结构不同分成两种，1.单元素单元素 2.广义表。广义表。12原因：广义表的元素可以是不同结构原因：广义表的元素可以是不同结构（原子或列表）（原子或列表）typedef struct GNode *GList;struct GNodeint Tag; /*标志域：0表示结点是单元素，1表示结点是广义

3、表 */ /*子表指针域Sublist与单元素数据域Data复用，即共用存储空间*/union ElementType Data;GList SubList; URegion;GList Next; * 指向后继结点 */;TagDataSubListNext示例示例（1）B=（a，（，（b, c ）,d）010a0d0b0c0112.多重链表多重链表多重链表：链表中的节点可能同时隶属于多个链，多重链表：链表中的节点可能同时隶属于多个链，多重链表中结点的指针域会有多个，多重链表中结点的指针域会有多个，如前面例子包含了如前面例子包含了NextNext和和SubListSubList两个指针域；两

4、个指针域；但包含两个指针域的链表并不一定是多重链表，比如在双向链但包含两个指针域的链表并不一定是多重链表，比如在双向链表但包含两个指针域的链表并不一定是多重链表表但包含两个指针域的链表并不一定是多重链表。 多重链表有广泛的用途：基本上如树、图这样相对复杂的多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。数据结构都可以采用多重链表方式实现存储。 堆栈1. 1. 定义（定义（stackstack） 是一种只允许在一端进行插入和删除的线性表，它是一种是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。操作受限的线性表。 与一般线性表的区别：仅

5、在于运算规则不同。与一般线性表的区别：仅在于运算规则不同。2. 2. 构成构成栈顶（栈顶（toptop）：在表中只允许进行插入和删除的一端；）：在表中只允许进行插入和删除的一端；栈底栈底(bottom)(bottom)：不允许进行插入和删除另一端。：不允许进行插入和删除另一端。举例：特殊情况空栈abc栈顶栈底逻辑结构abc3. 3. 运算规则运算规则 只能在栈顶运算，且访问结点时按照后进先出（只能在栈顶运算，且访问结点时按照后进先出（LIFOLIFO，last last in first outin first out）原则。）原则。练习：练习： 一个栈的输入序列为一个栈的输入序列为1,2,3

6、1,2,3，若在入栈的过程中允许出栈，若在入栈的过程中允许出栈，则不可能得到的出栈序列是什么？则不可能得到的出栈序列是什么？分析：不可能的出栈顺序为312。654ABCBTopDCBTop5ATopAA6TopCreatStack( ); Push(S,A);Push(S,B);Push(S,C);DCBA352CBATopBATopATop61Topx=Pop(S);x=Pop(S);x=Pop(S);IsEmpty (S)4. 4. 逻辑结构逻辑结构 与线性表相同，仍为一对一与线性表相同，仍为一对一( 1:1)( 1:1)关系。关系。5. 5. 主要运算主要运算 （1 1）入栈）入栈插入元

7、素到栈顶的操作；插入元素到栈顶的操作； （2 2）出栈）出栈从栈顶删除最后一个元素的操作。从栈顶删除最后一个元素的操作。6. 6. 存储结构存储结构 顺序栈：栈的数组表示，但以顺序栈更常见；顺序栈：栈的数组表示，但以顺序栈更常见； 链栈：栈的链式表示。链栈：栈的链式表示。7.7.堆栈的抽象数据类型描述堆栈的抽象数据类型描述类型名称类型名称: : 堆栈（堆栈（StackStack）数据对象集：一个有数据对象集：一个有0 0个或多个元素的有穷线性表。个或多个元素的有穷线性表。操作集：长度为操作集：长度为MaxSizeMaxSize的堆栈的堆栈SStackSStack，堆栈元素，堆栈元素itemEl

8、ementTypeitemElementType1 1、Stack CreateStack( int MaxSize )Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为生成空堆栈，其最大长度为MaxSizeMaxSize；2 2、int IsFull( Stack S, int MaxSize )int IsFull( Stack S, int MaxSize )：判断堆栈：判断堆栈S S是否已满；是否已满；3 3、void void Push( Stack S, ElementType item )Push( Stack S, ElementTyp

9、e item )：将元素：将元素itemitem压入堆栈；压入堆栈；4 4、int int IsEmpty ( Stack S )IsEmpty ( Stack S )：判断堆栈：判断堆栈S S是否为空；是否为空；5 5、ElementType ElementType Pop( Stack S )Pop( Stack S )：删除并返回栈顶元素；：删除并返回栈顶元素；8.8.栈的顺序存储实现栈的顺序存储实现栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。假设用一维数组组成。假设用一维数组DataMaxSizeDa

10、taMaxSize表示一个栈，表示一个栈，MaxSizeMaxSize为栈中可存为栈中可存储数据元素的最大个数。习惯上将栈底放在数组下标小的那端，栈顶位储数据元素的最大个数。习惯上将栈底放在数组下标小的那端，栈顶位置用一个整型变量置用一个整型变量TopTop记录当前栈顶元素的下标值，当记录当前栈顶元素的下标值，当TopTop指向指向-1-1时，表时，表示空栈；当示空栈；当TopTop指向指向MaxSize-1MaxSize-1时，表示满栈。时，表示满栈。顺序栈类型顺序栈类型StackStack如下：如下： #define MaxSize #define MaxSize typedef stru

11、ct SNode Stack;typedef struct SNode Stack;struct SNodestruct SNodeElementType DataMaxSize;ElementType DataMaxSize;int Top;int Top;（1 1）入栈操作）入栈操作PushPush首先判别栈是否满，若不满，首先判别栈是否满，若不满，TopTop加加1 1，并将新元素放入，并将新元素放入DataData数组的数组的TopTop分分量中。量中。void Push( Stack PtrS, ElementType item )void Push( Stack PtrS, Ele

12、mentType item )if ( PtrS-Top = MaxSize-1 ) if ( PtrS-Top = MaxSize-1 ) printf(“ printf(“堆栈满堆栈满”); ”); return; return; else else PtrS-Data+(PtrS-Top)=item; PtrS-Data+(PtrS-Top)=item; return; return; （2 2）出栈操作）出栈操作PopPop首先判别栈是否空；若不空，返回首先判别栈是否空；若不空，返回DataTopDataTop，同时将，同时将TopTop减减1 1。ElementType Pop( S

13、tack PtrS )ElementType Pop( Stack PtrS ) if ( PtrS-Top = -1 ) if ( PtrS-Top = -1 ) printf(“ printf(“堆栈空堆栈空”);”); return ERROR; return ERROR; else else return ( PtrS-Data(PtrS-Top)- ); return ( PtrS-Data(PtrS-Top)- ); 例例 请用一个数组实现两个堆栈，要求最大地利用数组空间，使请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。数组只要有空间入栈操作

14、就可以成功。【分析】【分析】 一种比较聪明的方法是使这两个栈分别从数组的两头开始一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。#define MaxSize #define MaxSize struct DStack struct DStack ElementType DataMaxSize;ElementType DataMaxSize; int Top1; / int Top1; /* * 堆栈的栈顶指针堆栈的栈顶指针 * */ / int Top2; / int Top2;

15、 /* * 堆栈的栈顶指针堆栈的栈顶指针* */ / S; S;两个堆栈的初始化方法是：两个堆栈的初始化方法是：S.Top1 = -1;S.Top1 = -1;S.Top2 = MaxSize;S.Top2 = MaxSize;void Push( struct DStack void Push( struct DStack * *PtrS, ElementType item, int Tag )PtrS, ElementType item, int Tag ) / /* * Tag Tag作为区分两个堆栈的标志，取值为作为区分两个堆栈的标志，取值为1 1和和2 2 * */ /if ( Pt

16、rS-Top2 PtrS-Top1 = 1) /if ( PtrS-Top2 PtrS-Top1 = 1) /* *堆栈满堆栈满* */ / printf(“ printf(“堆栈满堆栈满”);”); return; return; if ( Tag = 1 ) / if ( Tag = 1 ) /* * 对第一个堆栈操作对第一个堆栈操作 * */ / PtrS-Data+(PtrS-Top1) = item; PtrS-Data+(PtrS-Top1) = item; else else PtrS-Data-(PtrS-Top2) = item; PtrS-Data-(PtrS-Top2)

17、= item; ElementType Pop( struct DStack ElementType Pop( struct DStack * *PtrS, int Tag )PtrS, int Tag ) / /* * Tag Tag作为区分两个堆栈的标志，取值为作为区分两个堆栈的标志，取值为1 1和和2 2* */ /if ( Tag = 1 ) /if ( Tag = 1 ) /* * 对第一个堆栈操作对第一个堆栈操作* */ / if ( PtrS-Top1 = -1 ) / if ( PtrS-Top1 = -1 ) /* *堆栈堆栈1 1空空* */ / printf(“ prin

18、tf(“堆栈堆栈1 1空空”);”); return NULL; return NULL; else return PtrS-Data(PtrS-Top1)-; else return PtrS-Data(PtrS-Top1)-; else / else /* * 对第二个堆栈操作对第二个堆栈操作 * */ / if ( PtrS-Top2 = MaxSize ) / if ( PtrS-Top2 = MaxSize ) /* *堆栈堆栈2 2空空 * */ /printf(“printf(“堆栈堆栈2 2空空”); ”); return NULL; return NULL; else ret

19、urn PtrS-Data(PtrS-Top2)+; else return PtrS-Data(PtrS-Top2)+; 9.9.堆栈的链式存储实现堆栈的链式存储实现栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。栈顶指针除操作只能在链栈的栈顶进行。栈顶指针TopTop就是链表的头指针。就是链表的头指针。 typedef struct SNodetypedef struct SNodeElementType Data;ElementType Data;struct SNode struct SNode

20、 * *Next;Next; LinkStack; LinkStack;LinkStack LinkStack * *Top;Top;为了表示方便，链栈附带一空的表头结点，表头结点后面的第一个结点为了表示方便，链栈附带一空的表头结点，表头结点后面的第一个结点就是链栈的栈顶结点，栈中的其他结点通过它们的指针就是链栈的栈顶结点，栈中的其他结点通过它们的指针NextNext链接起来，链接起来，栈底结点的栈底结点的NextNext为为NULLNULL。(1) (1) 堆栈初始化（建立空栈）堆栈初始化（建立空栈）LinkStack CreateStack()LinkStack CreateStack()

21、 / /* * 构建一个堆栈的头结点，返回指针构建一个堆栈的头结点，返回指针 * */ /Stack S;Stack S;S =(Stack)malloc(sizeof(struct SNode);S =(Stack)malloc(sizeof(struct SNode);S-Next = NULL;S-Next = NULL;return S;return S;(2) (2) 判断堆栈判断堆栈S S是否为空是否为空int IsEmpty(LinkStack S)int IsEmpty(LinkStack S) / /* *判断堆栈判断堆栈S S是否为空，若为空函数返回整数是否为空，若为空函数

22、返回整数1 1，否则返回，否则返回0 0 * */ /return ( S-Next = NULL );return ( S-Next = NULL ); (3)(3)入栈入栈void Push( ElementType item, LinkStack void Push( ElementType item, LinkStack * *S)S) / /* * 将元素将元素itemitem压入堆栈压入堆栈S S * */ /struct SNode struct SNode * *TmpCell;TmpCell;mpCell=(struct SNode mpCell=(struct SNode

23、* *)malloc(sizeof(struct SNode);)malloc(sizeof(struct SNode);TmpCell-Element = item;TmpCell-Element = item;TmpCell-Next = S-Next;TmpCell-Next = S-Next;S-Next = TmpCell;S-Next = TmpCell; （4 4）出栈）出栈ElementType Pop(Stack S)ElementType Pop(Stack S) / /* * 删除并返回堆栈删除并返回堆栈S S的栈顶元素的栈顶元素 * */ / struct SNode

24、struct SNode * *FirstCell;FirstCell; ElementType TopElem; ElementType TopElem; if( IsEmpty( S ) ) if( IsEmpty( S ) ) printf(“printf(“堆栈空堆栈空”); return NULL;”); return NULL; else else FirstCell = S-Next;FirstCell = S-Next;S-Next = FirstCell-Next;S-Next = FirstCell-Next;TopElem = FirstCell -Element;Top

25、Elem = FirstCell -Element;free(FirstCell);free(FirstCell);return TopElem;return TopElem; 10.10.堆栈应用：表达式求值堆栈应用：表达式求值 例例 算术表达式算术表达式5+6/2-35+6/2-3* *4 4。正确理解：。正确理解：5+6/2-35+6/2-3* *4 = 5+3-34 = 5+3-3* *4 = 8-34 = 8-3* *4 = 8-12 = -44 = 8-12 = -4由两类对象构成的：由两类对象构成的：m运算数，如运算数，如2 2、3 3、4 4m运算符号，如运算符号，如+ +、-

26、 -、* *、/ /不同运算符号优先级不一样不同运算符号优先级不一样m中缀表达式：运算符号位于两个运算数之间。中缀表达式：运算符号位于两个运算数之间。m后缀表达式：运算符号位于两个运算数之后。后缀表达式：运算符号位于两个运算数之后。例题的后缀形式：例题的后缀形式：562/+34562/+34* *- -中缀表达式如何转换为后缀表达式中缀表达式如何转换为后缀表达式从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理 运算数：直接输出；运算数：直接输出； 左括号：压入堆栈；左括号：压入堆栈； 右括号：将栈顶的运算符弹出并输出，直到

27、遇到左括号（出栈，不输出）；右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）； 运算符：运算符：若优先级大于栈顶运算符时，则把它压栈；若优先级大于栈顶运算符时，则把它压栈；若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈； 若各对象处理完毕，则把堆栈中存留的运算符一并输出。若各对象处理完毕，则把堆栈中存留的运算符一并输出。189中缀转换为后缀示例：中缀转换为后缀示

28、例： （ 2 2* *（9+6/3-59+6/3-5）+4+4）步骤待处理表达式堆栈状态输出状态（底顶）2*（9+6/3-5）+42*（9+6/3-5）+4234567101112131415（9+6/3-5）+49+6/3-5）+4+6/3-5）+46/3-5）+4/3-5）+43-5）+4-5）+45）+4）+4+44*（*（*（ +*（ +*（ + /*（ + /*（ -*（ -*+22292929629629632963/+2963/+52963/+5-2963/+5-*2963/+5-*42963/+5-*4+应用堆栈实现后缀表达式求值的基本过程：应用堆栈实现后缀表达式求值的基本过程

29、：从左到右读入后缀表达式的各项（运算数）；从左到右读入后缀表达式的各项（运算数）；1. 1. 运算数：入栈；运算数：入栈；2. 2. 运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈；运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈；3. 3. 最后，堆栈顶上的元素就是表达式的结果值。最后，堆栈顶上的元素就是表达式的结果值。堆栈的其他应用：堆栈的其他应用：函数调用及递归实现函数调用及递归实现 深度优先搜索深度优先搜索 回溯算法回溯算法。作业作业一、选择题一、选择题1.1.栈中元素的进出原则是栈中元素的进出原则是先进先出先进先出 后进先出后进先出 栈空则进栈空则进 栈满则出栈满则出2.2

30、.若已知一个栈的入栈序列是若已知一个栈的入栈序列是1 1，2 2，3 3，n n，其输出序列为，其输出序列为p1p1，p2p2，p3p3，pnpn，若，若p1=np1=n，则，则pipi为为i i n=i n=i n-i+1 n-i+1 不确定不确定3.3.判定一个栈判定一个栈STST（最多元素为（最多元素为m0m0）为空的条件是）为空的条件是ST-top0 ST-top0 ST-top=0 ST-top=0 ST-topm0 ST-topm0 ST-top=m0 ST-top=m0 二、从供选择的答案中，选出应填入下面叙述二、从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解内的最确切的解答，把相应编号写在答卷的对应栏内。答，把相应编号写在答卷的对应栏内。设有设有4 4个数据元素个数据元素a1a1、a2a2、a3a3和和a4a4，对他们分别进行栈操作。在进栈操作，对他们分别进行栈操作。在进栈操作时，按时，按a1a1、a2a2、a3a3、a4a4次序每次进入一个元素。假设栈的初始状态都是次序每次进入一个元素。假设栈的初始状态都是空。空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是时，第一次出栈得到的元