第三章栈与队列-数据结构.doc

第三章 栈与队列 3.15 typedef struct{???????????????? Elemtype *base[2];PAGE \# 页：# *base[2]是随*base[1]而确定的，因此这里的定义改为*base更好些，否则容易仍人误解为存在两个数组空间。 ?????????????? ??Elemtype *top[2];????????? ?????}BDStacktype; //双向栈类型 Status Init_Stack(BDStacktype tws,int m)//初始化一个大小为m的双向栈tws{??tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype));PAGE \# 页：# 这里写错了吧？只要简单一看就能看出错来，因为语句中没有“m”，说明参数中的m没有用上，可能是这位同学粗心大意，或是对C语言掌握得还不够好。 ??tws.base[1]=tws.base[0]+m;??tws.top[0]=tws.base[0];??tws.top[1]=tws.base[1];PAGE \# 页：# 随着定义的改动，这里就改为tws.top[1]=tws.base+m; 同时请注意，初始化确定了“栈顶指针的定义”，按这位同学的定义(我只是按照他原来的两个语句的写法改成现在这个样子)栈的高端指针定义为指向当前高端栈的栈顶元素，而不是它的前一位置。这样后面的入栈和出栈的算法自然就不对了，对吗？入栈应该先移指针，再复制元素，栈满的条件也不对了。如果这位同学原打算将高端栈顶指针定义为指向前一位置，那么这个语句就应该改为tws.top[1]=tws.top[0]+m-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;??else if(i==1) *tws.top[1]--=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[1]==tws.base[1]) return OVERFLOW;????x=*++tws.top[1];??}??else return ERROR;??return OK;}//pop 3.16 PAGE \# 页：# 对这个题目的理解错了，题目要求生成一个栈的操作序列，而不是对当前的火车序列进行调度。假设以“E”表示入栈，以“D”表示出栈，那么对于“HHSHSSH”的火车序列应该生成的调度序列为“EEEDEEDEDEDDDD”。另外对字符串应该用“串的结束标志来判别，而不应该用“空”。 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,否则返回0{??InitStack(s);??while((e=getchar())!=)??{????if(e==’@’) return 0;//不允许在’’之前出现’@’????push(s,e); ??}??while( (e=getchar())!=@)