实验九 动态查找算法的实现
一、【实验目的】
1、掌握二叉排序树的基本概念
2、掌握二叉排序树的基本算法（查找算法、插入算法、删除算法） 2、理解并掌握二叉排序数查找的平均查找长度。
二、【实验内容】
1、已知一个个数为12的数据元素序列为{Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May, July,Jan,Mar},要求：
（1）按各数据元素的顺序（字母大小顺序）构造一棵二叉排序数，并中序打印排序结果。 （2）查找数据”Sept”是否存在。 三、【实验源代码】
四、【实验结果】
五、【实验心得】
选作实验
实验 有序顺序表
一、【实验目的】
1、掌握建立顺序表的基本方法。
2、掌握顺序表的插入、删除算法的思想和实现
二、【实验内容】仿照教材中的顺序表示例，设计一个有序顺序表（数据元素从小到有序），有序顺序表数据类型定义如下： ?逻辑结构：有序线性表 ?存储结构：顺序
?操作集合：初始化、插入、删除,具体说明如下: (1)ListInitiate(L) 初始化线性表，生成一个空表
(2)ListInsert(L,x) 在有序表L中插入数据元素x,使得新表仍然有序 (3)ListDelete(L,x) 在有序表L中删除数据元素x 并通过主函数验证所设计的有序顺序表的正确性。
提示：插入操作时，从顺序表的第一个数据元素开始，逐个比较list[i]值和x的值，当list[i]值小于等于x时，进行下一个结点的比较；否则就找到了插入结点的合适位置，向后移动元素，腾出空位，插入元素x；当比较到最后一个结点仍有list[i]值小于等于x时，则把x插入到顺序表表尾。
实验 线性表综合应用
一、【实验目的】
1、掌握线性表的两种存储结构的灵活运用。 二、【实验内容】
约瑟夫环（Josephus）问题的求解
具体描述是：设有编号为1，2，??，n的n(n>0)个人围成一个圈，从第K个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，??，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。
请根据以上描述，选择合适的存储结构，完成 约瑟夫环的求解。请打印出出圈人的序号。
提示：约瑟夫环问题主要可分解为建环、删除两个操作。可使用课上给出的头文件。
三、实验源代码
实验 栈 一、实验目的：
1．掌握堆栈的存储方式和基本操作
2．掌握堆栈后进先出运算原则在解决实际问题中的应用 3．掌握使用栈的原理来解决数制转换问题。
二、实验内容：
1.利用栈结构，编写程序将十进制数转换成二进制数或八进制数。 说明：十进制数值转换成二进制使用辗转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。十进制数值转换成八进制算法类似。转换算法要求用一个函数完成。
三、实验源代码
四、实验结果
五、实验心得
实验 队列
一、实验目的
1．掌握队列的顺序存储结构
2．掌握队列先进先出运算原则在解决实际问题中的应用 二、实验内容
仿照教材顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括：初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。 以下是队列操作函数的定义： (1)QueueInitiate(Q) 初始化队列Q (2)QueueNotEmpty(Q) 队列Q非空否
(3)QueueAppend(Q,x) 入队列，在队列Q的队尾插入数据元素x。 (4)QueueDelete(Q,d) 出队列，把队列Q的队头元素删除并由参数d带回。 提示：队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。 三、实验源代码
四、实验结果（测试数据） 五、实验心得