1 备战NOIP2010提高组初赛复习——数据结构篇 早期的程序设计主要偏重于数值计算领域，采用的数据结构相对简单。例如FORTRAN 语言仅定义了数组（包括多维数组）和复数两种结构型数据，这两种数据类型足以应付当时多数的科学计算问题。 但是随着现代科技的发展，计算机逐渐应用于数据处理和非数值计算问题，从客观事物中抽象出的数据日益显现出多样化的特征，简单的数据类型已远远不能满足需要，各数据元素之间的复杂联系已经不是普通的数学方程式所能表达的了。在这种背景下，一种专门研究数据之间结构关系的学科—数据结构便应运而生。 数据结构专门研究各种数据的表示、数据的类型以及它们之间关系的集合，其研究范围主要包括各种数据结构的性质，即它们的逻辑结构、物理结构以及施于其上的操作。数据结构的类型种类繁多，可以从不同的角度来划分：若从数据元素的值在使用时具有不可分割的性质或者是它可以由更基本的成份组成这个角度来划分，数据结构可以分成简单类型和构造类型两大类；如果从数据所占据的内存空间在程序执行期间是否发生变化这个角度来划分，数据结构又可以分成静态结构和动态结构两大类；如果从数据结点后继关系的多少和是否具有层次性的角度划分，数据结构还可以分成线性结构和非线性结构两大类。 简单类型 整型、实型、字符型、布尔型 静态数据类型 构造类型 数组、记录、集合、字符串 文件、指针 动态数据的类型 线性结构 数组、栈、队列、链表、串 非线性结构 树、图 通常高级程序设计语言都提供了各种简单类型和静态构造类型的数据结构。例如PASCAL 就提供了１２种类型的定义。这１２种类型中除了文件和指针属于动态结构的构造类型外，其余１０种均属于简单类型和静态构造类型。在上表的数据结构中，像数组、栈、串和队列等数据结构属于线性数据结构，而树和图属于非线性数据结构。线性数据结构易于表示各结点之间的联系，其存储方式相对简单；非线性数据结构往往能比较形象地反映各结点之间的层次关系。无论是线性结构或非线性结构，若采用数组方式存储，则属于静态数据类型；若采用指针类型存储，则属于动态数据类型。考虑到篇幅限制和读者大多具备pascal 语言或c 语言的基础，本书侧重讲解线性结构和非线性结构两种。 数据结构和算法有着密切的联系，简洁有效的算法很大程度上出自于对数据结构的正确选取。奥林匹克信息学竞赛的试题大都属于非数值计算问题，从问题中抽象出的数据多半是结构类型...
