}
3.32 试利用循环队列编写求k阶菲波那契序列中前n+1项的算法，要求满足：fn?max而
fn?1?max，
其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶菲波那契序列中的最后k项）
解：
int Fibonacci(int k,int n) { }
3.33 在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。
解：
// Filename:Queue.h typedef struct{
ElemType *base; int front; int rear; Status tag; int MaxSize;
if(k<1) exit(OVERFLOW); Queue q; InitQueue(q,k); ElemType x,e; int i=0; while(i<=n){ }
return q.base[(q.rear+q.MaxSize-1)%q.MaxSize];
if(i if(i==k-1){ } if(i>=k){ } i++; // 队列求和 x=sum(q); DeQueue(q,e); EnQueue(q,x); if(!EnQueue(q,1)) exit(OVERFLOW); if(!EnQueue(q,0)) exit(OVERFLOW); }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) { } Status DeDQueue(DQueue& q,ElemType& e) { } // Filename:XT333.cpp 主程序文件 #include if(q.front==q.rear&&!q.tag)return FALSE; else{ // 非空队列 } return OK; e=q.base[q.front]; q.front=(q.front+1)%q.MaxSize; q.tag=0; if(q.front==q.rear&&q.tag) return FALSE; if(q.front==q.rear&&!q.tag){ // 空队列 } else{ // 非空非满 } return OK; if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2){ } else{ // 从队尾入队 } q.base[q.rear]=e; q.rear=(q.rear+1)%q.MaxSize; if(q.rear==q.front)q.tag=1; // 从队头入队 q.front=(q.front+q.MaxSize-1)%q.MaxSize; q.base[q.front]=e; if(q.rear==q.front)q.tag=1; q.base[q.rear]=e; q.rear=(q.rear+1)%q.MaxSize; if(q.rear==q.front)q.tag=1; typedef int ElemType; #include \ int main() { } 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]){ } while(dq.front!=dq.rear||dq.tag){ DeDQueue(dq,e); if(ch[i]=='P') cout< if(ch[i]=='S') EnDQueue(dq,ch[i],0);// 从队头入队 if(ch[i]=='H') EnDQueue(dq,ch[i],1);// 从队尾入队 i++; 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){ } return 0; DeDQueue(dq,e); cout< } } cout< cout< 第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 String::String(const String& ob) { } String::String(const char* init) { ch=new char[MaxSize+1]; if(!ch) exit(1); curlen=strlen(init); ch=new char[MaxSize+1]; if(!ch) exit(1); curlen=ob.curlen; strcpy(ch,ob.ch); char *ch; int curlen; 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(); public: