《限定性线性表——栈和队列》由会员分享，可在线阅读，更多相关《限定性线性表——栈和队列（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
2、Push(TSqStack &tws, int i, SElemType x) /将元素x压入双向栈tws的第i个栈中，i=0，1 if (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.17Status 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,x); i
4、f (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=
5、&c=)|(x=&c=) return FALSE; /if c=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=(CQ
6、ueuePtr)malloc(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, CQ
7、ElemType &e) /若队列不空，则删除cq的队头元素，用e返回其值 /并返回OK，否则返回ERROR if (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
8、EnQueue(SqQueue &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，否则返回ERROR if (q.length=0) return ERROR; e=q.base(q.rear-q.length+MEXSIZE)%MAXSIZE; q.lengt
9、h-; return OK;3.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 *base1;Elemtyp
10、e *top1;BDStacktype; /双向栈类型 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 t
11、ws.top) return 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
12、=*+tws.top;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()/判断输入的字符串中&前和&后部分是否为逆串,是则返回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
