11-12-2学期-数据结构习题及补充考研-.ppt

第三章习题;#define MAX 100 typedef struct node{???????Elemtype *base[2];???????Elemtype *top[2];???}BDStacktype; //双向栈类型 ;status Init_Stack(BDStacktype tws) //初始化一个大小为MAX的双向栈tws{ tws.base[0]=(Elemtype*)malloc(MAX*sizeof(Elemtype));?? tws.base[1]=tws.base[0]+MAX-1;?? tws.top[0]=tws.base[0]; ?tws.top[1]=tws.base[1];?? return OK;}//Init_Stack ;status push(BDStacktype tws,int i,Elemtype x) //x入栈,i=0表示低端栈,i=1表示高端栈{ if(tws.top[0]tws.top[1]) return OVERFLOW; //栈满??if(i==0) {*tws.top[0]=x; tws.top[0]++；}??else if(i==1) {*tws.top[1]=x; tws.top[1]--；}? ?else return ERROR;??return OK;}//push ;status pop(BDStacktype tws,int i) //x出栈,i=0表示低端栈,i=1表示高端栈{ if(i==0){?if(tws.top[0]==tws.base[0]) return FALSE;???? --tws.top[0];}? ?else if(i==1){if(tws.top[1]==tws.base[1]) return FALSE;???? ++tws.top[1];}?? else return ERROR; return OK;}//pop ;3.28假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。;;status DeCiQueue(CiQueue Q,int x) //从循环链表表示的队列Q头部，删除队头元素放入x中{if(Q==Q-next) return （FALSE）; //队列已空??p=Q-next-next;//队头元素?? x=p-data;??Q-next-next=p-next;??free(p);??return (OK);}//DeCiQueue ;3.29如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值相同时的队列状态是 “空”还是“满”。试编写与此结构相应的入队列和出队列的算法。;#define MAXQSIZE 100 //最大队列长度 //与栈不同，循环队列不能进行再分配。 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 头指针，若队列不空，指向队列头元素 int rear; // 尾指针，若队列不空，指向队列尾元素 的下一个位置 } SqQueue;; status EnQueue(SqQueue Q, QElemType e ) { // 插入元素e为Q的新的队尾元素 if((Q.rear+1)% MAXQSIZE==Q.front) //队列满 return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)% MAXQSIZE; return OK; };#define MAXQSIZE 100 //最大队列长度。 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 指向队头元素 int rear; // 指向队尾元素的下一个位置 int tag; } CyQueue ;;status EnCyQueue(CyQueue Q,int x) //带tag域的循环队列入队列算法{ if(Q.front==Q.rearQ.tag==1) //tag域的值为0表示“空”,1表示“满”????return OVERFLOW;??Q.base[Q.rear]=x;??Q.rear=(Q.rear+1)%MAXSIZE;??if(Q.front==Q.rear) Q.