数据结构与算法绪论
一. 数据结构相关概念
- 1.数据：
用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。 - 2.数据元素：
数据的基本单位，通常作为一个整体进行考虑和处理 - 3.数据项：
是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成 - 4.数据对象：
性质相同的元素的集合叫做数据对象
二.逻辑结构
- 1.概念：数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构
- 2.线性结构：线性结构中数据元素之间是一对一的关系（线性表、数组、队列、双队列、栈、串）
- 3.非线性结构：
树：树形结构中的数据元素之间存在一对多的层次关系
图：数据元素是多对多的关系
多维数组： - 4.集合：集合结构中的数据元素除了同属于一个集合外，它们之间没有其它关系 集合：集合结构中的数据元素除了同属于一个集合外，它们之间没有其它关系
三.物理结构
数据结构在计算机中的表示(又称映像，也称物理结构)，存储结构主要分为顺序存储（线性表）、链式存储（链式表）、索引存储和散列(哈希)存储。
- 1.顺序存储结构:借助数据元素之间的相对位置来表示元素之间的逻辑结构.（vector动态数组、 deque双端队列、stack栈容器、queue队列容器）
- 2.链式存储结构:借助数据元素之间的元素的指针表示数组元素的逻辑结构.
- 3.散列存储结构:顺序存储+算列.（哈希表）
- 4.索引存储结构:顺序存储+索引.
四.数据运算
- 1.插入
- 2.修改
- 3.删除
- 4.查找
静态查找：对查找表只作查找操作的查找表
动态查找：查找过程中同时插入表中不含的元素，或者 删除查找表中已有的元素的操作的查找表
顺序查找：顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既 适用于顺序表，也适用于链表。
二分法（折半）查找：是一种效率较高的查找方法，但前提是表中元素必须 按关键字有序（按关键字递增或递减）排列。
分块查找：块内无序、块间有序、如何分块 效率最高
动态查找表：二叉排序树查找。
哈希表：哈希函数构造：直接定址法、除留余数法、平方取中法，随机数法，数字分析法。
五.排序
1.直接插入排序：
- 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
2.希尔排序：
- 基本思想：先将整个待排序记录序列分成为若干个子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时在对全体序列进行一次直接插入排序，子序列的构成不是简单的逐段分割，而是将像个某个增量的记录组成一个子序列。
3.冒泡排序：
- 也称冒泡法，每相邻两个记录关键字比大小,大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每交换一次，记录减少一个反序数。
4.快速排序：
- 在当前无序区R【1…H】中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R【1…I-1】和R【I+1…】，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R【1…I-1】≤X.Key≤R【I+1…H】(1≤I≤H)，当R【1…I-1】和R【I+1…H】均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
5.简单选择排序：
- 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
6.堆排序：
- 堆排序是一树形选择排序，在排序过程中，将R[1…N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
7.二路归并排序
8.基数排序
各排序算法比较：
六.算法
1.特性
-
有穷性：
算法的执行步骤、时间、都是有限的。不会无休止的一直执行下去。 -
确切性：
算法的每一步都必须有明确的定义和描述。 -
输入：
一个算法应该有相应的输入条件，就像我们小时候做的应用题，已知什么什么。来求某个结果，已知部分便是输入条件。 -
输出：
算法必须有明确的结果输出。没有结果，那这个算法是没有任何意义的。 -
可行性：
算法的步骤必须是可行的，无法执行的则没有意义，也解决不了任何问题
2.算法的分类
-按照算法的应用来分：
算法可以分为基本算法、几何算法、加密/解密算法、查找算法、图标数据分析算法等。
- 按照算法的思路来分：
算法可以分为递推算法、递归算法、穷举算法、分治算法、概率算法等。
3.重点介绍算法基本思路
- 穷举算法思想：
- 根据题目的部分条件确定范围，并在次范围内对所有情况逐一穷尽验证，直到找到那个最符合的解。如循环遍历找解。
- 递推算法思想：
- 递推算法是一种理性思维模式的代表，根据已有的数据和关系，逐步推导而得到结果，通常是根据前面的一些项得到后面的一些项。如斐波那契数列。
- 递归算法思想：
- 1.直接递归 ，在方法中调用自身。
- 2.间接递归，间接的调用一个方法。比如方法a调用方法b，方法b又调用方法a。
- 递归方法在编写时，要注意使用if语句来在某些情况下强制退出递归返回结果。否则，会形成死循环。无法结束，当然也无法得到实际问题的解
使用递归，可以是代码更简洁清晰，可读性更好。如八皇后问题、汉诺塔问题，阶乘计算。 - 分治算法思想:
- 基本思想是将一个计算复杂的问题分为规模较小，计算简单的小问题求解，然后综合各个小问题，从而得到最终答案。例如我们常说的合并排序、二分法查找、堆排序、快速排序等。
- 概率算法思想:
- 概率算法依照概率统计的思路来求解问题，其往往不能得到问题的精确解，但是在数值计算领域得到了广泛的应用。因为很多数学问题，往往需要通过数值计算来求解近似值。数值概率算法;
蒙特卡罗(Monte Carlo)算法;拉斯维加斯(Las Vegas)算法;舍伍德(Sherwood)算法;