关于数据结构的读书笔记

之前学习的C语言，我们主要是学习和了解C语言的基本语法以及简单的使用。在数据结构中，我们要重点使用C语言来构造数据。

C语言中的结构体是用于构造引用类型。引用类型是一种抽象数据类型。我们使用抽象数据类型来描述具体的事物。

首先，何为数据：

数据是信息的载体,能被计算机识别、存储和加工处理。

数据结构就是数据之间的相互关系，即数据的组织形式。

它包括：

1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；

2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。

3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。

数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现

数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。

按照"值"不同的特性，高级程序语言中的数据类型可以分为两类：原子类型和结构类型。

原子类型是不可分解的，例如C中的基本类型（整形、字符型）、指针类型和空类型。结构类型的值是由若干成分按照某种结构组成的，因此是可分解的。它的成分是可以是结构的，也可以是非结构的。例如：数组的值由若干分量组成，每个分量可以是整数，也可以是数组。

实际上，在计算机中，数据类型的概念并非局限于高级语言中，每个处理器都提供了一组原子类型或者结构类型。例如：一个计算机硬件系统通常包含"位，字节，字"等原子类型，它们的操作是通过计算机设计的一套指令系统直接由电路系统完成，而高级程序语言提供的数据类型，其操作需要通过编译器或者解释器转化为底层，即汇编语言或者机器语言的数据类型来实现。

引用了数据类型的目的，从硬件的角度来讲，是作为解释计算机内存中信息含义的一种手段，而对于使用数据类型的用户来说，实现了信息的屏蔽，可以把一切用户不需要了解的细节都封装在类型中。例如，用户在使用整型的时候，不需要了解"整数"在计算机内部是如何表示的，也不需要知道具体的操作是如何实现的。如"两个整数求和"，程序设计者仅仅注重其"在数学上的求和"的抽象特征，而不需要关注硬件的"位"是如何操作的。

抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。

抽象数据类型和数据类型实质上是一个概念。例如，各个计算机都拥有的"整数"类型是一个抽象数据类型，尽管他们在不同处理器上实现的方法可以不同，但是由于其定义的数学特性相同，在用户看来都是相同的。因此，抽象的意义在于数据类型的数学抽象特性。

抽象数据类型的范畴更加广阔，它不再局限于当前所描述的处理器中定义和实现的数据类型，还包括了用户自己定义的数据类型。为了提高软件的复用率，近代程序设计方法中指出，一个软件系统的框架应该建立在数据之上，而不是操作之上。即在构成软件系统的每个相对独立的模块上，定义一组数据和施用于这些数据上的一组操作，并在模块内部给出这些数据的表示及操作的细节，而在模块外部使用的只是抽象的数据和抽象的操作。显然，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度越高。

关于算法：

对于算法正确性的解释：

正确一词含义在通常的用法中又很大的差别，有如下4个层次：

a程序不含语法错误；

b程序对于几组输入数据能够得出满足规格说明要求的结果；

c程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够满足规格说明要求的结果；

d程序对于一切合法的输入数据都能产生满足规格说明的结果。

显然，达到d层意义下的正确是极为困难的。对于大型软件需要进行专业的测试，

一般来说，通常达到c层意义的正确性作为衡量一个程序是否合格的标准。

一般来说，用计算机解决一个问题大致要经历下面几个步骤：

首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，后编出程序，进行测试、调整直到终解答。

寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。