数据结构复习要点–前言,链表,字符串

所谓万变不离其宗,数据结构的基础是很多复杂大的算法以及大的工程的基础,有了基础才能跑的快,这篇文章就是按照常用的数据结构里的点,来建立一些简要描述帮助大家能够快速抓到重点,应该会持续更新的。

其实感觉数据结构是一门非常基础的编程基础,编程的目标是要告诉计算机,应该如何认知这个世界并且进行操作。

回想一下人类是如何认识这个世界的,从小到大一个连一个的融汇贯通的,先认识我们的爸妈,认识我们的床,然后认识亲戚们,然后认识放窗的屋子,按照时间或者空间,一个一个的物品,一件一件事情被串联了起来,万事万物都是有关联的,时间关系(链表),子女关系(树),地图上的国家(图)等等,像是打鸟枪一样,先把自己周围的东西先认识一遍,完成初级教育。

我们认识这个世界还需要上学,学数字和文字(字符串),学学习的方法,我们知道了做事情要一件一件来做(队列),复习的时候早前复习的东西最容易忘,新学的东西用的最熟(栈),所以我们要经常的找寻复习以前学习过的东西(搜索),当然有学无止境,世界上关联的东西实在是太多了,我们不一定能全都遍历一遍,我们的精力只能放在最重要的那几点上(排序)。

差不多有了这些基础之后,我们逐渐的学习成长,见识到了越来越多奇妙的东西,后面的故事以后再说了,先看这些基础了。下面的要点主要是通过Java 实现的。

 链表

链表,出现一个点,连一个点,结点之间最多两条边的操作,总共就是Node 和 List 两个对象,而且就是针对List的增删改查,不是很难吧。

单向链表

插入:头插入,尾插入,以及中间插入,难点:head为空的时候的插入,size的控制,以及index的控制

删除:指定下标删除,指定元素删除,难点:size控制,index的控制(超过Size),删除的是头尾结点的时候,未找到元素,查找时候判断相等的时候,如果是模板类使用 .equals,而不是直接==。

查: 指定下标的查找,指定元素的查找,难点:相等判断,头结点为空

改:指定下标修改元素内容,查找到之后,修改一下值就行了,如果是自定义类,要自己定义Set方法

双向链表,基本就是在上面的操作里面的每一个Next 后面增加Pre操作(有些不用),我在代码实现的时候,出现的错误是删除和插入的时候,空结点的size 没控制好。

代码和测试代码如下:链表代码(Interface MyList 实现链表多态)

常见的题目包括:定位起始的环的位置(快慢指针),大数加和乘,链表的归并排序

字符串

 在C++语言里面,String就是一堆字符+’\0′ 结尾的这么个串,ASNCII对应256个编码,Java,Python高级语言里面就是“XXXXX’”,这里能有啥问题呢,的确作为数据结构的基础,字符串在实现方面唯一能拿得出手的可能就是KMP的算法。但是在应用层面上讲,各类应用大部分处理的核心对象就是字符串。动态规划,Shell里面基于正则表达式的各种神级操作,海量数据处理中的Trie树,后缀树,Hadoop的分布式存储,信息检索中的索引和搜索。。。。。总之,地位非常的重要,但是还好,这里我们只讲基础和KMP。

Java的String

这是一个内置的类,不需要引用什么。

String a = “abc”; 就定义了一个String    |||    String[] arr = {“abc”,”cbd”}; 就定义了一个数组   |||  a.contains(“cdf”)或者 a.indexOf(“abc”)  就实现了KMP  |||  a.charAt(i) 只有这样的方式才能获得Java 字符串的中某位元素 ||| s.split(regex) 就能通过正则是就能实现切分了|| s.replace(regex, newString) 就能实现替换了,不过原值不会发生改变。

所以基本上用 JAVA 来写代码的时候,我们都不要太关系底层的实现的,已经帮我们做了非常多的事情了,但是这里KMP还是需要讲讲的,是一种非常聪明的方式。

KMP

这个命名的来源,就是发明者的名字缩写D.E.Knuth与V.R.Pratt和J.H.Morris,这个算法实现的功能是判断一个字符串T 是否是另外一个字符串S的子串。最暴力的方法是 O(len1 * len2), 挨个比较就可以了。KMP的方法并不能降低这个复杂度,但是却可以很大程度的降低运算次数,降低为O(len1+len2)。

传统的暴力匹配如下图:

 

QQ20141108-2    图1 暴力匹配 abcdex

第一步不匹配之后,实际上直接到第六步就可以了,暴力搜索中的其他步骤全都没有意义。再来一张大概就能明白KMP是如何运作的了。

QQ20141108-1  图2 暴力匹配 abcabx

通过图1就明白了,实际上这里可以直接跳到第5个步骤的,那么KMP也就基本成型了,当在S[i] 和 T[j] 匹配的第i位的时候,如果发生了不匹配,则 j 不是向前移动一位(暴力),而是直接跳转到符合 T[0:k-1] ==S[i-k:i-1] 条件的K位的,例如图2中的 abcabx,我们实际上可以设置出x的跳转位 为c的下标也就是2,设置next[T.len] 表示T位中的某一位如果不匹配的跳转位置,考虑一下其他的条件,可以得出以下的公式:

<br /> next[j] = \left \{ \begin{array}{rcl}<br /> -1 & & {j==0}\\<br /> k & & {s[0:k-1]==s[j-k:j-1]]}\\<br /> 0 & & others\\</p> <p>\end{array} \right.<br />

有了这个Next数组之后,基本上就是非常简单了,同时遍历S 中的每一位字符串S[i] 和 T[j] 如果相等OK,如果不相等,i不变,j 变为 next[j], 在匹配,直到 相等或者j 为-1,i++;如果遍历过程中j能到达 T.lenght 说明匹配成功,KMP求解成功。

整个KMP算法就是两步,

1. 求解Next数组,遍历T数组,难点在于如果i-1位子串和前 j 位字符不匹配,j变为 next[j]

2. 求是否匹配,遍历S数组, 难点在于如果 位于 i位的字符不匹配,j位字符变为 next[j], i 不变

再来几个典型的T, aaaaa, abcde, abcababc 。

代码:KMP

参考文献:

大话数据结构

Java 正则表达式详解

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.