c语言版习题数据结构13

1、3.2 栈的应用举例3.2.5 表达式求值 算符优先法:4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8 操作数(operand): 进OPND栈 操作符(operator): 进OPTR栈 界限符(delimiter):算符间的优先关系:1 2+-*/()# + - * / ( # =Precede: 判定运算符栈的栈顶运算符1与读入的运算符2之间 的优先关系的函数.Operate: 进行二元运算ab的函数.算术表达式求值过程(算法3.4)OperandType EvaluateExpression()InitStack(OPTR); Push(OPTR,

2、#); InitStack(OPND); c = getchar(); While(c!=# | GetTop(OPTR)!=#) If(!In(c,OP) Push(OPND,c); c = getchar(); / 不是运算符则进栈 else switch(Precede(GetTop(OPTR),c) case : / 退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; default: printf(“Expression error!”); return(E

3、RROR); / switch / while return GetTop(OPND); / EvaluateExpression对算术表达式3*(7-2)求值.步骤 OPTR栈 OPND栈 输入字符 主要操作1 # 3 * ( 7 - 2 ) # Push(OPND,3)2 # 3 * ( 7 - 2 ) # Push(OPTR,*)3 # * 3 ( 7 - 2 ) # Push(OPTR,()4 # * ( 3 7 - 2 ) # Push(OPND,7)5 # * ( 3 7 - 2 ) # Push(OPTR,-)6 # * ( - 3 7 2 ) # Push(OPND,2)7 #

4、 * ( - 3 7 2 ) # Operate(7,-,2)8 # * ( 3 5 ) # POP(OPTR)9 # * 3 5 # Operate(3,*,5)10 # 15 # Return(GetTop(OPND)例：汉诺塔问题：将a柱子上的盘移到 c柱，用 b柱放临时盘 要求：一次只能移动一个盘，大盘不可放于小盘上。abchanoi塔问题定义函数：movetower(n,a,c,b) n个盘ac，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)

5、 将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塔的递归算法3.4 队列3.4.1抽象数据类型队列的定义队列（Queue）: 先进先出(First In First Out) (缩写为FIFO）的线性表。仅在队尾进行插入和队头进行删除操作的线性表。队头（front）: 线性表的表头端，即可删除端。队尾（rear）: 线性表的表尾端，即可插入端。队头对尾.a1a2a3a

6、n-1an入队列(Enqueue)出队列(Dequeque)队列的抽象数据类型ADT Queue 数据对象：D = ai | ai属于Elemset, (i=1,2,n, n0)数据关系：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

7、 ,visit () ADT Queue队列的基本操作(之一)InitQueue (&Q) 操作结果:构造一个空的队列Q。DestroyQueue (&Q) 初始条件: 队列Q已经存在。 操作结果: 销毁队列Q。ClearQueue (&Q) 初始条件: 队列Q已经存在。 操作结果: 将队列Q重置为空队列。队列的基本操作(之二)QueueEmpty(Q)初始条件: 队列Q已经存在。操作结果: 若队列Q为空队列，则返回TURE;否则返回FALSE。QueueLength(Q) 初始条件: 队列Q已经存在。 操作结果: 返回队列Q中的数据元素个数, 即队列Q的长度。GetHead(Q,&e) 初始

8、条件: 队列Q已经存在且非空。 操作结果: 用e返回队列Q中队头元素的值。队列的基本操作(之三)EnQueue (&Q,e)初始条件: 队列Q已经存在。操作结果: 插入元素e为新的队尾元素。DeQueue (&Q,&e)初始条件: 队列Q已经存在且非空。操作结果: 删除队列Q 的队头元素并用e返回其值。QueueTraverse(Q,visit ()初始条件: 队列Q已经存在且非空。操作结果: 从队头到队尾依次对队列Q的每个元素调用函数visit ()。一旦visit ()失败，则操作失败。3.4.2 链队列 - 队列的链式表示与实现typedef struct QNode QElemType

9、 data; struct QNode *next; Qnode, *QueuePtr;typedef struct QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;#define OK 1#define OVERFLOW -1#define ERROR 0data*nextfrontrear链队列示意图frontrearfrontrear赵frontrear钱赵frontrear钱赵(a)空队列(b)元素“赵”入队列(c)元素“钱”入队列(d)元素“赵”出队列链队列的操作实现举例/* InitQueue 构造一个空的队列Q*/St

10、atus InitQueue(LinkQueue &Q) Q.rear=(QueuePtr)malloc(sizeof(QNode) ); Q.front = Q.rear; if(!Q.front) return(OVERFLOW); Q.front - next = NULL; return OK; / InitQueue链队列的操作实现(DestroyQueue) / 销毁队列QStatus DestroyQueue(LinkQueue &Q) while(Q.front ) Q.rear = Q.front - next; free(Q.front); Q.front = Q.rear

11、; return OK; / DestroyQueue链队列的操作实现(EnQueue) / 插入元素e为新的队尾元素Status EnQueue(LinkQueue &Q, QelemType e) p = ( QueuePtr )malloc(sizeof(QNode); if(!p) return(OVERFLOW); p-data = e; p - next = NULL; Q.rear -next = p; Q.rear = p; return OK; / EnQueue链队列的操作实现(DeQueue)/ 若队列不空, 删除队列Q 的队头元素并用e返回其值, 同时返回OK; 否则返

12、回ERROR 。Status DeQueue(LinkQueue &Q, QelemType &e) if(Q.front = Q.rear) retrun ERROR; p = Q.front - next; e = p-data; Q.front-next = p-next; if(Q.rear = p) Q.rear = Q.front ; free(p); return OK; / DeQueue3.4.3 循环队列 - 队列的顺序表示与实现采用顺序存储结构约定:1)初始空队列：front = rear=0 ; 2)插入新的元素时, rear+; 3)删除队头元素时,front+;J1

13、J2J3Q.frontQ.rearJ3Q.frontQ.rearJ5J6Q.frontQ.rearQ.rearQ.front102354循环列表-解决数组越界但未占满空间的办法10maxsize-1.Q.frontQ.rear.队列当Q.rear Q.front时: Q.rear Q.front = 队列中元素个数当Q.rear Q.front时: Q.rear Q.front +maxsize = 队列中元素个数当Q.rear = Q.front时: 队列是空或满循环队列的头尾指针012345J3J4J5Q.rearQ.front(a)一般队列012345Q.rearQ.front(c)空队

14、列J6J3J4J5012345J7J8Q.rearQ.front(b)满队列循环队列-队列的顺序存储结构实现(1)typedef struct QElemType *base; / 存储空间基地址 int front; / 队头指针 int rear; / 队尾指针 SqQueue;#define MAXSIZE 100Status InitQueue(SqQueue &Q)Q.base=(QElemType*)malloc(sizeof(QElemType) *MAXSIZE ); if(!Q.base) return(OVERFLOW); Q.front = Q.rear = 0; return OK; / InitQueue循环队列-队列的顺序存储结构实现(2)Status EnQueue(SqQueue &Q, QelemType e) if(Q.rear+1)% MAXSIZE = Q.front) return(ERROR); Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXSIZE; return OK; / EnQueue循环队列-