关注公众号凡花花的小窝，收获更多的考研计算机专业编程相关的资料 3.29 如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。 解： #define MaxQSize 4 typedef int ElemType; typedef struct{ ElemType base; int front; int rear; Status tag; }Queue; Status InitQueue(Queue& q) { q.base=new ElemType[MaxQSize]; if(!q.base) return FALSE; q.front=0; q.rear=0; q.tag=0; return OK; } Status EnQueue(Queue& q,ElemType e) { if(q.frontq.rear&&q.tag) return FALSE; else{ q.base[q.rear]=e; q.rear=(q.rear+1)%MaxQSize; if(q.rearq.front)q.tag=1; } return OK; } Status DeQueue(Queue& q,ElemType& e) { if(q.frontq.rear&&!q.tag)return FALSE; else{ e=q.base[q.front]; q.front=(q.front+1)%MaxQSize; q.tag=0; } return OK; } 设标志节省存储空间，但运行时间较长。不设标志则正好相反。 3.30 假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。 解： #define MaxQSize 4 typedef int ElemType; typedef struct{ ElemType *base; int rear; int length; }Queue; Status InitQueue(Queue& q) { q.base=new ElemType[MaxQSize]; if(!q.base) return FALSE; q.rear=0; q.length=0; return OK; } Status EnQueue(Queue& q,ElemType e) { if((q.rear+1)%MaxQSize(q.rear+MaxQSize-q.length)%MaxQSize) return FALSE; else{ q.base[q.rear]=e; q.rear=(q.rear+1)%MaxQSize; q.length++; } return OK; } Status DeQueue(Queue& q,ElemType& e) { if((q.rear+MaxQSize-q.length)%MaxQSize==q.rear) return FALSE; else{ e=q.base[(q.rear+MaxQSize-q.length)%MaxQSize]; q.length–; } return OK; } 3.31 假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。 解： Status SymmetryString(char p) { Queue q; if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(*p){ Push(s,*p); EnQueue(q,*p); p++; } while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK; } 3.32 试利用循环队列编写求k阶菲波那契序列中前n+1项的算法，要求满足：而，其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶菲波那契序列中的最后k项） 解： int Fibonacci(int k,int n) { if(k<1) exit(OVERFLOW); Queue q; InitQueue(q,k); ElemType x,e; int i=0; while(i<=n){ if(i<k-1){ if(!EnQueue(q,0)) exit(OVERFLOW); } if(ik-1){ if(!EnQueue(q,1)) exit(OVERFLOW); } if(i>=k){ // 队列求和 x=sum(q); DeQueue(q,e); EnQueue(q,x); } i++; } return q.base[(q.rear+q.MaxSize-1)%q.MaxSize]; } 3.33 在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。 解： // Filename:Queue.h typedef struct{ ElemType *base; int front; int rear; Status tag; int MaxSize; }DQueue; Status InitDQueue(DQueue& q,int size) { q.MaxSize=size; q.base=new ElemType[q.MaxSize]; if(!q.base) return FALSE; q.front=0; q.rear=0; q.tag=0; return OK; } Status EnDQueue(DQueue& q,ElemType e) { if(q.frontq.rear&&q.tag) return FALSE; if(q.frontq.rear&&!q.tag){ // 空队列 q.base[q.rear]=e; q.rear=(q.rear+1)%q.MaxSize; if(q.rearq.front)q.tag=1; } else{ // 非空非满 if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2){ // 从队头入队 q.front=(q.front+q.MaxSize-1)%q.MaxSize; q.base[q.front]=e; if(q.rearq.front)q.tag=1; } else{ // 从队尾入队 q.base[q.rear]=e; q.rear=(q.rear+1)%q.MaxSize; if(q.rearq.front)q.tag=1; } } return OK; } Status DeDQueue(DQueue& q,ElemType& e) { if(q.front==q.rear&&!q.tag)return FALSE; else{ // 非空队列 e=q.base[q.front]; q.front=(q.front+1)%q.MaxSize; q.tag=0; } return OK; } // Filename:XT333.cpp 主程序文件 #include <iostream.h> #include <stdlib.h> typedef int ElemType; #include “D:\VC99\Queue.h”
int main() { int t1,t2,t3,t4; ElemType e; cout<<"请输入作业a1、a2、a3、a4的执行时间: "; cin>>t1>>t2>>t3>>t4; DQueue dq; InitDQueue(dq,5); EnDQueue(dq,t1); EnDQueue(dq,t2); EnDQueue(dq,t3); EnDQueue(dq,t4); while(dq.front!=dq.rear||dq.tag){ DeDQueue(dq,e); cout<<e<<endl; } return 0; } 3.34 假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧（分别以P,H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符‘E’和‘D’表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。 解： int main() { ElemType e; DQueue dq; InitDQueue(dq,20); char ch[20]; cout<<“请输入待调度的车厢字符序列(仅限PHS)：”; cin>>ch; int i=0; while(ch[i]){ if(ch[i]‘P’) cout<<ch[i]; if(ch[i]‘S’) EnDQueue(dq,ch[i],0);// 从队头入队 if(ch[i]==‘H’) EnDQueue(dq,ch[i],1);// 从队尾入队 i++; } while(dq.front!=dq.rear||dq.tag){ DeDQueue(dq,e); cout<<e; } cout<<endl; return 0; } 第4章 串 4.1 解：空格串是指一个或多个空格字符(ASCII码为20H)组成的串，而空串中没有任何字符。 4.2 解：串赋值(StrAssign)、串比较(StrCompare)、求串长(StrLength)、串连接(Concat)、求子串(SubString)这五种基本操作构成串类型的最小操作子集。 4.6 解： s1=SubString(s,3,1) s2=SubString(s,6,1) Replace(s,s1,s2) Concat(s3,s,s1) Concat(t,SubString(s3,1,5),SubString(s3,7,2)) 算法设计题： // Filename: String.h #include <stdlib.h> #include <string.h> #define MaxSize 128 class String{ char ch; int curlen; public: String(const String& ob); String(const char init); String(); ~String(); void StrAssign(String t); int StrCompare(String t); int StrLength(); void Concat(String t); String SubString(int start,int len); void show(); }; String::String(const String& ob) { ch=new char[MaxSize+1]; if(!ch) exit(1); curlen=ob.curlen; strcpy(ch,ob.ch); } String::String(const char* init) { ch=new char[MaxSize+1]; if(!ch) exit(1); curlen=strlen(init); strcpy(ch,init); } String::String() { ch=new char[MaxSize+1]; if(!ch) exit(1); curlen=0; ch[0]=’\0’; } String::~String() { delete ch; curlen=0; } void String::StrAssign(String t) { strcpy(ch,t.ch); curlen=t.curlen; } int String::StrCompare(String t) { return strcmp(ch,t.ch); } int String::StrLength() { return curlen; } void String::Concat(String t) { strcat(ch,t.ch); curlen=curlen+t.curlen; } String String::SubString(int start,int len) { String temp; int i,j; if(start>=0 && start+len<=curlen && len>0){ temp.curlen=len; for(i=0,j=start;i<len;i++,j++) temp.ch[i]=ch[j]; temp.ch[len]=’\0’; } return temp; } void String::show() { cout<<ch<<endl; } 4.10 解： void StrReverse(String& s) { String t; int i,j; j=s.StrLength(); for(i=j-1;i>=0;i–) t.Concat(s.SubString(i,1)); s.StrAssign(t); } 4.11 解：
