Welcome to here

简单即生活

哈夫曼编码简介

2016-05-21

DS
- 几个概念
我自己都感觉这样下去得出事，分类做的扩展性不好。

到时候DS下面肯定很臃肿。先写吧，总比没有强。

几个概念

哈夫曼树是一种最有二叉树，二叉树的【性质】也同样适用于它。

路径长度

从书中一个结点到另一个结点的分支数称作路径长度。假设计算一个叶子结点的路径长度，就是将叶子结点到根节点的结点数目减一。

树的路径长度

从树根到每一个结点的路径长度之和。

树的带权路径长度WPL

树的所有叶子结点的带权路径长度之和。

前缀编码

假设A、B、C、D的编码分别为0,00，1,01，则字符串’‘000011010’就有多种译法，所以，这里设计长度不同的编码，则必须是任何一个字符的编码不是另一个字符的前缀，这种编码称之为_前缀编码_。这里我省略了一个概念。
Read All
回调函数的使用方法

2016-05-20

c/c++
[来自](http://stackoverflow.com/questions/142789/what-is-a-callback-in-c-and-how-are-they-implemented)

这里没有回调在c中，这里使用函数指针实现,举个例子：
```
void populate_array(int *array, size_t arraySize, int (*getNextValue)(void))
{
    for (size_t i=0; i<arraySize; i++)
        array[i] = getNextValue();
}

int getNextRandomValue(void)
{
    return rand();
}

int main(void)
{
    int myarray[10];
    populate_array(myarray, 10, getNextRandomValue);
    ...
}
```
Here, the populate_array function takes a function pointer as its third parameter, and calls it to get the values to populate the array with. We've written the callback getNextRandomValue, which returns a random-ish value, and passed a pointer to it to populate_array. populate_array will call our callback function 10 times and assign the returned values to the elements in the given array.
Read All
sort排序

2016-05-18

algorithm
- 一摘要
- 二各种排序算法的实现
一摘要

排序算法是很重要的在计算机科学中。

二各种排序算法的实现

这里，性能的分析最后补上，因为自己的数学实在差劲。尤其注意一下需排序数组的下标从0开始还是从1开始，这两者在实现上有很大的不同。本文所有的排序都是从0开始的，尽管自己因为这个标准吃尽了苦头

2.1合并排序

code 这里的合并排序只是简单的使用一个数组，没有考虑两个数组的情况，其实是一样的。请记住，在执行完两个子数组的其中任何一个接下来执行的操作，这才是重点。参数为你要排序的数组、起始位、中间位、结尾。

2.2交换排序

bubble sort

所谓的冒泡排序大家都听说过，这里直接上代码，不过你要注意那个标志符的作用。我还是在老地方犯错：先是一个while、接着for，之间填一个sorted=1;这样效率上会有提升。
```
/*我的困难局限于标志变量的位置*/
void bubblesort(int a[],int n){
	int i,j,temp,sorted;
	i = sorted = 0;
	while( (i < n - 1) && (!sorted)){
		sorted = 1;
		for(j = n - 1; j > i; j--){
			if(a[j] < a[j-1]){
				temp = a[j];
				a[j] = a[j-1];
				a[j-1] = temp;
				sorted = 0;
			}
		}
	}
}
```
2.3 插入排序

插入排序分为直接插入排序和希尔排序

插入排序

将一个记录插入到已排序良好的有序表中，从而得到一个记录数增加1的新表，直到整个表有序为止。

要点：

设立哨兵，作为临时存储和判断数组边界之用。最难的是确定插入的位置，在思维上的模糊感还是特别强。
```
version 1:
void insert_sort(int a[],int n){
	int i,t;
	int tmp;
	for(i = 1; i < n; i++){ // 只需注意后一项比前一项大的即可
		if(a[i] < a[i-1]){
			t = i - 1;	// 先前移一个元素？这里快想透了
			tmp = a[i];
			a[i] = a[i-1];
			while(tmp < a[t]){ //寻找在有序表插入的位置
				a[t+1] = a[t];
				t--;
			}
			a[t+1] = tmp; //将哨兵元素放入其中
		}
	}
}
```
我自己写的时候的模糊点：
```
1. 首先前移一位；
2. 寻找在有序表的位置及移动的方法及将哨兵放入排序后的空缺位置
```
下面是严蔚敏版数据结构的代码
```
void insert(int a[],int n){
	int i,j;
	int tmp;//我没用哨兵，使用的是临时变量
	for (i = 1; i < n ;++i){ //..
		if(a[i] < a[i-1]){ //说明需要插入有序表
			tmp = a[i];
			a[i] = a[i-1];
			for(j = i - 1 ; a[j] > tmp; --j){ // 移动,
							//这里我把比较符号
							//搞反了。
				a[j+1] = a[j];
			}
			a[j + 1] = tmp;
		}
	}
}
```
效率: O(n^2).

折半插入排序

利用插入排序的基本操作是在一个有序表中进行查找和插入。所以，我们的查找使用折半.

shell 排序

先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序。

1 确定一个递增序列t1,t2,….tk,最后tk=1；

2 按递增序列个数k，对序列进行k趟排序

这里我们需要处理的序列：增量序列d={n/2,n/4,n/8…1}n为要排序的个数。
```
void shell_insert(int a[],int n,int dk){
	int i;
	for(i = dk; i < n; i++){
		if(a[i] < a[i-dk]){  //思路上是有些怪诞
			int j = i - dk;
			int x = a[i];
			a[i] = a[i-dk];
			while(x < a[j]){
				a[j+dk] = a[j];
				j -= dk;
			}
			a[j+dk] = x; //插入排序的最后一步要将空
		}				//缺的值填补上
	}

}
void shell_sort(int a[],int n){
	int dk = n/2;
	while(dk >= 1){
		shell_insert(a,n,dk);
		dk /=2;
	}
}
```
影响shell排序的一个重要因素就是dk的选取，最好的效率是nlogn目前。

2.4 选择排序

简单选择排序

基本思想：就是在要排序的一组数中，选出最小（或者最大的）的一个数与第一个数字交换，以此类推，直到最后一个元素和倒数第二个元素比较位置。注意，是两个元素相互交互。

比如有以下几个乱序数字：

3 1 5 7 2 4 9 6 8

第一趟排序为1 3 5 7 2 4 9 6 8

第二趟排序为1 2 5 7 3 4 9 6 8
```
/*
 * 之所以传递给一个i，主要也是为了降低
 * 复杂度
 */
int select_min_key(int a[],int n,int i){
	int k = i;
	int j;
	for(j = i + 1; j < n; j++){
		if (a[k] > a[j]) k = j;
	}
	return k;

}
void select_sort(int a[], int n){
	int key,tmp;
	int i;
	for(i = 0; i < n; i++ ){
		key = select_min_key(a,n,i);
		if(key != i){
			tmp = a[i];
			a[i] = a[key];
			a[key] = tmp;
		}
	}
}
```
其实我的本意是将两个函数合并在一起的，没有成功呢！这样的思路很熟悉，但是自己写不出来。

简单选择排序的改进：

在每次的比较中确定最大值和最小值，这样只需要[n/2]次选择即可。

[折半插入排序没有成功]

堆排序

首先是堆的定义：n个元素的序列{k1,k2,…kn}当且仅当满足下列关系时，称之为堆。
```
 Ki <= K2i
 Ki <= K2i-1.
```
而且是一棵完全二叉树，或者说反过来也对.非终端节点的值不大于(或者不小于)左右子节点，所以根节点是最大的元素，这像完全二叉树。所谓的堆排序就是找出其中一个的最值，在其余n-1个数列中重建堆。如此反复，便能得到一个有序序列，这个过程称之为堆排序。

为此，实现堆排序需要两个解决两个问题：(1)如何构建一个堆(2)如何输出一个堆顶元素后，调整剩余元素为一个新的堆。

性质在一个模拟堆的数组中，下标为(floor(A[n/2])..n)(其中的括号是向下取整)全都是叶子。
```
#include<stdio.h>
#include "test_data.h"

int A[10] = {3,1,2,5,9,6,7,4};

/*
 *	start: 相当于root,start对于数组的观点来说直观
 *		从srart到end选取最大的数
 *	root: 相对于tree来说直观
 *		为了方便数组下标从0开始，end应该为个数减1
 *		尤其注意这点
 */
void maxheap_down(int a[],int start,int end){
	int current = start;
	int left = start * 2 + 1;
	int tmp = a[current];   /*从根节点、左右子孩子中选择一个最大的*/
	for(; left < end; current = left, left = 2 * current + 1){
		if(left < end && a[left] < a[left + 1])
			left++;  //右孩子大
		if(a[left] <= tmp)
			break;   //这一句包含了两种情况
		else{		// 调整tmp与大的孩子的值
			a[current] = a[left];
			a[left] = tmp;
		}
	}
}
void heap_sort(int a[],int n){
	int i,temp;
	for(i = n / 2 - 1;i >= 0; i--){
		maxheap_down(a,i,n-1);//看你从主函数调用时传递的参数
	}
	printf("MAX is %d\n",a[0]);
	/*从最后一个元素开始，不断缩小范围直至最后一个元素*/
	for(i = n - 1;i >= 0; i--){
		temp = a[i];
		a[i] = a[0];
		a[0] = temp;
		/*从堆头开始往下再次调整*/
		maxheap_down(a,0,i-1);
	}
```
堆排序的时间复杂度和稳定性：

因为有N的数列需要遍历，所以遍历一趟的时间复杂度为O(N).

堆排序采用的是二叉堆进行排序的，二叉堆就是一棵完全二叉树，它需要遍历的次数就是二叉树的深度。则完全二叉树的深度至少是lg(n+1),最多为lg(2n),二者结合的时间复杂度为O(N*lgN).
Read All
Makefile中后缀规则

2016-05-16

make
- make中的通配符原则
make中的通配符原则
```
EXE=test
OBJ=test.o

$(EXE): $(OBJ)
	gcc -o $@ $<

%.o: %.c
	gcc -c -o $@ $<
```
这里的意思很明显：可执行文件依赖于对象文件，对象文件又需要一条统配规则：所有.c的文件会生成.o的文件，下面是规则。
```
EXE=test
OBJ=test.o

$(EXE): $(OBJ)
	gcc -o $@ $<

.SUFFIXES: .c .o

.c.o:
	gcc -g $@ $<
```
与上面实现了同样的功能，但是有一点注意，这条默认规则不产生输出，上面的Makefile会输出。之所以把它称为隐晦规则，它的目标文件与依赖文件与统配符的表现形式完全相反，注意一点。
Read All
word论文操作记录

2016-05-15

word
参考文献管理

参见这篇文章

主要是结合mendeley文献管理软件自动生成文献的管理

word如何删除空白页

1.将鼠标放在前一页的最后,用DEL健删除。如果空白面是最后一页,且鼠标在第一行，可选“格式”-“段落”，将这一行的行距设为固定值1磅，该空白页将自动消失。

2.先显示分页符，即在Word的左下角调整到“普通视图”状态，这时分页符就出现了，直接删除即可。

3 选择“替换”点“高级”，在里面选择“使用通配符”以后下面有一个“特殊字符”字的开头，按住shift的时候再点下鼠标，选择空白页,再删除（解决了我的问题）

4.如果是插入分页符造成的空白页，少的话，删除分页符就行，就是到空白页顶部按退格键。（普通视图下或打开编辑标记会显示分页符）

5.如果分页符很多，可以编辑/替换/高级/特殊字符/人工分页符/全部替换就可以了。

6.如果是你画了一个表格，占了一整页，造成最后一个回车在第二页删不了，可以将表格缩小一点或者将上面或者下面页边距设小一点，在文件/页面设置中，上下的数字改小一点。

7.将鼠标放在前一页的最后,用DEL健删除。如果空白面是最后一页,且鼠标在第一行，可选“格式”-“段落”，将这一行的行距设为固定值1磅，该空白页将自动消失。

8、后面有空白是上一页内容过多导致的，一般可以把鼠标点到空白面上，然后按回退键，退有内容的那一面，空白的就没有了，如果还存在，可以稍调整一下上一页内容，少一行就可以了。

9、word 预览有空白页页面视图时没有。空白页有页码，造成我打印的文档页码不连续。怎样删除：可能是你的文档中有过宽，过长的对象（如表格，图片，公式），导致与打印纸张的规格不一至，调整附近的对象（如表格，图片，公式）大小看看。也可能与分栏和一些可个和回车符号有关。

10、ctrl+enter即可去除空白页

11、插入表格后的Word删除空白页

在Word2003中插入一张表格并使该表格充满当前页时，会在当前页后面产生一个空白页。尽管在产生的空白页中只含有一个段落标记，但是无法将其删除，从而无法去掉该Wo rd空白页。不过用户可以按以下步骤删除Word空白页：

第1步，在Word2003窗口选中空白页中的段落标记，然后在Word菜单栏依次单击“编辑”→ “全选”菜单命令。

第2步，在Word菜单栏依次单击“格式”→“段落”菜单命令，打开“段落”对话框。在“行距” 下拉菜单中选中“固定值”，并将“设置值”调整为“1”。设置完毕单击“确定”按钮

百度知道

页码的插入

我这里最怵的就是页码的插入，等你知道了流程，会后悔的要死。。。我们学校要求的是摘要(中英文)、目录、正文的页眉不同，摘要(中英文)、目录的页码用罗马数字表示，正文使用阿拉伯数字。

先鼓捣页眉，明显地摘要、目录之间需要分节符，分节符的目的就是使一篇文档分成不同章节，不同章节的操作互不影响。至于分节符的插入，应该是将光标定位在最后一页的第一个字之前，”页面布局”->”分节符”->”下一页”，单击页眉的时候，将工具栏中的连接到上一节的按钮去掉，这时就已经可以键入新的页眉了。

页码：分好节之后，先设置格式，比如罗马数字、阿拉伯数字，设置好起始页码后，再单击页码地段->普通数字，这时的页码就自动连续起来了，非常优美。

其他技巧

双栏排版　

页面布局->分栏

索引

Shift + ctrl + =

返回上次编辑的地方

Shift +

关闭word的段首自动更新
<文件> ==》 <选项> ==> （校对） ==> (自动更正选项) ==> (句首字母大写) 去掉勾选
Read All
linux 内核栈基础

2016-05-11

kernel
- 网络内存管理
  - sk_buff
网络内存管理

sk_buff

数据包在应用层为data，在TCP为segment, 在IP层为packet,在数据链路层为frame. 这个结构会在各个层次中使用存放接收或者发送的数据

接下来的这张图片说明了调用sk_buff的方式.

图中的data这个指针指向的位置是可变的。它有可能随着报文所处的层次而变动。

图中的h是第四层/传输层，用h表示：在sk_buff结构体中有三个联合体的简写。

nh是第三层/网络层，也就是传说中的IP头，以network header 命名。

mac也就是MAC层的头，这种安排也体现了报文各层头部的逻辑关系。

使用alloc_skb,就创建了一个套接字缓冲区，其实，内核中的很多结构有自己的alloc 可以类比，其他的也是创建了xx缓冲区。
Read All

71/90

Welcome to here

哈夫曼编码简介

几个概念

路径长度

树的路径长度

树的带权路径长度WPL

前缀编码

回调函数的使用方法

sort排序

一 摘要

二 各种排序算法的实现

2.1合并排序

2.2交换排序

bubble sort

2.3 插入排序

插入排序

要点：

折半插入排序

shell 排序

2.4 选择排序

简单选择排序

[折半插入排序没有成功]

堆排序

Makefile中后缀规则

make中的通配符原则

word论文操作记录

参考文献管理

word如何删除空白页

页码的插入

其他技巧

双栏排版

索引

返回上次编辑的地方

关闭word的段首自动更新

linux 内核栈基础

网络内存管理

sk_buff

一摘要

二各种排序算法的实现

双栏排版　