数据结构习题解析第0章.docVIP

第0章 数据结构导论 0.1 数据结构学习指导 0.1.1 课程地位 《数据结构》是计算机科学与技术专业本科生的专业基础课程之一。用计算机解决任何实际问题都离不开数据表示和数据处理，而数据表示和处理的核心问题之一是数据结构及其实现——这正是数据结构课程的基本内容。从这个意义上来说，数据结构课程在知识学习和技能培养两个方面都处于关键性地位，是理论和实践要求都相当高的课程。本课程不仅为操作系统、数据库系统、编译方法、计算机网络等后续课程提供了必要的知识基础，而且也为计算机及其专业人员提供了必要的技能训练。 在对清华大学计算机系历届毕业生和部分研究生追踪调查显示，几乎所有的同学都认为《数据结构》是他们在学校里学过的最有用的课程之一，也是国内外许多软件开发机构要求考核的基本课程之一。由此可见《数据结构》这门课程的重要性。 0.1.2 课程要求 根据课程的教学大纲要求，《数据结构》主要讨论在软件开发中如何进行数据结构和算法的设计。因此，用抽象数据类型以及面向对象的方法组织、存储各种类型的数据是本课程的重点，也是学生需要掌握的重点。面向对象方法以及结构化技术都是建立高质量软件的技术，通过《数据结构》课程的学习和实践，可以加深对这些先进软件开发方法的理解和体会。因此，《数据结构》课程的任务是按照软件工程思想，介绍用面向过程和面向对象方法进行数据设计和程序设计的基本思想，在必要的课程实践中逐步熟练掌握。 通过本课程的学习，应达到知识和技能两方面的目标： 1、知识方面：从数据结构的类定义和对象的使用，以及存储表示和操作的实现两个层次，系统地学习和掌握常用的基本数据结构（包括数组、顺序表、多项式、字符串、链表、栈与队列、优先级队列、广义表、树与森林、二叉树、堆、集合、图、有哪些信誉好的足球投注网站结构、索引结构、散列结构等）及其不同的实现，了解并掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法，为后续课程的学习打好基础。 2、技能方面：系统地学习和掌握对象类的设计方法和面向对象的程序设计风格，在不同的存储结构上实现的算法的设计思想，从中体会和掌握选择结构的方法和算法设计的思考方式及技巧，提高分析问题和解决问题的能力。 0.1.3 课程学习指导 学生在初学时往往感到《数据结构》课程内容多、面授容易接受，但自学难度大，特别是在编写小程序时常常无从着手。为以有限的时间和精力学好这门课程。应当注意以下几点，有助于改善自学效果。 1、注意先修课程的知识准备 在学习本课程之初，必须注意复习在用C / C++ 程序设计语言编写小程序时的语法规则和方法。为本课程的学习打下基础 C语言与Pascal语言一样，是一种面向过程的语言。C程序结构的特点是遵循“输入-处理-输出”的模式来解决问题。C++ 保留了C的面向过程编程的成分，但由于引入了面向对象的成分，在数据组织方面很自然地实现了抽象数据类型的思想，并利用模板机制实现了软件复用。所以在复习C / C++ 语言时，要注意： (1) 函数的概念和相关问题。包括函数类型，函数特征，函数名重载，函数参数的传递。特别注意传值参数和引用参数在使用上的区别。还有函数的返回值的4种类型之间的区别。 (2) 函数中局部变量的作用域，它的创建和回收的有效范围。特别注意在函数中对局部变量的任何改变，因在退出函数过程时局部变量被释放而不能当作函数返回值返回。 (3) 类和对象的定义方式。特别注意为保证信息隐蔽，对类中的所有数据成员和成员函数将规定其存取级别：public, private和protected。放在public域中表示对于其他程序都是可用的；放在private域中表示对于其他程序是不可用的，对于其派生类也是不可用的；放在protected域中表示对于其他程序是不可用的，对于其派生类是可用的。 (4) 在C++ 中的动态存储分配和动态存储回收方式。 (5) 类的实例对象的建立和回收方式，构造函数和析构函数的使用，对象数据成员初始化的方式等。特别注意成员函数的作用域。 (6) 在C/C++ 中的输入/输出流文件的定义和使用。特别注意文件的连接、ifstream和ofstream类，以及文件的打开与关闭、文件模式的作用。 (7) 友元类和友元函数的定义和使用。 (8) 模板类的定义和模板类的使用。 2、在学习《数据结构》时，要注意知识体系 数据结构课程中的知识本身具有良好的结构性。从总体上来说，课程的主要内容是围绕着数组、线性表、顺序表、链表、栈、队列、优先级队列、广义表、树与二叉树、图、集合与有哪些信誉好的足球投注网站结构、索引与散列结构等常用的数据结构和递归、排序等常用算法来组织的。其中有些结构是面向应用的，有些结构是面向实现的。在课文中要注意这两个层次以及它们之间的联系。 为了