数据结构与算法

一、数据结构

集合结构 线性结构 树形结构 图形结构
1.1、集合结构 说白了就是一个集合，就是一个圆圈中有很多个元素，元素与元素之间没有任何关系 这个很简单
1.2、线性结构 说白了就是一个条线上站着很多个人。 这条线不一定是直的。也可以是弯的。也可 以是值的 相当于一条线被分成了好几段的样子 （发挥你的想象力）。 线性结构是一对一的关系
1.3、树形结构 说白了 做开发的肯定或多或少的知道 xml 解析 树形结构跟他非常类似。也可以想象 成一个金字塔。树形结构是一对多的关系
1.4、图形结构这个就比较复杂了。他呢 无穷。无边 无向（没有方向）图形机构 你可以理解为多 对多 类似于我们人的交集关系

数据结构的存储

数据结构的存储一般常用的有两种 顺序存储结构 和 链式存储结构

2.1 顺序存储结构

发挥想象力啊。 举个列子。数组。1-2-3-4-5-6-7-8-9-10。这个就是一个顺序存储结构 ，存储是按顺序的 举例说明啊。 栈。做开发的都熟悉。栈是先进后出 ，后进先出的形式 对不对 ？你可以这样理解:
hello world 在栈里面从栈底到栈顶的逻辑依次为 h-e-l-l-o-w-o-r-l-d 这就是顺序存储 再比如 队列 ，队 列是先进先出的对吧，从头到尾 h-e-l-l-o-w-o-r-l-d 就是这样排对的

2.2 链式存储结构

再次发挥想象力例如 还是一个数组:
1-2-3-4-5-6-7-8-9-10 链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地 址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序 ，也就说顺序乱了，1（地址） 1 后面跟着的这个地址指向的是 2，2 后面的地址指向的是 3，3 后面的地址指向是谁你应该清楚了吧。
执行的时候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存储 的时候就是完全随机的。明白了？！

单向链表\双向链表\循环链表

3.1 单向链表

A->B->C->D->E->F->G->H. 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个 头拉着跑

单向链表

3.2 双向链表

双向链表

数组和链表区别： 数组：数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用元 素很少变化的情况 链表：链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高

3.3 循环链表

循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指 向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。发挥想象力 A->B->C->D->E->F->G->H->A. 绕成一个圈。就像蛇吃自己的这就是循环 不需要去死记硬背哪些理论 知识。

二叉树／平衡二叉树

4.1 什么是二叉树

树形结构下,两个节点以内 都称之为二叉树 不存在大于 2 的节点 分为左子树 右子树 有顺序 不能颠 倒 .

二叉树有五种表现形式

1.空的树（没有节点）可以理解为什么都没 像空气一样
2.只有根节点。 （理解一个人只有一个头 其他的什么都没，说的有点恐怖）
3.只有左子树 （一个头 一个左手 感觉越来越写不下去了）
4.只有右子树
5.左右子树都有

二、算法面试题（一）

1、不用中间变量,用两种方法交换 A 和 B 的值 算法

2、求最大公约数 最大公约数

3、模拟栈操作

栈是一种数据结构，特点：先进后出

模拟栈的操作

保护全局变量：在全局变量前加 static 后，这个全局变量就只能在本文件中使用 static int data[1024];
栈最多能保存 1024 个数据 static int count = 0;

目前已经放了多少个数(相当于栈顶位置) 模拟栈操作

4、排序算法

选择排序、冒泡排序、插入排序三种排序算法可以总结为如下： 都将数组分为已排序部分和未排序部分。

1.选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。

2.冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。

3.插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。

4.1、选择排序

【选择排序】：最值出现在起始端 第 1 趟：在 n 个数中找到最小(大)数与第一个数交换位置 第 2 趟：在剩下 n-1 个数中找到最小(大)数与第二个数交换位置 重复这样的操作...依次与第三个、第四个...数交换位置 第 n-1 趟，最终可实现数据的升序（降序）排列。 选择排序

4.2、冒泡排序

【冒泡排序】：相邻元素两两比较，比较完一趟，最值出现在末尾 第 1 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 n 个元素位置 第 2 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 n-1 个元素位置 …… ……
第 n-1 趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第 2 个元素位置

冒泡排序算法

4.3.插入排序

【插入排序】：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

算法实现：直接插入排序是将无序序列中的数据插入到有序的序列中，在遍历无序序列时，首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置，一直到无序序列中的所有元素插完为止。对于一个无序序列arr{4，6，8，5，9}来说，我们首先先确定首元素4是有序的，然后在无序序列中向右遍历，6大于4则它插入到4的后面，再继续遍历到8，8大于6则插入到6的后面，这样继续直到得到有序序列{4，5，6，8，9}。 插入排序流程

代码实现：

void StraightSort(int *arr,int len)
{
int tmp;
int i;
int j;
for (i = 1;i < len;i++)
{
    tmp = arr[i];
    for (j = i - 1;j >= 0 && arr[j] > tmp;j--)
    {
        arr[j + 1] = arr[j];
    }
    arr[j + 1] = tmp;
}
}

5、折半查找（二分查找）折半查找：优化查找时间（不用遍历全部数据） 折半查找的原理：

1.数组必须是有序的
2.必须已知 min 和 max（知道范围）
3.动态计算 mid 的值，取出 mid 对应的值进行比较
4.如果 mid 对应的值大于要查找的值，那么 max 要变小为 mid-1
5.如果 mid 对应的值小于要查找的值，那么 min 要变大为 mid+1

已知一个有序数组, 和一个 key, 要求从数组中找到 key 对应的索引位置 折半查找

三、算法面试题（二）

字符串反转

给定字符串 "hello,world",实现将其反转

序数组合并

将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为 {1,2,3,4,5,6,6,7,8,9,9,10,11,12}

image.png

HASH 算法

哈希表例：给定值是字母 a，对应 ASCII 码值是 97，数组索引下标为 97。 这里的 ASCII 码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。
在一个字符串中找到第一个只出现一次的字符。如输入"abaccdeff"，输出'b'字符(char)是一个长度为 8 的数据类型，因此总共有 256 种可能。每个字母根据其 ASCII 码值作为数组下标对应数组种的一个 数字。数组中存储的是每个字符出现的次数。

image.png

查找两个子视图的共同父视图

思路:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图。 查找两个子视图的共同父视图

求无序数组中的中位数

中位数：当数组个数 n 为奇数时，为(n + 1)/2，即是最中间那个数字；当 n 为偶数时，为(n/2 + (n/2 + 1))/2, 即是中间两个数字的平均数。 首先要先去了解一些几种排序算法:iOS 排序算法 思路:
1.排序算法+中位数
首先用冒泡排序、快速排序、堆排序、希尔排序等排序算法将所给数组排序，然后取出其中位数即可。
2.利用快排思想