《数据结构》实验题目实验一、约瑟夫生死者游戏（链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
）实验目的：熟练掌握单循环链表操作的基本算法实现。实现功能：以单循环链表为存储结构，实现约瑟夫生死者游戏的要求。约瑟夫游戏大意为：每30个游客同乘一条船，因为严重超载，加上风高浪大，危险万分。因此船长告诉乘客，只有将全船一半的旅客投入大海，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30人围成一圈，由第一人数起，一次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再把他扔入大海中，如此循环进行，直到剩下15个乘客为止。问那些位置是将被扔下大海的位置，哪些位置是生者的位置。实验机时：8设计要求：以单循环链表为存储结构。为了不失一般性，将30改为一个任意输入的正整数n，而报上限（原为9）也为一个任选的正整数k。这样算法描述如下：（1）创建含有n个结点的单循环链表（建立单循环链表函数）（2）生者与死者的选择（生者与死者的选择函数）P指向链表第一个结点，初始i为1；while(i<=n/2)//删除一半的结点{从p指向的结点沿链表前k-1步;删除第k个结点（q所指向的结点）;p指向q的下一个结点;输出其位置q->data;i自增1;}（3）输出所有生者的位置（输出所有生者函数）（4）输出所有被扔下大海的位置（输出所有死者函数）实验二、串模式匹配算法（串）实验目的：熟练掌握串模式匹配算法。实现功能：从主串中第K个字符起，求出子串在主串中首次出现的位置，即模式匹配或串匹配。要求用三种模式匹配算法分别实现：朴素的模式匹配算法（BF算法）KMP改进算法(Next[])KMP改进算法(NextVal[])实验机时：6设计要求：首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出5个菜单项的内容和输入提示：1．输入主串、子串和匹配起始位置2．朴素的模式匹配算法3．KMP改进算法(Next[])4．KMP改进算法(NextVal[])0．退出管理系统请选择0—4：菜单设计要求：使用数字0—4来选择菜单项，其它输入则不起作用。实验三、求二叉树上结点的路径（二叉树）实验目的：熟练掌握二叉树应用的基本算法实现。实现功能：在采用链式存储结构存储的二叉树上，以bt指向根结点，p指向任一给定的结点，编程实现求出从根结点bt到给定结点p之间的路径。实验机时：6设计思路：数据结构：typedefstructnode{chardata;//数据域structnode*lchild,*rchild;//左右孩子指针}BinTNode;//树中结点类型typedefBinTNode*BinTree;主要实现函数：二叉树的建立求指定结点路径二叉树的前、中、后序非递归遍历算法查找函数主控函数及运行环境设置
浙公网安备 33021202002483