DS04_线性结构b_陈越主编_数据结构

1、第3章 线性结构 3.3 堆栈例例3.4 对于算术表达式来说，其基本规则是：对于算术表达式来说，其基本规则是： 先乘除，后加减；先括号内，再括号外；先乘除，后加减；先括号内，再括号外； 相同优先级情况下从左到右。相同优先级情况下从左到右。 比如，比如，5+6/2-3*4就是一个算术表达式，它的正确理解应该是：就是一个算术表达式，它的正确理解应该是： 5+6/2-3*4 = 5+3-3*4 = 8-3*4 = 8-12 = -4。 可以看到这类表达式主要由两类对象构成的，即运算数（如可以看到这类表达式主要由两类对象构成的，即运算数（如2、3、4等）和运算符号（如等）和运算符号（如+、-、*、/等

2、）。等）。 不同运算符号优先级是不一样的，而且运算符号均位于两个运算数不同运算符号优先级是不一样的，而且运算符号均位于两个运算数中间。中间。 堆栈堆栈要实现要实现表达式求值表达式求值，首先需要正确理解一个表达式，主要是，首先需要正确理解一个表达式，主要是运算的先后顺序运算的先后顺序。计算机编译程序是如何计算机编译程序是如何自动地理解表达式的？自动地理解表达式的？ 1/23例例 6 2 3 4 2 = ?8对象对象: 6 (运算数运算数 )6对象对象: 2 ( 运算数运算数 )2对象对象: ( 运算符运算符 )2 6= 3toptop3top对象对象: 3 (运算数运算数 )3top对象对象:

3、(运算符运算符)3toptop3 = 00top对象对象: 4 (运算数运算数 )top4对象对象: 2 (运算数运算数 )top2对象对象: ( 运算符运算符 )top2top4 = 88top对象对象: (运算符运算符)top8top0 = 88top Pop: 8topT( N ) = O ( N )。不需要知道运算符的优先规则。不需要知道运算符的优先规则。第3章 线性结构 3.3 堆栈 中缀表达式中缀表达式：运算符号位于两个运算数之间。运算符号位于两个运算数之间。如如 ，a b c d e 后缀表达式后缀表达式：运算符号位于两个运算数之后。如，运算符号位于两个运算数之后。如， a b

4、c d e 后缀表达式后缀表达式toptoptop2/23第3章 线性结构 3.3 堆栈 把数据插入称为压把数据插入称为压入栈（入栈（Push）； 而数据删除可看作从堆栈中取出数据，叫做弹而数据删除可看作从堆栈中取出数据，叫做弹出栈（出栈（Pop）。 最后入栈的数据将被最先弹出，所以堆栈也被称为最后入栈的数据将被最先弹出，所以堆栈也被称为“后入先出后入先出”表（表（Last In First Out，简称，简称LIFO）。）。 堆栈的定义堆栈的定义“堆栈（堆栈（Stack）”可以认为是具有一定可以认为是具有一定操作操作约束的线性表，约束的线性表，插入和删除操作插入和删除操作都作用在一个称为都作

5、用在一个称为栈顶栈顶(Top)的端点位置的端点位置。类型名称类型名称: 堆栈（堆栈（Stack）数据对象集：数据对象集：一个有一个有0个或多个元素的有穷线性表。个或多个元素的有穷线性表。操作集：操作集：对于一个具体的长度为正整数对于一个具体的长度为正整数MaxSize的堆栈的堆栈S Stack，记堆栈中的，记堆栈中的任一元素任一元素item ElementType。1、Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为生成空堆栈，其最大长度为MaxSize；2、int IsFull( Stack S, int MaxSize )：判断堆栈：判断堆栈S是

6、否已满。若是否已满。若S中元素个数等于中元素个数等于MaxSize时返时返回回1(TRUE)；否则返回；否则返回0(FALSE) ；3、void Push( Stack S, ElementType item )：将元素：将元素item压入堆栈。若堆栈已满，压入堆栈。若堆栈已满，返回堆栈为满信息；否则将数据元素返回堆栈为满信息；否则将数据元素item插入到堆栈插入到堆栈S栈顶处；栈顶处；4、int IsEmpty ( Stack S )：判断堆栈：判断堆栈S是否为空，若是返回是否为空，若是返回1(TRUE)；否则返回；否则返回0(FALSE)；5、ElementType Pop( Stack

7、S )：删除并返回栈顶元素。若堆栈为空，返回堆栈：删除并返回栈顶元素。若堆栈为空，返回堆栈为空信息；否则将栈顶数据元素从堆栈中删除并返回。为空信息；否则将栈顶数据元素从堆栈中删除并返回。6、 ElementType Top(Stack S )：3/23第3章 线性结构 3.3 堆栈TopTopTopTopAABABCABCDTopTopTopTopDABCCBAABACreatStack( ); Push(S,A); Push(S,B); Push(S,C); x=Pop(S); x=Pop(S); x=Pop(S); IsEmpty (S) 1234566 5654/23 Push 和和 P

8、op 可以任意穿插可以任意穿插交替交替进行；进行； 求后缀求后缀表达式表达式 5 6 2 / + 3 4 * - 时：时： Push 和和 Pop的序列的序列是：是： Push(S,5); Push(S,6); Push(S,2); /* S: 5 6 2 */x=Pop(S); /* x=2 */y=Pop(S); /* y=6 */Push(S,y/x); /* y/x=3, S: 5 3 */x=Pop(S); /* x=3 */y=Pop(S); /* y=5 */Push(S,x+y); /* y+x=8 , S: 8 */Push(S,3); Push(S,4); /* S: 8

9、3 4 */x=Pop(S); /* x=4 */y=Pop(S); /* y=3 */Push(S,x*y); /* y*x=12 , S: 8 12 */x=Pop(S); /* x=12 */y=Pop(S); /* y=8 */Push(S,y-x); /* S: -4 */x=Pop(S); /* x=-4 */第3章 线性结构 3.3 堆栈5/23第3章 线性结构 3.3 堆栈【分析分析】 1 只有一个字符出入栈时，显然只有一种可能，即只有一个字符出入栈时，显然只有一种可能，即A入栈也只有入栈也只有A出栈。出栈。有两个字符有两个字符AB出入栈时，如果进栈顺序为出入栈时，如果进栈顺序

10、为AB，那么出栈的系列，那么出栈的系列AB、BA都有可能都有可能： 即可以即可以A进栈、进栈、A出栈、出栈、B进栈、进栈、B出栈，产生输出序列出栈，产生输出序列AB； 也可以也可以A进栈、进栈、B进栈、进栈、B出栈、出栈、A出栈，产生输出序列出栈，产生输出序列BA。 这两个可能的序列也是正好是两个字符的全排列。这两个可能的序列也是正好是两个字符的全排列。例例3.5 如果将如果将ABCD四个字符按顺序压入堆栈，四个字符按顺序压入堆栈，是不是是不是ABCD的所有排列都可能是出栈的序列？的所有排列都可能是出栈的序列？可以产生可以产生CABD这样的序列吗？这样的序列吗？如果有三个字符如果有三个字符AB

11、C出入栈时，全排列有出入栈时，全排列有3！= 6 种可能种可能。 其中的其中的CAB是没法生成是没法生成的。的。 因为先输出因为先输出C，需要，需要C进栈再出栈，而要求按照进栈再出栈，而要求按照ABC这样的顺这样的顺序进栈，所以序进栈，所以C出栈时出栈时AB必然还在栈里，而且必然还在栈里，而且A还压在还压在B下面下面。 其它其它5种排列都可以生成。种排列都可以生成。如果有四个字符如果有四个字符ABCD出入栈时，排列有出入栈时，排列有4!=24种可能种可能。 不是所有排列都有可能是出栈的序列，象不是所有排列都有可能是出栈的序列，象CABD这样的序列这样的序列是产生不了的。是产生不了的。 四个字符

12、出栈的所有可能序列有几种？四个字符出栈的所有可能序列有几种？（14种）种）6/23第3章 线性结构 栈的顺序存储结构通常由一个栈的顺序存储结构通常由一个一维数组一维数组和一个记录和一个记录栈顶栈顶元素位置的变量组成元素位置的变量组成。#define MaxSize typedef struct ElementType DataMaxSize;int Top; Stack;3.3 堆栈的实现1栈的顺序存储实现栈的顺序存储实现void Push( Stack *PtrS, ElementType item ) if ( PtrS-Top = MaxSize-1 ) printf(“堆栈满堆栈满”)

13、; return; else PtrS-Data+(PtrS-Top) = item; return; TopAB(1)入栈入栈PtrS7/23第3章 线性结构 3.3 堆栈的实现ElementType Pop( Stack *PtrS ) if ( PtrS-Top = -1 ) printf(“堆栈空堆栈空”); return ERROR; /* ERROR是是ElementType的特殊值，标志错误的特殊值，标志错误 */ else return ( PtrS-Data(PtrS-Top)- );TopAB(2)出栈出栈PtrS8/23例例. 请用一个数组实现两个堆栈，要求最大地利用数组

14、请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。写出相应的空间，使数组只要有空间入栈操作就可以成功。写出相应的入栈和出栈操作函数。入栈和出栈操作函数。【分析分析】 一种一种比较比较聪明的方法是使这两个栈分别从数组的聪明的方法是使这两个栈分别从数组的两头两头开始向中间生长开始向中间生长；当两个栈的；当两个栈的栈顶指针相遇栈顶指针相遇时，表示两个栈都时，表示两个栈都满了。此时，最大化地利用了数组空间满了。此时，最大化地利用了数组空间。第3章 线性结构 3.3 堆栈#define MaxSize struct DStack ElementType DataMax

15、Size; int Top1; /* 堆栈的栈顶指针堆栈的栈顶指针 */ int Top2; /* 堆栈的栈顶指针堆栈的栈顶指针 */ S;S.Top1 = -1; S.Top2 = MaxSize;9/23第3章 线性结构 3.3 堆栈void Push( struct DStack *PtrS, ElementType item, int Tag ) /* Tag作为区分两个堆栈的标志，取值为作为区分两个堆栈的标志，取值为1和和2 */ if ( PtrS-Top2 PtrS-Top1 = 1) /*堆栈满堆栈满*/printf(“堆栈满堆栈满”); return ; if ( Tag =

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

17、eturn NULL; else return PtrS-Data(PtrS-Top1)-; else /* 对第二个堆栈操作对第二个堆栈操作 */ if ( PtrS-Top2 = MaxSize ) /*堆栈堆栈2空空 */ printf(“堆栈堆栈2空空”); return NULL; else return PtrS-Data(PtrS-Top2)+;10/23第3章 线性结构 栈的栈的链式链式存储结构存储结构实际上就是实际上就是一个一个单链表单链表，叫做，叫做链栈链栈。插入和删。插入和删除操作只能在链栈的栈顶进行；除操作只能在链栈的栈顶进行；栈顶指针栈顶指针Top就是链表的头指针就是

18、链表的头指针。3.3 堆栈的实现2堆栈的链式存储实现堆栈的链式存储实现LinkStack *CreateStack() /* 构建一个堆栈的头结点，返回指针构建一个堆栈的头结点，返回指针 */ LinkStack *S; S = malloc( sizeof(struct Node ); S-Next = NULL; return S;int IsEmpty( LinkStack *S ) /*判断堆栈判断堆栈S是否为空，若为空函数返回整数是否为空，若为空函数返回整数1，否则返回，否则返回0 */ return ( S-Next = NULL );(1) 堆栈初始化（建立空栈）堆栈初始化（建立

19、空栈）(2) 判断堆栈判断堆栈S是否为空是否为空typedef struct NodeElementType Data;struct Node *Next; LinkStack; LinkStack *Top;S11/23第3章 线性结构 3.3 堆栈的实现void Push( ElementType item, LinkStack *S ) /* 将元素将元素item压入堆栈压入堆栈S */struct Node *TmpCell;TmpCell = malloc( sizeof( struct Node ) );TmpCell-Element = item;TmpCell-Next = S

20、-Next;S-Next = TmpCell;ElementType Pop( LinkStack *S ) /* 删除并返回堆栈删除并返回堆栈S的栈顶元素的栈顶元素 */ struct Node *FirstCell;ElementType TopElem;if( IsEmpty( S ) ) printf(“堆栈空堆栈空”); return NULL; else FirstCell = S-Next; S-Next = FirstCell-Next;TopElem = FirstCell -Element;free(FirstCell);return TopElem;12/23 堆栈应用：

21、表达式求值堆栈应用：表达式求值第3章 线性结构 3.3 堆栈 应用堆栈实现后缀表达式求值的基本过程：应用堆栈实现后缀表达式求值的基本过程：. 从左到右从左到右读入后缀表达式的各项读入后缀表达式的各项（运算符或（运算符或运算运算数）；数）；. 根据读入的对象（运算符或根据读入的对象（运算符或运算运算数）判断执行操作；数）判断执行操作；. 操作分下列操作分下列3种情况：种情况：当读入的是一个当读入的是一个运算数运算数时，把它被压入栈中；时，把它被压入栈中；当读入的是一个当读入的是一个运算符运算符时，就从堆栈时，就从堆栈中弹出适当数量的运算数中弹出适当数量的运算数，对，对该运算进行计算，该运算进行计

22、算，计算结果再压回到栈计算结果再压回到栈中；中；处理完整个后缀表达式之后，处理完整个后缀表达式之后，堆栈顶上的元素堆栈顶上的元素就是表达式的就是表达式的结果值结果值。对象对象序列的序列的后缀表达式后缀表达式结果值结果值字符字符序列的序列的后缀表达式后缀表达式求值求值利用堆栈利用堆栈对象分割对象分割GetOp1.2 1.3 + 2 4.2 * -1.2 1.3 + 2 4.2 * -5.913/23 中缀中缀表达式求值表达式求值第3章 线性结构 3.3 堆栈对象对象序列的序列的中缀中缀表达式表达式字符字符序列的序列的中缀中缀表达式表达式对象分割对象分割GetOp(1.2 +1.3 2) * 4.

23、2(1.2 +1.3 2)* 4.22.1对象对象序列的序列的后缀后缀表达式表达式结果值结果值求值求值利用堆栈利用堆栈1.2 1.3 + 2 - 4.2 *对象分割对象分割GetOp求值求值利用堆栈利用堆栈利用堆栈利用堆栈转换转换利用堆栈利用堆栈转换转换14/23中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式第3章 线性结构 3.3 堆栈 从头到尾读取从头到尾读取中缀表达式的每个对象中缀表达式的每个对象，对不同对象按不同的情况处理。，对不同对象按不同的情况处理。对象分下列对象分下列6种情况：种情况： 如果遇到如果遇到空格空格则认为是分隔符，不需处理；则认为是分隔符，不需处理；若遇到若遇到

24、运算数运算数，则直接输出；，则直接输出；若是若是左括号左括号，则将其，则将其压入堆栈压入堆栈中；中；若遇到的是若遇到的是右括号右括号，表明括号内的中缀表达式已经扫描完毕，表明括号内的中缀表达式已经扫描完毕，将将栈顶的运算符弹出栈顶的运算符弹出并并输出输出，直到遇到左括号直到遇到左括号（左括号也出栈，（左括号也出栈，但不输出）；但不输出）；若遇到的是若遇到的是运算符运算符，若该运算符的，若该运算符的优先级大于栈顶运算符优先级大于栈顶运算符的优的优先级时，则把它先级时，则把它压栈压栈；若该运算符的；若该运算符的优先级小于等于栈顶运算符优先级小于等于栈顶运算符时，将栈时，将栈顶运算符弹出并输出顶运算

25、符弹出并输出，再比较新的栈顶运算符，按同样，再比较新的栈顶运算符，按同样处理方法，直到该运算符大于栈顶运算符优先级为止，然后将该处理方法，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈运算符压栈；若中缀表达式中的各对象若中缀表达式中的各对象处理完毕处理完毕，则把堆栈中存留的，则把堆栈中存留的运算符运算符一并输出一并输出。15/23第3章 线性结构 3.3 堆栈( ?例例 a ( b c ) d = ? a b c d top输出输出: 输入对象输入对象: a (操作数操作数)a输入对象输入对象: (乘法乘法)top输入对象输入对象: ( (左括号左括号) ( ?top(输入对象输入对

26、象: b (操作数操作数)b输入对象输入对象: (加法加法)NO?!top+输入对象输入对象: c (操作数操作数)c输入对象输入对象: ) (右括号右括号)top top输入对象输入对象: (除法除法) ?top top输入对象输入对象: d (操作数操作数)dtop T( N ) = O ( N ) 16/23中缀转换为后缀示例中缀转换为后缀示例： （ 2*（9+6/3-5）+4）第3章 线性结构 3.3 堆栈步骤步骤待处理表达式待处理表达式堆栈状态堆栈状态（底（底顶）顶）输出状态输出状态12*（9+6/3-5）+42*（9+6/3-5）+423（9+6/3-5）+4*249+6/3-5）

27、+4*（25+6/3-5）+4*（2 966/3-5）+4*（ +2 97/3-5）+4*（ +2 9 683-5）+4*（ + /2 9 69-5）+4*（ + /2 9 6 3105）+4*（ -2 9 6 3 / +11）+4*（ -2 9 6 3 / + 512+4*2 9 6 3 / + 5 -134+2 9 6 3 / + 5 - *14+2 9 6 3 / + 5 - * 4152 9 6 3 / + 5 - * 4 +17/23第3章 线性结构 把数据插入称为把数据插入称为入入队列队列（AddQ）； 而数据删除可看作从而数据删除可看作从队列队列中取出数据，叫做中取出数据，叫做出

28、出队列队列（DeleteQ）。 最最先先入入队列队列的数据将被最先弹出，的数据将被最先弹出，即即先来先服务先来先服务; 所以所以队列队列也被也被称为称为“先进先出先进先出”表（表（Fist In First Out，简称，简称FIFO） 。 队列队列的定义的定义“队列队列(Queue)” 是具有一定是具有一定操作操作约束的线性表，约束的线性表，插入和删插入和删除操作除操作有一定要求：只能在有一定要求：只能在一端插入一端插入，而在，而在另一端删除另一端删除。3.4 队列类型名称类型名称：队列：队列(Queue)数据对象集：数据对象集：一个有一个有0个或多个元素的有穷线性表。个或多个元素的有穷线性

29、表。操作集操作集：对于一个长度为正整数：对于一个长度为正整数MaxSize的队列的队列Q Queue，记队列中的任一元，记队列中的任一元素素item ElementType。1、Queue CreatQueue( int MaxSize )：生成长度为：生成长度为MaxSize的空队列。的空队列。2、int IsFullQ( Queue Q, int MaxSize )：判断队列判断队列Q是否已满，若是返回是否已满，若是返回1(TRUE)；否则返回；否则返回0(FALSE)。3、void AddQ( Queue Q, ElementType item )： 若队列已经满了，返回已满信息；否则将

30、数据元素若队列已经满了，返回已满信息；否则将数据元素item插入到队列插入到队列Q中去。中去。4、int IsEmptyQ( Queue Q )： 判断队列判断队列Q是否为空，若是返回是否为空，若是返回1(TRUE)；否则返回；否则返回0(FALSE)。5、ElementType DeleteQ( Queue Q )：若队列为空信息，返回队列空信息；否则将队头数据元素从队列中删除并返回。若队列为空信息，返回队列空信息；否则将队头数据元素从队列中删除并返回。6、 ElementType FrontQ( Queue Q )：18/23第3章 线性结构 队列队列的顺序存储结构通常由一个的顺序存储结构

31、通常由一个一维数组一维数组和一个记录和一个记录队列头队列头元元素位置的变量素位置的变量front以及以及一个记录一个记录队列尾队列尾元素位置的变量元素位置的变量rear组成组成。#define MaxSize typedef struct ElementType Data MaxSize ;int rear;int front; Queue;1队列的顺序存储实现队列的顺序存储实现3.4 队列的实现Job 3例例 一个工作队列一个工作队列AddQ Job 1AddQ Job 2AddQ Job 3DeleteQ Job 1AddQ Job 4AddQ Job 5AddQ Job 6DeleteQ

32、 Job 2AddQ Job 7AddQ Job 8Job 1Job 2RearJob 4Job 5Job 6FrontRearJob 70123456RearRearFrontRear19/23 0 1 2 3 4 5 AddQ Job 1AddQ Job 2AddQ Job 3DeleteQ Job 1AddQ Job 4AddQ Job 5AddQ Job 6AddQ Job 7Job1Job2Job3Job4Job5Job6队列满！队列满！RearRearFrontRearFrontRearRearRear注注: 如果数据结构中增加一个如果数据结构中增加一个 Size 域，用来区分队列

33、域，用来区分队列“空空”和和“满满”的话，的话， 可以可以“节省节省”一个数据元素的存储单元。一个数据元素的存储单元。但是会带来算法描述的复杂性。但是会带来算法描述的复杂性。Rear第3章 线性结构 3.4 队列的实现20/23第3章 线性结构 void AddQ( Queue *PtrQ, ElementType item) if ( (PtrQ-rear+1) % MaxSize = PtrQ-front ) printf(“队列满队列满”); return; PtrQ-rear = (PtrQ-rear+1)% MaxSize; PtrQ-DataPtrQ-rear = item;3.4