01-高级数据表示

第17章　高级数据表示

本章介绍以下内容：

• 函数——进一步学习 malloc() ；
• 使用C表示不同类型的数据；
• 新的算法，从概念上增强开发程序的能力；
• 抽象数据类型（ADT）。

学习计算机语言和学习音乐、木工或工程学一样。首先，要学会使用工具：学习如何演奏音阶、如何使用锤子等，然后解决各种问题，如降落、滑行以及平衡物体之类。到目前为止，读者一直在本书中学习和练习各种编程技能，如创建变量、结构、函数等。然而，如果想提高到更高层次时，工具是次要的，真正的挑战是设计和创建一个项目。本章将重点介绍这个更高的层次，教会读者如何把项目看作一个整体。本章涉及的内容可能比较难，但是这些内容非常有价值，将帮助读者从编程新手成长为老手。

我们先从程序设计的关键部分，即程序表示数据的方式开始。通常，程序开发最重要的部分是找到程序中表示数据的好方法。正确地表示数据可以更容易地编写程序其余部分。到目前为止，读者应该很熟悉C的内置类型：简单变量、数组、指针、结构和联合。

然而，找出正确的数据表示不仅仅是选择一种数据类型，还要考虑必须进行哪些操作。也就是说，必须确定如何存储数据，并且为数据类型定义有效的操作。例如，C实现通常把 int 类型和指针类型都存储为整数，但是这两种类型的有效操作不相同。例如，两个整数可以相乘，但是两个指针不能相乘；可以用*运算符解引用指针，但是对整数这样做毫无意义。C语言为它的基本类型都定义了有效的操作。但是，当你要设计数据表示的方案时，你可能需要自己定义有效操作。在C语言中，可以把所需的操作设计成C函数来表示。简而言之，设计一种数据类型包括设计如何存储该数据类型和设计一系列管理该数据的函数。

本章还会介绍一些算法（algorithm），即操控数据的方法。作为一名程序员，应该掌握这些可以反复解决类似问题的处理方法。

本章将进一步研究设计数据类型的过程，这是一个把算法和数据表示相匹配的过程。期间会用到一些常见的数据形式，如队列、列表和二叉树。

本章还将介绍抽象数据类型（ADT）的概念。抽象数据类型以面向问题而不是面向语言的方式，把解决问题的方法和数据表示结合起来。设计一个ADT后，可以在不同的环境中复用。理解ADT可以为将来学习面向对象程序设计（OOP）以及C++语言做好准备。