c++ 执行期语意学

执行期和编译期的理解

• 执行期：此时是对已经编译等生成的可执行文件装载到内存并调用cpu将其作为一个进程执行的过程，对c.c++来说程序的入口为main,即第一条指令是执行main函数开始的，而c++可能会加入一些额外的代码，所以实际写的第一条语句和执行的第一条语句可能有偏差；
  阅读全文 »

ping and traceroute

ping

ping是ICMP中的回显报文类型：

• ping 对应的icmp，type字段为0/8,code字段为0
• ICMP回显请求和应答报文格式：
  阅读全文 »

leetcode_string

传统字符串匹配：

• 简单写写,变量命名等就先不纠结了

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

int strStr(char s[],char p[])
{
		if(s[0]=='\0'||p[0]=='\0')
				cout<<"p or s is null"<<endl;
		int k=0,j=0,i=0;
		for(i=0,j=0;s[i]!='\0'&&s[k]!='\0';)
		{
		     if(p[j]=='\0')
				   break;	 
			 if(s[k]==p[j])
			 {
					 k++;
					 j++;
			 }
			 else //不匹配时重新来过
			 {
					 i++;
					 k=i;
					 j=0;
			 }
		}
        if(p[j]=='\0')
				return i;
        else 
				return -1;
}```
#### kmp匹配算法
kmp算法：基本过程见另一篇文章数据结构之字符串<!--more-->，这里贴写代码(未经大数据检验，谨慎观看)
```cpp
int nextfunc(char p[],int next[])
{
   next[0]=-1;
   next[1]=0;
   int j=1;
   int k=0;
   while(p[j]!='\0')
   {
		   if(k==0||p[j]==p[k])
		   {
				   ++j;
				   ++k;
				   next[j]=k;
		   }
		   else
				   k=next[k];
   }
   return 0;
}

int kmp(char s[],char p[])
{
   int i=0;
   int j=0;
   int next[100];
   nextfunc(p,next);
   for (i=0;s[i]!='\0'&&p[j]!='\0';i++)
   {
		   //if(j==-1)j=0;
		   if(s[i]==p[j])
		   {
		     j++;
			 continue;
		   }
		   while(s[i]!=p[j]&&j>=0)j=next[j];
		   j++;
   }
  if(p[j]=='\0')
		 return i-j;
  else 
		 return -1;
} 

简单测试

1
2
3
4
5
6
7
8
9
10

int main ()
{
		char a[19]={'a','b','c','a','b','c','a','s','s','f','r','e','r'};
		char b[10]={'a','b','c','a','s'};
		int pos=strStr(a,b);
		cout<<pos<<endl;
		int pos2=kmp(a,b);
		cout<<pos2<<endl;
		return 0;
}

其他字符串算法题目：

判读字符串是否为回文串

• 所谓回文串即正者读反着读都一样：
• 解决方案：
  • 1.设置两个索引，一个从字符串开始位置往后走，一个从字符串最后的位置往前走，比较这两个索引指向的字符是否相等，直到遍历完整个字符串；注意这里其实并不需要遍历整个字符串，一个索引只需要走一半就可以，回文串两边对称的。
  • 2.利用栈，思路类似

字符串转整数(atoi)

• 分析：这个题目需要注意的是各种不规则的输入和其他边缘条件如int整数的范围等
• 解决方案:
  • 若是严格的检查，则判断字符ASCII码是否在0-9之间，注意整数的首位不能为0）；整数的正负；数据是否溢出；是否数据的表现形式如33x8fe；等等。
  • 非严格的检查，如遇到非法的字符跳过即可；首位为0时跳过或者当成八进制等等

对两个二进制字符串求和

• 如”111”+”101”=”1100”
• 解决方案：
  • 1. 像十进制那样直接求和，进位，从最右边的字符开始，若相加大于1则进位，注意两个字符串可能一个很长一个很短，而进位可能一直需要延续
  • 2.将两个字符串分别转换为十进制再做运算，结果再转为二进制

最长回文子串

• 暴力方法：将所有子串列出来先判断哪些是回文串，再取长度最长的；

  正则表达式

• 我对正则表达式的处理方案一直很倾向于用状态机，这种方法可以用图表示出来，方案的完备性好判断，别人也好理解；
• 递归方案

  最长公共前缀

• 找出字符串数组中的最长公共前缀：给定一个字符串数组，找出他们的最长公共前缀
• 分析：这道题目需求不明确，是需要 所有的字符串=都有的公共前缀还是若只有部分字符串有公共前缀也可以？也可能我理解有误~

实现strtod()函数

• 即判断一个字符串是否表示一个数字如:”1.0”
• 分析：可以用状态机实现

整数和罗马数字的相互转换

• 这道题有些无聊

  count and say

• 一个数列如下：
  1 11 21 1211 111221,…
  意思是1,第二个表示第一个的情况，即1个1故为11,第三个数表示第二个数的情况，即两个1,21，以此类推
• 求数列中的第n个数
• 解决方案，直接模拟，一个一个算出来

Anagrams:

• 字符串中的打乱字母顺序从而得到新的单词如eat打乱后得到tea等

给定绝对路径简化它

在一个英文句子中找到最后一个单词的长度

数据结构之串

欢迎来到简单而又复杂的串世界,博主许久没有去研究串，还停留在以前学习和使用串的水平，再来一波学习和归纳，发现串的基本用法其实简单，也好理解，但是衍生出来的和应用相关，而且复杂，下面道来；

IP选路和ICMP协议

IP如何选路概述：

• ip选路实际上是一种选路机制，它搜索路由表并决定向哪个网络接口发送分组，区别于选路策略，后者是一组决定把哪些路由放入路由表的规则；ip执行选路机制，而路由守护程序则一般提供选路策略如rip,ospf
• 点对点时，直接送到
• 非点对点时，经过路由器送到
• Ip层可以是配置为路由或者主机前者非则转发，后者非则丢弃
• 路由表项：每一项为
  阅读全文 »

构造和析构函数语义学

1.

即使是abstract base class也可能需要手动写constructor,de…,关键是看它有没有non satic data member

c++ function语意学

something:
恩，这部分记录自己对c++中的函数特殊性的理解，本想深入函数本质，之前接触过，记得在linux内核剖析那本书讲的很好。
可以参考；

c++ class datamemory

详细介绍c++的成员布局，类本身的布局和在各种情况下的布局

“类”本身的大小：

• the simplest 引入
• 1.2 多少内存能表现一个class?
  最小是１　 size
  阅读全文 »

多态：

为什么需要多态？

引入几个点：
　　继承的机制中，基类的指针和引用能指向派生类，（派生类对象中的基类成员是在内存前面的，即指向派生类对象的指针指向的是第一个基类的第一个成员）

• 指针的值本质上是内存地址，也就是说指向不同变量(int char.)，对象的指针本身的值都是地址的value)
• 指针的类型限定了指针的操作内存范围和取值的方式，如通过int指针取值的时候，取到４byte,通过char指针取值时取得1byte;）
  阅读全文 »

c++ 继承：

继承是什么能做什么

继承是创建复杂类的另一种方式，它展现出来俩个obj 的is-a的概念（前一种方式是加入复杂的函数和成员等has-a　概念）
继承体现的是两个对象（类）之间的联系，子类继承父类的成员和方法，然后特殊化于扩展自己的成员和方法，正如苹果和梨都是水果，它们拥有水果的一般特性，等边三角形是特殊的等腰三角形