浅析KMP算法之Next数组
首先我们需要知道KMP是干嘛的，通俗易懂的来讲是查找相同字符串的一种捷径
我们人的本能的趋简避繁，例如aababcbdaabacbbbd这样的字符串，我们需要在其中找到子串aabacb我们怎么操作？
为什么会将子串第一个字符依次对比字符串的每一个字符来判断：
=----------1---------=
aababcbdaabacbbbd
aabacb
=----------2---------=
aababcbdaabacbbbd
aabacb
=----------3---------=
aababcbdaabacbbbd
aabacb
=----------4---------=
aababcbdaabacbbbd
abacb
=----------5---------=
aababcbdaabacbbbd
abacb
=----------6---------=
aababcbdaabacbbbd
abacb
=----------7---------=
aababcbdaabacbbbd
abacb
=----------8---------=
aababcbdaabacbbbd
abacb
=----------9---------=
aababcbdaabacbbbd
abacb
=----------10---------=
aababcbdaabacbbbd
abacb
=----------end完结撒花---------=
怎么样是不是很麻烦吧？//麻烦个嘚，我就喜欢
不是，既然计算机大拿说了麻烦咱就认行吗？
于是开头字母分别为KMP的三个人设计了一个算法叫KMP算法（具体思路自己百度，以下只解释最重要也是最难理解的Next数组该怎么求）
Next数组说白了就是求子串中每一个最长相等前后缀（听不懂没关系，往下看）
这里声明一个规则：
前缀：不包含未元素的串
后缀：不包含首元素的串
我们来举个例子这是子串|a|a|b|a|a|f|
（1）|a|
前缀以及后缀都为0 导致最长相等前后缀为0
（2）|a|a|
前缀为|a|
后缀为|a|相等
最长相等前后缀为1
（3）|a|a|b|
前缀为|a|a|
后缀为|a|b|不相等
在这有两个元素的前后缀的基础上再下一次比较
前缀|a|
后缀|b|依然不相等//注意这里的|a|和|b|不是后缀中的|a|b|拆分的，是前缀|a|a|的第一个|a|以及后缀|a|b|最后的那个|b|
最长相等前后缀为0
（4）|a|a|b|a|
前缀为|a|a|b|
后缀为|a|b|a|当然不相等
在这有三个元素的两个前后缀的基础上再下一次比较
前缀|a|a|
后缀|b|a|依然不相等
同理再比较
前缀|a|
后缀|a|相等
所以最长相等前后缀为1
（5）|a|a|b|a|a|
前缀|a|a|b|a|
后缀|a|b|a|a|不等
再前缀|a|a|b|
后缀|b|a|a|不等
再|a|a|
后缀|a|a|相等长度为2
最长相等前后缀为2
（6）|a|a|b|a|a|f|
前缀|a|a|b|a|a|
后缀|a|b|a|a|f|不等
前缀|a|a|b|a|
后缀|b|a|a|f|不等
前缀|a|a|b|
后缀|a|a|f|不等
前缀|a|a|
后缀|a|f|不等
前缀|a|
后缀|f|不等
所以最长相等前后缀为0
所以Next数组的值就是，这6个算出来的数值
即|0|1|0|1|2|0|
以上为理论部分（聪明的人会看到这里的）
以下是代码实现部分（C++）
#include < stdio.h >
#include < iostream >//c++的头文件
#include< string >
using namespace std;//c++的命名空间，如果没有这句话，很多地方会这样写std::cout等等
class solution {//定义类，c++语法
public://公共方法（好像java才说方法）以及属性
void getnext(int* next, const string& s) {//传入next数组以及字串
int j = 0;//j初始化为0
next[0] = 0;//首元素设置为0
for (int i = 1; i < s.size(); i++) {//我们假设i指向后缀的末尾，j指向前缀的末尾
while (j > 0 && s[i] != s[j]) {//while是用来处理前后缀不相同的情况
j = next[j - 1];//这句代码的意思是回退，回退到前一个数组元素的值为数组下标处
}
if (s[i] == s[j]) {//if用来处理前后缀相同的情况
j++;//如果想相同，则会将j++，让j来表示最长相等前后缀的情况
}
next[i] = j;//让此处的最长相等前后缀为j的值
}
}
};
int main()
{
int next[8];
string s = "abcabcab";
solution*a = new solution();
a->getnext(next,s);
for(int i=0;i<8;i++)
printf("%d",next[i]);
}
//放心，代码你十有八九看不懂，不过没关系，毕竟你要是自己研究出来了
//你就是KMP的发明者了，今天看几遍，过几天再来，慢慢的就理解了
图的最小生成树
给定图，利用Kruskal算法（克鲁斯卡算法） 生成最小生成树
(注意：这里之所以是选40而不是15的边是因为C和D已经有了通路)
即
给定图，利用Prim算法（普里姆算法） 生成最小生成树，给定A为初始点
总结两种算法的结果是相同的，但是其过程是不同的，解答这类题目的答案就是需要步骤的
哈夫曼树
已知
A
B
C
D
E
0.15
0.16
0.07
0.21
0.41
(1)画出相对应的哈夫曼(Huffman)树
(2)计算带权路径长度WPL
(3)求A、B、C、D、E的哈夫曼(Huffman)编码
（1）取最小的两者不断重构(结合以后的生成的数再放到整个比较)
以下是详细步骤
1>ABCDE中A与C的数值最小于是乎先画出A C
2>把A和C的合并数值0.22当成AC再去和剩下的B、D、E比较大小，选出最小两个(也就是B和D)，这个时候刚才画的就别动，在旁边重新画一棵树
3>思想同上(别告诉我你现在还没有看明白😒😒😒)
以上就是对应的完整的哈夫曼树了
(2)计算WPL（看带字母的节点，然后看这个节点到顶点经过了几条边，经过几条就数值*几就行）
例如A，从顶点到A经过了4条边(幼儿园的都知道怎么数🤣🤣🤣)
也就是0.15*4，总之把所有字母的边*数加起来就是WPL
∴WPL=1*0.41+3*0.15+3*0.07+3*0.06+3*0.21//*是乘号✖，我靠这样看起来很头疼吗？？这不就是程序员必备的？
∴WPL=1✖0.41+3✖0.15+3✖0.07+3✖0.06+3✖0.21//满足你
(3)求哈夫曼编码（将哈夫曼树的左边画0，右边画1，你就知道了）
哈希函数
设散列表长为11，记录关键字集合为{15，17，28，41，37，31，56，23，45，51，73}，散列函数：H(Key) = key MOD 11，冲突处理采用线性探测法，请给出散列表的构造过程，再求平均查找程度ASL
(1)先看散列函数，H(Key) = Key MOD 11.(对每个数都取余，与11相除，取余)
余数
4 6 6 8 4 9 1 1 1 7 7
原数
15
17
28
41
37
31
56
23
45
51
73
(2)我们先写出一个0-10（11个）
我们规定，按照余数，放进这个表格中，如果冲突线性探测就是往后顺延一位（如果一位不行就再继续顺）
我们一步步来，把余数4对应的15放到4处
0 1 2 3 4 5 6 7 8 9 10
15
此时记录15到位4处动了（1）次，接着把17放到6处
0 1 2 3 4 5 6 7 8 9 10
15 17
记录17动了（1）次，接着放28，因为28是6，和之前的17冲突了，采用线性探测就是往后顺延一位
0 1 2 3 4 5 6 7 8 9 10
15 17 28
记录28动了（2）次，接着41放8处
0 1 2 3 4 5 6 7 8 9 10
15 17 28 41
记录41动了（1）次，接着37，与15冲突了往后顺延1位
0 1 2 3 4 5 6 7 8 9 10
15 37 17 28 41
记录37动了（2）次，接着31，放9处
0 1 2 3 4 5 6 7 8 9 10
15 37 17 28 41 31
记录31动了（1）次，接着56放1处
0 1 2 3 4 5 6 7 8 9 10
56 15 37 17 28 41 31
记录56动了（1）次，接着23放1处冲突顺延到2处
0 1 2 3 4 5 6 7 8 9 10
56 23 15 37 17 28 41 31
记录23动了（2）次，接着45放1处冲突顺延到2处再冲突再顺延3处
0 1 2 3 4 5 6 7 8 9 10
56 23 45 15 37 17 28 41 31
记录了45动了（3）次，接着把51放7处与28冲突顺延到8冲突到9冲突于是放到10
0 1 2 3 4 5 6 7 8 9 10
56 23 45 15 37 17 28 41 31 51
记录51动力4次，接着73放7处冲突，再8冲突，再9冲突，再10冲突，再0放
0 1 2 3 4 5 6 7 8 9 10
73 56 23 45 15 37 17 28 41 31 51
以上就是表的构造过程了
15：1次
17：1次
28：2次
41：1次
37：2次
31：1次
56：1次
23：2次
45：3次
51：4次
73：5次
求ASL(平均查找程度就是将以上数加起来再除他们的总个数)
ASL= 1 + 1 + 2 + 1 + 2 + 1 + 1 + 2 + 3 + 4 + 5 10 = 2.3
还有一种题目是冲突采用链地址表示法
前面求余数的步骤一样就是构造的时候采用链表的思想
余数
4 6 6 8 4 9 1 1 1 7 7
原数
15
17
28
41
37
31
56
23
45
51
73
就是构造以下基表竖着的
0
^
1
->
56
->
23
->
45
^
2
^
3
^
4
->
15
->
37
^
5
^
6
->
17
->
28
^
7
->
51
->
73
^
8
->
41
^
9
->
31
^
10
^
求ASL，就是1*第一列的个数+2*第二列的个数+3*第三列的个数...
此题就是ASL=1*6+2*4+3*1
图的深度优先与广度优先
1
->
3
->
2
->
4
^
2
^
3
->
4
->
5
^
4
^
5
->
2
->
4
^
我们来分析一下深度优先
第一步 我们给1标上了①，接下来给3表上了②，于是这时候跳到了
① 1->
② 3->
2
->
4
^
2
^
3
->
4
->
5
^
4
^
5
->
2
->
4
^
跳到了3处，往后给4表上③，这时候跳到
① 1->
② 3->
2
->
4
^
2
^
② 3->
③ 4->
5
^
4
^
5
->
2
->
4
^
这时候跳到了
① 1->
② 3->
2
->
4
^
2
^
② 3->
③ 4->
5
^
③ 4^
5
->
2
->
4
^
注意这时候，4后面没有任何东西，于是回退到上一个的最后继续标
① 1->
② 3->
2
->
4
^
2
^
② 3->
③ 4->
④ 5^
③ 4^
5
->
2
->
4
^
标了于是跳到5处，给5的下一个2标上
① 1->
② 3->
2
->
4
^
2
^
② 3->
③ 4->
④ 5^
③ 4^
④ 5->
⑤ 2->
4
^
到此为止全部的数都标完了
于是 深度优先遍历 就是：1、3、4、5、2
接下来我们讨论一下广度优先遍历 (简单的一批，就是从上到下，从左到右)
1
->
3
->
2
->
4
^
2
^
3
->
4
->
5
^
4
^
5
->
2
->
4
^
就是1、3、2、4、5
二叉树的前中后序遍历
这类题目一般给前中/后中，来确定后/前序遍历，因为只有前中/后中才能确定唯一的二叉树，而前后序不能确定
//很好，接下来并不是右C，而是E，因为B也是一棵子树二叉树的根
也就是根B的左：E //接下开E又是一棵子树的根
也就是根E的左：F //因为F不再是任何树的根，这时候就可以到右
也就是根E的右：G //完成以后，我们回退到E？不，因为E的左右都写完了，于是我们再回退B，根B写了左但还没写右
也就是根B的右：D //此时D又是根，于是再写D的左
也就是根D的左：H //此时H不是根了，就可以写右
也就是根D的右：I //这时候，根D左右写完，回退B，B的左右也写完了，回退A，A只写完了左，右还没有写，于是
也就是根A的右：C //到此为止，我们的前序遍历就算写完了
前序：ABEFGDHIC
//这个左是整个树的左
根：E //这应该能理解吧？不能理解？废了，重开吧
右：G //此时，一棵子树以及遍历完了，按理说是返回到B，但是B是根，把B看成根，也就是E子树为左，D子树为右
也就是根：B 现在你肯定想说，接下来不就是D了吗？no、no、no，时刻谨记D是根，我们优先左再根再右，也就是根D树的左H
左：H
根：D
右：I 现在D树完成，回退到B，B树的左右也完成了，回退到A，A左完成，根据左根右，也就是左完成，现在是根，于是
根：A
右：C 这还用我说？🤏🤏🤏
中序：FEGBHDIAC
//现在B的左树已经写完，根据左右根规则，我们看B的右边的树，也就是以D为根的树，但是我们肯定不是先写D，要先左
左：H
右：I
根：D //好了，左右子树都写完，就写根了
根：B 现在总体看，A树的左子树写完了，再看A的右树
右：C
根：A 完结撒花😃😃😃😃😃
后序：FGEHIDBCA
（1）给定前序ABDGHCEFI与中序GDHBAECIF，写出后序遍历。
你肯定有点思路，但我知道并不多，我们来用一种流氓的思路来解决他
画以下的类似二维坐标系的图
G
D
H
B
A
E
C
I
F
G
D
H
B
A
E
C
I
F
I
F
E
C
H
G
D
B
A
怎么样，画出上面的图，我们肯定知道A是根节点，别问为什么，因为前序遍历第一个肯定是总树的根节点啊😡😡😡😡
接下来我们画线
G
D
H
B
A
E
C
I
F
G
D
H
B
A
E
C
I
F
I
F
E
C
H
G
D
B
A
画这些点和线真的累死我啦🤨😥😭
看起来是不是很简单，但是如果你现在直接把我题目抄在草稿纸上，自己去画，绝对会有地方卡住
这就是为什么你有时候学习，以为学的很好了，看起来很简单，但是自己一动手就废了
注意看我画的图，你怎么知道A必须连接B？为什么不左连接D，右连B？等等问题
在这里我们遵循几个原则
1.这是二叉树，最多只有两个子树，也就是最多只能有两个孩子
2.左孩子的x不会大于根的x
3.根一定在孩子上方
4.与最近的结合
行了，以上是我瞎总结的，这些就是经验，教科书又臭又长，但是学懂了，根本不需要记住那么多东西
就是自然而然的。
然后就是喜闻乐见的，答题环节
后序遍历：GHDBEIFCA //你可能还是困惑为什么E在C前面，I在F前面，真的想一巴掌拍晕你，左右根，A的右树开始是C，但是C是A右子树的根啊，所以开始E，然后C的右，右F也是一棵子树，F也是根所以先I再F啊
（2）给定后序ACDBGIHFE与中序ABCDEFGHI求前序遍历
在解答这道题前别着急写，别以为学了点东西就以为天下无敌了，乱拳打不死老师傅
仔细想想中序遍历不管他，我们前一题给的是前序遍历，在y轴上当然A最在最上面，因为A是全部的根
但是后序呢？最后一个字母E才是根，如果还按之前的y轴排，E在最下面，那成啥了？
A
B
C
D
E
F
G
H
I
A
B
C
D
E
F
G
H
I
A
C
D
B
G
I
H
F
E
按照同样的思路连线，你可以自己尝试一下，再来看我画的
A
B
C
D
E
F
G
H
I
A
B
C
D
E
F
G
H
I
A
C
D
B
G
I
H
F
E
我知道你如果自己试了的话，有可能在C为什么不连A，而是B连A，这个问题在于，B作为一个根，你将其从上到下看成一个金箍棒
如果C连的左子树为A，那么A大概率在B这根金箍棒的右边而不是左边
下面是题目的答案
前序遍历：EBADCFHGI
一开始学习的时候我问过一个问题：
第三中，给定前后序，怎么求中序啊？（不知道你会不会有这种想法）
还记得我们一开始说的吗？只有前中以及后中才能确定一棵树，而前后并不能确定唯一的一棵树
常见的几种排序
希尔排序、快速排序、堆排序、归并排序、基数排序、折半查找
对{40，24，80，39，43，18，20，10，90，70} 进行从小到大排序过程(两两分组比较)
[40]
[24]
[80]
[39]
[43]
[18]
[20]
[10]
[90]
[70]
[24，40]
[39，80]
[18，43]
[10，20]
[70，90]
[24，39，40，80]
[10，18，20，43]
[70，90]
[10，18，20，24，39，40，43，80]
[70，90]
[10，18，20，24，39，40，43，70，80，90]
这应该看得懂吧？一目了然了都😏😏
对{46，58，15，45，90，18，10，62}进行快速排序
以第一个数为基准提出来
___ 58 15 45 90 18 10 62
___ 58 15 45 90 18 10 62<--
这时候比较最后一个数与第一个数46的大小，62>46(不动)
___ 58 15 45 90 18 10<-- 62
这时候比较向前移动一位比较10和46大小，10<46(将10移动到46原本在的第一位)
10 58 15 45 90 18 ___ 62
这个时候比较的指向是从前面也就是10的后面开始
10 58<-- 15 45 90 18 ___ 62
58>45(将58移动到10原本的位置)
10 ___ 15 45 90 18 58 62
这时候再从后面也就是58的前面
10 ___ 15 45 90 18<-- 58 62
18<46(移动到58原本所在的前面)
10 18 15 45 90 ___ 58 62
再从18的后面开始比较
10 18 15<-- 45 90 ___ 58 62
15<46(不动)
10 18 15 45<-- 90 ___ 58 62
45<46(不动)
10 18 15 45 90<-- ___ 58 62
90>46(移动到后面的空位去)
10 18 15 45 ___ 90 58 62
到此为止全部元素都和46比较过了，于是把46放到空位处
10 18 15 45 46 90 58 62
此时46的位置已经确定了，46所在的位置就是这里，你可能也感觉出来了，这一轮比较就是把比46小的一股脑丢46前面，比46大的一股脑丢到后面去
既然46确定了，只需要比较两块内容就行了，也就是46前面的，和46后面的就行，还是按照之前的方法
___ 18 15 45<-- 46 ___ 58 62<--
哈哈哈，开启双开模式，前面提10，后面提90
45>10(不动);62<90(动)
10 18 15<-- 45 46 62 58<-- ___
10 18<-- 15 45 46 62 58 90
我会把比较完成的数标红
10 18 15 45 46 62 58 90
10 ___ 15 45<-- 46 ___ 58<-- 90
10 ___ 15<-- 45 46 58 ___ 90
10 15 18 45 46 58 62 90
利用希尔排序对关键字系列{40，24，80，39，43，18，20，10，90，70}从小到大排序(增量5，3，1)
增量的意思就是每个x个为一个组比较大小
当增量为5时
40 ，24，80，39，43，18 ，20，10，90，70
40 ，24 ，80，39，43，18 ，20 ，10，90，70
40 ，24 ，80 ，39，43，18 ，20 ，10 ，90，70
40 ，24 ，80 ， 39 ，43，18 ，20 ，10 ，90 ，70
40 ，24 ，80 ， 39 ，43，18 ，20 ，10 ，90 ，70
最终我们得出增量为5的分组（颜色不同来区分）
40 ，24 ，80 ， 39 ，43，18 ，20 ，10 ，90 ，70
（把小的放前，大的放后就行）
18 ，20 ，10 ， 39 ，43，40 ，24 ，80 ，90 ，70
就是以上的第一次增量，当增量为3的时候
18 ，20 , 39，43 ，40 ，24，80 ，90 ，70
18 ，20 , 24，43 ，40 ，39，80 ，90 ，70
完成，以下是增量为1的
18，20, 24，43，40，39，80，90，70
18，20，24，39，40，43，70，80，90
完成
对{457,131,481,219,392,674,350,815,315}进行基数排序
看
个
位
数
放
Q_0
Q_1
Q_2
Q_3
Q_4
Q_5
Q_6
Q_7
Q_8
Q_9
350
481
392
674
475
815
315
137
219
接下来就是收集（从上到下，从左到右）：{350,481,392,674,475,815,315,137,219}
看
十
位
数
放
Q_0
Q_1
Q_2
Q_3
Q_4
Q_5
Q_6
Q_7
Q_8
Q_9
815
315
219
137
350
674
475
481
392
接下来就是收集（从上到下，从左到右）：{815,315,219,137,350,674,475,481,392}
看
百
位
数
放
Q_0
Q_1
Q_2
Q_3
Q_4
Q_5
Q_6
Q_7
Q_8
Q_9
137
219
315
350
392
475
481
674
815
接下来就是收集（从上到下，从左到右）：{137，219，315，350，392，475，481，674，815}
至此你也看出来了，它到底是怎么运作来实现排序的
也不难，先个位数，再十位数，再百位数，一步步确保
对{5,13,17,29,37,41,61,79,89}利用折半查找值为29的元素
_0_
_1_
_2_
_3_
_4_
_5_
_6_
_7_
_8_
5
13
17
29
37
41
61
79
89
↑
↑
↑
low
mid
high
我们规定了首尾都有一个指针，其次mid的指针由下面式子给出
m i d = l o w + h i g h 2 = 0 + 8 2 = 4 37 比我们要找的值29大
这就是说明我们的中间的指针是比这个大的(😏废话)
所以我们把高指针的指向重新定义为mid(中间指针)的前一个
如果你对为什么是前一个没有疑虑，那么你很聪明
因为我们比较的就是中间指针肯定是要么大要么小，如果相同的就结束了啊
所以这个相当于不属于我们下一次查找的范围了
_0_
_1_
_2_
_3_
_4_
_5_
_6_
_7_
_8_
5
13
17
29
37
41
61
79
89
↑
↑
↑
low
mid
high
m i d = l o w + h i g h 2 = 0 + 3 2 = 1
_0_
_1_
_2_
_3_
_4_
_5_
_6_
_7_
_8_
5
13
17
29
37
41
61
79
89
↑
↑
↑
low
mid
high
m i d = l o w + h i g h 2 = 2 + 3 2 = 2
_0_
_1_
_2_
_3_
_4_
_5_
_6_
_7_
_8_
5
13
17
29
37
41
61
79
89
↑
↑
↑
low
mid
high
m i d = l o w + h i g h 2 = 3 + 3 2 = 3 对{5,1,6,9,2}如何构造大/小根堆
怎么说呢，就是大小根堆简单就是根是最大/小的就是
我们操作的步骤第一步就是将给出的数列按完全二叉树排列(完全二叉树不知道的话那，废了)
5 2 = 2 7 2 = 3 6 2 = 3 到这里并没有结束，我之前说的情况发生了
就是第六个数10比第三个数（掉下来的）-54大，此时同样需要换
最终就是
顺序存储 的线性表 的操作（初版）纯手打（原创）
/*
* 线性表的ADT（抽象）
* 1.初始化。2.增删改查。3.判空。4.销毁。
* InitList(&L) 初始化
* ListInsert(&L,i,e) 插入操作，因为要修改表所以传入其本身
* ListDelete(&L,i,&e) 删除操作，因为也要删除表中元素所以传入其本身
* ListAlert(&L,i,e) 修改操作，因为同样修改表中元素所以传入其本身
* ListGetElem(L,i) 获取操作，因为并不需要修改表，所以只需要副本即可
* ElemIsNull(L) 判空操作，同样因为不需要修改表，所以只需要副本即可
* GetLength_List(L) 获取表长 同理
* DestroyList(&L) 销毁操作，因为要销毁表本身，所以要传入本身
* ShowList(L)
*/
#include< stdio.h >
#include< iostream >
#include< stdlib.h >//开辟内存空间必需的头文件
using namespace std;
//线性表的实现
//1.有限的序列
//2.序列中的每个元素都有唯一的前驱和后继，除了开头和结尾两个节点
//3.逻辑顺序与物理顺序相同
#define MaxSize 30//定义线性表的最大长度
//线性表的存储类型描述
typedef struct
{
int data[MaxSize];
int length;
}List;//List是别名 是整个结构体定义语句的替代者
bool InitList(List& L);
int ListInsert(List& L, int i, int e);
bool ListDelete(List& L, int i, int& e);
bool ListAlert(List& L, int i, int e);
int ListGetElem(List L, int i);
bool ElemIsNull(List L);
int GetLength_List(List L);
void DestroyList(List& L);
int ShowList(List L);
bool InitList(List &L)//初始化
{
for (int i = 0; i < MaxSize; i++)
{
L.data[i] = 0;
L.length = 0;
}//一般初始化都是这样吧？如果没有赋值就会出现混乱
return true;
}
int GetLength_List(List L)//获取表长
{
//首先这个函数我本来不想添加的，因为结构体中的一个表长元素已经定义了表长
//实现的角度来看就是将，结构体中的length赋值返回
return L.length;
//其实我是很纠结要不要减一的，被题目骗怕了
//但是仔细一想，表长就是元素的个数，而不是数组小标
}
int ListInsert(List &L, int i,int e)//插入
{
//插入的算法的实现，就是传入插入的位置以及插入的元素值
//其实我们拿到了表的本身也好改
//我们先遍历到需要插入的，nonono，我突然想到，这位置不就是数组的下标-1吗？我把链表搞混了
//但是我们的基本盘不变，要让程序变得壮硕
//我们还要判断表能不能插入，有没有位置
while(i <= 0 || i > MaxSize)
{
printf("插入输入不合法！请重新输入\n");
scanf_s("%d%d", &i, &e);
}
if (L.length == MaxSize)
{
return 1;//1代表表现在已经不能插入数据了
}
//接下来我们就可以插入操作了记住数组的插入等，是需要将其后面的元素全部后移的
//此时我们的插入位置i，并不是下标，而是下标+1=插入位置i
for (int j = L.length -1 ; j >= i - 1;j--)
{
L.data[j + 1] = L.data[j];//我们这时候执行的是将插入位置（包括插入位置）的元素全部后移
}
//后移完成以后，我们将元素插入
L.data[i - 1] = e;
L.length++;//记得将长度加一
return 2;//2代表程序已经成功插入元素
}
bool ListDelete(List &L, int i, int &e)//删除
{
//表的元素删除操作，这不是删除表，而是删除表中的元素
//删除是和增加反着来的，就是删了以后它后面的全部元素前移
//第一步我们还是健壮性
if (!ElemIsNull(L))
{
return 0;//返回0代表的是表是空的，没办法进行删除
}
//删除的位置一定是在表长范围内的
if (i > L.length)
return 0;
//第二步就是删除了，我们还是先前移，再删除
//等等，你有没有发现，我既然前移了，我直接把你覆盖不就是删除了？
//牛逼,我们先把元素传出去
e = L.data[i - 1];
for (int j = i - 1; j < L.length - 1; j++)//为什么这里是表长 -1 ，而且还是小于号？就是我们不是想前移动吗？
//假如此时j是倒数第二个，j++不就是倒数第一个了，这就是最后一次循环
{
L.data[j] = L.data[j++];
}
return 1;//成功删除返回一
}
bool ListAlert(List&L,int i,int e) //修改
{
//判断表是否空，同时，修改的这个元素是否在表中，也就是这个删除的位置一定是小于等于表长的
if (!ElemIsNull(L))
return false;
if (i > L.length)
return false;
//表的修改，我有点感觉多余了，但是这也是我学数据库得来的，增删改查一个不少
L.data[i - 1] = e;
return true;//修改成功返回真
}
int ListGetElem(List L,int i)//获取元素值
{
//同样判断表空以及位置是否越界
if (!ElemIsNull(L))
{
printf("表空\n");
return 0;
}
if (i > L.length)
{
printf("你要删除的不存在\n");
return 0;
}
//直接返回就行了
return L.data[i - 1];
}
bool ElemIsNull(List L)//判空
{
if (L.length == 0)
{
return false;
}
if (L.length != 0)
{
return true;
}
}
void DestroyList(List &L)//销毁
{
//销毁的操作,但是这个不是动态分配的内存所以不能手动销毁
//这个是栈上的内存
}
int ShowList(List L)
{
if (!ElemIsNull)
{
printf("表是空的或者不存在\n");
return 0;
}
else {
for (int i = 0; i < L.length; i++)
printf("|%d|\n", L.data[i]);
}
return 1;
}
int main()
{
int i = 0;
int j=0, e=0;
List L;
printf("请选择你的操作：\n1.初始化\n2.增加元素\n3.修改元素\n4.删除元素\n5.查找元素\n6.打印所有元素值\n7.结束\n");
scanf_s("%d", &i);
while (i != 7) {
switch (i) {
case 1:
if (InitList(L))
{
printf("初始化成功\n");
}
break;
case 2:
printf("请输入插入位置以及值\n");
scanf_s("%d%d", &j, &e);
ListInsert(L,j,e);
break;
case 3:
printf("请输入需要修改的元素位置\n");
scanf_s("%d", &i);
printf("请输入需要修改的值\n");
scanf_s("%d", &j);
ListAlert(L, i, j);
break;
case 4:
printf("请输入需要删除的位置\n");
scanf_s("%d", &j);
ListDelete(L,j,e);
printf("第%d个元素值%d删除成功\n", j, e);
break;
case 5:
printf("请输入你要查找的第几个元素\n");
scanf_s("%d",&j);
e = ListGetElem(L, j);
printf("第%d个元素的值为%d\n",j,e);
break;
case 6:
ShowList(L);
break;
case 7:
return 0;
break;
}
printf("请选择你的操作：\n1.初始化\n2.增加元素\n3.修改元素\n4.删除元素\n5.查找元素\n6.打印所有元素值\n7.结束\n");
scanf_s("%d", &i);
}
return 0;
}
后缀表达式 的求值与转换 四则运算表达式转化为后缀表达式的规则：
1.数字直接写
2.运算符号如果级别高于栈顶的，直接入栈写上，如果等于或者低于栈顶的让栈顶先出，自己再进去
3.左括号不管入，遇到右括号，将左括号上面的所有出栈
我们来举个例子：9+（3-1）×3+10
数字直接写：9
然后就是+号，符号入栈
这
是
个
栈
+
然后就是（入
这
是
个
栈
+
(
9+（3-1）×3+10，然后就是3，直接写
93
然后就是-入
这
是
个
栈
+
(
-
9+（3-1）×3+10，然后就是1，数字直接写
931
然后就是）右括号，你瞧，直接打包出来，其实也没有就一个-号，收获不大啊，竹篮打水一场空
931-
这
是
个
栈
+
然后就是x，和此时的栈顶+比较，谁牛逼，显然x牛点，所以入栈
这
是
个
栈
+
x
9+（3-1）×3+10，然后就是3，数字直接写
931-3
然后就是+，比较栈顶的x，哦豁，没有它厉害，乖乖让x出来
就是
931-3x
此时栈：
这
是
个
栈
+
还没有完，还要继续比较现在的栈顶，是+和即将入的+是相等的，让栈顶出来
931-3x+
这
是
个
栈
这个时候，我们的+再入栈
931-3x+
这
是
个
栈
+
9+（3-1）×3+10，然后就是10，数字直接写
931-3x+10
然后没了，栈里面的给我滚出来吧
931-3x+10+
1.当是数字的时候直接入栈
2.当是运算符号的时候
3.就将栈的最上面两个数拿出进行运算 后 再将结果进栈 记住（栈顶元素永远在运算符号的右边）
看9 3 1 - 3 * + 10 2 / +
9 3 1依次入栈，没有异议
这
是
个
栈
9
3
1
接下来是-，取出栈顶的两个元素，分别是1 3，1是栈顶，放-号的右边
就是3-1=2
将2入栈
这
是
个
栈
9
2
9 3 1 - 3 * + 10 2 / +接下来是 3 入栈
这
是
个
栈
9
2
3
9 3 1 - 3 * + 10 2 / +接下来是*，取出来运算
2*3=6，即便是*这种不在意次序的，你也务必养成习惯将栈顶放右边
6入栈
这
是
个
栈
9
6
9 3 1 - 3 * + 10 2 / +接下来是+，取出运算
9+6=15，15入栈
这
是
个
栈
15
9 3 1 - 3 * + 10 2 / +接下来是10，数字入栈
这
是
个
栈
15
10
9 3 1 - 3 * + 10 2 / +接下来是
2入栈
这
是
个
栈
15
10
2
9 3 1 - 3 * + 10 2 / +接下来是/，取出两个运算
10/2=5入栈
这
是
个
栈
15
5
9 3 1 - 3 * + 10 2 / +接下来是+，取出来运算
15 + 5 = 20
好了，这就是最后结果了，不信你自己算嘛，给你9+（3-1）x 3+10/2
时间复杂度、空间复杂度
#include < iostream >
#include < vector >
using namespace std;
bool find(vector< int > &nums);
int main()
{
//时间复杂度，假设输入的数据量大小为N
//时间复杂度统计的是【计算的操作数量】而不是【运行的绝对时间】
//其次【计算的操作数量】和【运行的绝对时间】的正相关(并不是相等)
//再次，运行时间受到【运行环境、语言、处理器】的影响
//⬯[最差]、⊝[平均]、Ω[最佳]
vector< int > a;
a.push_back(1);
a.push_back(2);
a.push_back(7);
if (find(a))
{
cout << "找到啦！" << endl;
}
else
{
cout << "没有找到" << endl;
}
}
bool find(vector< int > &nums)
{
for (int i=0;i < nums.size();i++)
{
if (nums[i] == 7)
{
return true;
}
}
return false;
}
//最好的情况就是【7,a,b,c,e,d,da,a,s,sa,】第一次就找到了
//最坏的情况就是整个数组都没有7，循环了一遍也没有
//常见的算法时间复杂度有：⬯(1)<⬯(log N)<⬯(N)<⬯(N log N)<⬯(N²)<⬯(2^N)<⬯(N!)
//⬯(1)表示运行次数不随输入数据大小N的变化而变化
int algo(int N)
{
int a = 1;
int b = 2;
int x = a * b + N;
return 1;
}
//⬯(N)运行次数和N大小是线性关系
int algo1(int N)
{
int a = 0;
for (int i = 0; i < N; i++)//运行了N次
{
a++;
}
return a;
}
//⬯(N²)表示运行次数和N还是线性关系，但是是N²的关系
int algo2(int N)
{
int a = 0;
for (int i = 0; i < N; i++)//此处运行了N次
{
for (int j = 0; j < N; j++)//又运行了N次
{
a++;
}
}//总体上运行了N的平方次
}
//⬯(2^N)是指数级，类似我们的细胞分裂，一分为二，二分为四，四分为八
int algo3(int N)
{
if (N <= 0)
return 0;
int a = algo3(N - 1);//递归调用，自我递归叫做直接递归
int b = algo3(N - 1);//这两个式子，就是让每一个都可以一分为二
return a + b;
}
//⬯(N!)这个是一开始分裂的是N个，然后每一层分裂比上一层少一个
int algo4(int N)
{
if (N <= 0)return 1;
int a = 0;
for (int i = 0; i < N; i++)
{
a += algo4(N - 1);//为什么这里用循环，因为循环的次数的外层循环×上内层循环的次数，每向内一层的循环次数-1就能达到我们想要的效果
}
return a;
}
//⬯(log N)对数阶和指数阶是相反的，指数阶是每轮分裂，这个是每轮结合，也就是八合四，四合二，二合一
int algo5(int N)
{
int a = 0;
float i = N;
while (i > 1)
{
i = i / 2;
a++;
}
return a;
}
//⬯(N log N)，相信你已经明白了，不就是套个N的循环嘛，yes
int algo6(int N)
{
int a = 0;
float i = N;
while (i > 1)//while循环次数为log N，因为每次减半
{
i = i / 2;
for (int j = 0; j < N; j++)//循环次数为N
{
a += 1;
}
}
return a;
}
//------------------------------------------------------------------------
//空间复杂度
//栈帧空间
int test()
{
return 0;
}
int algor(int N)
{
for (int i = 0; i < N; i++)
{
test();//这个循环中每次调用函数test以后，栈帧空间就会被释放
}
}//因此这个函数的空间复杂度为⬯(1)
//---------------------------------------
int algor1(int N)
{
if (N <= 1)
{
return 1;
}
return algor1(N - 1) + 1;//注意这是个递归函数，每次使用了，栈帧空间是不释放的
}//因此空间复杂度为⬯(N)
链表例题
问题如下：我们实现图书的管理员手上有一张链表图书表，其中int为图书编号，现在我们需要倒序输出图书的编号
#include< stdio.h >
#include< iostream >
using namespace std;
struct book
{
int head;
book* prev;
book* next;
};
int main()
{
int a = 0;
cout << "请输入你想要添加书本的数量" << endl;
cin >> a;
cout << sizeof(book) << endl;
book* b = (book*)malloc(sizeof(book));
book* p = b;
for (int i = 0; i < a; i++)
{
int j = 0;
cout << "请输入第"<< i+1<<"本书的编号" << endl;
cin >> j;
b->head = j;
//book* temp = b;
b->next = (book*)malloc(sizeof(book));
b->next->prev = b;
b = b->next;
//b->prev = temp;
}
b = b->prev;
cout << "书本倒序的编号为：" << endl;
for (int i = 0;i < a;i++)
{
cout << b->head << endl;
b = b->prev;
}
return 0;
}
我们具体来分析一下思路，结构体定义，没话可说吧？我一开始只定义了后续节点的指针，导致我倒序输出，没办法，当然硬实现还是可以的，反正耍赖谁都会
我是那种理论学的太多了，实践就傻眼了，结构体初始化，我竟然还是数组的那种思想
就是我以为一开始就初始化好就行了，但是细看就是内存谁知道在哪里，怎么初始化？我这段话看起来可能有点语无伦次
事实上也是如此，好了，就是说链表其实是动态的主动的给分配内存的，b->next = (book*)malloc(sizeof(book));的作用就是分配内存
栈与队列
栈是限定在表尾进行修改操作的线性表
允许操作的一端为栈顶(top)，另一端为栈底(bottom)
ADT 栈
Data
同线性表，元素具有相同类型，相邻元素具有前驱和后继关系
Operation
InitStack(*S):初始化，建立栈
DestroyStack(*S):若栈存在就摧毁
ClearStack(*S):将栈清空
StackEmpty(S):若栈为空，返回true，否则返回false
GetTop(S,*e):若栈存在且非空，用e返回栈顶元素
Push(*S,e):若栈存在，插入新元素e到栈中成为新栈顶
Pop(*S,*e):删除栈S中栈顶元素，并用e返回其值
StackLength(S):返回栈S的元素个数
endADT
别觉得不重要，当你真的到那种境界的时候，看以上的东西就够了
别问，问就是答：我当然没有到那种境界了
----------------------------------------
typedef struct
{
int data[MaxSize];//栈
int top;//栈顶指针
}stack;
-----------------------------------------
下载 本页面PDF