绝代码农 发表于 2021-7-5 22:49:06

数据结构基础1——概念

1、数据结构研究内容

    这是一门研究==非数值计算程序设计中的操作对象==,及这些对象之间的==关系==和==操作==的学科。
  ==程序设计的实质==:为所处理的问题选择一种好的数据结构,并在此结构的基础上施加一种好的算法。
2、基本概念
(1)数据



  一切能输入计算机并被计算机程序处理的符号的总称。
(2)数据元素

  组成数据的基本单位,在计算机中通常被当作一个整体进行考虑和处理。
(3)数据项

  组成数据的,局有独立含义的,不可分割的最小单位。
(4)数据对象

    性质相同的数据元素的集合。
  是数据的子集。
3、数据结构

    互相之间存在一种或多种特性关系的数据元素的集合。
  结构指的是数据元素之间的关系
(1)逻辑结构

    从逻辑关系上描述数据,与数据的存储无关,独立于计算机
    两要素:数据元素,关系
  集合结构:
      数据元素之间除了“同属于一个集合”之外,再无其他关系。
  线性结构:
      数据元素之间存在一对一的关系。例如,数组、字符串、线性表、栈、队列等
  树形结构:
      数据元素之间存在一对多的关系。例如,二叉树(两个分支),树(多个分支)
  图形结构或网状结构
    数据元素之间存在多对多的关系。例如,有向图、无向图
(2)存储结构

    数据对象在计算机中的存储表示,也被称为物理结构。
    将数据存入计算机时,通常要求既要存储数据元素,又要存储数据元素之间的关系。
  顺序存储:
      将数据元素存入一片连续的存储空间中,借助数据元素在存储器中的相对位置表示数据元素之间的逻辑关系,通常借助程序设计语言中的数组描述
  链式存储
    链式存储无需占用连续的存储空间,为了表示元素之间的关系,需要给每个元素附加一个节点,保存下一个元素的地址,通常借助指针来描述
4、数据类型

    是高级程序设计语言中的一个基本概念,是一个值集以及定义在这个值集上的一组操作的总称
  体现了程序设计语言的数据描述和处理能力
5、抽象数据类型(abstract data type,缩写为:ADT)

    是由用户定义的、表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称
    包括:数据对象,数据关系,对数据对象的基本操作
    定义格式如下:
ADT 抽象数据类型名{
    数据对象:(数据对象的定义)
    数据关系:(数据关系的定义)

    基本操作名1(参数列表)
      初始条件:条件描述
      操作结果:结果描述
    基本操作名2(参数列表)
      初始条件:条件描述
      操作结果:结果描述
    ...
}ADT 抽象数据类型名    基本操作有两种参数
      赋值参数:只为操作提供输入
      引用参数:以&符号打头,除了提供输入外,还将返回操作结果
    初始条件:描述了操作之前数据结构和参数列表应满足的条件,若为空,则省略。
    操作结果:描述了操作正常结束之后,数据结构的变化状况和应返回的结果
//复数的抽象数据的定义
ADT Complex{
    数据对象:D = {e1, e2 | e1, e2∈R,R是实数集};
    数据关系:S = {<e1, e2> | e1是复数的实部, e2是复数的虚部}

    基本操作:
    Create(&C, x, y)
      操作结果:构造复数C,实部与虚部的值分别为x和y
    GetReal(C)
      初始条件:复数C已存在
      操作结果:返回复数C实部的值
    GetImag(C)
      初始条件:复数C已存在
      操作结果:返回复数C虚部的值
    Add(C1, C2)
      初始条件:C1,C2是复数
      操作结果:返回C1、C2的和
    Sub(C1, C2)
      初始条件:C1,C2是复数
      操作结果:返回C1、C2的差
    Delete(C)
      初始条件:复数C已存在
      操作结果:删除复数C
}ADT Complex

//复数的抽象数据类型的实现
typedef struct
{
    float real;
    float imag;
}Complex;

void Creat(Complex ** C, float x, float y)
{
    *C = malloc(sizeof(Complex));
    *C->real = x;
    *C->imag = y;
}

float GetReal(Complex C)
{
    return C.real;
}

float GetImag(Complex C)
{
    return C.imag;
}

Complex Add(Complex C1, Complex C2)
{
    Complex sum;
    sum.real = C1.real + C2.real;
    sum.imag = C1.imag + C2.imag;
    return sum;
}

Complex Sub(Complex C1, Complex C2)
{
    Complex dif;
    dif.real = C1.real - C2.real;
    dif.imag = C1.imag - C2.imag;
    return dif;
}

viod Delete(Complex * C)
{
    free(C);
}
页: [1]
查看完整版本: 数据结构基础1——概念