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

数据Data

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

  • 信息的载体
  • 对客观事物符号化的表示
  • 能够被计算机识别、存储和加工

• 数据可以分为两类

  • 数值型的数据整数、实数等。
  • 非数值型的数据文字、图像、图形、声音等。

数据元素Data element

• 组成数据的基本单位在计算机程序中通常作为一个整体来进行考虑和处理。
• 也简称为元素或称为记录、结点或顶点后面要学到的树的结点、图的顶点指的都是数据元素。
• 一个数据元素可由若干个数据项组成。

比如说这样一个学生表假设某个同学转学了那么是对那个同学的那一行进行整体的删除这样一个学生的相关信息就是作为整个数据的某一个整体来操作 每一行学生信息就是组成数据的数据元素

`数据项Data Item

• 构成数据元素的不可分割的最小单位。
  • 例如学生基本信息中的学号、姓名、性别等都是数据项。

• 数据、数据元素、数据项的关系
  • 数据 > 数据元素 > 数据项
  • 数据是由数据元素组成的数据元素是由数据项组成的。
    • 例学生表 > 个人信息 > 学号、姓名…

数据对象Data Object

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

  • 整数数据对象的集合是 N = {0±1±2…}
  • 字母字符数据对象是集合 C = {‘A’,‘B’…‘Z’}
  • 学籍表也能看成一个数据对象由若干条学生记录构成的子集。

数据元素与数据对象

• 数据元素组成数据的基本单位
  • 与数据的关系是集合的个体。
• 数据对象性质相同的数据元素的集合
  • 与数据的关系集合的子集

2. 数据结构

数据结构

• 数据元素之间不是孤立存在的他们之间存在着某种关系数据元素相互之间的关系称为结构比如线性、非线性。
• 是指相互之间存在一种或多种特定关系的数据元素的集合。
• 或者说数据结构是带结构的数据元素的集合。

数据结构包括

1. 逻辑结构数据元素之间的逻辑关系也称为逻辑结构。
2. 物理结构存储结构数据元素及其关系在计算机内存中的表示也称为映像称为数据的物理结构或数据的存储结构。
3. 数据的运算和实现即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

逻辑结构

• 描述数据元素之间的逻辑关系。
• 和数据的存储无关独立于计算机。
• 是从具体的问题抽象出来的数学模型。

物理结构存储结构

• 数据元素及其关系在计算机存储器中的结构存储方式。
• 是数据结构在计算机中的表示。

逻辑结构与存储结构的关系

• 存储结构时逻辑关系的映像和元素本身的映像。
• 逻辑结构是数据结构的抽象存储结构是数据结构的实现。
• 两者综合起来建立了数据元素之间的结构关系。

逻辑结构的种类

划分方法1 线性和非线性

1. 线性结构

   • 有且仅有一个开始和一个终端结点并且所有结点都最多只有一个直接前趋和一个直接后继。
   • 如线性表、栈、队列、串
     • 每个结点成员最多前后各有一个成员

   

2. 非线性结构

   • 一个结点可能有多个直接前趋和直接后继。
   • 如树结构一对多、图结构多对多。
   • 每个结点成员都可能连接着多个其他结点成员。

划分方法2 四类基本逻辑结构

1. 集合结构结构中的数据元素之间除了同属于一个集合的关系之外没有其他任何的关系。

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

3. 树形结构结构中的数据元素之前存在着一对多的层次关系

4. 图状结构或网状结构结构中的数据元素之间存在着多对多的任意关系。

存储结构的种类

顺序存储结构

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

• C语言中用数据来实现顺序存储结构。

  • 例如要存这样一组字符串就用字符串数组元素的顺序是什么样的就怎么忘内存中存。

链式存储结构

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

• C语言中用指针来实现链式存储结构。

• 存储着每个元素本身的同时还存储着下一个元素的地址。

  • 像有根链条连起来一样在存储元素本身的同时还存着下一个元素的地址不管你存在哪里等用到你的时候都可以用前一个元素存着的下个元素的地址找到下一个元素。

索引存储结构

• 在存储结点信息的同时还建立附加的索引表。
  • 存储真正的信息的同时还建立了个索引表目录方便查找。
• 索引表中的每一项称为一个索引项。
• 索引项的一般形式是==关键字、地址。
• 关键字是能唯一标识一个结点的那些数据项。
• 若每个结点在索引表中都有一个索引项则该索引表称之为==稠密索引Dense Index。
  • 若一组结点在索引表中只对应一个索引项则该索引表称之为稀疏索引Sparse Index。

散列存储结构

• 根据结点的关键字直接计算出该结点的存储地址。
  • 详细内容在后面的散列表的查找中有介绍。

3. 数据类型和抽象数据类型

数据类型

• 在使用高级程序设计语言编写程序时必须对程序中出现的每个变量、常量或表达式明确说明他们所属的数据类型。
  • 例如在 C 语言中
    • 提供 intcharfloatdouble 等基本数据类型。
    • 数组、结构体、共用体、枚举 等构造数据类型。
    • 还有 指针、空(void)类型。
    • 用户也可以使用 typedef 自定义数据类型。
• 一些最基本的数据结构可以用数据类型来实现如数组、字符串等
• 而另一些常用的数据结构如栈、队列、树、图等不能直接用数据类型来表示。
• 高级语言中的数据类型明显的或隐含的规定了在程序执行期间变量和表达的所有可能的取值范围以及在这写数值范围撒花姑娘所允许进行的操作。
  • 例如C语言中定义变量 i 为 int 类型就表示 i 是 [-mid,max] 范围的整数在这个整数集合上只可以进行 +、-、*、/、% 等操作。

数据类型的作用

• 约束变量或常量的取值范围。
• 约束变量或常量的操作。

数据类型Data Type

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

抽象数据类型

• 抽象就是抽取出实际问题的本质。在计算机中使用二进制来表示数据在汇编语言中则可能给出各种数据的十进制表示他们是二进制数据的抽象。
• 在高级语言中则给出更高一级的数据抽象出现了数据类型如整型、实型、字符型等可以进一步利用这些类型构造出线性表、栈、队列、树、图等复杂的抽象数据类型。

抽象数据类型Abstract Data Type,ADT

• 是指一个数学模型以及定义在此数学模型上的一组操作。
  • 由用户定义从问题抽象出数学模型逻辑结构。
  • 还包括定义在数据模型上的一组抽象运算相关操作。
  • 不考虑计算机内的具体存储结构与运算的具体实现算法。

抽象数据类型的形式定义

• 抽象数据类型可用DSP三元组 表示。
  • D 是数据对象
  • S 是 D 上的关系集
  • P 是对 D 上的基本操作集。

一个抽象数据类型的定义格式如下

• 其中数据对象、数据关系的定义用伪代码描述。
• 基本操作的定义格式为
  • 基本操作名参数表
  • 初始条件<初始条件描述>
  • 操作结果<操作结果描述>。

基本操作定义格式说明

• 参数表
  • 赋值参数只为操作提供输入值。
  • 引用参数以 & 打头除了可提供输入值以外还将返回操作结果。
• 初始条件
  • 描述操作执行之前数据结构和参数应满足的条件
  • 若不满足则操作失败并返回相应出错信息。若初始条件为空则省略之。
• 操作结果
  • 说明操作正常完成之后数据结构的变化状况和应该返回的结果。

定义举例Circle 的定义

#include <stdio.h>
#include <math.h>
void Circle(int* C,int r,int x,int y)//数据对象
{
        C[0]= r;
        C[1]= x;
        C[2]= y;
}
double Area(int* C)
{
        return 3.14 * pow(C[0],2);
}
double Circumference(int* C)
{
        return 2 * 3.14 * C[0];
}
int main()
{
        int C[3]= {0},r,x,y;
        int i;
        printf("请输圆的半径及xy的坐标");
        scanf ("%d %d %d",&r,&x,&y);

        Circle(C,r,x,y);
        printf("圆的面积是%lf\n",Area(C));
        printf("圆的周长是%lf\n",Circumference(C));
        return 0;
}

请输圆的半径及xy的坐标 3 3 3
圆的面积是28.260000
圆的周长是18.840000

概念小结