数据结构的作业.docVIP

作业2：Josephus问题 基本问题：设n个人，围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。 注：m,n,s可由玩家自定。若不设定,其缺省为n = 9, s = 1, m = 5。各位同学可以访问下一节的“信息共享-实验评测”，登录系统后做1012题Joseph。 变形问题1：设n个人，围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后反转方向，从出局的下一个人重新开始报数，数到第m个人，再让他出局，再反转方向……，如此反复直到所有的人全部出局为止。 变形问题2：设有k个好人在前k个坏人在后共计n=2k个人，围坐在一个圆桌周围，现在从第1个人开始报数，数到第m个人，让他出局；从出局的下一个人重新开始报数，数到第m个人，再让他出局……，如此反复直到所有坏人都出局而所有好人都存活下来为止。接受用户输入的任何一个k，编程输出合适的m。(这个编程可在“实验评测”1012题中测试实现) 实验2、单链表一元多项式运算 目的：掌握链式存储的单链表的一个典型应用。 问题描述：用单向链表保存一元多项式，实现它的创建、显示以及算术加法操作。 步骤： 1.定义一元多项式的ADT和基本操作。 2.采用链式存储结构保存多项式并实现创建、显示。 3.实现多项式加法操作。 设备和环境：PC计算机、Windows操作系统、C/C++开发环境 结论：能够定义一元多项式，掌握有序单链表的复杂合并。 实验3、线性表的顺序存储和链式存储实现 目的： 1.掌握线性表的不同存储结构下的实现。 2.练习编写实验报告1。 问题描述：完成线性表的顺序存储和链式存储方式的实现。实现线性表ADT中列出的基本操作。采用有/无头结点两种不同的方式逐一实现。 步骤： 1.定义线性表的ADT和基本操作，并给出相应的C语言版本。 2.完成创建、查找、插入、删除以及遍历。 3.实现双向链表的各项基本操作，包括：创建、撤销、清除、插入、修改、删除、定位等。 4.完成实验的实验报告，报告的格式采用《数据结构题集》的模板格式。两周之后提交。 设备和环境：PC计算机、Windows操作系统、C/C++开发环境 结论：能够用不同存储结构实现线性表，可以采用有/无头节点的方法来管理，能够体会其中的差异。 思考题：1.链式考虑动态链和静态链两种方法。 实验4、表达式求值 目的： 1.掌握使用栈来计算四则运算表达式的值。 2.通过这个学期的强化练习，能够较熟练地掌握一门编程语言。 问题描述：完成教材3.2的应用举例，特别是实现利用栈结构完成表达式求值。 步骤： 1.用C语言定义所需栈的ADT和基本操作。 2.实现表达式求值的算法。 3.测试自己完成的练习，包括不断改进程序的输入、输出等。 设备和环境：PC计算机、Windows操作系统、C/C++开发环境 结论：能够理解进而掌握对栈结构的定义和使用；理解基于栈结构的应用的基本特点。 思考题：1. 实现一个可编程计算器。计算器能够完成多个功能：a)、能够执行带括号的四则算术运算；b)、支持表达式包含变量，包括支持重复出现的变量；c)、使用自定义的简单函数；d)、其他你自己想到的功能。 2.迷宫求解目前可以选作。 实验5、银行排队的模拟[选做] 目的：掌握使用队列来模拟类似银行的排队处理系统。 问题描述：完成教材3.5(pp65)的银行应用模拟。 步骤： 1.用C语言定义所需队列的ADT和基本操作。 2.实现银行排队的模拟算法。 3.测试自己完成的练习，观察并理解模拟程序的各个处理。 设备和环境：PC计算机、Windows操作系统、C/C++开发环境 结论：能够理解进而掌握对队列结构的定义和使用；理解基于队列的应用的基本特点。 思考题： 1.计算杨辉三角某一行的系数的程序。 2.实现通用的输出二项式系数的算法。即：对任意整数n，n0，使用循环队列输出(a+b)n的各项系数。 实验6、字符串ADT实现 目的：掌握字符串的定义及基本操作的实现。 问题描述：用堆存储方式保存字符串，实现字符串的各种基本操作，包括赋值、替换、取子串、串连接等。 步骤： 1.用C语言定义字符串的ADT和基本操作。 2.实现赋值、替换、取子串、串连接等操作。 3.测试自己完成的练习，观察每个操作的执行效果。 设备和环境：PC计算机、Windows操作系统、C/C++开发环境 结论：能够理解并掌握字符串的定义和堆存储方式的实现方法。 思考题： 1.估算各个操作的复杂度和空间利用效率。 实验7、文件字符串查找 目的：掌握