安徽农业大学计算机科学与技术课件.ppt

程序流程： Multiply(13,4) M = 13 N = 4 N != 1 Result =13 + Multiply(13,3) return Result M = 13 N = 3 N != 1 Result =13 + Multiply(13,2) return Result M = 13 N = 2 N != 1 Result =13 + Multiply(13,1) return Result M = 13 N = 1 N == 1 Result =13 return Result 52 39 26 13 从以上的例子中，我们可以归纳出几个解递归问题的步骤： 步骤1：了解题意是否适合用递归来解题。 步骤2：决定递归结束条件(Stopping Cases)。 步骤3：决定递归执行部分(Recursive Step)。 3.3 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出 ( FIFO ) a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1,a2,……,an) 双端队列 入队 出队 入队 a1 a2 a3…………………….an 端1 端2 出队 链队列 结点定义 typedef struct node { int data; struct node *link; }JD; 头结点 ^ …... front 队头 队尾 rear 设队首、队尾指针front和rear, front指向头结点，rear指向队尾 front rear x入队 ^ x front rear y入队 x ^ y front rear x出队 x ^ y front rear 空队 ^ front rear y出队 ^ 入队算法 出队算法 JD *ldcr ( JD *rear , int x ) { JD *p; p = ( JD *) malloc ( sizeof ( JD )); p - data = x; p - link = NULL; rear - link = p; rear = p; return ( p ); } int ldsc ( JD *front , JD *rear ) { JD *s; int x; if ( front = = rear ) return ( - 1 ); s = front - link; front - link = s - link; if ( s - link = = NULL) rear = front; x = s - data; free ( s ); return ( x ); } 队列的顺序存储结构 实现：用一维数组实现sq[M] front=0 rear=0 1 2 3 4 5 0 队空 1 2 3 4 5 0 front J1,J2,J3入队 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入队 J4 J5 J6 front 设两个指针front,rear,约定： rear指示队尾元素下一位置； front指示队头元素； 初值front=rear=0 空队列条件：front==rear 入队列：sq[++rear]=x; 出队列：x=sq[++front]; rear rear front J1,J2,J3出队 front front rear 1 2 3 4 5 0 J1 J2 J3 front 存在问题 设数组维数为M，则： 当front=0,rear=M时，再有元素入队发生溢出——真溢出 当front?0,rear=M时，再有元素入队发生溢出——假溢出 解决方案 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0; 实现：利用“模”运算 入队： sq[rear]=x; rear=(rear+1)%M; 出队： x=sq[front]; front=(front+1)%M; 队满、队空判定条件 0 M-1 1 front rear …... …... 0 1 2 3 4 5 rear front J4 J5 J6 0 1 2 3 4 5 rear fron