3.1.4-3 假设以I和O分别表示入 栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。
#include <stdio.h>//假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列，否则//称为非法序列。//算法思想：一次读取字符串中的字符，并用i和j记录入栈和出栈的次数，如出栈的次数大于入栈的次数，则非法；等到字符串遍历完毕，如入栈的次数和出栈的//次数不相等，则栈不为空，也为非法。bool judge(char A[]){int i=0,j=0,k=0;//分别记录入栈和出栈的次数,k为遍历下标while(A[k]){ //字符串结束符的值为0switch(A[i]){ //如扫描结果为I，则break跳出switch循环，如扫描结果为O，则要比较i和j的大小，减少了if判断的次数case 'I':i++;break;case 'O':j++;if(j>i){return false;}}k++;}if(i!=j){return false;}return true;}int main() {char A[10];bool ret;printf("input c:\n");scanf("%s",A);printf("%s\n",A);ret=judge(A);if(ret){printf("right string\n");}else{printf("wrong string\n");}return 0;}输出结果：input c:IIOOOIIOOOwrong string进程已结束，退出代码为 0
3.1.4-4 设单链表的表头指针为L，结点结构由data和next两个域构成，其中data为字符型。
请设计算法判断该链表的全部n个字符是否中心对称。
3.1.4-5 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区 [0……MAXSIZE-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式，编写程序实现S1,S2有关入栈和出栈的操作。
#include <stdio.h>//共享栈的基本操作#define MaxSize 10typedef int ElemType;typedef struct{ElemType data[MaxSize];int top[2];//top为两个栈顶指针}SqStack;//初始化栈void InitStack(SqStack &S){S.top[0]=-1;//左边的s1栈顶指针S.top[1]=MaxSize;//右边的s2栈顶指针}//入栈判栈满，出栈判栈空//入栈bool Push(SqStack &S,int i,ElemType x){ //i为栈号，i=0表示左边的s1栈，i=1表示右边的s2栈，x是入栈元素if(i<0||i>1){printf("wrong input\n");return false;}if(S.top[1]-S.top[0]==1){ //入栈判栈满printf("the stack is full\n");return false;}if(i==0){S.data[++S.top[0]]=x;}else{S.data[--S.top[1]]=x;}return true;}//出栈bool Pop(SqStack &S,int i,ElemType &x){if(i<0||i>1){printf("wrong output");return false;}if(i==0){if(S.top[0]==-1){ //出栈判栈空printf("the stack s1 is empty\n");return false;}x=S.data[S.top[0]--];}else{if(S.top[1]==MaxSize){printf("the stack s2 is empty\n");return false;}x=S.data[S.top[1]++];}return true;}//读取栈顶元素bool GetTop(SqStack S,int i,ElemType &x){ //x保存栈顶元素的值if(i<0||i>1){printf("wrong stack\n");return false;}if(i==0){if(S.top[0]==-1){printf("the stack s1 is empty\n");return false;}x=S.data[S.top[0]];}else{if(S.top[1]==MaxSize){printf("the stack s2 is empty\n ");return false;}x=S.data[S.top[1]];}}int main() {SqStack S;InitStack(S);Push(S,0,1);Push(S,0,2);Push(S,0,3);Push(S,0,4);Push(S,1,1);Push(S,1,2);Push(S,1,3);ElemType x;bool ret;ret=Pop(S,0,x);printf("x is:%d\n",x);ret=Pop(S,1,x);printf("x is:%d\n",x);ret= GetTop(S,0,x);printf("x is:%d",x);return 0;}输出结果：x is:4x is:3x is:3进程已结束，退出代码为 0
3.2.5-1 若希望队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分队头指针front和队尾指针rear相同时的状态是空还是满，试编写与此结构相对应的入队和出队算法
#include <stdio.h>//若希望队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分队头指针front和队尾指针rear相同时的状态是空还是满，//试编写与此结构相对应的入队和出队算法#define MaxSize 20typedef int ElemType;typedef struct{ElemType data[MaxSize];int front,rear;int tag;//tag=0，表示因删除操作导致front=rear，则队列为空；tag=1，表示因插入操作导致front=rear，则队列为满}SqQueue;//队列初始化void InitStack(SqQueue &Q){Q.front=Q.rear=0;//front指向队头元素，rear指向队尾元素的下一个元素Q.tag=0;}//入队bool EnQueue(SqQueue &Q,ElemType x){if(Q.rear==Q.front&&Q.tag==1){printf("the queue is full\n");return false;}Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;Q.tag=1;return true;}//出队bool DeQueue(SqQueue &Q,ElemType &x){if(Q.rear==Q.front&&Q.tag==0){printf("the stack is empty\n");return false;}x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;Q.tag=0;return true;}int main() {SqQueue Q;InitStack(Q);EnQueue(Q,1);EnQueue(Q,2);EnQueue(Q,3);EnQueue(Q,4);ElemType x;bool ret;ret=DeQueue(Q,x);if(ret){printf("the front element is:%d",x);}return 0;}输出结果：the front element is:1进程已结束，退出代码为 0
3.5.2-2 Q是一个队列，S是一个空栈，实现将队列中的元素逆置的算法。
#include <stdio.h>//Q是一个队列，S是一个空栈，实现将队列中的元素逆置的算法。#define MaxSize 10typedef int ElemType;typedef struct{ElemType data[MaxSize];int top;}SqStack; //栈的结构体类型申明typedef struct{ElemType data[MaxSize];int front,rear;}SqQueue; //队列的结构体类型申明//队列初始化void InitQueue(SqQueue &Q){Q.front=Q.rear=0;}//队列入队:入队判队满bool EnQueue(SqQueue &Q,ElemType x){if((Q.rear+1)%MaxSize==Q.front){printf("the queue is full\n");return false;}Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;return true;}//队列出队：出队判队空bool DeQueue(SqQueue &Q,ElemType &x){if(Q.rear==Q.front){printf("the queue is empty\n");return false;}x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;}//栈初始化void InitStack(SqStack &S){S.top=-1;}//入栈：入栈判栈满bool Push(SqStack &S,ElemType x){if(S.top==MaxSize-1){printf("the stack is full\n");return false;}S.data[++S.top]=x;return true;}//出栈：出栈判栈空bool Pop(SqStack &S,ElemType &x){if(S.top==-1){printf("the stack is empty\n");return false;}x=S.data[S.top--];return true;}//算法思想：元素全部从队列出队，然后全部进栈，然后全部出栈，再全部入队bool ReverseQueue(SqQueue &Q,SqStack &S){ElemType x;while(Q.front!=Q.rear){ //出队，入栈DeQueue(Q,x);Push(S,x);}while(S.top!=-1){ //出栈，入队Pop(S,x);EnQueue(Q,x);}return true;}int main() {SqQueue Q;InitQueue(Q);int i;while(i<9){EnQueue(Q,i+1);i++;}SqStack S;InitStack(S);ReverseQueue(Q,S);return 0;}
3.2.5-4 请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④入队操作和出队操作的时间复杂度始终保持为O(1)。请设计队列的存储结构，并实现入队和出队的基本操作。
#include <stdio.h>#include<stdlib.h>//请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；// ③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；// ④入队操作和出队操作的时间复杂度始终保持为O(1)。请设计队列的存储结构，并实现入队和出队的基本操作。//[分析]：队列允许增加占用空间且出队元素空间不自动释放，则只能使用链式存储。// 又要求出队元素的空间可重复使用，则需要元素出队不断链，且要求入队和出队操作是O(1)复杂度，// 考虑可使用不带头结点的单循环链表（带头结点时，front始终指向头结点，无法把出队的元素空间排在队尾后面）。// 元素从队头出队后，即可排在队尾等待插入；front指针后移指向新的队头元素即可。//需要考虑的是，如何判断队列空和满的问题？常规循环单链表判空的操作无法实现。//借鉴循环队列，设置一个空闲结点，初始时，front和rear指针均指向空闲结点，且rear->next=front，则此时队列既是满，也是空；// 即front指向当前元素，rear指向队尾元素的下一个元素(即下一个待插入结点)//入队时，如队满，则在rear后面插入一个新的空闲结点，并使该结点指向front所指结点，// 入队元素保存在rear所指的结点中，然后rear后移;如队不满，则直接在rear所指的结点插入元素，然后rear后移//出队时，如队不空，则取front所指结点的元素，并使front=front->next.typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode;typedef struct{LNode *front,*rear;}LinkQueue;//初始化队列void InitQueue(LinkQueue &Q){LNode *s=(LNode *)malloc(sizeof(LNode));s->next=s;Q.front=Q.rear=s;}//判队空bool IsEmpty(LinkQueue Q){if(Q.rear==Q.front){printf("the queue is empty\n");return true;}printf("the queue is not empty\n");return false;}//判队满bool IsFull(LinkQueue Q){if(Q.rear->next==Q.front){printf("the queue is full\n");return true;}printf("the queue is not full\n");return false;}//入队bool EnQueue(LinkQueue &Q,ElemType x){Q.rear->data=x;//将x值赋值给队尾指针所指结点if(IsFull(Q)){LNode *s=(LNode *)malloc(sizeof(LNode));//如队满，则开辟新的空闲结点s->next=Q.front;//新结点指向队头结点Q.rear->next=s;//然后将尾指针的next指针指向该结点Q.rear=s;//尾指针移动到该结点}else{Q.rear=Q.rear->next;//如队不满，rear指针后移指向下一个结点}return true;}//出队bool DeQueue(LinkQueue &Q,ElemType &x){if(IsEmpty(Q)){return false;}else{x=Q.front->data;Q.front=Q.front->next;}return true;}int main() {LinkQueue Q;InitQueue(Q);printf("---------------------\n");printf("the initial queue is:\n");IsEmpty(Q);//初始时，既是队空，也是队满IsFull(Q);printf("--------------------\n");ElemType x;DeQueue(Q,x);//初始是空闲结点，不能出队EnQueue(Q,1);//初始时，即队满，入队需要开辟新的结点空间，并将元素插入前面一个结点中EnQueue(Q,2);//队满，开辟新空间，并将元素插入前面的结点DeQueue(Q,x);//队不空，出队DeQueue(Q,x);//队不空，出队DeQueue(Q,x);//出队队空，不能出队EnQueue(Q,6);//队不满，直接插入元素EnQueue(Q,7);//队不满，直接插入元素EnQueue(Q,8);//队满，开辟新的结点空间，并将元素插入前面一个结点中return 0;}输出结点：---------------------the initial queue is:the queue is emptythe queue is full--------------------the queue is emptythe queue is fullthe queue is fullthe queue is not emptythe queue is not emptythe queue is emptythe queue is not fullthe queue is not fullthe queue is full进程已结束，退出代码为 0
用栈实现中缀表达式的计算:
#include <stdio.h>#include<string.h>//用栈实现中缀表达式的计算//算法思想：//① 初始化两个栈，操作数栈和运算符栈；//②依次读取中缀表达式元素，如扫描到操作数，则压入操作数栈；//③若扫描到运算符‘+-*/’或者界限符'()'，则进行以下操作：// a.如栈空，则将运算符压入运算符栈；// b.如是左界限符‘（’，则也压入栈中；如是右界限符，则依次出栈运算符，同时将运算符加入后缀表达式，直到左界限符弹出栈；// c.如是运算符’+-*/‘，则依次与栈顶元素进行比较，如栈顶元素的优先级大于等于现运算符，则将栈顶的运算符依次出栈并加入后缀表达式，最后再把当前运算符入栈。//④ 每当从运算符栈弹出一个运算符，则从操作数栈弹出两个数字进行运算，并将运算结果压入操作数栈中;//⑤后缀表达式扫描完毕后，如运算符栈不为空，则继续计算#define MaxSize 20typedef struct{int data[MaxSize];int top;}DigitStack;typedef struct{char data[MaxSize];int top;}SignalStack;//操作数入栈bool PushDigit(DigitStack &S,int x){if(S.top==MaxSize-1){return false;}S.data[++S.top]=x;return true;}//操作数出栈bool PopDigit(DigitStack &S,int &x){if(S.top==-1){return false;}x=S.data[S.top--];return true;}//运算符入栈bool PushSignal(SignalStack &S,char x){if(S.top==MaxSize-1){return false;}S.data[++S.top]=x;return true;}//运算符出栈bool PopSignal(SignalStack &S,char &x){if(S.top==-1){return false;}x=S.data[S.top--];return true;}//比较运算符优先级int ComPri(char x){if(x=='+'||x=='-'){return 1;}else if(x=='*'||x=='/'){return 2;}else{ //指的是'('return 0;}}//操作数计算int calculate(char s,int left,int right){ //left为左操作数，right为右操作数switch(s){case '+':return left+right;case '-':return left-right;case '*':return left*right;case '/':return left/right;default:return 9999;}}void CalExp(char str[],int length,int &result){ //result保存计算结果DigitStack ds;//操作数栈SignalStack ss;//运算符栈ds.top=-1;//操作数栈初始化ss.top=-1;//运算符栈初始化int left,right;//左操作数和右操作数int cal=0;//保存操作数阶段计算结果char stop;//保存栈顶的运算符for(int i=0;i<length;i++){if(str[i]>='0'&&str[i]<='9'){ //如是操作数，则压入操作数栈int digit=0;while(str[i]>='0'&&str[i]<='9'){ //计算操作数digit=digit*10+(int)(str[i]-'0');i++;}PushDigit(ds,digit);}if(ss.top==-1||str[i]=='('){ //运算符栈空或者是左括号，则直接压入运算符栈PushSignal(ss,str[i]);}else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'){ //当前为运算符while(ComPri(ss.data[ss.top])>= ComPri(str[i])){ //将当前元素依次与栈顶元素比较，弹出所有优先级不低于当前元素的运算符PopSignal(ss,stop);//运算符栈顶元素出栈PopDigit(ds,right);//右操作数先出栈PopDigit(ds,left);//左操作数后出栈cal=calculate(stop,left,right);//计算新的操作数PushDigit(ds,cal);//将操作数计算结果压入操作数栈}PushSignal(ss,str[i]);//将当前运算符压入栈中}else if(str[i]==')'){PopSignal(ss,stop);while(stop!='('){ //依次将运算符出栈并加入后缀表达式计算，直到左括号PopDigit(ds,right);//右操作数先出栈PopDigit(ds,left);//左操作数后出栈cal=calculate(stop,left,right);//计算新的操作数PushDigit(ds,cal);//将操作数计算结果压入操作数栈PopSignal(ss,stop);}}}while(ss.top!=-1){ //如运算符栈不为空，则继续计算PopSignal(ss,stop);//运算符栈顶元素出栈PopDigit(ds,right);//右操作数先出栈PopDigit(ds,left);//左操作数后出栈cal=calculate(stop,left,right);//计算新的操作数PushDigit(ds,cal);//将操作数计算结果压入操作数栈}PopDigit(ds,result);}int main() {char str[20];int length;//统计字符串长度int result;//表达式计算结果printf("input expression:\n");gets(str);puts(str);length=strlen(str);//计算字符串长度，不包含结束符printf("length is:%d\n",length);CalExp(str,length,result);printf("the result is:%d\n",result);return 0;}输出结果：input expression:3-(5*2)+10*(6+2)3-(5*2)+10*(6+2)length is:16the result is:73进程已结束，退出代码为 0
3.3.6-1 栈在括号匹配中的应用
#include <stdio.h>//栈在括号匹配中的应用#define MaxSize 20typedef char ElemType;typedef struct{ElemType data[MaxSize];int top;}SqStack;//初始化栈void InitStack(SqStack &S){S.top=-1;}//判断栈空bool IsEmpty(SqStack S){if(S.top==-1){return true;}return false;}//入栈bool Push(SqStack &S,ElemType x){if(S.top==MaxSize-1){return false;}S.data[++S.top]=x;return true;}//出栈bool Pop(SqStack &S,ElemType &x){if(S.top==-1){return false;}x=S.data[S.top--];return true;}//括号匹配检查//算法思想：初始设置一个空栈，依次读取括号，如是左括号，则依次入栈；// 如是右括号，判断栈是否为空，如空，则不匹配；// 如栈不空，则出栈并将出栈元素与右括号判断是否匹配，如匹配，继续读取括号；//如括号读取完毕，此时栈不空，则不匹配。bool BracketCheck(ElemType str[],int length){SqStack S;InitStack(S);for(int i=0;i<length;i++){if(str[i]=='{'||str[i]=='['||str[i]=='('){ //左括号，则入栈Push(S,str[i]);}else{ //右括号if(IsEmpty(S)){ //栈空，无左括号可匹配return false;}ElemType x;Pop(S,x);if(str[i]=='}'&&x!='{'){ //左右括号不匹配return false;}if(str[i]==']'&&x!='['){return false;}if(str[i]==')'&&x!='('){return false;}}}if(!IsEmpty(S)){ //括号数组扫描完毕，但栈不空，即无右括号可匹配return false;}return true;}int main() {ElemType str[20];printf("please input brackets:\n");gets(str);printf("str=%s\n",str);bool ret= BracketCheck(str,10);if(ret){printf("check success\n");}else{printf("check fail\n");}return 0;}输出结果：please input brackets:{{{{(())}}str={{{{(())}}check fail进程已结束，退出代码为 0
3.3.6-3 利用一个栈实现以下递归函数的非递归计算：
Pn(x)=1,n=0; Pn(x)=2x,n=2;Pn(x)=2xPn-1(x)-2(n-1)Pn-2(x),n>1.
#include <stdio.h>#define MaxSize 20//用递归算法实现函数double FuncPn1(int n,double x){if(n<=1){return (n==0?1:2*x);}else{return 2*x* FuncPn1(n-1,x)-2*(n-1)* FuncPn1(n-2,x);}}//利用栈实现非递归计算//算法思想：//①设置一个栈，用于保存n和对应的Pn(x)；//②首先将n值，从n到2依次入栈（因为n=1和n=0对应的Pn(x)作为初始值已经给出）；//③计算Pn(x),先用P0和P1计算P2，再用P2和P1计算P3，以此类推。因此设置两个变量P1和P2记录此中间变量，初始时,P1=P0，P2=P1；// 然后计算栈顶元素的值P3，并且P1=P2，P2=P3，栈顶元素出栈，再计算下一个栈顶元素的值，直到栈空。double FuncPn2(int n,double x){typedef struct{int num; //n值double val; //Pn(x)的值}SqStack;SqStack S[MaxSize]; //定义栈-结构体数组int top=-1;//结构体数组S的下标变量double p1=1,p2=2*x;//初始化中间变量的值for(int i=n;i>=2;i--){ //从n到2依次入栈S[++top].num=i;}while(top!=-1){ //栈不为空时，则依次计算S[top].val=2*x*p2-2*(S[top].num-1)*p1;//计算栈顶元素的值p1=p2;//中间变量p1更新为现在的p2值p2=S[top].val;//p2更新为栈顶元素的值top--;//栈顶元素出栈}if(n==0){ //如n值输入为0，则返回p1return p1;}return p2;//如n值输入为1,则直接返回p2;如n值输入为大于等于2，则为最后返回的栈顶元素值，即为p2}int main() {double count;count= FuncPn1(3,2);printf("count1=%5.2f\n",count);count= FuncPn2(3,2);printf("count2=%5.2f",count);return 0;}输出结果：count1=40.00count2=40.00进程已结束，退出代码为 0
