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

数据结构实验报告实验一 杨辉三角形(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,ai> | ai-1 , 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为非空队列 操作结果：用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.抽象数据类型定义定义数据类型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 GetHead 若头尾元素不相等 队头元素赋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；当i<=n-1时循环，每轮循环结束i+1； ； 输出t；用x获取Q的队头元素；t=t+x；运算结果t插入队尾；/判断语句确保首行为空，即去除杨辉三角顶角 若n>1 /输出行尾的1，完成一行的输出 用x获取并销毁Q的队头元素； 输出x； 将1插入队尾；输出换行以调整结构； 4.函数调用关系图Main函数 调用InitQueue函数 调用EnQueue函数 调用DeQueue函数 调用GetHead函数 结束四、 调试分析程序的编写及调试基本正常，开始时由于细节问题导致杨辉三角结构上出现些许问题：1. 主函数输出的杨辉三角有顶角（即首行为1），后调整循环判定条件并增加if语句消除首行使三角输出正常2. 杨辉三角结构混乱，不整齐，后通过设定输出字符数调整正常五、 用户使用说明根据提示输入所需杨辉三角级数即可示例：请输入所需的杨辉三角级数：7六、 测试结果操作及输出流程详见如下截图七、 附录源程序如下：#include <stdio.h>#include <stdlib.h> /引用的函数库typedef struct QNodeint data;struct QNode *next;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(!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.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;i<=n-1;i+) /逐个输出队列元素，并构建下一行需输出的队列DeQueue(Q,t); printf("%3d ",t); /输出Q的队头元素并销毁GetHead(Q,x);t=t+x;EnQueue(Q,t); /运算结果插入队尾if(n>1) /判断语句确保首行为空，即去除杨辉三角顶角 /输出行尾的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 ListNode数据对象：D=ai | aiCharSet，i= 1，2，n，n0数据关系：R1=< ai-1 ，ai > | 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(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的每个数据元素进行访问。ADT CirLinkedList2. 主程序流程 void main() 初始化； 输入数据； 执行功能；显示结果；3. 程序模块间调用关系 主程序 各功能模块三、 详细设计1. 抽象数据类型定义定义数据类型 LNode整形变量 num；指针变量 *next； 定义LNode类型NODE； 2. 各程序模块算法NODE *createlinklist(int n)/初始化循环链表,并返回头指针 定义指针 *head,*p,*q； 整形 i=1； 定义头指针； 赋p值i； 令i=2；当i<=n是循环，每轮循环结束i+1 动态内存分配； 若q=0 返回0； q->p->next； q->p=q； 赋p值i； 表尾指针指向表头； 返回头指针；joseph函数(NODE *p,int n,int m)/约瑟夫函数，用于输出约瑟夫环整形 i,j； NODE *q； 令i=1；当i<=n时循环，每轮循环末i+1令j=1；当j<m时循环，每轮循环末j+1p->next->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；当i<n时循环，每轮循环结束i+1head->next->head;else 令i=1；当i<s-1时循环，每轮循环结束i+1head->next->head; 调用joseph函数，输出序列；4. 函数调用关系图 main函数 调用createlinklist函数 调用joseph函数 结束 四、 调试分析 程序的编写和调试基本正常，开始编写程序时忘记考虑s=1时的情况，导致程序出现bug，经过单步跟踪调试后发现程序的错误，采用if语句对s=1的情况单独处理将问题解决。本实验采用数据抽象的与模块化程序设计方法。这对于提高我们编写算法的能力是一次很好的锻炼机会。五、 用户使用说明 根据提示输入人数n，起始点s，间隔m示例： 围绕圆桌的人数为? 7 从第几人开始? 2 数到几的人出列?3六、 测试结果 七、 附录源程序如下：#include<stdio.h>#include<stdlib.h> /引用函数库struct LNode int num; struct LNode *next; /定义链表typedef struct LNode 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;i<=n;i+) q=(struct LNode*)malloc(sizeof(struct LNode); if(q=0) return(0); p->next=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;j<m;j+) p=p->next; /计算出列者序号 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;i<n;i+) head=head->next; else for(i=1;i<s-1;i+) head=head->next;/输出约瑟夫环出列顺序 printf("出列的顺序如下:n"); joseph(head,n,m); printf("n");