说明：本篇博文，作为个人的学习笔记使用。参考教材：[数据结构（c语言版）].严蔚敏

一、什么是数据结构

二、基本概念和术语　　

三、抽象数据类型的表示与实现

四、算法和算法分析

一、什么是数据结构

　　1) 用计算机解决实际问题

　　一般用计算机解决问题的步骤：

　　　　1.从具体问题抽象成数据模型--》2.设计解决此模型的算法--》3.最后，编程-测试-调整至得到最终答案

　　但是，有更多的问题是非数值计算型的，无法用数学方程描述：

　　　　如：图书馆自动检索系统、人机对弈问题，多×路口，交通灯管理问题。

　　简单来说，数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的关系和操作等的学科。

　　数据结构的重要性：

　　　　在计算机科学中，数据结构 不仅是一般程序设计的基础，而且是设计和实现编译程序，操作系统，数据库系统以及其他系统程序应用程序的重要基础。

二、基本概念和术语

　　数据（data）：

　　　　     可以输入到计算机中，并被计算机程序处理的符号 的 总称。

　　数据元素 （data element）：

　　　　　　数据的基本单位。在计算机中通常作为一个整体考虑和处理。有时候一个数据元素包含多个数据项，如书的书目信息为一个数据元素，书目信息中的作者、书名就是一个数据项。

　　数据对象（data object）：

　　　　　　是具有相同性质的数据元素的集合，是数据的一个子集。（列如：数据库中的一张表就是一个数据对象。整数集，字母集也是一个数据对象）

　　数据结构（data structure）：

　　　　　　是相互之间一种或多种特定关系的数据元素的集合。

　　　　　　数据元素之间的关系称为，结构。

　　根据数据元素之间关系的不同，分为以下四种结构：

　　　　　　1.集合：除同属于一个集合之外，没有任何其他关系

　　　　　　2.线性结构：数据元素之间存在着一对一的关系

　　　　　　3.树状结构：数据元素存在着一对多的关系

　　　　　　4、网状或图状结构：数据元素间存在着多对多的关系

　　数据结构的形式定义为：数据结构是一个二元组

　　　　Data_Structure=( D , S )

　　　　D是数据元素的有限集合，S是 D 上面 关系的有限集合。

　　数据的逻辑结构：

　　　　讨论数据结构的目的是，在计算中实现对它的操作，因此还需研究如何在计算机中表示它。

　　　　数据结构在计算机中的表示（又称映像）称为 物理结构 又称存储结构。它包括数据元素的表示 和 关系的表示。

　　　　　　计算机中表示信息的最小单位是 二进制数的一位，叫做 位（bit）。

　　　　　　在计算机中 ，我们可以用多个位组合起来形成的一个位串来表示一个数据元素，通常称这个位串为元素（element） 或 结点（node）。

　　　　　　当数据元素由若干个数据项组成的时候，位串中对应于各个数据项的子位串 称为：数据域。因此元素 或 结点可以看成是 数据元素在计算机中的映像。

　　　　数据元素之间的关系：

　　　　　　1.顺序映像

　　　　　　　　　　特点：借助数据元素的 在 存储器 中的相对位置来表示数据元素之间的逻辑关系。

　　　　　　2.非顺序映像

　　　　　　　　　　特点：借助元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。

　　　　数据的逻辑结构和存储结构是密切相关的来个方面，任何一个算法的设计取决于选定的数据结构（逻辑结构），而算法的实现依赖于采用的 存储结构。

　　　　数据类型：是和数据结构密切相关的一个概念，最早出现在高级程序语言中，用于刻画操作对象的特性。

　　　　　　　　　数据类型是一个值的集合和定义在这个值上集合的一组操作的总称。

　　　　抽象数据类型（ADT）:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与其在计算机中如何表示，实现没有关系，即不论其内部机构如何变化，只要其数学特性不变，都不影响其外部使用。

　　　　　　　　　　比如“整数”就是一种抽象数据类型，虽然在不同的处理器上实现方式不同，但对于用户来说都是一样的。

　　　　一个含抽象数据类型的软件模块通常包含定义、表示和实现3个部分。

　　　　抽象数据类型的定义：由一个值域和值域上的一组操作组成，按其值的特性可分为可细分为3中类型：

　　　　　　1.原子型 ：值是不可分解的，列如整数

　　　　　　2.固定聚合型 ：由确定数目的成分构成，例如复数，

　　　　　　3.可变聚合型 ：值的数目不确定，如一个有序整数序列

　　　　　　后两种类型称为结构类型。

　　　　和数据结构的形式相对应，抽象数据类型用三元组表示：

　　　　　　　　（D, S , P）

　　　　其中，D是数据对象，S是D上的关系集，P是对D的基本操作集，本书采用以下格式定义抽象数据类型

　　　　　　　　ADT 抽象数据类型名{

　　　　　　　　　　数据对象：《数据对象的定义》

　　　　　　　　　　数据关系：《数据关系的定义》

　　　　　　　　　　基本操作：《基本操作的定义》

　　　　　　　　}ADT 抽象数据类型名

　　　　　　基本操作的格式定义：

　　　　　　　　基本操作名 （参数列表）                  赋值参数只提供输入值。引用参数以&打头，可以提供输入值还可以返回操作结果。

　　　　　　　　　　初始条件：<初始条件描述>　　   描述了操作执行前 数据结构和参数应该满足的条件

　　　　　　　　　　操作结果：<操作结果描述>

三、抽象数据类型的表示与实现

　　抽象数据类型可以通过固有类型来表示和实现， 即利用处理器中已有的数据类型来说明新的结构，用已实现的操作来组合新的操作。

四、算法和算法分析

　　算法（algorithm）：

　　　　是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作，此外一个算法还具有一下5个特性：

　　　  1.有穷性  2确定性  3，可行性   4，输入    5 ，输出

　　算法设计的要求：

　　　　1.正确性   2.可读性    3.健壮性    4.效率与地存储量需求

　　算法效率的度量：

　　　　度量程序的执行时间通常有一下两种方法：

　　　　　　1.事后统计方法

　　　　　　2.事前分析估算的方法

　　　　一个算法是由控制结构和原操作组成，则算法的时间取决于两者的综合效果

　　　　用原操作执行的次数作为算法的时间度量：

　　　　　　一般情况下，算法中基本操作执行的次数是问题规模 n 的某个函数 f(n)，算法的时间度量记做：

　　　　　　　　T(n)=O( f(n) )

　　　　　　它表示岁问题规模n的不断增加，算法执行时间的增长率和 f(n) 的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度

　　　　　　一般时间复杂度用 常量阶 O(1) ,线性阶 O(n) , 平方阶 O(n 的平方) 对数阶 O(log n)，指数阶 O(2 的n次方）

　　　　　　注：有时候，算法的时间复杂度和 输入的数据有关系，如：冒泡排序。

　　算法的存储空间需求：

　　　　类似时间复杂度，此处以空间复杂度作为算法所需存储空间的度量：

　　　　　　记作：S（n）= O（f（n））

数据结构-绪论