下载掌阅APP，畅读海量书库
立即打开
授课视频1-1 数据结构的表示方法
根据数据结构的概念，在计算机中表示用户自定义的数据结构，实现数据结构上的操作及应用，需要描述三方面的内容： 数据对象的类型、数据对象的关系 和 对数据对象的操作 。下面介绍 常用的四种描述数据结构的方法：C语言描述、C++语言描述、Java语言描述和Python语言描述 。本书采用的数据结构描述方法是完全的面向对象语言——Java语言描述。读者可参考本节内容，很方便地将书中的算法描述转换为C语言描述、C++语言描述或Python语言描述。
C语言不是面向对象的程序设计语言，因此不具有将数据结构三方面的内容封装的功能，必须分别描述。
数据对象的类型可以是C语言提供的int、char、float、double等基本数据类型，也可以是用户自定义的数组、结构体、共用体等数据类型。为了表示方便，将数据对象的类型抽象地表示为DataType，在针对具体数据对象的数据结构实现时，可通过下面的形式指定DataType。
数据对象的关系体现了数据的逻辑结构，可以采用顺序存储表示，也可以采用链式存储表示。一般顺序存储采用数组类型表示，链式存储采用指针类型表示。
例如，顺序存放a 1 ，a 2 ，…，a n 的存储定义为
链式存放a 1 ，a 2 ，…，a n 的存储定义为
数据对象的操作在C语言中被描述为独立的函数。
C++是对C语言的改进和扩充，它以C语言为基础，包含了整个C语言，具备C语言的全部特性、属性和优点，同时，添 加了对面向对象编程的完全支持。因此，采用C++描述数据结构，可以仍采用和C语言描述一样的方式，也可以采用面向对象的方式描述。
采用面向对象的方式描述时，数据对象的类型可被描述成一个类，如
对数据对象的关系和操作的描述也是通过定义类的形式，将对数据对象关系的存储与对数据对象操作的定义封装到一个类中。数据对象的关系通过类的私有数据描述体现， 数据对象的操作被描述成类的成员函数 ，较好地 保证了数据结构的抽象和独立 。
例如，对于 顺序存储a 1 ，a 2 ，…，a n 的数据结构 ，描述如下：
对于链式存放a 1 ，a 2 ，…，a n 的数据结构 ，存放每个数据元素的结点可以 定义为结点类：
链式存放a 1 ，a 2 ，…，a n 的链表 可描述为 由上述结点类构成的链表类：
Java语言是完全的面向对象语言。与C/C++语言相比， Java语言具有以下优点：
1）给开发人员提供了更为 简洁的语法 。
2） 取消指针 虽然损失了一些编程的灵活性，但带来的却是更高的代码质量。
3） 完全的面向对象 使得开发人员从设计开始就必须采用面向对象的软件设计方法。
4）独特的运行机制使得Java语言具有天然的 可移植性 。
Java语言的这些优点使得它成为当前应用开发中使用较广泛的语言之一，采用Java语言描述数据结构会为采用Java语言编程的人员提供更实用的参考。
Java语言的数据类型分为两大类： 基本数据类型 和 引用数据类型 。其中，基本数据类型有八种，即四种整型类型、两种浮点类型、一种字符类型和一种布尔类型；没有前面在C语言、C++语言中描述数据结构时用到的结构体类型和指针类型。Java语言类似C++语言，仍然采用类定义数据对象，并将对 数据对象的关系的存储描述与数据对象的操作封装到类的定义中 ，最大的不同是使用 引用类型代替指针类型 。不用指针类型描述数据结构，使得数据结构的描述中没有了与地址相关的运算*和&，更易于对数据结构的理解。
数据对象的类型可被描述成一个类，如
对于顺序存储a 1 ，a 2 ，…，a n 的数据结构，描述如下：
对于链式存放a 1 ，a 2 ，…，a n 的数据结构，存放每个数据元素的结点可以定义为结点类：
链式存放a 1 ，a 2 ，…，a n 的链表可描述为由上述结点类构成的链表类：
本书采用类Java语言描述数据结构及操作的实现算法。
Python是一门强大而且应用广泛的动态语言， 语法自然而易于使用 ，与Java语言一样有广泛的平台支持，大量应用在Web和Internet开发、科学计算和统计、人工智能、教育、商业桌面应用等各个领域。
作为面向对象的语言，Python和Java在语法上有一定的相似性，在此特给出Python语言的描述结构以作参考。
下面是一个 典型的Python面向对象程序 。
下面是 类Data的使用方式
有以下几点需要注意：
1）Python 没有明确的数据类型 ，所以也不需要进行类型声明，变量随使用而定义。
2）Python 类变量作用域默认为public ，类属变量使用[self.变量名]定义和使用。
3）类变量的初始化方式为直接 以函数形式调用类名 。
4）类的构造函数统一 以__init__为名 。
5）类方法必须包含代表本类对象的 self关键字 。
6）Python 使用缩进区分代码结构 。
与Java语言类似，Python对于 链式存放a 1 ，a 2 ，…，a n 的数据结构 ，存放每个数据元素的结点可以 定义为结点类：
