数据结构实验(杨辉三角约瑟夫环)

1、实验一杨辉三角形(Pascalstriangle)需求分析输入的形式和输入值的范围本程序中，需输入的杨辉三角级数level为正整数，由键盘输入，以回车结束输出的形式通过屏幕输出杨辉三角程序所能达到的功能用户从键盘输入需要的杨辉三角级数，从屏幕输出杨辉三角4.测试数据输入：5输出：1112113311464115101051概要设计以链队列结构实现该实验抽象数据类型定义基本操作：ADTQueue数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=vai-1,ai|ai-1,aiD,i=2；,n约定其中ai端为队列头，an端为队列尾InitQueue(&Q)操作结果：构造一

2、个空队列QDestroyQueue(&Q)初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在ClearQueue(&Q)初始条件：队列Q已存在操作结果：将Q清为空队列QueueEmpty(Q)初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE否则FALSEQueueLength(Q)初始条件：队列Q已存在操作结果：返回Q的元素个数，即队列长度GetHead(Q,&e)初始条件：Q为非空队列操作结果：用e返回Q的队头元素EnQueue(&Q,e)初始条件：队列Q已存在操作结果：插入元素e为Q的新队尾元素DeQueue(&Q,&e)初始条件：Q为非空队列操作结果：删除Q的队头元素，并

3、用e返回其值QueueTraverse(Q,visit()初始条件：Q已存在且非空操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADTQueue主程序流程voidmain()初始化；输入数据；执行功能；显示结果；各程序模块间调用关系主程序各功能模块三、详细设计抽象数据类型定义定义数据类型QNode整形数据data;指针变量*next;QNode,*QueuePtr;typedefstruct设定队头指针设定队尾指针LinkQueue;各功能模块算法(1)/构造空队列QintInitQueue获取数据结构类型QNode；设定头结点，头尾

4、指针指向头结点；(2)/插入e为Q的队尾元素intEnQueue分配动态内存空间；确认分配成功；队尾元素赋值；定义队尾指针；/销毁Q的队头元素并用e返回其值intDeQueue若头尾元素相等返回ERRO；R队头元素赋p；P值赋e；销毁队头元素；用e返回Q的队头元素intGetHead若头尾元素不相等队头元素赋e返回；否则不返回；主函数voidmain()定义整形变量n,j,i,t,x,level;通过键盘输入杨辉三角级数level初始化队列插入1为队列队尾元素/输出杨辉三角令n=1；当n=level+1时循环，每轮循环结束n+1插入1为队列队尾元素令j=1；当j=level-n+1时循环，每轮

5、循环结束j+1输出空格以调整三角结构；令i=1；当i1/输出行尾的1，完成一行的输出用x获取并销毁Q的队头元素；输出x；将1插入队尾；输出换行以调整结构；函数调用关系图Main函数调用InitQueue函数调用EnQueue函数调用DeQueue函数调用GetHead函数结束四、调试分析程序的编写及调试基本正常，开始时由于细节问题导致杨辉三角结构上出现些许问题：主函数输出的杨辉三角有顶角（即首行为1），后调整循环判定条件并增加if语句消除首行使三角输出正常杨辉三角结构混乱，不整齐，后通过设定输出字符数调整正常五、用户使用说明根据提示输入所需杨辉三角级数即可示例：请输入所需的杨辉三角级数：7六、

6、测试结果操作及输出流程详见如下截图七、附录源程序如下：#include#include/引用的函数库typedefstructQNodeintdata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;/队头指针QueuePtrrear;/队尾指针LinkQueue;intInitQueue(LinkQueue&Q)/构造空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(-2);Q.front-next=NULL;return1;intEnQ

7、ueue(LinkQueue&Q,inte)/插入e为Q的队尾元素QueuePtrP=(QueuePtr)malloc(sizeof(QNode);if(!P)exit(-2);P-data=e;P-next=NULL;Q.rear-next=P;Q.rear=P;return1;intDeQueue(LinkQueue&Q,int&e)/销毁Q的队头元素并用e返回其值if(Q.front=Q.rear)return0;QueuePtrP=Q.front-next;e=P-data;Q.front-next=P-next;if(Q.rear=P)Q.rear=Q.front;free(P);r

8、eturn1;intGetHead(LinkQueueQ,int&e)/用e返回Q的对头元素if(Q.front!=Q.rear)e=Q.front-next-data;return1;elsereturn0;voidmain()intn,j,i,t,x,level;/定义变量printf(请输入所需的杨辉三角级数:n);scanf(%d,&level);/获取杨辉三角级数LinkQueueQ;InitQueue(Q);EnQueue(Q,1);/插入1为队列队尾元素printf(n所求杨辉三角如下:n);for(n=1;n=level+1;n+)EnQueue(Q,1);/插入1为队列队尾元

9、素for(j=1;j=level-n+1;j+)printf();for(i=1;i1)/判断语句确保首行为空，即去除杨辉三角顶角/输出行尾的1，完成一行的输出DeQueue(Q,x);printf(%3d,x);EnQueue(Q,1);printf(n);实验二约瑟夫环(JosephusRing)需求分析输入的形式和输入值的范围本程序中，需输入的系数n,s,m都是正整数，由键盘按提示依次输入，以回车结束输出的形式从屏幕输出出列顺序程序所能达到的功能用户由键盘输入约瑟夫环的必要数据(人数，起始序号，出列数)，由屏幕输出出列顺序测试数据输入：723输出：4731625概要设计以单向循环链表实现

10、该程序抽象数据类型的定义ADTListNode数据对象：D=ai|aiCharSet,i=1,2,，n,n0数据关系：R仁|aiD,1=2，n基本操作：InitList(&L)操作结果：构造一个最大长度ms内容为空的有序表L。ClearList(&L)初始条件：线性表L已经存在。操作结果：将L重置为空表。EmptyList(L)初始条件：线性表L已经存在。操作结果：若L为空表返回TRUE否则返回FALSEListLength(L)初始条件：线性表L已经存在。操作结果：返回L中数据元素个数。GetElem(L,pos,&e)初始条件：线性表L已经存在，KiListLength(L)操作结果：用e

11、返回L中第i个数据元素的值。LocateElem(L,e)初始条件：线性表L已经存在。操作结果：返回L中第1个与e相同的元素的位序。若不存在返回0。ListInsert(L,i,e)初始条件：线性表L已经存在。操作结果：在L中的第i个元素的位置之前插入新元素e,L的长度加1。ListDelete(L,pos,e)初始条件：线性表L已经存在，KiListLength(L)操作结果：删除L的第i个数据元素，并用e返回其值,L的长度减1。ListTraverse(L)初始条件：线性表L已经存在。操作结果：依次对L的每个数据元素进行访问。ADTCirLinkedList主程序流程voidmain()初

12、始化；输入数据；执行功能；显示结果；程序模块间调用关系主程序各功能模块三、详细设计抽象数据类型定义定义数据类型LNode整形变量num；指针变量*next；定义LNode类型NODE各程序模块算法NODE*createlinklist(intn)/初始化循环链表,并返回头指针定义指针*head,*p,*q；整形i=1；定义头指针；赋p值i;令i=2；当ip-next；q-p=q；赋p值i;表尾指针指向表头；返回头指针；joseph函数(NODE*p,intn,intm)/约瑟夫函数，用于输出约瑟夫环整形i,j；NODE*q；令i=1；当i=n时循环，每轮循环末i+1令j=1；当jnext-p；

13、p-next-q；q-next-p-next；输出q值；释放q；主函数算法main()NODE*head;整形n,s,m;整形i;由键盘获取n；由键盘获取s；由键盘获取m；获取头指针head；若s=1令i=1；当inext-head;else令i=1；当inext-head;调用joseph函数，输出序列；函数调用关系图main函数调用createlinklist函数调用joseph函数结束四、调试分析程序的编写和调试基本正常，开始编写程序时忘记考虑s=1时的情况，导致程序出现bug，经过单步跟踪调试后发现程序的错误，采用if语句对s=1的情况单独处理将问题解决。本实验采用数据抽象的与模块化程

14、序设计方法。这对于提高我们编写算法的能力是一次很好的锻炼机会。五、用户使用说明根据提示输入人数n起始点s，间隔m示例：围绕圆桌的人数为？7从第几人开始？2数到几的人出列？3六、测试结果FMMicfi&fr&ftVisual叭训匚VisualStudFoVCormcflXMSDevSeXBirtXDebugFfadfsd.l-lJL気绕圆桌的人数为?7.F:MiciroEO-ftVisualStudi口、Mie口gftVku曲StudijoComnnjcnMSDev9El!BinDebugffadf5d.1nl回国绕园桌的入铀加h第几幵姑r怪绕凰桌的人数为？乩第几人开嫡？豪到几的人出列？3-跟绕

15、閱桌的人敌为?*h第几人开始f数到几的人岀列？哲歹!|的瞬序如下：4731625Prtstanyktjitocgntlnu引用函数库定义链表七、附录源程序如下：#include#include/structLNodeintnum;structLNode*next;；/typedefstructLNodeNODE;NODE*createlinklist(intn)/初始化循环链表，并返回头指针NODE*head,*p,*q;inti=1;head=p=(structLNode*)malloc(sizeof(structLNode);p-num=i;for(i=2;inext=q;p=q;p-num=i;p-next=head;/使链表尾指向链表头,形成循环链表returnhead;voidjoseph(NODE*p,intn,intm)/约瑟夫函数，用于输出约瑟夫环inti,j;NODE*q;for(i=1;i=n;i+)for(j=1;jnext;/计算出列者序号q=p-next;p-next=q-next;printf(%d,q-num);free(q);p-next=NULL;voidmain()N