血an0塔的递归算法 定义函数: movetower(n,a,c,b)n个盘a->c,b放临时盘 分三步: movetower(n-1,a,b,c)将n-1个盘从a->b,c放临时盘 movedisk(a, n, c) 将第n个盘从a->c movetower(n-1,b,c,a)将n-1个盘从b->c,a放临时盘 void hanoi (int n, char a, char b, char c) fif(n==1)move(a, 1, c) else hanoi(n-1, a, c, b) move(a, n,c) hanoi(n-1,b, a, c)
定义函数：movetower(n,a,c,b) n个盘a－>c，b放临时盘 分三步： movetower(n-1,a,b,c) 将n-1个盘从a->b， c放临时盘 movedisk(a,n,c) 将第n个盘从a->c movetower(n-1,b,c,a) 将n-1个盘从b->c,a放临时盘 void hanoi(int n, char a, char b, char c) {if (n==1) move(a,1,c); else{ hanoi(n-1,a,c,b); move(a,n,c); hanoi(n-1,b,a,c); } } hanoi塔的递归算法
34队列 34.1抽象数据类型队列的定义 队列( Queue):先进先出( First in first out) 缩写为FIFO)的线性表 仅在队尾进行插入和队头进行删除操作的线性表。 队头(ront):线性表的表头端,即可删除端。 队尾(rear):线性表的表尾端,即可插入端。 队头 对尾 a a, a 1a2 3 n 出队列 equeque) 入队列( Enqueue)
3.4 队列 3.4.1抽象数据类型队列的定义 队列（Queue）: 先进先出(First In First Out) • (缩写为FIFO）的线性表。 • 仅在队尾进行插入和队头进行删除操作的线性表。 队头（front）: 线性表的表头端，即可删除端。 队尾（rear）: 线性表的表尾端，即可插入端。 队头 对尾 a1 a2 a3 ...... an-1 an 出队列(Dequeque) 入队列(Enqueue)
队列的抽象数据类型 ADT Queue i 数据对象:D={a1|a1属于 Elemnet, 1,2,,n,n≥0) 数据关系:列队尾为队属于 D,(-23,,n) 基本操作: InitQueue(&Q) DestroyQueue(& Q) Clear Queue(& Q); QueueEmpty(Q); QueueLength(Q); GetHead(Q, &e); En Queue(&Q,e); De Queue(& Q, &e); QueueTraverse(Q, visit O ADT Queue
队列的抽象数据类型 ADT Queue { 数 据 对 象 ： D = {ai | ai 属 于 Elemset, (i=1,2,…,n, n≥0)} 数据关系 ： R1 = { ＜ ai-1 ,ai ＞ |ai-1 ,ai 属 于 D,(i=2,3,…,n)} 约定an为队尾, a1为队头。 基本操作： • InitQueue(&Q); DestroyQueue (& Q); • ClearQueue (& Q); QueueEmpty(Q); • QueueLength(Q) ; GetHead(Q,&e); • EnQueue (& Q,e); DeQueue (& Q,&e); • QueueTraverse(Q ,visit ()) }ADT Queue