【第1章 数据结构概述】

目录

一. 基本概念

1. 数据、数据元素、数据对象

2. 数据结构

二. 数据结构的分类

1. 数据的逻辑结构可分为两大类：a. 线性结构；b. 非线性结构

2. 数据的存储结构取决于四种基本的存储方法：顺序存储、链接存储、索引存储、散列存储

3. 数据的运算

三. 数据类型

1. 基本类型、组合类型

2. 抽象数据类型

四. 算法和算法分析

1. 算法概念

2. 算法分析

---

一. 基本概念

1. 数据、数据元素、数据对象

数据：客观事物的符号表示，对现实世界的事物采用计算机能够识别、存储和处理的形式进行描述的符号的集合。

数据元素：数据的基本单位，可以由若干数据项组成。其中数据项包括：初等项（数据不可分割的最小单位；组合项：由若干数据项组成）

数据对象：性质相同的数据元素的集合

例如：

 每一行是一个学生的相关信息，即学生个体，则是一个数据元素；

学号、姓名、性别等信息，为数据项，其中成绩为组合项，学号为初等项；

学生情况表则是一个数据对象。

2. 数据结构

一般认为包括以下三个方面：

（1）逻辑结构：数据元素与数据元素之间的逻辑关系；

（2）存储结构（物理结构）：数据元素与数据元素之间的关系在计算机中的存储表示；

（3）数据的运算：对数据的操作。

二. 数据结构的分类

1. 数据的逻辑结构可分为两大类：a. 线性结构；b. 非线性结构

（1）线性结构

有且仅有一个开始节点和终端节点，并且所有节点最多只有一个前驱和一个后继。

例如：线性表就是典型的线性结构。

（2）非线性结构

一个节点可能有多个前驱和后继。

树：一个节点最多只有一个前驱，而可以有多个后继

图：对节点的前驱和后继的个数不作限制-------------最一般的非线性结构

2. 数据的存储结构取决于四种基本的存储方法：顺序存储、链接存储、索引存储、散列存储

（1）顺序存储：把逻辑上相邻的节点存储在物理位置相邻的存储单元里，节点之间的逻辑关系用存储单元的邻接关系来体现。

注意：

• 顺序存储主要用于线性结构，但是非线性结构也可以通过线性化的方法实现顺序存储
• 通常顺序存储用程序语言的数组描述

（2）链接存储：对逻辑上相邻的节点不要求在存储的物理位置上也相邻，节点之间的逻辑关系由附加的指针表示。

注意：

• 链接存储常用于非线性结构，但线性结构也可以链接存储
• 通常链接存储用程序语言的指针描述

（3）索引存储：在存储节点数据的同时，还建立附加的索引表。索引表的每一项称为索引项。一般索引项由关键字（唯一标识该节点的数据项）和地址（节点的存储地址）组成。

（4）散列存储：根据节点的关键字计算出该节点的存储地址，然后按存储地址存放该关键字对应的数据元素。

 注意：

• 同一种逻辑结构采用不同的存储方法，可得到不同的存储结构
• 通常将同一逻辑结构的不同存储结构用不同的名称标识，如：

1. 线性表的顺序存储称为顺序表；
2. 线性表的链接存储称为链表；
3. 线性表的散列存储称为散列表。

3. 数据的运算

同一种逻辑结构，采用同一种存储方式，如果定义的运算不同，也用不同的名称标识。如：

• 栈：线性表插入、删除操作限制在表的一端；

1. 若该线性表为顺序存储，则称为顺序栈；
2. 若该线性表链式存储，则称为链式栈。

• 队列：线性表的插入限制在表的一端，删除限制在表的另一端

1. 若该线性表为顺序存储，则称为顺序队列；
2. 若该线性表为链式存储，则称为链式队列。

综述：数据的逻辑结构 + 数据的存储结构 + 数据的运算 = 数据结构

三. 数据类型

1. 基本类型、组合类型

高级程序语言中，数据类型分为两种：

（1）基本数据类型：其取值范围，允许的操作，由系统预先规定；

（2）组合类型：由基本类型组合构造.

2. 抽象数据类型

Abstract Data Type，ADT，指抽象数据的组织和与之相关的操作，即将数据和操作封装在一起，使得用于程序只能通过在ATD里定义的某些操作来访问其中的数据，从而实现信息隐蔽。

四. 算法和算法分析

1. 算法概念

定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算系列。

算法的五大特性：

（1）输入：一个算法必须有一个或多个输入（通过输入，使得任务开始，从而算法启动有了意义），这里不同于程序的特性；

（2）输出：一个算法应该有一个或多个输出；

（3）确定性：无歧义，每一种情况，需执行的动作要严格、清晰规定；

（4）有穷性：有限个步骤结束；

（5）可行性：可通过基本操作执行完成。

2. 算法分析

一个好的算法应满足下述要求：

（1）正确性；

（2）可读性；

（3）健壮性：输入非法数据，能做出反应或处理，输出错误信息并终止执行；

（4）时间效率和存储占用量：时间开销往往和空间开销相互制约，需折中处理。

撇开与计算机软硬件相关的因素，可以认为一个特定算法“运行工作量”的大小只依赖于问题的规模，或者问题规模的函数。一般将求解问题的输入量作为问题的规模，用n表示。

时间复杂度T(n) = f(n)，其中f(n)是算法所求解问题规模n的函数，当n趋于无穷大时，时间复杂度T(n)的数量级（阶）称为算法的渐进时间复杂度。即T(n) = O(f(n)).

有时，算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始化状态有关。

常见的时间复杂度，按数量级递增排列，有O(1) <<O(log2n)<<O(n)<<O(nlog2n)<<O(n^2)<<O(n^3)...<<O(n^k)<<O(2^n)

空间复杂度指所需存储空间的耗费，记为S(n) = O(f(n))，其中n为问题规模，f(n)为算法所处理的数据所需的存储空间与算法操作所需辅助空间之和。