数据结构习题与实验.docVIP

PAGE 数据结构习题与实验 -C++  浙江万里学院 内 容 简 介 数据结构是计算机专业的核心课，是重要的专业基础课。实践是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课下独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致，相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一方面提高联系实际分析解决问题的能力。正是基于以上的原因编写了这本“数据结构实验与习题”。 本资料的前期版本（用C语言描述算法，用 C/ C++描述算法）已经使用数届，现在是第三次修订，主要是使用C++面向对象技术描述算法和实现程序。 本参考书包括C++语言基础、书面作业练习题和上机实验习题三部分。 在C++语言基础知识部分，这里针对数据结构上机实验所必须的C++基本知识（结构体、类等等）做补充介绍。这部分内容非常重要，掌握的是否熟练会直接影响“数据结构“的学习。 在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。 在实验部分，包括有完整的C++语言源程序例题，介绍了一些设计数据结构题目所需的C++语言常用的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实验题。 第1部分、第2部分的习题1、习题2、习题5、习题6和第3部分的上机实验要求及规范、实验1、实验2、实验5 、实验6由杨秀金改写。第2部分的习题3、习题9和第3部分的实验3、实验9由汪沁改写。第2部分的习题4、习题7、习题8和第3部分的实验4、实验7、实验8由邓芳改写。由于时间仓足、水平有限，书中难免存在错误和不妥之处，敬请读者指正。 计算机与信息学院 杨秀金 汪沁 邓芳 2005年2月 修订 于浙江万里学院钱湖校区 目 录 第1部分 C++语言基本知识 一、C++源程序结构1 二、结构体及运用1 三、类的基本概念及运用3 四、结构体在类中的使用4 第2部分 书面作业练习题 习题1 绪论6 习题2 线性表8 习题3 栈和队列11 习题4 串13 习题5 数组15 习题6 树与二叉树17 习题7 图24 习题8 查找31 习题9 排序34 第3部分 上机实验习题 上机实验要求及规范37 实验1 复数ADT及其实现 39 实验2 线性表40 实验3 栈和队列47 实验4 串53 实验5 数组57 实验6 树与二叉树60 实验7 图64 实验8 查找68 实验9 排序71 PAGE 80 第1部分 C++基本知识 各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学发展过程中，早期数据结构教材大都采用PASCAL语言为描述工具，后来出现了采用C语言为描述工具的教材版本、至今又出现了采用C++语言为描述工具的多种教材版本。本教实验指导书是为已经学习过C++语言的学生而编写。编写实验指导书目的为了配合理论教学。程序要求在C++ Builder开发环境之下调试运行，采用面向对象方法进行设计。典型的数据结构被设计成为类（class），典型算法设计成为类的函数成员，然后在主函数中声明创建类对象，根据实际需要调用重要的算法。 由于C++的使用具有一定的难度，为了同学更好的学习数据结构自身的知识内容，减轻描述工具所带来的困难，这里针对数据结构上机实验所必须的C++基本知识（结构体、类等等）做补充介绍。 #include …. // #include …. //编译预处理 …… …… class A {……….. }; // 类成员函数定义； ……. int main() {……………. } 编译预处理等 类的相关程序编码 主函数程序代码 这部分内容详细参见本指导书的第3部分的程序实例。 二、结构体及运用 数据结构课程所研究的问题均运用到“结构体”和“类”。在C++语言中结构体和函数又是理解和掌握“类”的语法基础。定义结构体的一般格式： struct 结构体类型名 { 类型名1 变量名1； //数据子域 类型名2 变量名2；…… 类型名n 变量名n； } 其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量，声明创建一个结构体变量的方法是： 结构体类型名