數(shù)據(jù)結(jié)構(gòu)語(yǔ)言課件習(xí)題語(yǔ)言版棧和隊(duì)列

1、 3.1 棧 3.1.1抽象數(shù)據(jù)類型棧的定義 3.1.2棧的表示與實(shí)現(xiàn) 3.2 棧的應(yīng)用舉例 3.2.1 數(shù)制轉(zhuǎn)換 3.2.4 迷宮求解 3.2.5 表達(dá)式求值 *3.3 棧和遞歸的實(shí)現(xiàn) 3.4 隊(duì)列 3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義 3.4.2 鏈隊(duì)列 - 隊(duì)列的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 3.4.3 循環(huán)隊(duì)列 - 隊(duì)列的順序表示與實(shí)現(xiàn)第三章 棧和隊(duì)列- 操作受限的線性表?xiàng)＃╯tack）: 先進(jìn)后出( FILO）的線性表。或后進(jìn)先出（ LIFO）的線性表?；騼H在表尾進(jìn)行插入和刪除操作的線性表。棧頂（top）: 線性表的表尾端，即可操作端。棧底（bottom）: 線性表的表頭。3.1 棧3.1.1 抽象數(shù)

2、據(jù)類型棧的定義棧底棧頂.a1a2a3an-1an入棧(push)出棧(pop)棧的抽象數(shù)據(jù)類型ADT Stack 數(shù)據(jù)對(duì)象：D = ai | ai屬于Elemset, (i=1,2,n, n0)數(shù)據(jù)關(guān)系：R1 = ai-1,ai|ai-1,ai屬于D,(i=2,3,n) 約定an為棧頂, a1為棧底。 基本操作： InitStack(&S); DestroyStack(&S); ClearStack(&S); StackEmpty(S); StackLength(S) ; GetTop(S,&e); Push(&S,e); Pop(&S,&e); StackTraverse(S,visit (

3、) ADT Stack棧的基本操作(之一) InitStack(&S) 操作結(jié)果:構(gòu)造一個(gè)空的棧S。 DestroyStack(&S)初始條件: 棧S已經(jīng)存在。 操作結(jié)果: 銷毀棧S。ClearStack(&S)初始條件: 棧S已經(jīng)存在。操作結(jié)果: 將棧S重置為空棧。棧的基本操作(之二)StackEmpty(S)初始條件: 棧S已經(jīng)存在。操作結(jié)果: 若棧S為空棧，則返回TURE;否則返回FALSE。StackLength(S)初始條件: 棧S已經(jīng)存在。 操作結(jié)果: 返回棧S中的數(shù)據(jù)元素個(gè)數(shù)。GetTop(S,&e)初始條件: 棧S已經(jīng)存在且非空。操作結(jié)果: 用e返回棧S中棧頂元素的值。棧的基本

4、操作(之三)Push(&S,e) 初始條件: 棧S已經(jīng)存在。操作結(jié)果: 插入元素e為新的棧頂元素。Pop(&S,&e)初始條件: 棧S已經(jīng)存在且非空。操作結(jié)果: 刪除S的棧頂元素并用e返回其值。StackTraverse(S,visit ()初始條件: 棧S已經(jīng)存在且非空。操作結(jié)果: 從棧底到棧頂依次對(duì)S的每個(gè)元素調(diào)用函數(shù)visit ()。一旦visit ()失敗，則操作失敗。3.1.2 棧的順序表示與實(shí)現(xiàn)- (順序棧)typedef struct SElemType *base; /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL*/ SElemType *top; /* 棧頂指針 */

5、int stacksize; /* 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位*/SqStack;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define OVERFLOW -1#define ERROR 0順序棧示意圖*base*topstacksize.a1.aian*base*topstacksize初始空棧*top = *base; stacksize = STACK_INIT_SIZE順序棧順序棧的操作實(shí)現(xiàn)舉例 InitStack /* 構(gòu)造一個(gè)空的棧S*/Status InitStack(SqStack

6、*s) s-base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType); if(!s - base) return(OVERFLOW); s - top = s - base; s - stacksize = STACK_INIT_SIZE; return OK; /* InitStack */順序棧的操作實(shí)現(xiàn) (GetTop) 棧S非空, 則用e返回棧S中棧頂元素的值，并返回OK, 則返回ERROR。Status GetTop(SqStack s, SElemType *e) if (s.top = s.base)return

7、 ERROR; *e = *(s.top-1); return OK; /* GetTop */*base*topstacksize.a1.aianse*e = *(s.top-1);順序棧的操作實(shí)現(xiàn) （Push）插入元素e為新的棧頂元素。 Status Push(SqStack *s, SElemType e) if (s-top s-base = s-stacksize) /* 棧滿，追加存儲(chǔ)空間 */ l_temp=(SElemType*)realloc (s-base,(s-stacksize+STACKINCREMENT) *sizeof(SElemType); if (!l_tem

8、p) return(OVERFLOW); s-base = l_temp; s-top = s-base + s-stacksize; s-stacksize += STACKINCREMENT; *(s-top+) = e; return OK; /* Push */插入新的棧頂元素時(shí)，堆棧變化示意e*base*topstacksize.a1.aians*base*topstacksize.a1.aians棧滿時(shí)，追加存儲(chǔ)空間*(s-top+) = e;順序棧的操作實(shí)現(xiàn) (Pop) 棧S非空, 則刪除S的棧頂元素, 用e返回棧S中棧頂元素的值，并返回OK, 否則返回ERROR。Status

9、Pop(SqStack *s, SElemType *e) if (s-top = s-base)return ERROR; *e = *(-s-top); return OK; /* Pop */*base*topstacksize.a1.aianse*e = *(-s-top);3.2 棧的應(yīng)用舉例3.2.1 數(shù)制轉(zhuǎn)換N = (N div d)d + N mod d; 1348 = 1348/8 * 8 %8例：（1348）10 = （2504）8 N (N div 8) N mod 8 21 0 21 2 5 2 0 2先進(jìn)后出： 數(shù)據(jù)生成的順序：4,0,5,2 讀出的順序：2,5,0,

10、4*base*topstacksize4052數(shù)制轉(zhuǎn)換算法（算法3.1） 輸入一個(gè)非負(fù)的十進(jìn)制數(shù)，輸出等值的八進(jìn)制數(shù)void conversion() InitStack(&s); scanf(“%d”,&N); while(N) Push(&s, N%8); N = N/8; while(!StackEmpty(s) Pop(&s,&e); printf(“%d”,e); /* conversion */#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define OVERFLOW -1#define ERRO

11、R 0typedef struct int *base; int *top; int stacksize;sqstack;棧使用的完整C程序?qū)嵗齣nt initstack(sqstack *s) s-base=(int *)malloc (STACK_INIT_SIZE*sizeof(int); s-top=s-base; s-stacksize=STACK_INIT_SIZE; return OK;void pop(sqstack *s,int *e) if(s-top=s-base)return ERROR; *e=*(-s-top); void push(sqstack *s,int e

12、) if(s-top-s-base=s-stacksize) s-base=(int*)realloc(s-base,(s- stacksize+STACKINCREMENT)*sizeof(int); if (!s-base)exit(OVERFLOW); s-top=s-base+s-stacksize; s-stacksize+=STACKINCREMENT; *(s-top+)=e;main() sqstack s; int n,m,e; initstack(&s); clrscr(); scanf(%d %d,&n,&m); while(n) push(&s,n%m); n=n/m;

13、 while(!(s.top=s.base) pop(&s,&e); printf(%d,e); 3.2.4 迷宮求解例1: start : (1,1) end : (1,4)0 1 2 3 4 5 0 1 2 3 4 5 當(dāng)前位置:棧s.seat的變化迷宮求解的算法思想: 設(shè)定當(dāng)前位置的初值為入口位置;do 若當(dāng)前位置可通, 則 將當(dāng)前位置插入棧頂; 若該位置是出口位置、則結(jié)束; 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置; 否則 若棧不空且棧頂位置尚有其它方向未經(jīng)探索, 則設(shè)定新的當(dāng)前位置為順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置 的下一相鄰塊; 若棧不空但棧頂位置的四周均不可通, 則 刪去棧頂位置;

14、若棧不空,則重新測(cè)試新的棧頂位置, 直至找到一個(gè)可通的相鄰塊或出棧至空棧; while (棧不空);迷宮求解的算法: typedef struct int ord; PosType seat; int di;SElemType;Status MazePath (MazeType maze, PosType start, PosType end) InitStack(s); curpos = start; curstep = 1; do if(Pass(curpos) / 當(dāng)前位置可通 FootPrint(curpos); / 留下足跡 e = (curstep, curpos,1); Push

15、(s,e); / 加入路徑 if(curpos = end) return (TRUE); / 到達(dá)終點(diǎn)(出口) curpos = NextPos(curpos,1); / 下一個(gè)位置是當(dāng)前位置的東鄰方塊 curstep + ; / 探索下一步 else / 當(dāng)前位置不能通過(guò) if(!StackEmpty(s) Pop(s,e); While(e.di=4 & !StackEmpty(s) MarkPrint(e.seat); / 留下不能通過(guò)的足跡 Pop(s,e); / 退回一步 if(e.di4) e.di+; Push(s,e); / 換一個(gè)方向探索 curpos = NextPos(e.seat, e.di); / 設(shè)定當(dāng)前位置是該新方向上的相鄰方塊 while (!StackEmpty(s); return (FALSE