数据结构简述

一、什么是数据结构

  数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或者多种特定关系的数据元素的集合。
  数据结构 研究的是数据的逻辑结构、物理结构以及他们之间的相互关系,并对这种结构定义相适应的算法，设计出相应的算法，并确保经过这些运算以后所得到的新的机构仍然保持原来的机构类型。

二、数据结构基本术语

• 数据： 程序的操作对象，用于描述客观事物。特点：一个输入到计算机；可以被计算机处理。
• 数据对象： 是性质相同的数据元素的集合，是数据的子集。如数组、集合。
• 数据元素： 组成数据对象的基本单位，也叫节点或记录。如：结构体、对象。
• 数据项： 一个元素由若干数据项组成。

//声明一个结构体类型
struct person {     //一种数据结构
    char *name;     //数据项
    int gender;     //数据项
    int age;        //数据项
};

struct person p1;           //p1：数据元素
struct person pArray[10];   //pArray：数据对象

二、数据的逻辑结构

  数据的逻辑结构是指 放映数据元素之间逻辑关系的数据结构，与他们在计算机中存储的位置无关。逻辑结构包括以下四种：

• 集合：数据结构中的元素除了“属于同一个集合”的相互关系外，别无其他关系。各个数据元素之间是“平等”的。
• 线性结构：
  数据结构中的数据元素存在一对一的相互关系。
  常用的线性结构有：数组、队列、哈希表、单/双链表栈、双队列、串等。
• 树形结构
  数据结构中的数据元素存在一对多的相互关系。
  常见的树形结构有：二叉树、二叉搜索树、哈夫曼树、红黑树、AVL、堆、线段树、K-D树、并查集等。
• 图结构
  数据结构中的数据元素存在多对多的关系。
  常见的图形结构：邻接矩阵、邻接表。

三、数据的物理结构

   物理结构：又称“存储结构”，指的是数据的逻辑结构在计算机存储空间的存放形式。数据元素的存储结构形式有2种：

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

  非顺序存储 特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

  一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。