数据结构实验报告(杨辉三角,约瑟夫环).doc

《数据结构实验报告(杨辉三角,约瑟夫环).doc》由会员分享，可在线阅读，更多相关《数据结构实验报告(杨辉三角,约瑟夫环).doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告实验一 杨辉三角形(Pascals triangle)一、 需求分析1. 输入的形式和输入值的范围本程序中，需输入的杨辉三角级数level为正整数，由键盘输入，以回车结束2. 输出的形式通过屏幕输出杨辉三角3. 程序所能达到的功能用户从键盘输入需要的杨辉三角级数，从屏幕输出杨辉三角4. 测试数据输入：5输出： 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 二、 概要设计以链队列结构实现该实验1. 抽象数据类型定义ADT Queue 数据对象：D = ai | aiElemSet , i = 1,2,n,n0 数据关系：R1= | ai-1

2、, aiD, i=2,n 约定其中ai端为队列头，an端为队列尾基本操作： InitQueue ( &Q ) 操作结果：构造一个空队列Q DestroyQueue ( &Q ) 初始条件：队列Q已存在 操作结果：队列Q被销毁，不再存在 ClearQueue ( &Q ) 初始条件：队列Q已存在 操作结果：将Q清为空队列 QueueEmpty ( Q ) 初始条件：队列Q已存在 操作结果：若Q为空队列，则返回TRUE，否则FALSE QueueLength ( Q ) 初始条件：队列Q已存在 操作结果：返回Q的元素个数，即队列长度 GetHead ( Q , &e ) 初始条件：Q为非空队列 操

3、作结果：用e返回Q的队头元素 EnQueue ( &Q , e ) 初始条件：队列Q已存在 操作结果：插入元素e为Q的新队尾元素 DeQueue ( &Q , &e ) 初始条件：Q为非空队列 操作结果：删除Q的队头元素，并用e返回其值 QueueTraverse ( Q , visit( ) ) 初始条件：Q已存在且非空 操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit( )。一旦visit( )失败，则操作失败。ADT Queue2. 主程序流程void main ( )初始化；输入数据；执行功能；显示结果；3. 各程序模块间调用关系主程序 各功能模块三、 详细设计1.抽象

4、数据类型定义定义数据类型QNode 整形数据 data; 指针变量 *next;QNode,*QueuePtr;typedef struct设定队头指针设定队尾指针LinkQueue;2.各功能模块算法(1)/构造空队列Q int InitQueue 获取数据结构类型QNode；设定头结点，头尾指针指向头结点；(2)/插入e为Q的队尾元素int EnQueue分配动态内存空间；确认分配成功；队尾元素赋值；定义队尾指针；(3)/销毁Q的队头元素并用e返回其值 int DeQueue若头尾元素相等 返回ERROR；队头元素赋p；P值赋e；销毁队头元素；(4)/用e返回Q的队头元素 int GetH

5、ead 若头尾元素不相等 队头元素赋e返回；否则 不返回；3.主函数void main()定义整形变量n , j , i , t , x , level ; 通过键盘输入杨辉三角级数level初始化队列 插入1为队列队尾元素/输出杨辉三角令n=1；当n=level+1时循环，每轮循环结束n+1插入1为队列队尾元素 令j=1；当j=level-n+1时循环，每轮循环结束j+1输出空格以调整三角结构；令i=1；当i1 /输出行尾的1，完成一行的输出 用x获取并销毁Q的队头元素； 输出x； 将1插入队尾；输出换行以调整结构； 4.函数调用关系图Main函数 调用InitQueue函数 调用EnQue

6、ue函数 调用DeQueue函数 调用GetHead函数 结束四、 调试分析程序的编写及调试基本正常，开始时由于细节问题导致杨辉三角结构上出现些许问题：1. 主函数输出的杨辉三角有顶角（即首行为1），后调整循环判定条件并增加if语句消除首行使三角输出正常2. 杨辉三角结构混乱，不整齐，后通过设定输出字符数调整正常五、 用户使用说明根据提示输入所需杨辉三角级数即可示例：请输入所需的杨辉三角级数：7六、 测试结果操作及输出流程详见如下截图七、 附录源程序如下：#include #include /引用的函数库typedef struct QNodeint data;struct QNode *ne

7、xt;QNode,*QueuePtr;typedef structQueuePtr front; /队头指针QueuePtr rear; /队尾指针LinkQueue;int InitQueue(LinkQueue &Q)/构造空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(-2);Q.front-next=NULL;return 1;int EnQueue(LinkQueue &Q,int e)/插入e为Q的队尾元素QueuePtr P=(QueuePtr)malloc(sizeof(QNode);if(!

8、P)exit(-2);P-data=e;P-next=NULL;Q.rear-next=P;Q.rear=P;return 1;int DeQueue(LinkQueue &Q,int &e)/销毁Q的队头元素并用e返回其值if(Q.front=Q.rear)return 0;QueuePtr P=Q.front-next;e=P-data;Q.front-next=P-next;if(Q.rear=P)Q.rear=Q.front;free(P);return 1;int GetHead(LinkQueue Q,int &e)/用e返回Q的对头元素if(Q.front!=Q.rear)e=Q

9、.front-next-data;return 1;else return 0;void main()int n,j,i,t,x,level; /定义变量printf(请输入所需的杨辉三角级数: n);scanf(%d,&level); /获取杨辉三角级数LinkQueue Q;InitQueue(Q); EnQueue(Q,1); /插入1为队列队尾元素printf(n所求杨辉三角如下: n);for(n=1;n=level+1;n+)EnQueue(Q,1); /插入1为队列队尾元素 for(j=1;j=level-n+1;j+)printf( );for(i=1;i1) /判断语句确保首

10、行为空，即去除杨辉三角顶角 /输出行尾的1，完成一行的输出 DeQueue(Q,x); printf(%3d ,x); EnQueue(Q,1);printf(n); 实验二 约瑟夫环（Josephus Ring）一、 需求分析1. 输入的形式和输入值的范围本程序中，需输入的系数n，s，m都是正整数，由键盘按提示依次输入，以回车结束2. 输出的形式从屏幕输出出列顺序3. 程序所能达到的功能用户由键盘输入约瑟夫环的必要数据（人数，起始序号，出列数），由屏幕输出出列顺序4. 测试数据输入：7 2 3输出：4 7 3 1 6 2 5二、 概要设计以单向循环链表实现该程序1. 抽象数据类型的定义ADT

11、 ListNode数据对象：D=ai | aiCharSet，i= 1，2，n，n0数据关系：R1= | ai D， I=2，n基本操作： InitList(&L) 操作结果：构造一个最大长度ms内容为空的有序表L。 ClearList(&L) 初始条件：线性表L已经存在。 操作结果：将L重置为空表。 EmptyList(L) 初始条件：线性表L已经存在。 操作结果：若L为空表返回TRUE，否则返回FALSE。 ListLength(L) 初始条件：线性表L已经存在。 操作结果：返回L中数据元素个数。 GetElem(L, pos, &e) 初始条件：线性表L已经存在，1iListLength

12、(L)。 操作结果：用e返回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已经存在，1iListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L) 初始条件：线性表L已经存在。 操作结果：依次对L的每个数据元素进行访问。A

13、DT CirLinkedList2. 主程序流程 void main() 初始化； 输入数据； 执行功能；显示结果；3. 程序模块间调用关系 主程序 各功能模块三、 详细设计1. 抽象数据类型定义定义数据类型 LNode整形变量 num；指针变量 *next； 定义LNode类型NODE； 2. 各程序模块算法NODE *createlinklist(int n)/初始化循环链表,并返回头指针 定义指针 *head,*p,*q； 整形 i=1； 定义头指针； 赋p值i； 令i=2；当ip-next； q-p=q； 赋p值i； 表尾指针指向表头； 返回头指针；joseph函数(NODE *p,i

14、nt n,int m)/约瑟夫函数，用于输出约瑟夫环整形 i,j； NODE *q； 令i=1；当i=n时循环，每轮循环末i+1令j=1；当jnext-p；p-next-q；q-next-p-next；输出q值；释放q；3. 主函数算法main()NODE *head; 整形 n,s,m;整形 i;由键盘获取n； 由键盘获取s； 由键盘获取m；获取头指针head；若s=1令i=1；当inext-head;else 令i=1；当inext-head; 调用joseph函数，输出序列；4. 函数调用关系图 main函数 调用createlinklist函数 调用joseph函数 结束 四、 调试分

15、析 程序的编写和调试基本正常，开始编写程序时忘记考虑s=1时的情况，导致程序出现bug，经过单步跟踪调试后发现程序的错误，采用if语句对s=1的情况单独处理将问题解决。本实验采用数据抽象的与模块化程序设计方法。这对于提高我们编写算法的能力是一次很好的锻炼机会。五、 用户使用说明 根据提示输入人数n，起始点s，间隔m示例： 围绕圆桌的人数为? 7 从第几人开始? 2 数到几的人出列?3六、 测试结果 七、 附录源程序如下：#include#include /引用函数库struct LNode int num; struct LNode *next; /定义链表typedef struct LNo

16、de NODE;NODE *createlinklist(int n)/初始化循环链表,并返回头指针 NODE *head,*p,*q; int i=1; head=p=(struct LNode*)malloc(sizeof(struct LNode); p-num=i; for(i=2;inext=q; p=q; p-num=i; p-next=head; /使链表尾指向链表头,形成循环链表return head;void joseph(NODE *p,int n,int m)/约瑟夫函数，用于输出约瑟夫环int i,j; NODE *q; for(i=1;i=n;i+) for(j=1;

17、jnext; /计算出列者序号 q=p-next; p-next=q-next; printf(%d ,q-num); free(q); p-next=NULL;void main() NODE *head; int n,s,m; int i;/确定计算系数 printf(围绕圆桌的人数为?n); scanf(%d,&n); printf(从第几人开始?n); scanf(%d,&s); printf(数到几的人出列?n); scanf(%d,&m); /确定头指针 head=createlinklist(n); if(s=1) for(i=1;inext; else for(i=1;inext;/输出约瑟夫环出列顺序 printf(出列的顺序如下:n); joseph(head,n,m); printf(n);