《限定性线性表——栈和队列》由会员分享，可在线阅读，更多相关《限定性线性表——栈和队列（20页珍藏版）》请在金锄头文库上搜索。
1、第 3 章 限定性线性表栈和队列3.15 #define StackSize 100;typedef struct SElemType *base;SElemType *top0;SElemType *top1;TSqStack;Status InitStack(TSqStack tws)/构造一个空的双向栈if (!(tws.base=(SElemType *)malloc(StackSize*sizeof(SElemType)exit(OVERFLOW);tws.top0=tws.base;tws.top1=tws.baseStackSize-1;return OK;Status Push
2、(TSqStack &tws, int i, SElemType x)/将元素 x 压入双向栈 tws 的第 i 个栈中，i=0，1if (tws.top0=tws.top1+1)exit(OVERFLOW);if (i=0) *tws.top0+=x; else if (i=1) *tws.top1-=x;else return ERROR;return OK;SElemType Pop(TSqStack &tws, int i)/若双向栈 tws 的第 i 个栈不空，则删除第 i 个栈的栈顶元素并返回其值，否则返回空元素if (i!=0|i!=1) return NULL;if (i=0&
3、tws.top0) return *-tws.top0;if (i=1&tws.top1!=tws.baseStackSize-1) return *+tws.top1;return NULL;3.17 Status Model()/识别依次读入的一个以为结束符的字符序列是否为形如序列 1&序列 2模式的字符序列/序列 1 和序列 2 中不包含字符 &，序列 1 是序列 2 的逆序列InitStack(s); c=getchar();while (c!=&) Push(s,c); c=getchar();c=getchar(); while (c!=&!StackEmpty(s) Pop(s,
4、x);if (c=x) c=getchar();else return FALSE;if (c= & StackEmpty(s) return TRUE;else return FALSE; 3.19Status BracketsMatch()/判断依次读入的以为结束符的算术表达式中括号是否正确配对出现InitStack(s); c=getchar();while (c!=)if ( c=( | c= | c=) Push(s,c);if ( c=) | c= | c=)if EmptyStack(s) return FALSE;Pop(s,x);if (!(x=(&c=)|(x=&c=)|(
5、x=&c=) return FALSE;/ifc=getchar();/while if EmptyStack(s) return TRUE;else return FALSE;3.28typedef struct CQNode CQElemType data;struct CQNode *next;CQNode, *CQueuePtr;typedef struct CQueuePtr rear;CLinkQueue;Status InitCQueue(CLinkQueue &cq) /初始化一个只有尾指针的带头结点的循环链表表示的队列if (!(cq.rear=(CQueuePtr)mall
6、oc(sizeof(CQNode) exit(OVERFLOW);cq.rear-next=cq.rear;return OK;Status EnCQueue(CLinkQueue &cq, CQElemType e) /插入元素 e 为 cq 的新的队尾元素if (!(p=(CQueuePtr)malloc(sizeof(CQNode) exit(OVERFLOW);p-data=e; p-next=cq.rear-next;cq.rear-next=p; cq.rear=p;return OK;Status DeCQueue(CLinkQueue &cq, CQElemType &e)/若
7、队列不空，则删除 cq 的队头元素，用 e 返回其值/并返回 OK，否则返回 ERRORif (cq.rear=cq.rear-next) return ERROR;p=cq.erar-next-next;e=p-data; cq.rear-next-next=p-next;if (cq.rear=p) cq.rear=cq.rear-next;free(p); return OK;3.30#define MAXSIZE 100;typedef struct QElemType *base;int rear; int length;SqQueue;Status EnQueue(SqQueue
8、&q, QElemType e)/插入元素 e 为 q 的新的队尾元素if (q.length=MAXSIZE) return ERROR;q.baseq.rear=e;q.rear=(q.rear+1)%MEXSIZE; return OK;Status DeQueue(sQQueue &q, QElemType &e)/若队列不空，则删除 q 的队头元素，用 e 返回其值/并返回 OK，否则返回 ERRORif (q.length=0) return ERROR;e=q.base(q.rear-q.length+MEXSIZE)%MAXSIZE;q.length-;return OK;3.
9、31Status ReturnText() /判断读入的一个以为结束符的字符序列是否为回文InitStack(s); InitQueue(q); c=getchar();while (c!=)Push(s,c); EnQueue(q,c);c=getchar();while (!EmptyStack(s)Pop(s,x); DeQueue(q,y);if (x!=y) return FALSE;return TRUE;(以下内容来自 http:/) 第三章 栈与队列3.15 typedef structElemtype *base 1;Elemtype *top 1;BDStacktype;
10、/双向栈类型 Status Init_Stack(BDStacktype &tws,int m)/初始化一个大小为 m 的双向栈 twstws.base 0 =(Elemtype*)malloc(sizeof(Elemtype);tws.base=tws.base 0 +m;tws.top 0 =tws.base 0 ;tws.top=tws.base; return OK;/Init_Stack Status push(BDStacktype &tws,int i,Elemtype x)/x 入栈,i=0 表示低端栈,i=1 表示高端栈if(tws.top 0 tws.top) return
11、 OVERFLOW; /注意此时的栈满条件if(i=0) *tws.top 0 +=x;else if(i=1) *tws.top-=x;else return ERROR;return OK;/push Status pop(BDStacktype &tws,int i,Elemtype &x)/x 出栈,i=0 表示低端栈,i=1 表示高端栈if(i=0)if(tws.top 0 =tws.base 0 ) return OVERFLOW;x=*-tws.top 0 ;else if(i=1)if(tws.top=tws.base) return OVERFLOW;x=*+tws.top;
12、else return ERROR;return OK;/pop 3.16 void Train_arrange(char *train)/这里用字符串 train 表示火车,H表示硬席,S表示软席p=train;q=train;InitStack(s); while(*p)if(*p=H) push(s,*p); /把H存入栈中else *(q+)=*p; /把S调到前部p+;while(!StackEmpty(s)pop(s,c);*(q+)=c; /把H接在后部/Train_arrange 3.17 int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串, 是则返回
13、1,否则返回 0InitStack(s);while(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackEmpty(s) return 0;pop(s,c);if(e!=c) return 0;if(!StackEmpty(s) return 0;return 1;/IsReverse 3.18 Status Bracket_Test(char *str)/判别表达式中小括号是否匹配count=0;for(p=str;*p;p+) if(*p=() count+;else if(*p=) count-;if (count1)if(gx-1
14、y=old)gx-1y=color;EnQueue(Qx,x-1);EnQueue(Qy,y); /修改左邻点的颜色if(y1)if(gxy-1=old)gxy-1=color;EnQueue(Qx,x);EnQueue(Qy,y-1); /修改上邻点的颜色if(x=0) s=0;else if(m0&n=0) s=n+g(m-1,2*n);else return ERROR;return OK;/g 3.25 Status F_recurve(int n,int &s)/递归算法if(n=e)p=(p+A/p)/2;return p;/sqrt_notrecurve 3.27 这一题的所有算
15、法以及栈的变化过程请参见数据结构(pascal 版), 作者不再详细写出. 3.28 void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列 QQ=(CiLNode*)malloc(sizeof(CiLNode);Q-next=Q;/InitCiQueue void EnCiQueue(CiQueue &Q,int x)/把元素 x 插入循环链表表示的队列 Q,Q指向队尾元素,Q-next 指向头结点,Q-next-next 指向队头元素p=(CiLNode*)malloc(sizeof(CiLNode); p-data=x;p-next=Q-next; /直接把 p 加在 Q 的后面Q-next=p;Q=p; /
