数据结构教程上机实验指导

第1章绪论--上机实验题1解析1

实验题1.1求素数1

实验题1.2求一个正整数的各位数字之和2

实验题1.3求一个字符串是否为回文4

第2章线性表--上机实验题2解析6

实验题2.1实现顺序表各种基本运算的算法6

实验题2.2实现单链表各种基本运算的算法10

实验题2.3实现双链表各种基本运算的算法15

实验题2.4实现循环单链表各种基本运算的算法21

实验题2.5实现循环双链表各种基本运算的算法26

实验题2.6求集合（用有序单链表表示）的并、交和差运算33

实验题2.7求两个多项式相加运算37

第3章栈和队列--上机实验题3解析41

实验题3.1实现顺序栈各种基本运算的算法41

实验题3.2实现链栈各种基本运算的算法44

实验题3.3实现顺序队列各种基本运算的算法48

实验题3.4实现链队各种基本运算的算法52

实验题3.5求解迷宫问题的所有路径及最短路径程序56

实验题3.6病人看病模拟程序59

实验题3.7停车场管理程序62

.第4章串--上机实验题4解析69

实验题4.1实现顺序串各种基本运算的算法69

实验题4.2实现链串各种基本运算的算法74

实验题4.3顺序串的各种模式匹配运算81

实验题4.4文本串加密和解密程序85

实验题4.5求一个串中出现的第一个最长重复子串87

第5章数组和稀疏矩阵--上机实验题5解析90

实验题5.1求5×5阶螺旋方阵90

实验题5.2求一个矩阵的马鞍点92

实验题5.3求两个对称矩阵之和与乘积94

实验题5.4实现稀疏矩阵（采用三元组表示）的基本运算97

第6章递归--上机实验题6解析103

实验题6.1输出求解akm(2,1)的递推和求值过程103

实验题6.2求解n皇后问题104

实验题6.3求解背包问题107

实验题6.4采用递归和非递归方法求解f（n）110

第7章树状结构--上机实验题7解析113

实验题7.1实现二叉树各种基本运算的算法113

实验题7.2实现二叉树各种遍历算法119

实验题7.3求二叉树中从根结点到叶子结点的路径126

实验题7.4由遍历序列构造二叉树130

实验题7.5实现中序线索化二叉树134

实验题7.6构造哈夫曼树138

实验题7.7用二叉树来表示代数表达式142

第8章广义表--上机实验题8解析145

实验题8.1实现广义表的各种基本运算算法145

实验题8.2实现广义表求表头和表尾的运算149

实验题8.3实现广义表的相关运算算法（一）152

实验题8.4实现广义表的相关运算算法（二）156

第9章图--上机实验题9解析162

实验题9.1实现图的邻接矩阵和邻接表存储162

实验题9.2实现图的遍历算法166

实验题9.3求有向图的简单路径170

实验题9.4求无向图中满足约束条件的路径175

实验题9.5求无向图的深度优先生成树和广度优先生成树178

实验题9.6采用普里姆算法求最小生成树181

实验题9.7采用克鲁斯卡尔算法求最小生成树184

实验题9.8采用狄克斯特拉算法求有向带权图的最短路径187

实验题9.9采用弗洛伊德算法求有向带权图的最短路径190

第10章查找--上机实验题10解析194

实验题10.1实现顺序查找的算法194

实验题10.2实现二分查找的算法195

实验题10.3实现分块查找的算法197

实验题10.4实现二叉排序树的基本运算算法200

实验题10.5统计一个字符串中出现的字符及其次数205

实验题10.6实现二叉平衡树的相关运算算法207

实验题10.7实现b彩鞯南喙卦怂闼惴216

实验题10.8实现哈希表的相关运算算法225

第11章内排序--上机实验题11解析230

实验题11.1实现直接插入排序算法230

实验题11.2实现希尔插入排序算法232

实验题11.3实现冒泡排序算法234

实验题11.4实现快速排序算法235

实验题11.5实现直接选择排序算法237

实验题11.6实现堆排序算法239

实验题11.7实现二路归并排序算法242

实验题11.8实现基数排序算法244

实验题11.9实现可变长度的字符串序列快速排序算法247

实验题11.10实现英文单词按字典序排列的基数排序算法250

第12章外排序--上机实验题12解析254

实验题12.1实现置换惭≡袼惴254

第13章文件--上机实验题13解析260

实验题13.1实现索引文件建立和查找算法260

第14章综合实验题解析267

综合实验题14.1链表综合算法设计267

综合实验题14.2求复杂表达式的值273

综合实验题14.3用二叉树实现家谱的相关运算287

附录296

附录a使用vc++6.0系统296

附录b实验报告格式315