线性表
n 个具有相同特性的元素的有限序列， List
数据元素之间的关系是一对一的关系
实现方式
类别
栈和队列是特殊的线性表，本质上他们都可以被看作是一类基本结构线性表案例
栈
后进先出的（限制后的）线性表，Last In First Out, Stack.
新增和删除操作只能在这个线性表的表尾进行，即在线性表基础上加了限制功能上，数组或者链表可以代替栈，但它们灵活性过高，数据量大时有风险
栈顶和栈底是用来表示这个栈的两个指针
栈有顺序表示和链式表示，分别称作顺序栈和链栈
栈的案例
队列
先进先出 (限制后的) 线性表, First In First Out, Queue
新增和删除操作只能分别在队尾和队头进行
队列适合面对数据处理顺序非常敏感的问题front 和 rear 两个指针队列有两种存储方式, 即顺序队列和链式队列
队列案例
数组
数组可以看成是线性表的一种推广，它属于另外一种基本的数据结构
数组是数据结构中的最基本结构数组的索引就是对应数组空间数组的基本操作
具有增删困难、查找容易的特点，可以在任意位置增删数据，所以数组的增删操作会更为多样。
对比数组和链表数组的案例
由 n 个字符组成的一个有序整体（ n >= 0 ）
对比字符串和线性表
特殊的字符串
字符串的存储结构与线性表相同，也有顺序存储和链式存储两种
字符串的基本操作
字符串匹配算法的案例
树和二叉树
树 — Tree
二叉树 — Tree二叉树每个结点最多有两个子结点，分别称作左子结点和右子结点。二叉树中两个特殊的类型存储二叉树的两种办法
树的基本操作遍历二叉树的增删查操作很普通，时间复杂度与链表并没有太多差别
二叉查找树 — Tree, BST特性查找操作 — 利用了“二分查找”，所消耗的时间复杂度为 O(logn)。插入操作删除操作
树的案例字典树 — Tree
哈希表
哈希表 — Hash Table, 也叫作散列表。
哈希表是一种特殊的数据结构，它与数组、链表以及树等我们之前学过的数据结构相比，有很明显的区别。
核心思想
实现 “地址 = f (关键字)” 的映射关系，快速完成基于数据的数值的查找。
哈希函数的设计直接定制法
哈希函数为关键字到地址的线性函数。如，H (key) = a*key + b。 这里，a 和 b 是设置好的常数。
数字分析法
假设关键字集合中的每个关键字 key 都是由 s 位数字组成（k1,k2,…,Ks），并从中提取分布均匀的若干位组成哈希地址。
平方取中法
如果关键字的每一位都有某些数字重复出现，并且频率很高，我们就可以先求关键字的平方值，通过平方扩大差异，然后取中间几位作为最终存储地址。
折叠法
如果关键字的位数很多，可以将关键字分割为几个等长的部分，取它们的叠加和的值（舍去进位）作为哈希地址。
除留余数法
预先设置一个数 p，然后对关键字进行取余运算。即地址为 key mod p。
解决哈希冲突开放定址法
常用的探测方法是线性探测法。比如有一组关键字 {34，35，36，45}，采用的哈希函数为 key mod 11。当插入 34，35，36 时可以直接插入，地址分别为 1、2、3。而当插入 45 时，哈希地址为 45 mod 11 = 1。然而，地址 1 已经被占用，因此沿着地址 1 依次往下探测，直到探测到地址 4，发现为空，则将 45 插入其中。
链地址法
将哈希地址相同的记录存储在一张线性链表中。如果出现冲突，就在对应的位置上加上链表的数据结构。
哈希表的基本操作哈希表中的增加和删除数据操作，不涉及增删后对数据的挪移问题哈希表查找的细节过程是：对于给定的 key，通过哈希函数计算哈希地址 H (key)。
哈希表的案例实时返回用户的字符串搜索结果
———END———
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，永久会员只需109元，全站资源免费下载 点击查看详情
站 长 微 信： nanadh666
