数据结构与算法的基本概念

整理一下数据结构和算法的基本概念：

有序数组是按关键字升序或降序排列的，可以使用二分法查找
有序数组的查找速度比无序数组快
有序数组在插入操作中由于所有靠后的数据都需要移动以腾开空间，使用速度较慢
有序数组和无序数组的删除操作都很慢，因为数据项必须向前移动来填补已删除的数据项的洞
有序数组使用于查找频繁的数据库，插入和删除较为频繁的时候，无法高效工作

无序数组插入块，查找慢
有序数组插入慢，查找快

数组创建之后大小就固定了。
数组中每一项占用一个特定的位置，这个位置可以用一个下标号直接访问
数组太大导致效率低下，太小导致空间溢出

--大O表示法
比较算法的速度

链表就可以随插入数据项而扩展大小

简单排序

冒泡排序
比较相邻的2个，然后交换顺序，然后循环

选择排序
扫描一遍，找出最小的，放在第0位，再从第1位扫描一遍，找出剩下的最小的，放在第1位

插入排序
先分小组，比较小组里的大小，在小组中进行排序

速度：
冒泡排序《选择排序《插入排序

栈
栈只允许访问最后插入的数据项。移除这个数据项之后才能访问倒数第二个插入的数据项
数组实现的栈会满
入栈和出栈是栈的两个最主要的操作
只能查看栈顶元素
栈通常很小，是临时的数据结构
栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短
栈不需要比较和移动操作
栈中最后插入的数据最先移除，后进先出

队列
第一个插入的数据最先被移除，先进先出

循环队列
队头指针指向队尾

双端队列
两端都是结尾的队列
队列的每一端都可以插入和移除数据项

优先级队列
优先级队列有一个队头和一个队尾，从队头移除数据项。
数据项按关键字的值有序，这样关键字最小的数据项（或者最大）总在队头
插入的时候按照顺序插入到合适的位置以确保队列的顺序
可以快速访问最小关键值的数据项
可以相当快的插入数据项

算术表达式
后缀表达式
操作符写在两个操作数的后面

中缀表达式
操作符写在两个操作数的中间

链表
链表中寻找一个特定元素的唯一方法就是沿着这个元素的链一直向下寻找
链表需要多少内存就用多少内存，可以扩展到所有可用的内存

单链表
对表头的插入和删除 

双端链表
对最后一个链结点的引用
保持一个对链表最后一个元素的引用
允许在表尾插入数据项

有序链表
数据按照关键值有序排列
删除常常只限于删除在链表头部的最小（或者最大）链接点

双向链表
不同于双端链表
传统链表沿链表的反向遍历困难
双向链表，允许向前遍历，也允许向后遍历整个链表
每个链结点有两个指向其他链结点的引用，而不是一个，一个往前指，一个往后指
每次插入或者删除一个链结点的时候，要处理四个链结点，而不是两个
链结点占用的空间也变大了一点
可以从表尾删除

迭代器
迭代器是随机访问链表元素的一种方法
迭代器是一个引用，它被封装在类对象中，这个引用指向相关联的链表中的链结点
迭代器方法允许使用者沿链表移动迭代器，并访问当前指向的链结点
能用迭代器遍历链表，在选定的链结点（或者所有链结点）上执行某些操作

有迭代器的链表

ADT--抽象数据类型
是一种考虑数据结构的方式，着重于它做了什么，忽略它是怎么做的
栈和队列是ADT,既可以用数组实现，又可以用链表实现

------------------
递归
是一种方法（函数）调用自己的编程技术
调用自身是为了解决更小的问题
存在某个足够简单的问题的层次，在这一层算法不需要调用自己就可以直接解答，且返回结果

三角数字
阶乘
变位字

二分查找
把数组从中间分成两半，然后看要查找的数据项在数组的哪一半，再次折半，如此下去

汉诺塔

归并排序
归并排序需要在存储器中有另外一个大小等于被排序的数据项数目的数组。
如果初始数组几乎占满整个存储器，那么归并排序将不能工作
------------------

希尔排序

快速排序
把一个数组分为两个子数组，然后递归的调用自身为每一个子数组进行快速排序来实现的

基数排序
把关键字拆分成数字位，按数字位的值对数据项进行排序
实现基数排序不需要比较操作

划分数据就是把数据分为两组，所有关键字大于特定值的数据项在一组，所有关键字小于特定值的数据项在另一组

------------------
二叉树
结合了有序数组和链表
在树中查找数据项的速度和在有序数组中查找一样快
插入和删除数据项的速度和链表一样快
二叉树的每个节点最多有两个子节点

二叉树，有两个子节点，左边节点的数值小于节点值，右边的数值大于节点值

前缀表达式