数据结构上机指导书第3次上机实验指导书

《数据结构上机指导书第3次上机实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2・n阶二项式系数(用队列实现)【冃的】理解队列操作的算法和程序实现，学会使用队列解决问题。【问题描述】计算并输出n阶二项式系数。【数据结构】用顺序存储的队列classQueue对象暂存求得的二项式系数。【算法描述】本题特点是递推式计算。计算求得的二项式系数可以摆成一个三角形，称为“杨辉三角形”。应用程序为YangHui(intn)函数。初始的两个系数1山常量赋值，以后每一个新系数山语句q.EnQueue(s+t)产牛:并插入队列。s和t分别表示新系数左肩上和右肩上的系数。新系数插入队列后，t值赋给s,出队一个数据赋给t,再进行下一个系数的计算，如此循环。

2、在上下行的换行处插入一个0,以产生边上的lo计算工作由二重循坏实现，外循环for(inti=l;i<=n;i++)控制产生n行系数。内循坏for(intj=I;jv=i+2;j++)控制按行输出系数。每行系数的个数与行序号存在对应关系，如i表示行号,则第i行系数个数为i+2。【算法实现—程序3.2】#include#include#includetemplateclassQueue{〃循环队列的类定义public:Queue(int=20);〜Queue(){deletef

3、]elements;}voidEnQueue(constType&item);//元素入队TypeDeQueue();〃元素出队TypeGetFront();〃取队首元素voidMakeEmpty(){front=rear=0;}〃置队列空intIsEmpty()const{returnfront==rear;}intIsFull()const{return(rear+1)%maxsize==front;}intLength()const〃求队列长度{return(rear-front+maxsize)%maxsize;}private:intrear,f

4、ront;Type*elements;intmaxsize;〃队尾和队首〃队列元素存储空间〃队列最大长度};templateQueue::Queue(intsz):front(0),rear(0),maxsize(sz){elements=newType[maxsize];assert(elements!=0);template::EnQueue(constType&item){〃丿亡素item入队assert(JIsFull());rear=(rear+1)%maxsiz

5、e;elements[rear]=item;}template::DeQueue(){//队首元素出队，若成功返冋元素值assert(!IsEmpty());front=(front+1)%maxsizc;returnelements[front];}templateTypeQucuc::GctFront(){〃取队首元索，若成功返回元索值assert(!IsEmpty());voidYangHui(intn){〃计算并打印Queueq;q.MakeEmpty()

6、;q.EnQueue(1);q.EnQueue(1);ints=0;for(inti=l;i<=n;i++){cout«endl;q.EnQueue(0);for(intj=1;jv=i+2;j++){intt=q.DeQueue();q.EnQueue(s+t);s=t;returnelements[front];n行二项展开式系数〃建立队列并初始化〃队列置空〃第一行系数入队〃s为下一个系数左肩上的数〃逐行计算，共n行〃当前输出行结束，换行〃下一行系数开始前插入一个0〃计算下一行，系数个数为i+2〃(为下一个系数右肩上的数〃s+t计算出下一个系数并入队〃

7、迭代取值，为求下一个系数做准备if(j!=i+2)cout«s«1*;〃输出一个系数}}}voidmain(){intn;n=6;YangHui(n);〃求n行二项展开式系数cout«endl;3.字符串运算和朴素的模式匹配【实验目的】理解字符串运算的原理，掌握主要算法的实现。木实验主要内容是要求编写并调试朴索的模式匹配。【问题描述】字符串模式匹配：给定任意一个长度为a的字符串A和一个长度为b的字符串B(a>b),串A为忖标(Target),串B为模式(pattern),要求在字符串A中查找(匹配)是否有与字符串B相等的子串。如果匹配成功，返回B在A屮的起

8、始位宜，否则匹配不成功,返回・1。【数据结构】按顺序表数据结构定义