0%

  模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的子串,这就是模式匹配。

1、Brute-Force模式匹配算法

  Brute-Force算法的思想是:在主串S=”s1,s2,s3,…,sn”中的第一个字符与模式串T=”t1,t2,t3,…tn”中的第一个字符开始匹配,如果相等,则比较S串第二个字符和T串中的第二个字符。如果T串中的每个字符都与S串中连续的字符匹配成功,则返回S串中第一个下标的位置。如果匹配不想等,则将S中的第二个字符与T中第一个字符匹配,然后一次匹配下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# include<stdio.h>
/*
S[] 是主串
T[] 是模式串
pos 是指在S中第pos个位置开始匹配,我设置为0
return i 如果匹配成功,返回 子串在S中第一个位置的下标。 匹配失败,返回-1
*/
int index_BF(char S[],char T[], int pos)
{
int i = pos;//i是S中的位置
int j = 0; //j是T中的位置
while(S[i] != '\0' && T[j] != '\0'){
if(S[i+j] == T[j]){ //两个字符判断成功,则j+1.判断下一个字符
j++;
}else{ //判断失败,则将T第一个与S第二个匹配 。于是i+1,S取下一个。j=0,T重新开始匹配
i++;
j = 0;
}
}
if(T[j] == '\0'){ //T中所有字符与S中连续字符匹配成功。
return i;
}else{
return -1;
}
}
int main()
{
char S[] = "qwertyuiop";
char T[] = "io";
int pos = 0;
int index = index_BF(S,T,pos);
printf("%d",index);
return 0;
}

2、KMP模式匹配算法

  看了一晚上终于明白KMP算法。KMP算法使用一种预先处理的方式。首先将模式串自我匹配。
Alt text
这个图中我们可以看到,刚开始出现的是a,b,c,于是我们就在模式串中找到a,b,c。通过这种自我匹配的方式,找到模式串可能出现的位置。
那么模式串是怎样自我匹配的呢。这里有前缀和后缀的概念。
Alt text
这样就能判断字符串前部和后部是不是有重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>  
#include <string.h>

int next[32] = {-999};

/*这个函数就是对模式串预处理
将预处理的信息保存到next数组中。
整个程序只运行一次这个函数

*/
void get_next(char T[])
{
int k = -1;
int j = 0;
int tLen = strlen(T);
next[j] = k; //模式串第一个设置为-1
while (j < tLen - 1)
{
if ( (k == -1) || (T[j] == T[k]) )
{
k++;
j++;
next[j] = k;
}
else
{
k = next[k];
}
}
}
int index_KMP(char S[], char T[], int pos)
{
int i = pos;
int j = 0;
int sLen = strlen(S);
int tLen = strlen(T);
while ( i < sLen && j < tLen )
{
/* j = -1 表示next[0]*/
if ( (j == -1) || S[i] == T[j])
{
i++;
j++;

}
else
{
printf("j == %d\t",j);
j = next[j]; //next[j]里面存的是开始匹配的位置。

}
}

if (tLen == j) //表示整个T都对比完了,匹配成功了
{
return i - tLen ;
}
else
{
return -1;
}
}

int main(void)
{
char s[] = "qwertyuiop";
char t[] = "io";
int i;
int pos = 0;
int index;
// 预处理next数组
get_next(t);
index = index_KMP(s, t, pos);
printf("%d\n", index);

return 0;
}

Alt text

冒泡排序

  冒泡排序是最基础的排序算法,冒泡排序不断对比两个相邻的元素大小,将顺序错误的值交换。将大的值交换到数组的底部,过程像冒泡一样。排序算法时间复杂度是O(n^2)

1
2
3
4
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# include<stdio.h>
/*冒泡排序*/
void bubble_sort(int *list)
{
int length= 10; //数组长度
int tempNum;
for(int index = 0;index < length;index++)
{
for(int i = 1;i < length- index;i++)
{
if(list[i-1] > list[i]){
tempNum = list[i-1];
list[i-1] = list[i];
list[i] = tempNum;
}
}
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
bubble_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

选择排序

  选择排序是一种不稳定的排序。选择排序是将数组中最小(或最大)的值找出来,放到第一个位置上,然后在剩余的元素中找到最小(或最大)的值,放到第二个位置上。选择排序时间复杂度是O(n^2),最好时间复杂度也是O(n^2)。
  假如有数组[5,5,3],使用选择排序进行排序,最小值3会和第一个5互换位置,这就导致第一个5挪到第二5后面,所以选择排序是不稳定的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# include<stdio.h>
/*选择排序*/
void selection_sort(int *list)
{
int length= 10; //数组长度
int tempNum;
for(int index = 0;index < length;index++)
{
for(int i = index;i < length;i++)
{
if(list[index] > list[i]){
tempNum = list[index];
list[index] = list[i];
list[i] = tempNum;
}
}
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
selection_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

直接插入排序

  直接插入排序是将待排序的值,插入到前面已经排序好的值中,直到所有的值插入完。数组中的第一个值默认已经排序。直接插入排序的时间复杂度是O(n^2 )

1
2
3
4
5
6
从第一个元素开始,该元素可以认为已经被排序
取出下一个元素,在已经排序的元素序列中从后向前扫描
如果该元素(已排序)大于新元素,将该元素移到下一位置
重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# include<stdio.h>
/*插入排序*/
void insert_sort(int *list)
{
int length= 10; //数组长度
int key; //存放要插入的值
for(int index = 1;index < length;index++) //这里是从1开始遍历,因为默认0是已经排序完的
{
key = list[index];
for(int i = index-1;i >= 0;i--)
{
if(list[i] > key){
list[i+1] = list[i];
list[i] = key;
}
}
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
insert_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

折半插入排序(二分插入排序)

  折半插入是对直接插入的优化。由于直接插入算法中,需要将排序的元素依次插入前面排好序的元素中。折半查找减少了比较的次数,但是没有减少移动次数,所以算法时间复杂度还是O(n^2 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# include<stdio.h>
/*插入排序*/
void binary_insertion_sort(int *list)
{
int length= 10; //数组长度
int key; //存放要插入的值
for(int i = 1;i < length;i++) //这里是从1开始遍历,因为默认0是已经排序完的
{
key = list[i];
int left = 0;
int right = i - 1;
while(left <= right)
{
int mid = left + (right - left) / 2;
if(key < list[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
/*因为要排序的元素前面的元素是有序的,所以必须将left后面的元素向后移动位置
这样才能空出来位置将要排序的元素插入进去。
*/
for(int j = i-1;j >= left;j--)
{
list[j+1] = list[j];
}
list[left] = key;
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
binary_insertion_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

希尔排序

希尔排序也是插入排序的一种,也称为缩小增量排序,是一种不稳定排序。
以下面的数据为例 {12,43,56,54,23,10,3,65,84,2},整个数据数量为10,,设置步长为5。则数据可以排列为:
12 43 56 54 23
10 3 65 84 2
然后对每一列排序,变为:
10 3 56 54 2
12 43 65 84 23
然后将步长改变为2,将上面的数据重新排列为:
10 3
56 54
2 12
43 65
84 23
然后对上面的数据按列排序,最后,将步长改为1,再按照列排序。即完成排序过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# include<stdio.h>
/*希尔排序*/
void binary_insertion_sort(int *list)
{
int length = 10;
int dist = length / 2; //步长
int key;
int j;
while(dist > 0)
{
for(int i=dist;i < length;i++)//从第二排,第一个元素开始遍历,知道最后一个
{
key = list[i];
j = i; //i是该元素原来的位置,j是对比过后,改变的地址
while(j >= dist && key < list[j-dist])//找到前面的同列中是不是有小的,遍历一遍
{
list[j] = list[j-dist];
j -= dist;
}
list[j] = key;
}
dist /= 2; //增量减半
}
}
int main()
{
int list[10] = {12,43,56,54,23,10,3,65,84,2};
binary_insertion_sort(list);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

归并排序

  归并排序是将两个已经排序好的数组合并,使用分治思想。我这里只实现了对数组的合并,可以使用递归对数组排序,使用2路归并算法。算法时间内复杂度为O(nlgn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# include<stdio.h>
/*归并排序*/
void merge_sort(int *list,int *list1,int *list2)
{
int length_list1 = 5;
int length_list2 = 5;
int j = 0;
int key = 0;
for(int i=0;i<length_list1;i++)
{
while(list2[j] < list1[i] && j < length_list2)
{
list[key] = list2[j];
key++;
j++;
}
list[key] = list1[i];
key++;
}
if(j < (length_list2-1))
{
for(int k=j+1;k<length_list2;k++)
{
list[k] = list2[k];
}
}
}
int main()
{
int list1[5] = {2,15,18,34,87};
int list2[5] = {4,21,43,54,65};
int list[10];
merge_sort(list,list1,list2);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

快速排序

  快速排序是随意选择一个元素作为基准数字,比基准数字大的在右边,比基准数字小的在左边。这样来快速排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# include<stdio.h>
/*快速排序*/
/* 这里是排序 */
int quick_sort(int *list,int i,int j)
{
int base = list[i];
while(i < j)
{
while(i < j && list[j] >= base)
{
j -= 1;
}
while(i < j && list[j] < base)
{
list[i] = list[j];
i += 1;
list[j] = list[i];
}
list[i] = base;
/* 测试输出每一次的变化
for(int k = 0;k < 10;k++)
{
printf("%d\t",list[k]);
}
printf("\n");
*/
}
return i;
}
/* 这里是一个递归*/
void recursion(int *list,int i,int j)
{
int base = 0;
if(i < j)
{
base = quick_sort(list,i,j);
recursion(list,i,base);
recursion(list,base+1,j);
}
}
int main()
{
int list[10] = {2,15,18,34,87,4,21,43,54,65};
int i = 0;
int length = 10;
recursion(list,i,length-1);
for(int i = 0;i < 10;i++)
{
printf("%d\t",list[i]);
}
return 0;
}

Alt text

Alt text

1、数制转换


实现十进制N转其他d进制数,简单的算法基于:

1
N = (N div d) x d + N mod d   //其中div:整除运算,mod:取余运算

例如:(1348)10 = (2504)8

N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
1
2
3
4
5
6
7
8
9
10
11
12
13
/*  输入任意的一个非负的十进制整数,输出其对应的八进制数*/
void conversion(){
InitStack(S); //初始化一个栈S
scanf("%d",N);
while(N){
Push(S, N % 8);
N = N / 8;
}
while(){
Pop(S,e);
printf("%d",e);
}
}

图示:

Alt text


2、人工模拟栈代替系统栈

2.1什么是系统栈?

说起系统栈,不得不提一下在操作系统中内存的用途,不管什么操作系统,进程调用的内存一般分成四个部分:

1
2
3
4
代码区:存储被装入执行的二进制机器代码,处理器到这个区域读取指令
数据区:存储全局变量
堆区: 进程可以在堆区动态申请一部分内存,用完之后归还给堆区。动态分配和回收是堆区的特定。
栈区:用于动态的存储函数之间的调用关系。保证调用函数返回时恢复到母函数中继续执行。

这里的栈区就是指的系统栈。系统栈对于高级编程语言是透明的,它主要实现高级语言中的函数调用。如果你还没明白,不要紧。现在以这个C语言的例子来简单说一下系统栈的作用。

1
2
3
4
5
6
7
8
9
10
# include<stdio.h>
int func_a()
{
//return
}
int main()
{
int var_num = 0;
func_a();
return 0;

  当CPU执行func_a函数的时候,需要在main函数中的代码区找到跳转到func_a函数的机器指令,取指并执行后,func_a函数执行完毕之后,它是怎么返回到main函数中的呢?
  这些函数之间的跳转都是通过系统栈的配合来完成的,当函数被调用时,系统栈会为这个函数开辟一个新的栈帧,并压入系统栈中,当函数返回时系统栈会弹出该函数对应的栈帧。

2.2 人工模拟栈

1
2
3
4
5
6
7
8
int func(int n)
{
if (n <= 1)
{
return 1;
}
return n * func(n -1);
}

  这个递归的例子,函数不断的递归,需要不断的调用系统栈。 下面来实现人工模拟系统栈实现这个递归函数的运行过程。

1
2
3
4
5
6
7
8
9
10
11
12
do{
if(! back) {
if(n <= 1) {
back = ture, ret = 1; //判断是不是该返回了
continue;
}
n进栈; //将n的值存到栈中
--n;
}else{
ret *= 出栈; //这里是栈返回的时候执行的。
}
}while(栈不为空)

参考资料

栈:
  严, 蔚敏, 吴, 伟民. 数据结构(C语言版)[J]. 计算机教育, 2012, No.168(12):62-62.
系统栈:
  佚名. 0day安全:软件漏洞分析技术(第2版)[J]. 信息安全与通信保密, 2013(11).

  在数据结构这门课,老师讲到实现动态顺序存储方式。给出了一个最好的办法:将数组扩大一倍,复制过去。
   具体来说。以数组为例,我们都知道初始化一个数组,需要给数组规定一个大小。因为数组的大小是固定的,一旦元素超过了数组的固定大小,就会产生错误。这时我们需要开辟一个新的空间,假设原来数组大小是X,则新开辟空间的大小是2X。将原来的数据复制到新的空间。原来的空间释放掉。

经过四次空间扩大
  这里就会出现均摊时间复杂度。我们知道,假设n个数据,此时复制操作的时间复杂度是O(n)。因为是扩大了一倍,此时整个数组的大小是2n,我们还可以再继续存放n个数据。数组插入的时间复杂度是O(1),只有剩余的n个空间全部插入数据才会开辟新的空间。
  开辟空间时间复杂度是O(n),而执行完n次插入数据才会再继续开辟空间,插入数据的时间复杂度是O(1),这n次插入数据操作平分开辟空间O(n)的时间复杂度,所以每次插入数据的时间复杂度都是O(1)。这就是均摊时间复杂度。
  C++中的vector(向量)就是这种方式实现动态的数组。

一、文件和用户权限

1.文件详细信息

  使用ls -l可以查看文件详细信息
Alt text
在显示的文件详细信息中:
  1列:表示文件的属性。“-”表示文件,“d”表示文件夹,“l”表示快捷方式(链接)
  2-4列:表示当前用户对文件的操作权限
   1). r 可读 2^2 = 4
   2). w可写 2^1 = 2
   3). x可执行2^0= 1 (最高权限是7)
  5-7列:表示当前用户所在的用户组对文件的操作权限
  8-10列:表示当前用户所在的用户组以外的用户对文件的操作权限
  11列:代表文件的链接数
  12列:代表当前用户
  13列:代表当前用户所在的用户组
  14列:代表文件大小
  15列:代表文件创建或修改时间

2.更改文件所属用户和用户组

1
2
3
  chown  用户名   文件名    #改变文件所属用户名
  chgrp 用户组 文件名 #改变文件所属的用户组
  chown 用户名:用户组 文件名 #直接改变用户名和用户组

3.更改文件权限

  上面介绍了文件的三种权限,分别是当前用户权限,当前用户组权限,用户组以外的用户权限,权限最高是7。

1
  chmod   700  文件名   #当前用户有所有权限,其他用户没有权限.

  使用这个语句来改变文件的操作权限。

删除文件

rm -d 目录名 #删除一个空目录
rmdir 目录名 #删除一个空目录
rm -r 目录名 #删除一个非空目录
rm 文件名 #删除文件

二、SSH服务器远程登录

1.映射关系

  我使用两台虚拟机来模拟多台服务器之间的远程登录。使用Vmware虚拟机,安装了两个ubuntu(ubuntu kylin 16.04 LTS)的系统。
  首先通过ifconfig查看两台linux的ip地址。如下图所示:
Alt text

Alt text
  使用vim打开vim /etc/hosts 查看ip和域名之间的映射关系(这里的域名是指电脑的名称,例如我的电脑名是:work1-pc,另一台电脑的名称是:gavin-pc。使用vim /etc/hostname 可以更改这个域名,不会使用vim的可以直接在/etc/hostname这个路径里面找到hostname文件,直接使用gedit 打开。注意:这里的电脑名不是管理员用户名!),当我们要访问远程服务器的时候,可以直接访问域名,远程服务器就会自动解析/etc/hosts 来定位远程机器的ip地址,从而访问远程机器。打开/etc/hosts文件:

Alt text
  在这个我们可以看到,work1-pc域名对应的ip地址是127.0.1.1,都是本机地址。使用work1-pc,要想ping gavin-pc,我们可以ping 192.168.111.136.但是如果我们想直接ping gavin-pc,只能把192.168.111.136 gavin-pc 这个映射关系添加在work-pchosts文件中。于是这样:
Alt text
这时我们直接ping gavin-pc 就能ping通。同理,我们可以在另一台电脑ping通这台电脑,这里就不演示了。

Alt text

2.SSH远程登录

  SSH是linux中一种网络协议,用来计算机中加密登录,是在用户计算机中登录另一台远程计算机。
  首先安装SSH和rsync自动同步服务

1
2
apt-get install ssh   安装ssh服务
apt-get install rsync 安装自动同步服务

安装完SSH,可以使用SSH localhost来测试SSH服务是否安装成功。
Alt text
  SSH是由客户端和服务端,这里我两个电脑都安装了客户端和服务端。
  那么一台计算机是怎样通过SSH来远程控制另一台电脑的呢?这里要说一下SSH的公钥加密方式。

1
2
3
  1.远程主机接收到用户的登录请求,主机就会把自己的公钥发给用户计算机;
  2.用户使用公钥,然后把加密后的登录密码发送给远程主机;
  3.远程主机使用自己的私钥,解密登录密码,如果正确同意登录。

  但是这种加密方式是有风险的,因为如果一个人伪造公钥,将公钥发送给用户,解密登录密码后登录远程主机。这就是中间人攻击
  SSH协议使用口令登录的方式来解决这个问题。当第一次登录的时候,会显示:
Alt text
  显示无法验证远程主机的真实性,知道公钥,询问是否连接。
  远程主机将用户的公钥,保存在登录后的用户主目录的**/.ssh/authorized_keys文件中。公钥就是一段字符串,只要把它追加在authorized_keys文件的末尾就行了。于是我们可以将远程主机的公钥文件~/.ssh/id_rsa.pub复制到用户计算机上,然后将公钥文件追加到authorized_keys文件中,然后将追加过的authorized_keys文件,直接覆盖远程主机的authorized_keys**文件,于是此时两台计算机可以相互通过SSH连接。

1
2
3
4
5
6
gavin-pc中:
root@gavin-pc:~# scp ~/.ssh/id_rsa.pub root@work1-pc:/root/Downlpads //将公钥文件发送到work1-pc的downloads文件夹中

work1-pc中:
root@work1-pc:~/Downloads# cat ~/.ssh/id_dsa.pub >> ~/.ssh/authorized_keys //将公钥追加进authorized_keys文件中
root@work1-pc:~# scp ~/.ssh/authorized_keys root@gavin-pc:~/.ssh/authorized_keys //将authorized_keys 文件,同步到gavin-pc中

  操作完成后,可以通过任意一台计算机远程连接另外一台计算机。