《王道》课后练习1：栈

03:

栈的初态和终态均为空，以I和O分别表示入栈和出栈，则出入栈的操作序列可表示为由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。

1）下面所示的序列中哪些是合法的？

分析：1.入栈次数>=出栈次数 (当前操作) 2.结束时要求栈是empty()

A.IOIIOIOO 合法

B.IOOIOIIO 不合法，因为先入栈1次然后出栈2次

C.IIIOIOIO 不合法，因为本题要求栈的终态为空

D.IIIOOIOO 合法

2)通过对1)的分析，写出一个算法，判定所给的操作序列是否合法，返回true/false

算法设计前思考：

1.input是一个一维数组，如1)中所示，output是true/false

2.遍历数组

3.不合法的条件：

if(当前入栈次数<出栈次数)

if(遍历完成后，栈not empty())

所以需要设置变量来记录I和O的数量，并且每遍历到下一个字母，都要进行一次if判断

bool Legal_OOL(vector<char> A){int num_I=0;//入栈次数int num_O=0;//出栈次数int i=0;//工作指针i，用来扫描字符串数组while(A[i]!='\0'){if(A[i]=='I'){  num_I++; }if(A[i]=='O'){  num_O++; }//判定if(num_O>num_I){ return flase; }i++;}//如果出入栈次数不相等，即最后栈非空if(num_O!=num_I){   return false; }return true;
}

04:

设单链表的表头指针为L,节点结构由data和next两个域构成，其中data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。(例如xyx,xyyx都是中心对称)。

算法设计前思考：

1.input是一个单链表，output是true/false,那么函数可以写作：

bool IsCenter(LinkList L){}

2.基本要做的事情就是遍历这个单链表L,从头到尾。那么如何判断中心对称呢?

如果正着数和倒着数是一模一样的，就返回true,因为单链表不像数组判定回文数那么方便从尾巴 “倒着”遍历

如果从第一个节点向后，一个一个把node放入栈，再从栈里拿出来，就得到逆序的了。

3.于是我copy一个LinkList L2,用工作指针p遍历L2同时再取stack.top,用if判定(stack.top==p)

然后stack.pop，while(stack not empty){}完成之后如果全都相等就返回true.

//栈用顺序数组实现
bool IsCenter(LinkList L,int n){LinkList L2=Copy(LinkList L);char st[n];//遍历L元素入栈st[i]LinkNode* p=L->next;int i=0;while(p!=nullptr){st[i]=p->data;p=p->next;i++;}LinkNode* p2=L2->next;while(p2!=nullptr){if(p2->data!==s[i]){return false;}else{p2=p2->next;i--;}}return true;
}LinkList Copy(LinkList L){//尾插法LinkList L2=L;LinkNode* rear=L2;while(p!=nullptr){LinkNode* p=L->next;LinkNode* node=new LinkNode;node->data=p->data;rear->next=node;rear=node;}
retuen L2;
}

05:

设有2个栈，都采用顺序栈的方式，并且共享一个储存区[0,...,MaxSize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的形式。试设计s1,s2有关入栈和出栈的操作算法。

#define MaxSize 100
typedef struct{int Share_stack[MaxSize];int top1;int top2;
}share_st;

1.入栈时st1有top1++,st2有top2--;

int push(int i,int x){
//先判断栈满
if(share_st.top2-share_st.top1==1){cout<<"栈已满，不可入栈";exit(0);
}if(i==1){//入左边栈share_st.top1++;share_st.Share_stack[share_st.top1]=x;return 1;
}
if(i==2){//入右边栈share_st.top2--;share_st.Share_stack[share_st.top2]=x;return 1;
}}

出栈时，top1--,top2++

int pop(int i){
//首先判空
if((share_st.top1==-1)||(share_st.top2==MaxSize))
{cout<<"栈为空，没有元素可以出栈";exit(0);
}if(i==1){//出左边栈顶元素return share_st.Share_stack[share_st.top1];top1--;
}
if(i==2){//出右边栈顶元素return share_st.Share_stack[share_st.top2];top2++;
}}