1、退棧進(jìn)棧a0an-1an-2topbottomADT Stack /對(duì)象對(duì)象:由數(shù)據(jù)類(lèi)型為由數(shù)據(jù)類(lèi)型為StackData的元素構(gòu)成的元素構(gòu)成 int Push (stack *S, StackData x); /進(jìn)棧進(jìn)棧 int Pop (stack *S, StackData &x); /出棧出棧 int GetTop (stack *S, StackData &x); /取棧頂取棧頂 void InitStack (stack *S); /置空棧置空棧 int StackEmpty (stack *S); /判?？辗衽袟？辗?int StackFull (stack *S); /判棧滿否判

2、棧滿否#define StackSize 100typedef char StackData;typedef struct /順序棧定義 StackData dataStackSize;/棧數(shù)組 int top; /棧頂指針 SeqStack;0 1 2 3 4 5 6 7 8 9 StackSize-1top ()dataint StackEmpty (SeqStack *S) /判斷棧是否空？空則返回1，否則返回0 return S-top = -1;int StackFull (SeqStack *S) /判斷棧是否滿？滿則返回1，否則返回0 return S-top = StackSi

3、ze-1; void InitStack ( SeqStack *S) /置空棧 S-top = -1; top空棧toptoptoptoptopa 進(jìn)棧b 進(jìn)棧aababcdee 進(jìn)棧abcdef 進(jìn)棧溢出abdee 退棧ctopc 退棧b 退棧abaa 退?？湛諚opabdd 退棧ctopabctoptopint Push (SeqStack *S, StackData x) /若棧滿返回0, 否則新元素 x 進(jìn)棧并返回1 if ( StackFull (S) ) return 0; S-data+S-top = x; /加入新元素 return 1;int Gettop (SeqSta

4、ck *S, StackData &x) /若?？辗祷?, 否則棧頂元素讀到x并返回1 if ( StackEmpty(S) ) return 0; x = S-dataS-top; return 1;int pop (SeqStack *S, StackData &x) /若棧空返回0, 否則棧頂元素退出到x并返回1 if ( StackEmpty(S) ) return 0; x = S-dataS-top-; return 1;toptypedef int StackData;typedef struct node StackData data; /結(jié)點(diǎn)數(shù)據(jù) struct node *l

5、ink; /結(jié)點(diǎn)鏈指針 StackNode;typedef struct StackNode *top; /棧頂指針 LinkStack;void InitStack ( LinkStack *S ) S-top = NULL;int Push ( LinkStack *S, StackData x ) StackNode *p = ( StackNode * ) malloc ( sizeof ( StackNode ) ); p-data = x; p-link = S-top; S-top = p; return 1;int StackEmpty (LinkStack *S) retur

6、n S-top = NULL;int Pop ( LinkStack *S, StackData &x ) if ( StackEmpty (S) ) return 0; StackNode * p = S-top; S-top = p-link; x = p-data; free (p); return 1; int GetTop ( LinkStack *S, StackData &x ) if ( StackEmpty (S) ) return 0; x = S-top-data; return 1; a0 a1 a2 an-1frontrearADT Queue /對(duì)象對(duì)象:由數(shù)據(jù)類(lèi)型

7、為由數(shù)據(jù)類(lèi)型為QueueData的元素構(gòu)成的元素構(gòu)成 int EnQueue (Queue *Q, QueueData x); /進(jìn)隊(duì)進(jìn)隊(duì) int DeQueue (Queue *Q, QueueData &x);/出隊(duì)出隊(duì) int GetFront (Queue *Q, QueueData &x);/取隊(duì)頭取隊(duì)頭 void InitQueue (Queue *Q); /置空隊(duì)置空隊(duì) int QueueEmpty (Queue *Q); /判隊(duì)空否判隊(duì)空否 int QueueFull (Queue *Q); /判隊(duì)滿否判隊(duì)滿否#define QueueSize 50;typedef int Q

8、ueueData;typedef struct QueueData dataQueueSize; int rear, front; SeqQueue;void InitQueue ( SeqQueue *Q ) Q-front = Q-rear = -1;front rear空隊(duì)列front rearA進(jìn)隊(duì)Afront rearB進(jìn)隊(duì)A Bfront rearC, D進(jìn)隊(duì)A B C Dfront rearA退隊(duì)B C Dfront rearB退隊(duì)C Dfront rearE,F,G進(jìn)進(jìn)隊(duì)C D E F GC D E F Gfront rearH進(jìn)進(jìn)隊(duì),溢出n n 01234567front01

9、234567front01234567frontrearAABCrearrear空隊(duì)列空隊(duì)列A進(jìn)進(jìn)隊(duì)隊(duì)B, C進(jìn)進(jìn)隊(duì)隊(duì)0123456701234567A退退隊(duì)隊(duì)B退退隊(duì)隊(duì)01234567D,E,F,G,H, I進(jìn)進(jìn)隊(duì)隊(duì)frontBCrearAfrontBCrearfrontCrearDEF GHIvoid InitQueue ( SeqQueue *Q ) Q-rear = Q-front = 0;int QueueEmpty ( SeqQueue *Q ) return Q-rear = Q-front;int QueueFull ( SeqQueue *Q ) return (Q-rear

10、+1) % QueueSize = Q-front;int EnQueue ( SeqQueue *Q, QueueData x ) if ( QueueFull (Q) ) return 0; Q-rear = ( Q-rear+1) % QueueSize; Q-dataQ-rear = x; return 1;int DeQueue ( SeqQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-dataQ-front;Q-front = ( Q-front+1) % QueueSize;return 1;int G

11、etFront ( SeqQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-data(Q-front+1) % QueueSize; return 1;frontreartypedef int QueueData;typedef struct node QueueData data; /隊(duì)列結(jié)點(diǎn)數(shù)據(jù)隊(duì)列結(jié)點(diǎn)數(shù)據(jù) struct node *link; /結(jié)點(diǎn)鏈指針結(jié)點(diǎn)鏈指針 QueueNode;typedef struct QueueNode *rear, *front; LinkQueue;void InitQueue

12、 ( LinkQueue *Q ) Q-rear = Q-front = NULL;int QueueEmpty ( LinkQueue *Q ) return Q-front = NULL;int GetFront ( LinkQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-front-data; return 1;int EnQueue ( LinkQueue *Q, QueueData x ) QueueNode *p = ( QueueNode * ) malloc ( sizeof ( QueueNode

13、) ); p-data = x; p-link = NULL; if ( Q-front = NULL ) /空,創(chuàng)建第一個(gè)結(jié)點(diǎn) Q-front = Q-rear = p; else Q-rear-link = p Q-rear = p; return 1;int DeQueue ( LinkQueue *Q, QueueData &x) /刪去隊(duì)頭結(jié)點(diǎn)，并返回隊(duì)頭元素的值 if ( QueueEmpty (Q) ) return 0;/判隊(duì)空 QueueNode *p = Q-front; x = p-data; /保存隊(duì)頭的值 Q-front = Q-front-link; /新隊(duì)頭 if

14、 (Q-front = NULL) Q-rear = NULL; free (p); return 1; 1 1 i = 1 1 2 12 1 3 3 13 1 4 6 4 14 1 51010 5 15 1 6152015 6 160 1 1 0ts+ti = 30 1 3 3 1 0si = 41 4 6 4 1i = 20 1 2 1 01 2 1 0 1 3 3 1 0 1 4 6s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1s+t s=t s=t s=t s=t s=t s=t s=t s=ts+t s+t s+t s+t s+t s+t s+

15、t s+t#include queue.hvoid YANGVI ( int n ) Queue q; /隊(duì)列初始化隊(duì)列初始化 InitQueue(q); EnQueue (q,1); EnQueue (q,1); int s = 0, t; for ( int i = 1; i = n; i+ ) /逐行計(jì)算逐行計(jì)算 printf (“n”); EnQueue (q, 0); for ( int j = 1; j link = NULL ) printf (“%dn”, f -data ); else Print ( f -link );f f f f f a0a1a2a3a4遞歸找鏈尾vo

16、id Print ( ListNode *f, ListData& x ) if ( f != NULL ) if ( f - data = x ) printf (“%dn”, f -data ); else Print ( f - link, x );f f f f 遞歸找含x值的結(jié)點(diǎn)x#include #include strclass.h”void Hanoi (int n, String A, String B, String C) /解決漢諾塔問(wèn)題的算法 if ( n = 1 ) printf ( move %s,A, to %s,C); else Hanoi ( n-1, A, C, B ); printf ( move %s,A, to %s,C); Hanoi ( n-1, B, A, C ); 遞歸遞歸工作記錄工作記錄.Function() .調(diào)用塊函數(shù)塊 long Factorial ( long n ) int temp; if ( n = 0 )