数据结构 概述

数据结构-概述

1.数据结构

数据结构是数据之间的相互关系，即数据之间的组织形式。数据结构包括三方面内容：

数据的逻辑结构：数据之间的逻辑关系，比如线性表，树、图
数据的存储结构（又叫数据的物理结构）：数据元素及其逻辑关系在计算机存储中的表示形式，比如顺序存储、链式存储、索引存储、散列存储
数据的运算：对数据施加的操作，数据的运算以数据的逻辑结构为基础。比如建立、插入、删除、查找、更新、排序

注意：

1.一个逻辑结构可以有不同的存储结构，比如线性表+顺序存储=顺序表，线性表+链式存储=链表，线性表+散列存储=散列表

2.一个逻辑结构会有不同的运算集合，比如线性表+只能在一端插入，另一端删除=队列，线性表+只能在一端插入、删除=栈。

数据的逻辑结构、数据的存储结构、数据的运算三者共同定义一个数据结构。有一个发生变化都会出现全新的数据结构

数据项？数据元素？数据结构？

数据项是数据记录中的最小单位，不可再分割。比如，字段、属性

数据元素有若干数据项组成，是数据的基本单位

数据结构是数据之间的组织形式

1.1.数据的逻辑结构

线性结构

线性结构有且仅有一个开始节点和一个终端结点，每个节点最多有一个直接前趋节点和直接后继结点，如线性表、栈、队列、串
非线性结构

非线性结构的一个节点可能有多个直接前驱结点和直接后继结点，如树、图

1.2.数据的存储结构

数据的存储结构又叫数据的物理结构

顺序存储

逻辑上相邻的结点物理位置也相邻，一般采用数组来实现，主要用于存储逻辑结构是线性的数据

二叉树也可以顺序存储，二叉树顺序存储时是层序存储的，层序存储使得二叉树结点之间为线性关系
链式存储

不要求逻辑上相邻的结点物理位置也相，结点间的逻辑关系由结点上附加的引用字段表示
索引存储

用索引表来存储结点，索引表的每个索引项由关键字、地址组成
- 稠密索引
  
  每个结点都有一个索引项，索引项中的地址指示结点的存储位置
- 洗漱索引
  
  一组结点对应一个索引项，索引项中的地址指示一组结点的起始存储位置
散列存储

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

1.常用数据结构

栈
队列
链表（顺序表、散列表）
树
图

以上几种数据结构的基本操作对比如下(以Java 集合为例)：

栈	队列	链表
入栈,push	入队,add/offer/put	添加,add(=addLast)/addFirst
出栈,pop	出队,remove/poll/take	删除,remove/removeFirst/removeLast
获取栈顶元素,peek	获取对头元素,element/peek	获取,get/getFirst/getLast
判空,empty	判空,isEmpty	判空,isEmpty
清空,clear	清空,clear	清空,clear
大小,size	大小,size	大小,size