数据结构题集(C语言版)

　　 本题集与清华大学出版社出版的《数据结构》(c语言版)一书相配套，主要内容有：习题与学习指导、实习题和部分习题的提示或答案三大部分和一个附录[“数据结构算法演示系统(类C描述语言3．1中文版)使用手册”，此软件已由清华大学出版社出版]。
　　 其中习题篇的内容和数据结构(C语言版)一书相对应，也分为l2章，每一章大致由基本内容、学习要点、算法演示内容及基础知识题和算法设计题五部分组成。实习题分成六组，每一组都有鲜明的主题，围绕1至2种数据结构，安排4至9个题，每个题都有明确的练习目的和要求，在每一组中都给出一个实习报告的范例，以供读者参考。
　　 本书内容丰富、程序设计观点新颖，在内容的详尽程度上接近课程辅导材料，不仅可作为大专院校的配套教材，也是广大工程技术人员和自学读者颇有帮助的辅助教材。
　　

第一篇 习题与学习指导
第0章 本篇提要与作业规范
第l章 绪论(预备知识)
第2章 线性表
第3章 栈和队列
第4章 串
第5章 数组与广义表
第6章 树和二叉树
第7章 图
第8章 动态存储管理
第9章 查找
第10章 内部排序
第11章 外部排序
第12章 文件
第二篇 实习题
一、概述
二、实习步骤
三、实习报告规范
实习0 抽象数据类型
实习1 线性表及其应用

　　 数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。数据结构不仅是计算机专业的核心课程，而且已成为其他理工科专业的热门选修课。课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，其重要程度决不亚于知识传授。因此，在数据结构的整个教学过程中，完成习题作业和上机实习是两个至关重要的环节。为了帮助读者学好这门课程，我们编写了这本具有学习指导功能的题集。
　　 目前，出版的数据结构系列教材有C和Pascal两种描述语言的版本。这本题集与《数据结构》(C语言版)(清华大学出版社，1997年出版)配套，习题和实习都是按相同的内容顺序编排的，很多习题涉及教科书上的内容或算法，因此读者手边最好能有这本教科书，以便随时查阅。
　　 习题的作用在于帮助学生深入理解教材内容，巩固基本概念，达到培养良好程序设计能力和习惯的目的。从认知的程度划分，数据结构的习题通常可分为三类：基础知识题、算法设计题和综合实习题。基础知识题主要是检查对概念知识的记忆和理解，一般可作为学生自测题。算法设计题的目的是练习对原理方法的简单应用，多数要求在某种数据存储结构上实现某一操作，是数据结构的基础训练，构成了课外作业的主体。综合实习题则训练知识的综合应用和软件开发能力，主要是针对具体应用问题，选择、设计和实现抽象数据类型(ADT)的可重用模块，并以此为基础开发满足问题要求的小型应用软件，应将其看作软件工程的综合性基础训练的重要一环，并给予足够的重视。
　　 本书第一篇含有全部四百多个习题，组织成12章，分别对应教科书中各章内容，并在每章之前给出该章的内容提要和学习要求。这些习题是作者在多年教学过程中所积累资料的基础上，参考大量国外教材之后精心设计而成的。书中对特别推荐的题目作了标记，并对每道习题的难易程度按五级划分法给出了难度系数，仅供参考。
　　 第二篇分别以抽象数据类型、线性表、栈和队列、串、数组和广义表、树和图以及查找和排序为核心，设置了7组上机实习题，每组有3至9个题目供读者自由选择。希望这些实习题能对习题起到良好的补充作用，使读者受到涉及“从问题到程序”的应用软件设计的完整过程的综合训练，培养合作能力，成为将来进行软件开发和研究工作的“实践演习”。
　　 第三篇安排了部分习题的提示或解答。对于多数有唯一确定解的题给出了答案，而对算法题则有选择地作了示范解答或提示。但是，算法的解答都不是唯一的，我们的解答也不一定是臻于完美的。希望我们的答案和提示能起到抛砖引玉的作用，愿读者开发出更多更好的解法。热忱欢迎读者将这些好的算法寄给我们，在此预先表示感谢。然而，我们仍想特别强调的是，本题集主要是为配合高等院校的教学而编写的，因此，为了培养学生独立思考和解决问题的能力，我们诚恳希望不再出版或编印本题集的更详尽的解答，以免于扰学校正常的教学和本书的训练意图，敬请谅解。
　　 数据结构是实践性很强的课程，光是“听”和“读”是绝对不够的。在努力提高课堂教学的同时，必须大力加强对作业实践环节的要求和管理。国内外先进院校一般都要求修读数据结构的学生每周应不少于4个作业机时，而且有一套严格的作业、实习规范和成绩评定标准，形成行之有效的教学质量保证体系。本题集强调规范化在算法设计基本训练中的重要地位。在习题篇中给出了算法书写规范，在实习题篇中给出了实习步骤和实习报告的规范。教学经验表明，严格实施这些貌似繁琐的规范，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将能起到显著的促进作用。
　　 数据结构及其算法的教学难点在于它们的抽象性和动态性。虽然在书本教材和课堂授课(板书或投影胶片)中采用图示可以在一定程度上化抽象为直观，但很难有效展现数据结构的瞬间动态特性和算法的作用过程。“数据结构的算法动态模拟辅助教学软件DS—DEMO”是为学习并掌握数据结构中各类典型算法而开发的一个辅助教学软件，可对教科书中80多个典型算法进行动态交互式跟踪演示，在算法执行过程中实现数据结构和算法的动态同步可视化，使读者获得单从教材文字说明中无法获得的直观知识。软件既可用于课堂讲解演示，又能供个人课外反复观察、体会和理解，对提高教学质量和效率有显著效果。为便于读者参考，在习题篇的每一章列举了与该章相关的算法清单，并在附录中提供该软件完整的使用说明。
　　 1987年出版的旧版题集一直发行至今，曾在计算机和其他理工专业的数据结构教学中得到广泛使用，反映良好。这本C语言版题集在力求反映程序设计和软件工程新思想方面作了一些探索，如：算法演示软件、模块化抽象和信息隐蔽、软件工程方法训练等。对于书中存在的谬误和有争议之处，作者诚恳地欢迎广大读者提出批评意见和建议，在此谨向热情的读者致以衷心的感谢。
　　 严蔚敏 清华大学计算机技术与科学系
　　 吴伟民 广东工业大学计算机科学与工程一系
　　 1998年7月