数据结构实习报告模版

《数据结构实习报告模版》由会员分享，可在线阅读，更多相关《数据结构实习报告模版（10页珍藏版）》请在金锄头文库上搜索。

1、数据结构 上机实习报告 实验题目： 约瑟夫环问题求解 班级： 姓名： 学号： 指导老师： 完成日期： 一、 需求分析 1、 问题描述 已知 n 个人（编号分别为 1， 2， .， n）按顺时针方向围坐一圈，每人持有一个正整数密码。 开始时任选一个报数上限值 m，从编号为 1 的人按顺时针方向自 1 开始报数，报到m 时停止报数，报 m 的那个人出列；将他的密码作为新的 m 值，从他在顺时针方向的下一个人开始重新从 1 报数，数到 m 的那个人又出列；依此规律重复下去，直到所有人全部出列。输入 n， m 两个正整数以及 n 个正整数为密码，设计程序来求 出列的编号序列。 2、 功能需求 用户准备

2、好输入文件， 其中包含程序中需要的输入数据。 程序在计算机终端上显示运算结果。 程序执行的命令包括： 1） 构造约瑟夫环； 2）分析并判断输入数据的合法性 3）约瑟夫环报数和出列的模拟与出列编号序列的输出； 4）结束。 3、 输入及输出格式 1、 输入数据 数据从文件输入，输入文件的格式如下： 文件 “JRInput.txt”第一行的正整数代表人数 n， 第二行的正整数代表密码的初始值 m，从第三行开始有 n 对正整数分别代表 n 个人的编码和密码。 2、 输出数据 （结果输出到屏幕，输出结果通常只有一行，含 n 个整数，表示 n 个人的出列顺序。 3、 输入输出样例 输入文件 JRInput

3、.txt 内容如下： 7 20 1 3 2 1 3 7 4 2 5 4 6 8 7 4 屏幕输出： 出列序号是： 6 1 4 7 2 3 5 二、 概要设计 1、 数据特性分析 a） n 代表总人数， m 是初始密码 b） 数据元素： ai=(ni， mi)，其 中 i=1,2,n (n1)， ni、 mi代表第 i 个人的编号和持有的密码 ，其中 ni不能省略 c） 数据元素间的关系：对 ai(1in-1)存在后继次序关系 ； an的直接后继是 a12、 操作特性分析 a） 建空约瑟夫环 b） 通过循环在约瑟夫环的尾部插入新的数据元素，从而建立约瑟夫环 c） 在约瑟夫环中从某结点开始遍历若干

4、步 d） 删除约瑟夫环中某结点的下一个结点 3、 问题的抽象数据类型分析 约瑟夫环的数据元素是由编号和密码值组成的二元组。约瑟夫环的逻辑结构是线性表。求解约瑟夫环问题可以分为两个步骤： 1. 构造约瑟夫环； 2. 约瑟夫环循环报数、出列。 在第一个步骤，由于构造约瑟夫环是通过在表尾循环插入元素结点，因此约瑟夫环的逻辑操作有： 1. 初始化约瑟夫环； 2. 在约瑟夫环表尾插入； 3. 循环报数出列。 通过以上分析，确定约瑟夫环抽象数据类型定义如下： ADT JesephRing 数据元素： ai=(ni， mi)， i=1,2,n (n1)， ni， mi代表第 i 个人的编号和持有的密码 ，其

5、中 ni不能省略。 结构：线性结构，对数据元素 ai(1in-1)存在次序关系 , an的直继是 a1。 逻辑操作：设 J 为 JesephRing 型 JesephRingInitiate(J); /构造一个空的约瑟夫环 J。 JesephRingInsertEnd(J, x); /在约瑟夫环 J 尾部插入新元素 x ，成功返回 1，失败返回 0。 JesephRing(J,m); /*给定初始报数上限 m，从 1 开始循环报数、删除、输出直至 J 为空，得到出列序列。 */ 4、 存储结构设计 1、存储结构的确定 数据结构的目的是有效组织和处理数据。为了有效组织和处理数据，先要分析约瑟夫环

6、逻辑操作的特点和指针所占空间比例，然后确定最优的存储结构。 a) 确定采用顺序存储结构还是采用链式存储结构 1. 约瑟夫环在构造时频繁执行插入操作，在出列阶段频繁执行删除操作。 2. 如果采用链表，指针存储开销和整个结点内容所占空间相比，其比例较小 综上所述，认为不采用顺序表，而采用链表。 b) 选择哪种链式存储结构？ 1. 约瑟夫环在构造时都是在尾部插入，因此增设尾指针，尾指针始终指向链表的尾部结点。 通过增设尾指针，在表尾插入的算法时间复杂度为 O（ 1） 。 2. an的直继是 a1，因此采用循环单链表。 综上所述，采用带尾指针的循环单链表存储结构。 2、设计带尾指针的循环单链表 a)

7、结构描述 b) 逻辑操作 设带尾指针的循环单链表类型名为 ListCWithRear， L 是 ListCWithRear 型。通过分析约瑟夫环的抽象数据类型，进一步确定带尾指针的循环单链表的逻辑操作如下所示： 1. LinListCWithRear(L)/初始化 2. InsertEnd(L, x)/ 判断是否是空表。如果表为空，返回 0，否则返回 1。 3. DeleteAfter(L,p)/在表尾插入新结点 x。插入成功返回 1，失败返回 0。 4. IsEmpty(L)/删除 p 结点的下一个结点，删除成功返回 1，失败返回 0。 5. LinListCWithRear(L)/ 撤销

8、三、 详细设计 1、 数据元素类型定义 typedef struct int number;/编号 int cipher;/密码 DataType; 2、 带尾指针的循环单链表实现 通过单链表数据结构实现带尾指针的循环单链表。 a) 带尾指针的循环单链表类型定义 1、 template class ListNode 略 注：需要定义 LinListCWithRear为 ListNode类的友元 2、 template class LinListCWithRear private: ListNode * head; /头指针 ListNode * rear; /尾指针 int m; /初始密码

9、public: LinListCWithRear(void); LinListCWithRear(void); int IsEmpty(void); void InsertEnd(const T& x); T DeleteAfter(ListNode *p); void JesephRing(void); ; /*带尾指针的循环单链表类的定义 b) template void LinListCWithRear : LinListCWithRear (int m0=1 ) /初始化带尾指针的循环单链表 head= new ListNode; head-next=head;/循环结构 rear=h

10、ead;/尾指针处理 m=m0; 时间复杂度为 O（ 1）。 c) template int LinListCWithRear : IsEmpty(void) if(head-next=head) return 1; else return 0; 时间复杂度为 O（ 1）。 d) template void LinListCWithRear : InsertEnd (const T& x) /*在带尾指针循环单链表的表尾结点后插入一个新元素 x。 */ ListNode *q=new ListNode(x); /*新结点 */ q-next=rear-next; /*插入 */ rear-ne

11、xt=q; rear=q; /尾指针处理 时间复杂度为 O（ 1）。 e) template void LinListCWithRear : DeleteAfter(ListNode *p) /*删除并释放带尾指针的循环单链表 L 中 p 结点的下一个结点 */ ListNode *s; T t; s=p-next; p-next=p-next-next;/删除 p 结点的下一个结点 if(s-next=head) rear=p;/尾指针处理 t=s-data; delete s; return t; 时间复杂度为 O（ 1）。 f) template LinListCWithRear:Lin

12、ListCWithRear(void) /析构函数，释放单链表所有结点（包括头结点） ListNode *p, *q; /*q 指向被删结点，缓冲指针 p 指向 q 结点的直接后继结点 */ p = head-next; /p 指向头结点 while(p != head) /循环释放结点空间直至没有结点 q = p; p = p-next; delete q; delete p; head= NULL; /头指针值为 NULL rear=NULL; m=1; g) JesephRing(J,m)基本算法 1、根据初始报数上限 m 值，寻找第 m 个结点（应该找到第 m-1 个结点的地址才便于删

13、除，因此为便于删除，定义 curr 指针找第 m 个结点， pre 指针始终指向 curr结点的直接前驱结点） 。 2、输出第 m 结点的 number 值； 3、把该结点的 cipher 值赋给 m，作为下一次循环的报数上限 m； 4、删除第 m 个结点； 如此循环 n 次或直至表为空时结束。 （实际只需循环 n-1 次， 最后只剩一个结点时，直接输出即可）。 时间复杂度为 O（0=niim ），其 中 n 为人数， mi是第 i 个人的密码值（ ni0 ）。 3、 主函数基本算法 1、 从文件 JRInput.txt 文件读入数据到 n， m 以及动态结构体一维数组 test 中。 2、

14、检查 n， m 以及 test 中各元素的合法性，如果非法则输出提示并退出。 3、 定义带尾指针的循环单链表对象 JR(m)。 4、 循环调用 JR.InsertEnd(x)函数构造约瑟夫环。 5、 调用 JR.JesephRing()函数约瑟夫环循环出列和输出。 4、 函数的调用关系图反映程序层次结构 main() 1、从文件 JRInput.txt读入数据。 2、检查各数据的合法性。 3、构造约瑟夫环。 4、约瑟夫环循环出列和输出。 LinListCWithRear类 LinListCWithRear (L); IsEmpty(L); InsertEnd(L, x); DeleteAfte

15、r(L,p); LinListCWithRear (L); 四、 调试分析 1、 在 VC 里点！按钮运行程序没问题，可以看到一个窗口显示运行结果。但是运行 Debug文件夹里的 exe 文件却不显示运行结果。 解决方法：在程序末尾加上 getchar();或者加上 system(pause);（前面要加上头文件#include）。 2、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行判断和检查，调试的时候经常会出错，比如 n 和 mi的输入值为字母、 0、大于 32767 的数（出现溢出）。 解决方法：在从文件读入 n 和 m 的值后，增加代码检查 n 和 mi值的合法性。如果值非法，则在窗口中输出提示并退出程序。 3、程序写完后发现所有基本操作的结果均