数据结构与算法( 七)字符串串算法

编程中还是经常用到字符串匹配的算发。

一.字符串匹配算法

字符串匹配算法通常分为两个步骤:预处理(Preprocessing)和匹配(Matching)。预处理就是计算每次匹配的时候滑动窗口,所以算法的总运行时间为预处理和匹配的时间的总和。

朴素的字符串匹配算法

从左向右匹配,每次匹配一个字串, 匹配失败后 向右移动一个字串。具体流程如下:

1.

首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

2.

因为B与A不匹配,搜索词再往后移。

3.

就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

4.

接着比较字符串和搜索词的下一个字符,还是相同。

5.

直到字符串有一个字符,与搜索词对应的字符不相同为止。

6.

这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。(下面部分就是KMP改进过程,原理在后面中讲)

7.

一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,继续把它向后移,这样就提高了效率。

8.

怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

9.

已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数:

  移动位数 = 已匹配的字符数 – 对应的部分匹配值

因为 6 – 2 等于4,所以将搜索词向后移动4位。

10.

因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 – 0,结果为 2,于是将搜索词向后移2位。

11.

因为空格与A不匹配,继续后移一位。

12.

逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 – 2,继续将搜索词向后移动4位。

13.

逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 – 0,再将搜索词向后移动7位,这里就不再重复了。

KMP算法

KMP算法是在朴素算法上的优化,因为我们发现,匹配失败后,每次向右移动一个字串,能不能移动多几个字串呢?

其实这也是以空间,时间,换时间的方式。进行一个预处理。

其实就是要找到匹配过的字串中的前缀与后缀匹配的字串长度,这样直接移动过去就好了,再演化一下,预处理就是先建立起部分匹配表(索引(hash)),寻找待匹配字串的前缀集与后缀集中的匹配长度。这样就可以计算出失败后的位移长度。

下面介绍《部分匹配表》是如何产生的。

首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

15.

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例,

  - ”A”的前缀和后缀都为空集,共有元素的长度为0;

  - ”AB”的前缀为[A],后缀为[B],共有元素的长度为0;

  - ”ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

  - ”ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

  - ”ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1;

  - ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2;

  - ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

16.

“部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置。

数据结构与算法( 六)图

没有最好的数据结构,只有最适合的数据结构,没有最快的算法,只有最适合的算法。

图是一种常见的非线性数据结构,探究图,其实就是将非线性数据线性化的尝试。

图的遍历部分发现一个博客写得挺好,直接修改转过来了

http://www.cnblogs.com/dolphin0520/archive/2011/07/13/2105236.html

一.图定义

1.有向图:边有方向的图。 无相图:边无方向。

2.无向完全图:任两个点之间都有边的图。

3.有向完全图:任两点之间都存在两个有向边的图。

4.路径:任两个顶点之间经过的顶点序列集,长度是顶点序列之间边的的数目。

5.简单路径:路径中没有重复的顶点。

6.连通图:任两个顶点之间都存在路径的图

7.连通分量(极大连通子图):image

8.连通图的生成树:包含图中全部的顶点,但只有n-1条边

9.图可以使用2维数组来表示他们之间的关系,(邻接矩阵单元值为0,表示没有边,1表示有边)。

image

二.图的遍历

图的遍历是树的遍历的推广,是按照某种规则(或次序)访问图中各顶点依次且仅一次的操作,亦是将网络结构按某种规则线性化的过程

由于图存在回路,为区别一顶点是否被访问过和避免顶点被多次访问,在遍历过程中,应记下每个访问过的顶点,即每个顶点对应有一个标志位,初始为False,一旦该顶点被访问,就将其置为True,以后若又碰到该顶点时,视其标志的状态,而决定是否对其访问。

对图的遍历通常有”深度优先搜索“和”广度优先搜索“方法,二者是人工智能的一个基础。

深度优先搜索(Depth First Search,简称DFS)

算法思路:

类似树的先根遍历。设初始化时,图中各顶点均未被访问,从图中某个顶点(设为V0)出发,访问V0,然后搜索V0的一个邻接点Vi,若Vi未被访问,则访问之,在 搜索Vi的一个邻接点(深度优先)…。若某顶点的邻接点全部访问完毕,则回溯(Backtracking)到它的上一顶点,然后再从此顶点又按深度优先的方法搜索下去,…,直到能访问的顶点都访问完毕为止。

设图G10如下图所示:

通过深度优先如下:

广度优先搜索(Breadth First Search),简称BFS

算法思路:

类似树的按层次遍历。初始时,图中各顶点均未被访问,从图中某顶点(V0)出发,访问V0,并依次访问V0的各邻接点(广度优先)。然后,分别从这些被访问过的顶点出发,扔仍按照广度优先的策略搜索其它顶点,….,直到能访问的顶点都访问完毕为止。

为控制广度优先的正确搜索,要用到队列技术,即访问完一个顶点后,让该顶点的序号进队。然后取相应队头(出队),考察访问过的顶点的各邻接点,将未访问过的邻接点访问 后再依次进队,…,直到队空为止。

通过广度优先如下:

下面看一下实现代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define MAX 20
  5. //访问记录
  6. int visit[MAX];
  7. //图的结构设计
  8. typedef struct
  9. {
  10. int vex[MAX];//记录顶点
  11. int adjmatrix[MAX][MAX];//邻接矩阵
  12. int n;//顶点的个数
  13. }GRAPH;
  14. //初始化图
  15. int init_graph(GRAPH *pG)
  16. {
  17.     memset(pG,0,sizeof(GRAPH));
  18.     pG->n = -1;
  19.     printf(“input vex\n”);
  20. while(scanf(“%d”,&pG->vex[++pG->n]));
  21. while(getchar() != ‘\n’);
  22. #ifndef _DEBUG_
  23. int i = 0;
  24. for(i = 0;i < pG->n ;i ++)
  25. {
  26.         printf(“V%d “,pG->vex[i]);
  27. }
  28.     printf(“\n”);
  29. #endif
  30.     return 0;
  31. }
  32. //获取顶点的位置
  33. int locatevex(GRAPH *pG,int vex)
  34. {
  35. int i = 0;
  36. for(i = 0;i < pG->n;i ++)
  37. {
  38. if(pG->vex[i] == vex )
  39.             return i;
  40. }
  41.     return 0;
  42. }
  43. //输入图的顶点之间的边
  44. int input_edge(GRAPH *pG)
  45. {
  46. int vex1,vex2;
  47. int i,j;
  48.     printf(“input edge(i,j):\n”);
  49. //任意字母键结束
  50. while(scanf(“(%d,%d)”,&vex1,&vex2))
  51. {
  52.         getchar();
  53.         i = locatevex(pG,vex1);
  54.         j = locatevex(pG,vex2);
  55.         pG->adjmatrix[i][j] = pG->adjmatrix[j][i] = 1;
  56. }
  57. #ifndef _DEBUG_
  58. int m,n;
  59. for(m = 0;m < pG->n;m ++)
  60. {
  61. for(n = 0;n < pG->n; n ++)
  62. {
  63.             printf(“%d “,pG->adjmatrix[m][n]);
  64. }
  65.         printf(“\n”);
  66. }
  67. #endif
  68.     return 0;
  69. }
  70. //栈的设计
  71. typedef struct
  72. {
  73. int buf[MAX];
  74. int n;
  75. }Stack;
  76. //创建空栈
  77. Stack *create_empty_stack()
  78. {
  79.     Stack *stack;
  80.     stack = (Stack *)malloc(sizeof(Stack));
  81.     stack->n = -1;
  82.     return stack;
  83. }
  84. //出栈
  85. int pop_stack(Stack *stack)
  86. {
  87. int temp;
  88.     temp = stack->buf[stack->n];
  89.     stack->n –;
  90.     return temp;
  91. }
  92. //入栈
  93. int push_stack(Stack *stack,int data)
  94. {
  95.     stack->n ++;
  96.     stack->buf[stack->n] = data;
  97.     return 0;
  98. }
  99. //判断空栈
  100. int is_empty_stack(Stack *stack)
  101. {
  102. if(stack->n == -1)
  103.         return 1;
  104. else
  105.         return 0;
  106. }
  107. int visit_all(GRAPH *pG)
  108. {
  109. int i = 0;
  110. for(i = 0;i < pG->n; i ++)
  111. {
  112. if(visit[i] != 1)
  113.             break;
  114. }
  115. if(i == pG->n)
  116.         return 1;
  117. else
  118.         return 0;
  119. }
  120. //图的深度非递归遍历
  121. int DFS(GRAPH *pG,int v)
  122. {
  123.     Stack *stack;
  124. int i = 0;
  125.     stack = create_empty_stack();
  126.     push_stack(stack,pG->vex[v]);
  127.     visit[v] = 1;
  128.     printf(“V%d “,pG->vex[v]);
  129. while(!is_empty_stack(stack) || !visit_all(pG))
  130. {
  131. for(i = 0;i < pG->n;i ++)
  132. {
  133. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
  134.                 break;
  135. }
  136. if(i == pG->n)
  137. {
  138.             v = pop_stack(stack);
  139. }else{
  140.             v = i;
  141.             push_stack(stack,pG->vex[v]);
  142.             visit[v] = 1;
  143.             printf(“V%d “,pG->vex[v]);
  144. }
  145. }
  146.     printf(“\n”);
  147.     return 0;
  148. }
  149. //队列的设计
  150. typedef struct node
  151. {
  152. int data;
  153.     struct node *next;
  154. }ListNode;
  155. typedef struct
  156. {
  157.     ListNode *front;
  158.     ListNode *rear;
  159. }Queue;
  160. //创建空队列
  161. Queue *create_empty_queue()
  162. {
  163.     Queue *queue;
  164.     ListNode *head;
  165.     queue = (Queue *)malloc(sizeof(Queue));
  166.     head = (ListNode *)malloc(sizeof(ListNode));
  167.     queue->front = queue->rear = head;
  168.     return queue;
  169. }
  170. //判断队列是否为空
  171. int is_empty_queue(Queue *queue)
  172. {
  173. if(queue->rear == queue->front)
  174.         return 1;
  175. else
  176.         return 0;
  177. }
  178. //入队
  179. int EnterQueue(Queue *queue,int data)
  180. {
  181.     ListNode *temp;
  182.     temp = (ListNode *)malloc(sizeof(ListNode));
  183.     temp->data = data;
  184.     temp->next = NULL;
  185.     queue->rear->next = temp;
  186.     queue->rear = temp;
  187.     return 0;
  188. }
  189. //出队
  190. int DelQueue(Queue *queue)
  191. {
  192.     ListNode *temp;
  193.     temp = queue->front;
  194.     queue->front = queue->front->next;
  195.     free(temp);
  196.     temp = NULL;
  197.     return queue->front->data;
  198. }
  199. //图的广度遍历
  200. int BFS(GRAPH *pG,int v)
  201. {
  202.     Queue *queue = create_empty_queue();
  203. int i = 0;
  204.     memset(&visit,0,sizeof(visit));
  205.     EnterQueue(queue,v);
  206.     visit[v] = 1;
  207. while(!is_empty_queue(queue))
  208. {
  209.         v = DelQueue(queue);
  210.         printf(“V%d “,pG->vex[v]);
  211. for(i = 0;i < pG->n;i ++)
  212. {
  213. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
  214. {
  215.                 EnterQueue(queue,i);
  216.                 visit[i] = 1;
  217. }
  218. }
  219. }
  220.     printf(“\n”);
  221.     return 0;
  222. }
  223. int main()
  224. {
  225.     GRAPH G;
  226. int n;
  227. //输入顶点,初始化图
  228.     init_graph(&G);
  229. //初始化邻接矩阵
  230.     input_edge(&G);
  231. //图的深度遍历
  232.     DFS(&G, 0);
  233. //图的广度遍历
  234.     BFS(&G,0);
  235.     return 0;
  236. }

输出结果:

数据结构与算法(五)查询

很多时候,我们会比较在意查询的时间,因为这是用户最常使用的功能,并且是实时的需求,非常影响用户体验,以下是各种数据结构查询的效率,我们可以看到平衡二叉树等查找效率比较高,其实这是将时间前移了,因为平衡二叉树本身就是有序的,相当于已经对数据进行了一个排序,我们可以看到插入构造这个树的时间LOG(N)。

image

一.无序数据基础查找

像单链表这种无序队列,插入的时候很快的,直接加到末尾就可以,但是其查找确实耗时,使用了直接查找法。

所以为了加速查找的速度,需要将数据预先进行排序,一般就是生成的 时候就进行排序,比如数据库表加索引,构造二叉树,哈希表存储数据,这样在这些有序数据基础上进行数据查找就快多了,虽然在构造的时候会消耗时间,甚至让总时间都增加了,但是,有什么关系呢。

二.有序数据查找

无序数据查找效率比较慢,所以一般查找前都会排序,分担一部分的压力。

折半查找法

适用场景:针对已排序序列,并且只适用于顺序存储结构的序列,这样才能O(1)找到其中间值。但是这样一来,其插入,删除会变得比较低效,鱼熊不可兼得。

B树(二叉查找树)算法

其查找效率与树的深度有关。

HASH查找

算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

算法流程:

1)用给定的哈希函数构造哈希表;

2)根据选择的冲突处理方法解决地址冲突;

常见的解决冲突的方法:拉链法和线性探测法。 详细的介绍可以参见:  哈希表 。

3)在哈希表的基础上执行哈希查找。

这也是用空间换时间的例子之一。所以哈希表是查询效率的极致了。但是要解决好健冲突问题,比如拉链法,相当于将有共同哈希值的数据存储到一个链上,哈希值索引指向这个链,如果链COUNT>1,则再在链上顺序查找,这也有分治法的应用效果,基本上std::map 这种 kv存储结构就是哈希表的应用。这还可以衍生出进行大数据外排查找Top K问题。

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。综合两者特性,设计一种寻址容易,插入删除也容易的数据结构,如拉链法实现的哈希表。

拉链法实现的哈希表应该也算是一个分块查找,索引查找的实现方式

分块查找(索引查找)

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

算法思想: 将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

这种也适合使用并行进行查找。

算法流程:

step1 先选取各块中的最大关键字构成一个索引表;

step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。

数据结构与算法(四)排序

根据待排序数据量能否被全部装载到内存中进行排序分为:内部排序外部排序。当然我们都希望直接在内存中进行排序,因为IO的延迟非常的大,但对于大数据集来说,内存是远远不够的,这时候就涉及到外排序,外排序通过读/写外存的次数来衡量其效率。基本上上学的时候学的都是内部排序,同时万不得已,都尽量使用内部排序,或者转化为内部排序。其实也就是说,我们要以空间换时间,以稳定性换时间,所以如何选择排序方法要综合场景来进行

一.基本排序

http://ibinguo.net/wp-content/uploads/2016/12/image_thumb8.png

image

冒泡排序->快速排序->归并排序

冒泡排序是最基本的排序算法,遍历所有数据,一次遍历查出最大值。所以如果要查询某个最大值也可以使用下冒泡。但是这个速度不敢恭维,所以有了变种快速排序,当然是以牺牲部分空间及稳定性为条件的。

快速排序快排是基础单线程排序中效率最好的了。以分治的思想进行排序,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

 

插入排序->希尔排序->并归排序

插入排序:遍历剩余所有数据,遍历待排序数据,将数据插入到一个已排序好的队列中,该已排序好的队列慢慢增大。

插入排序是每次将一个数据插入待排序序列,即步长为1希尔排序也可称为分组插入方法,则是步长>1,每个分组内使用插入排序或者二分插入排序。

并归排序:

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并。直到得到长度为n的有序表,排序结束。
归并操作的工作原理如下:

  1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2、设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4、重复步骤3直到某一指针达到序列尾

堆排序

堆实际上是一棵完全二叉树,利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

二.适用场景

综合上述,得到的各种情况下的最优排序分别是:

(1)序列完全有序,或者序列只有尾部部分无序,且无序数据都是比较大的值时, 【直接插入排序】最佳(哪怕数据量巨大,这种情形下也比其他任何算法快)

(2)数据基本有序,只有少量的无序数据零散分布在序列中时,【希尔排序】最佳

(3)数据基本逆序,或者完全逆序时,  【希尔排序】最佳(哪怕是数据量巨大,希尔排序处理逆序数列,始终是最好的,当然三数取中优化的快速排序也工作良好)

(4)数据包含大量重复值,【希尔排序】最佳(来自实验测试,直接插入排序也表现得很好)

(5)数据量比较大或者巨大,单线程排序,且较小几率出现基本有序和基本逆序时,【快速排序】最佳

(6)数据量巨大,单线程排序,且需要保证最坏情形下也工作良好,【堆排序】最佳

(7)数据量巨大,可多线程排序,不在乎空间复杂度时,【归并排序】最佳

 

三.

数据结构与算法(一)基础

数据结构是一门研究非数值计算程序设计问题中,计算机的操作对象以及他们之间的关系和操作的学科

数据是用来描述现实世界的数字字符图像声音以及能够输入到计算机中并能被计算机识别的符号的集合

数据结构三方面内容:

(1)数据的逻辑结构指数据元素之间固有的逻辑关系

(2)数据的存储结构指数据元素及其关系在计算机内的表示

( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除,更新,查询,排序等

一.数据结构基础概念

逻辑结构包括:

(1)线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。
(2)非线性结构,一个结点可能有多个直接前趋和后继。:集合,树形结构、图形结构

存储结构包括:

1)顺序存储,逻辑相邻的结点存储在物理上相邻的存储单元内。逻辑顺序与存储顺序一致
2)链接存储,结点间的逻辑关系由附加指针字段表示,1.逻辑顺序与存储顺序不一致2.每个节点存取的费时不同
3)索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。
4)散列存储,按结点的关键字直接计算出存储地址。

(操作)算法时间复杂度

是该算法的时间耗费,是求解问题规模n的函数。记为O(n)。
时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

评价算法的标准:正确性,高效性,健壮性(容错),可读性。

抽象数据类型的形式描述为:

ADT = ( D,S,P )

  其中:D 是数据对象,

S 是 D 上的关系集,

P 是 D 的基本操作集。

ADT 抽象数据类型名 {

 数据对象: 数据对象的定义

 数据关系: 数据关系的定义

 基本操作: 基本操作的定义

} ADT 抽象数据类型名

二.各类数据结构特点(算法时间复杂度)

    索引 插入 删除 查询 排序
  静态数组 O(1) O(1)  
  动态数组 O(1) O(n) O(n) O(n)  
  单链表 O(n) O(1) O(1) O(n)  
  双链表 O(n) O(1) O(1) O(n)  
  二叉排序树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  红黑树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  B树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  笛卡尔树 O(log(n)) O(log(n)) O(log(n))  
  哈希表 O(1) O(1) O(1)  
             
             
             
排序:

image