3.18数据结构

一、数据结构----->用来组织存储数据

一组用来保存一种或多种特定关系的数据的集合（组织和存储数据）

程序 = 数据结构 + 算法

MVC：软件设计架构

M：数据的管理（数据结构）

V：视图，数据的反映及人机交互

C：逻辑控制

二、数据与数据之间的关系

数据的逻辑结构：

数据元素与元素之间的关系

集合：关系平等

线性结构：元素之间一对一的关系（数组、链表）

树型结构：元素之间一对多的关系（二叉网）

图形结构：元素之间多对多的关系（网状结构）

数据的物理结构：

数据的逻辑结构在计算机内存中的存储形式

1、顺序存储：

采用一段连续的内存空间保存元素

①数据访问方便a[ i ]; // O(1)

②数据插入删除不方便

③内存预分配

④容易造成内存碎片

2、链式存储：

采用一组非连续的内存空间保存元素

①访问数据必须遍历O(n)

②插入删除效率高

③动态数据存储，不需要内存预分配

3、索引存储：

通过关键字构建索引表，通过索引表来来找到数据的存储位置

4、散列存储（哈希存储）：

将数据元素的存储位置与关键码之间建立确定对应关系从而实现查找的存储方式

 三、单向链表

有头链表：

第一个节点中并不存放有效数据

无头链表：

第一个链表节点中存储有效数据

1.头插

2.头插

3.头删 ，尾删

4.查找

5，替换 与 销毁

6.遍历

7.逆序

8.寻找链表中间的结点

9.寻找链表倒数第K个结点

10.删除指定结点

11.排序（插入排序）

约瑟夫环问题