什么是数据结构
数据结构是计算机存储、组织数据的方式，是数据之间存在着某种关联的数据元素的集合。
常见的数据结构：数组、栈、队列、链表、树、图、字典树、散列表（哈希表）
1. 数据结构种类-----
- 线性数据结构：元素之间存在着一对一的关系
- 栈、队列、数组和线性表（顺序表和链表）
- 树形结构：跟上一层的某个节点有关联，并且可以和下层多个节点有关联的数据
- 树、堆
-
图形结构：允许节点之间互相关联
-
散列表（哈希表）：是根据键（Key）而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
2. 线性数据结构-----
a. 数组和链表
数组：存放着一组相同类型的数据，需要预先指定数组的长度，不能动态地增减数据。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。
链表：链表是C语言中一种应用广泛的结构，它采用动态分配内存的形式实现，链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。链表还包含一个头指针，它指向链表的第一个元素，链表查找是根据next指针找到下一个元素
b. 数组和链表的区别
（1）数组事先定义长度，不能动态增减数据；链表动态地进行存储分配，可以适应数据动态地增减的情况
（2）数组从栈中分配空间，申请方便，查找速度快，自由度小；链表从堆中分配空间，自由度大，申请管理比较麻烦
（3）数组在内存中是连续存储的，可以利用下标索引进行随机访问；链表是链式存储结构，在访问元素的时候只能通过线性的方式由前到后顺序访问，所以访问效率比数组要低
c. 数组和链表的优缺点
（1） 优点：
数组：方便，查找速度快
链表：大小不固定，灵活扩展，插入删除速度快（改变指向的指针即可），内存利用率高。
（2） 缺点：
数组：插入删除效率低（动了需要移动其他位置），对内存要求高，需要连续内存，大小固定
链表：每次查找须从第一个指针开始遍历
d. 栈和队列
两者相似，队列是另一种顺序存储元素的线性数据结构。
栈与队列的最大差别在于栈是LIFO（后进先出），而队列是FIFO，即先进先出。
3. 哈希表-----
把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
优点：对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。结合了数组和链表的优点
iOS中 NSDictionary和NSMutableArray底层实现原理就是哈希表，原理
网友评论