数据结构实验手册.pdf

数据结构上机实验手册 西安电子科技大学软件学院 数据结构课程组 2013 年3 月 实验目录 数据结构上机实验手册 1 实验0 数组、指针和结构体 3 题目一 数据集合的表示及运算 3 题目二 约瑟夫问题 3 题目三 复数运算 4 实验一 链表的实现及运算 4 题目一 单链表基本运算 4 题目二 单链表上的排序运算 5 题目三 约瑟夫问题 6 题目四 一元多项式相加、减运算器 6 实验二 栈和队列的实现与应用 7 题目一 数制转换 7 题目二 括号匹配问题 7 题目三 停车场管理 8 题目四 迷宫问题 9 实验三 字符串运算 10 题目一 字符串运算 10 题目二 文学研究助手 11 实验四 二叉树的运算与应用 11 题目一 二叉树的遍历运算 11 题目二 哈夫曼编/译码器 12 实验五 查找方法 14 题目一 顺序查找、折半查找 14 题目二 二叉排序树的建立、查找、插入和删除运算 14 题目三 哈希表的设计和应用 14 附录A 实验报告模板 15 附录B 实验报告示例 16 2 实验0 数组、指针和结构体 题目一 数据集合的表示及运算 【问题描述】 构造一个非递减数列，然后在该数列中新加入一个数，并保持该数列非递减有序的特性。 【基本要求】 用一维数组存储数列。 【实现提示】 1. 为简单起见，设数组元素为整型，用静态数组（即固定大小的数组）存储数列，定义如下： #define ARRAYSIZE 10000 //先定义一个足够大的数组，并存入少量数据测试程序的处理逻辑是否正确 int data[ARRAYSIZE] = {10,20,30,40,50}; int n = 5; // 数列的长度用n 表示，程序中应保证n 不大于ARRAYSIZE 2. 新加入的数从键盘输入，该数有以下几种可能性，在运行程序时都要进行测试： （1）比数列中最小的数还要小； （2 ）比数列中最大的数还要大； （3 ）其他情况 3. 调用随机函数产生数列及要加入的新数，这就不能保证数列的非递减性质了，因此需要在程 序中增加一个专门用来排序的函数； 4*. 用动态数组，即用动态内存申请函数申请内存块（作为数组的存储空间），借助指针访问数 组元素，数组大小自行设定，例如： #define DSIZE 100 int n = 5; //数列的长度用n 表示，程序中应保证n 不大于DSIZE int *ptr; ptr = (int *)malloc(DSIZE * sizeof(int)); //calloc 也可以用来申请内存块 //与malloc 不同的是，calloc 函数会将申请到的内存区域初始化为0 //用法示例：ptr = (int *)calloc(DSIZE, sizeof(int)); if (!ptr) // 申请失败，程序中止 exit(0); for(i = 0; in; i++) *(ptr+i) = rand(); //调用随机函数产生数据 【测试数据】 自行设定。 题目二 约瑟夫问题 【问题描述】