数据结构62905.ppt

为表达方便，设入栈序列为1，2，3，4，5，6，7，8，9，……（数字更加好表达和理解）那么出栈数列中，对应每个数，其后续数列中，所有小于该数的数字是逆序排列的。就是比如出栈数列第一个数为5，那么1，2，3，4四个数必定是按照逆序排列的，中间可以夹杂其他数，只判断小于5的数即可，即应该是按照这样的顺序排列，5,X,X,X 4,X,X,X,3,X,X,2,X,X,X,X,X,X,X,1??（其中X代表其他数，不影响本次判断）同样，对于出栈数列中每一个数都可以进行这么一次判断。可以很直接的找出答案，而不用在纸上画push pop 等等。例，1，4，2，3，5? ?? ?? ?4后面有 2，3 排列，非逆序，非法? ?? ? 1，2，5，3，4? ?? ?? ?1后面没有比1小的，2后面没有比2小的。5后面 3，4 非法。? ?? ? 3，2，5，4，1，? ?? ?3后面 2，1 合法??2后面 1 合法 ， 5 后面 4，1 合法，4后面1 合法。所以该序列为可能输出序列。 定义是递归的 求解n! 的过程  long Fib ( long n ) { if ( n = 1 ) return n;  else return Fib (n-1) + Fib (n-2); } 【例3】求数组 A 中 n 个整数的和 int sum ( int n ) { if ( n == 1 ) result = A[0]; else result = A[n-1] + sum(n-1); return result; } 3.4.2 链队列 3.4.3 循环队列－队列的顺序表示和实现 第3章 习题 第3章思考题 设队首、队尾指针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出队 ^ 我们将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型： 链队列结点定义 typedef struct Qnode { QElemType data; struct QNode *next; } QNode,*QueuPtr; Typedef struct{ QueuPtr front;//队头指针 QueuPtr rear;//队尾指针 } LinkQueue 基本操作的函数原型说明见书P61。 基本操作的算法描述（部分） Status initQueue(linkqueue Q) {//构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof QNode)); If(!Q.front)exit (OVERFLOW);//存储分配失败 Q.front–next=NULL; Return OK; } 基本操作的算法描述（部分） Status DestroyQueue(linkqueue Q){ //销毁队列Q While(Q.front){ Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; } return OK;} Status EnQueue( LinkQueue Q, QElemType e) //插入元素e为Q的新的队尾元素； { p=(QueuePtr * )malloc ( sizeof(QNode)); if (!p) exit (OVERFLOW);//存储分配失败 p–data=e; p–next=NULL; Q.rear-next=p; Q.rear=p; return OK;} Status DeQueue(LinkQueue Q,QElemType e) 注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。 //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR { if( Q.front==Q.rear) return ERROR; p=Q.front-