数据结构与C++大作业题目.pdf

《数据结构与C++大作业题目.pdf》由会员分享，可在线阅读，更多相关《数据结构与C++大作业题目.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构与数据结构与 C+C+大作业题目大作业题目一、约瑟夫环问题一、约瑟夫环问题1.1.问题描述问题描述设有编号为 1，2，n的n(n0)个人围成一个圈，每个人持有一个密码m，从第 1 个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。2.2.基本要求基本要求 建立模型，确定存储结构；对任意n个人，密码为m，实现约瑟夫环问题；出圈的顺序可以依次输出，也可以用一个数组存储。3.3.设计思想设计思想首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循

2、环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。其次，建立一个不带头结点的循环链表并由头指针 first 指示。最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图 2-1 所示。二、一元多项式相加二、一元多项式相加1.1.问题描述问题描述已知A(x)=a0+a1x+a2x2+a n x n和B(x)=b0+b1x+b2x2+b mx m，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)+B(x)。2.2.基本要求基本要求 设计存储结构表示一元多项式；设计算法实现一元多项式相加；分析算法的时间复杂度和空间复杂度。3.3.设计思想设计思想一元多

3、项式求和 实质上是合并同类项的过程，其运算规则为：若两项的指数相等，则系数相加；若两项的指数不等，则将两项加在结果中。一元多项式A(x)=a0+a1x+a2x2+a n x n由n+1 个系数唯一确定，因此，可以用一个线性表(a0，a1，a2，a n)来表示，每一项的指数i隐含在其系数a i的序号里。但是，当多项式的指数很高且变化很大时，在表示多项式的线性表中就会存在很多零元素。一个较好的存储方法是只存非零元素，但是需要在存储非零元素系数的同时存储相应的指数。这样，一个一元多项式的每一个非零项可由系数和指数唯一表示。由于两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表不合适。采用

4、单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。结点结构如图 2-2 所示。其中，coef：系数域，存放非零项的系数；exp：指数域，存放非零项的指数；next：指针域，存放指向下一结点的指针。将两个一元多项式用两个单链表存储后，如何实现二者相加呢？设两个工作指针 p 和 q，分别指向两个单链表的开始结点。通过对结点 p 的指数域和结点 q 的指数域进行比较进行同类项合并，则出现下列三种情况：若 p-exp exp，则结点 p 应为结果中的一个结点；若 p-expq-exp，则结点 q 应为结果中的一个结点，将 q 插入到第一个链表中结点 p 之前；若 p-ex

5、p=q-exp，则结点 p 与结点 q 为同类项，将 q 的系数加到 p 的系数上。若相加结果不为 0，则结点 p 应为结果中的一个结点，同时删除结点 q；若相加结果为 0，则表明结果中无此项，删除结点 p 和结点q；算法用伪代码描述如下：三、三、简单个人电话号码查询系统简单个人电话号码查询系统1.1.问题描述问题描述人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。2.2.基本要求基本要求 在外存上，用文件保存电话号码信息；在内存中，设计数据结构存储电话号码信息；提供查询功能：根据姓名实现快速查询

6、；提供其他维护功能：例如插入、删除、修改等。3.3.设计思想设计思想由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据：const int max=10;struct TeleNumber string name;/姓名string phoneNumber;/固定电话号码string mobileNumber;/移动电话号码string email;/电子邮箱 Telemax;为

7、了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。四、四、职工信息管理和学生信息管理职工信息管理和学生信息管理1、设计题目一，设计题目一，使用继承的方法，编写最多能输入 10 个职工的信息表，再根据这个表产生一个基本设计要求设计要求实现如下功能：1)建立职工信息数据，包括职工编号、姓名、性别和年龄。2)根据职工信息表，建立只含有姓名和年龄的职工信息简表。3)使用继承的方法构造 2 个类，使用相应的对象数组放置 10 个职工信息。4)编写同名 display()成员函数，用来输出数组的内容。5)另外编制一个函数 printer()，用来根据实际对象输出它们的内容。设计菜单，简单界面为：1.增加职工记录2.生成信息简表3.显示原始记录4.显示简表记录5.结束程序运行选择 1-5：职工信息简表，并利用多态性实现信息的输出。2 2、设计题目二，设计题目二，请建立结构体类型使学生与教师共享该类型，然后编程实现输入学生与教师的情况，以便可以进行查询、删除、更新（修改）等处理。学生的信息有学号、姓名、性别、班级、院系等，教师的信息有代号、姓名、性别、职称、院系等。设计菜单，简单界面为：1.输入数据2.查询数据3.修改数据4.浏览数据5.删除数据6.程序结束运行请选择：16：