数据结构PPT(第三章))

1、退栈进栈a0an-1an-2topbottomADT Stack /对象对象:由数据类型为由数据类型为StackData的元素构成的元素构成 int Push (stack *S, StackData x); /进栈进栈 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;/栈数组 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 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈ctopc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptopint Push (SeqStack *S, StackData x) /若栈满返回0, 否则新元素 x 进栈并返回1 if ( StackFull (S) ) return 0; S-data+S-top = x; /加入新元素 return 1;int Gettop (SeqSta

4、ck *S, StackData &x) /若栈空返回0, 否则栈顶元素读到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; /结点数据 struct node *l

5、ink; /结点链指针 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 /对象对象:由数据类型

7、为由数据类型为QueueData的元素构成的元素构成 int EnQueue (Queue *Q, QueueData x); /进队进队 int DeQueue (Queue *Q, QueueData &x);/出队出队 int GetFront (Queue *Q, QueueData &x);/取队头取队头 void InitQueue (Queue *Q); /置空队置空队 int QueueEmpty (Queue *Q); /判队空否判队空否 int QueueFull (Queue *Q); /判队满否判队满否#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空队列front rearA进队Afront rearB进队A Bfront rearC, D进队A B C Dfront rearA退队B C Dfront rearB退队C Dfront rearE,F,G进进队C D E F GC D E F Gfront rearH进进队,溢出n n 01234567front01

9、234567front01234567frontrearAABCrearrear空队列空队列A进进队队B, C进进队队0123456701234567A退退队队B退退队队01234567D,E,F,G,H, I进进队队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; /队列结点数据队列结点数据 struct node *link; /结点链指针结点链指针 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 ) /空,创建第一个结点 Q-front = Q-rear = p; else Q-rear-link = p Q-rear = p; return 1;int DeQueue ( LinkQueue *Q, QueueData &x) /删去队头结点，并返回队头元素的值 if ( QueueEmpty (Q) ) return 0;/判队空 QueueNode *p = Q-front; x = p-data; /保存队头的值 Q-front = Q-front-link; /新队头 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; /队列初始化队列初始化 InitQueue(q); EnQueue (q,1); EnQueue (q,1); int s = 0, t; for ( int i = 1; i = n; i+ ) /逐行计算逐行计算 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值的结点x#include #include strclass.h”void Hanoi (int n, String A, String B, String C) /解决汉诺塔问题的算法 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() .调用块函数块 long Factorial ( long n ) int temp; if ( n = 0 )