数据结构
（课 程 设 计）实 验 报 告
学 院 ___ ___
专 业 _
班级/学号 ___________ _______
学生姓名 ______ ____________
成 绩 _______ ________ ___
设 计 地 点 _ _
设计起始时间 ___ __
指 导 教 师 _____ ___ _____ ___
课程实践目的：
综合运用数据结构课程所讨论的基础知识和基本理论，解决具有一定规模的、中等难度的实际应用问题，培养综合应用设计能力。
课程实践内容：
栈
基于链式存储结构实现栈的基本操作
a) 创建一个空栈
b) 清空栈
c) 入栈操作
d) 出栈操作
e) 打印栈中的所有元素（即从栈顶到栈底依次在屏幕输出栈中元素）
利用上述操作完成下面的算法：
f) 数值转换程序，可以实现十进制向任意进制数的转换。
g) 计算算术表达式的值
（2）队列
以顺序存储结构实现队列，请实现队列的以下操作：
a) 队列初始化
b) 判断队列状态
c) 入队
d) 出队
e) 打印队列中的所有元素（即从队头到队尾依次在屏幕输出栈中元素）
利用上述算法完成下面的各操作，并在每一操作后输出队列状态。
f) 5个元素逐一入队，入队后输出队列状态：5个元素
g) 3个元素出队 状态：２个元素
h) 再２个元素出队 状态：队空
(3) 采用基于稀疏矩阵的三元组压缩存储方法，实现m×n矩阵的快速转置，该算法的时间复杂度为O(n+t)（t位非零元素个数）
(4) 实现二叉链表存储的二叉树的基本操作和简单应用。
a） 根据先序遍历创建一棵二叉树
b） 以凹入方式打印输出一棵二叉树
c） 二叉树判空
d） 计算二叉树中叶子结点的数目
e） 求二叉树的高度
f） 求二叉树的结点数
g） 实现二叉树的中序遍历，输出按中序遍历的结点序列。（要求用非递归算法，将右子树根结点入栈）
h） 在二叉树中查找元素值为k的结点
提示：
1）用先序递归过程建立二叉树 (存储结构：二叉链表)
输入数据按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入‘*’号，如输入123**4**5**得到的二叉树为：
EMBED Visio.Drawing.11
创建 EMBED Visio.Drawing.11 时，输入 1 2 3 * * * 5 4 * * 6 * *
2）按凹入表方式输出该二叉树，并用l表示左孩子，r表示右孩子。
1
l2
l3
r4
r5
(5)排序与查找
随机产生50个0—100之间的整数，允许有重复
分别利用直接插入排序、直接选择排序、快速排序对这50个数进行排序（递增递减均可），并统计在各种排序方法中关键字的比较次数，最后输出各类排序方法的排序结果及关键字的比较次数。
用折半查找法在前面的已排好序的数据表上查找，是否有此数，如有，输出其序号。如没有，在屏幕给出提示信息。
课程实践准备及要求
（1）实践前复习相关内容，按照实践内容认真编写代码，做好实践准备。
(2) 课内调试运行完成程序。
（3）分析程序的运行结果，并书写实践报告。
实践步骤：
实践总结：
— PAGE 10 —
— PAGE 1 —
成绩评定评语：