栈与队列的应用—回文-广东药学院.DOC

数据结构实验指导书 广东药学院 软件工程教研室 内 容 简 介 数据结构是计算机及相关专业的核心课，是重要的专业基础课。实验是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课后独立完成数据结构的实验。实际上在读者群中程序设计的基础并不一致，相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一方面提高联系实际分析解决问题和编程的能力。正是基于以上的原因才编写了这本“数据结构实验指导书”。 本指导书以大类知识点做为章节，每个章节下面有若干实验，教师可以根据学生的实际情况安排具体的实验。 目录 第一章 C语言相关知识复习实验 1 1.1 C语言结构体与指针 1 第二章 线性表实验 2 2.1有序顺序表 2 2.2顺序表的建立与查找 3 2.3有序单链表 6 2.4单链表的基本操作 7 第三章 栈和队列实验 12 3.1栈的应用—括号匹配 12 3.2栈的应用--数制转换 14 3.3 队列的基本操作 17 3.4队列的应用—打印杨辉三角形 18 3.5栈与队列的应用—回文 19 第四章 数组实验 27 4.1??? 动态数组的实现 27 第五章 串实验 28 5.1 串的匹配与替换 28 第六章 递归实验 29 6.1折半查找递归算法 29 6.2递归算法的实现 30 第七章 二叉树实验 31 7.1二叉树的遍历应用 31 7.2二叉树层序遍历的实现 35 7.3哈夫曼编码的程序设计 36 第八章 图实验 38 8.1图的广度优先遍历的实现 38 第九章 排序实验 39 9.1插入排序算法的实现 39 9.2排序算法综合测试 40 第十章 查找实验 41 10.1动态查找表实验 41 第一章 C语言相关知识复习实验 1.1 C语言结构体与指针 一、实验目的 巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。 二、实验内容 1.学生信息的显示，具体要求如下： 1）定义一个结构体描述学生信息(学号,姓名,性别,年龄,住址)； 2）设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型； 3）设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于5人）。 提示：可用结构体数组保存学生信息。 ?2. 输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置，逆置要求用指针和动态内存分配方法实现。如?输入：10? ?2? ?30? ?4? ?5，逆置后显示为：5?? 4?? 30???2?? 10。 ?提示： 1.逆置的方法：设有n个数据元素a(0),a(1),a(2)…….,a(n-1)，将第i个元素与第n-i-1个元素调换位置即可。 2.采用动态内存分配方法可参考如下代码 ???int *a;????????? int i;????????? a=(int *)malloc(N*sizeof(int));//动态分配起始地址????????? for(i=0;iN;i++)???????????? { scanf(%d,a[i]);}?//给内存空间赋值 三、实验源代码 此处写程序源代码，请在程序中适当注释，便于老师更快地看懂你的程序。 四、实验结果 此处写出程序运行的结果，即输入数据是什么，输出数据是什么，分析结果是否正确，如果不正确是什么原因。 第二章 线性表实验 2.1有序顺序表 一、实验目的 1、掌握建立顺序表的基本方法。 2、掌握顺序表的插入、删除算法的思想和实现 二、实验内容仿照教材中的顺序表示例，设计一个有序顺序表，有序顺序表的数据类型定义如下： 逻辑结构：有序线性表 存储结构：顺序 操作集合：初始化、插入、删除,具体说明如下: (1)ListInitiate(L)? 初始化线性表，生成一个空表 (2)ListInsert(L,x)? 在有序表L中插入数据元素x,使得新表仍然有序 (3)ListDelete(L,i,x) 删除有序表L中的第i个数据元素，并用参数x返回。 并通过主函数验证所设计的有序顺序表的正确性。 ?三、实验源代码 ? ? 四、实验结果 2.2顺序表的建立与查找 一、实验目的 1、掌握建立顺序表的基本方法。 2、理解和掌握顺序表元素查找算法。 3、掌握顺序表的插入、删除算法的思想和实现。 二、实验内容 1、 建立一个顺序表，要求从键盘输