1.数据结构的研究内容

研究数据的特性和数据之间的关系

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

1.具体问题抽象成数学模型

实质:

分析问题--->提取操作对象--->找出操作对象之间的关系(数据结构)--->用数学语言描述

操作对象+对象之间的关系

2.设计算法

3.编程,调试,运行

早期计算机主要用于计算数值计算(数据对象关系简单,但计算复杂)

例:

求解梁架结构的应力(线性方程组)

预报人口增长的情况(微分方程)

当今

计算more often 的用于非数值计算

例1,

学生表

操作对象:每位学生的信息(学号,姓名,性别等)

操作算法:增删改查

关系:线性关系

数据结构:线性表/线性数据结构

例2:

人机对弈问题

操作对象:各种器具状态,即描述棋盘的格局信息

算法:走棋,即选择一种策略使棋局状态发生变化

关系:非线性关系,树

数据结构:树形结构

例3:

地图最短路径问题

操作对象:各个地点

算法:方向选择

关系,非线性关系,图

数据结构:图形结构

综上

以上都是一些非数值计算问题

描述非数值计算问题的数学模型不是数学方程,而是表,树,图之类的具有逻辑关系的数据

数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及他们之间的关系和操作的学科额

数据结构的基本概念和基本术语

数据

是能输入计算机且能被计算机处理的各种符号的集合

(信息的载体

对客观事物符号化的表示

能够被计算机识别存储和加工

)

包括

数值型的数据:整数,实数

非数值型的数据:文字,图像,声音等

数据元素:

数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理

元素/记录/结点/顶点/(如棋盘的格局)

数据项

构成数据元素的不可分割的最小单位

数据>数据元素>数据项

例

学生表>个人记录>学号/姓名

数据对象

是性质相同的数据元素的集合,是数据的一个子集.

例如

整数数据对象 集合N={0,(-/+)1,(-/+)2,(-/+)3...}

字母字符数据对象是集合C={A,B,C...Z}

学生表也可以看做一个数据对象

数据元素与数据对象

数据元素是数据的基本单位 是集合的个体

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

数据结构

数据元素不是孤立存在的,他们之间存在着某种关系,数据元素相互之间的关系称之为结构

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

也可以说,数据结构是带结构的数据元素的集合

包括三个内容

1.数据元素之间的逻辑关系,也成为逻辑结构

2.数据元素及其关系在计算机内存中的表示(又称为映像),称为数据的物理结构或数据的存储结构

3.数据的运算和实现,即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现

逻辑结构

描述数据元素之间的逻辑关系

与数据的存储无关,独立于计算机

是从具体问题抽象出来的数学模型

存储结构

数据元素及其关系在计算机存储器中的结构(存储方式)

是数据结构在计算机中的表示

逻辑结构与数据结构之间的关系

存储脚骨是逻辑关系的映像与元素元素本身的映像

逻辑结构是数据结构的抽象,存储结构是数据结构的实现

两种综合起来建立了数据元素之间的结构关系

逻辑结构分类

线性结构

有且仅有一个开始和一个终端结点,每个结点只有一个直接前趋和直接后继

例:线性表,栈,队列,串

非线性结构

一个节点可能有多个直接前趋和直接后继

例如:树,图

第二种分类

集合机构: 同属一个集合

线性结构 一对一

树形结构 一对多

图状结构/网状结构 多对多

存储结构

顺序存储结构

用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系由元素的存储位置来表示

c语言中用数组来实现顺序存储结构

例: int numbers[5] = {1, 2, 3, 4, 5};

链式存储结构

用一组任意的存储单元存储数据元素,数据之间的逻辑关系用指针来表示

c语言中用指针来实现链式存储结构

链表

索引存储结构

在存储结点信息的同时,还建立附加的索引表

散列存储结构

根据结点的关键字直接结算出该结点的存储地址

数据类型和抽象数据类型

在使用高级程序设计语言编写程序时,必须对程序中出现的每个变量,常量或表达式,明确说明他们所属的数据类型

例如:

c语言中,int char,float, double 等基本数据类型

数组,结构,共用体,枚举等构造数据类型

还有指针,空(void)类型

用户也可以typedef自己定义数据类型

一些最基本数据结构可以用数据类型来实现,如数组,字符串等

而另一些常用的数据结构,如栈,队列,树,图等,不能直接用数据类型来表示

高级语言中的数据类型明显地或隐含地规定了在程序执行期间变量和表达的所有可能的取值范围,以及在这些数值范围上所允许进行的操作

c语言中定义i 为int类型,就表示i的范围是整数, 这个整数可以进行+-*\%等操作

数据类型的作用

约束变量或常量的取值范围

约束变量或常量的操作 

数据类型

定义:数据类型是一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称

数据类型=值的集合+值集合上的一组操作

抽象数据类型

是指一个数学模型以及定义在此数学模型上的一组操作

由用户定义,从问题抽象出数据模型(逻辑结构)

还包括定义在数据模型上的一组抽象运算(相关操作)

不考虑计算机内具体的存储结构,与运算的具体实现算法

抽象数据类型的形式定义

抽象数据类型可用(D,S,P)三元组表示

其中D是数据对象,S是D上的关系集,P是对D的基本操作

定义格式

ADT 抽象数据类型名{

        数据对象:<数据对象的定义>

        数据关系:<数据关系的定义>

        基本操作:<基本操作的定义>

} ADT 抽象数据类型名

基本操作定义格式

基本操作名(参数表)

初始条件:<初始条件描述>

操作结果:<操作结构描述>

参数表

赋值操作:只为操作提供输入值.

引用参数 以& 打头,除可提供输入值外,还讲返回操作结构

scak(&G,n)

初始条件 

描述操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息.若初始条件为空,则省略

操作结果

说明操作完成之后,数据结构的变化状况和应返回的结果

ADT 抽象数据类型名