2013-07-09

常用的排序算法（三）——归并排序

归并排序的最好、最坏和平均时间复杂度都是O(nlogn)。它是分治算法的一种典型应用。

它是基本操作就是将待排序的数列分为多个有序子数列，然后再将这些子数列合并为有序的数列。

这种排序方法经常用于将多个有序的数据文件合并在一个有序的数据文件。

用C语言实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int len;
void print_list(int *list, int n)
{

    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", list[i]);
    }
    printf("]\n");
}

void merge(int *a, int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = (int *)malloc((n1+1) * sizeof(int));
    int *R = (int *)malloc((n2+1) * sizeof(int));
    int i, j, k;
    
    for (i=0; i<n1; i++) {
        L[i] = a[p+i];
    }
    for (j=0; j<n2; j++) {
        R[j] = a[q+j+1];
    }
    // 设置"哨兵牌"
    L[i] = INT_MAX;
    R[j] = INT_MAX;

    i = j = 0;
    for (k=p; k<=r; k++) {
        if (L[i] <= R[j]) {
            a[k] = L[i];
            i++;
        } else {
            a[k] = R[j];
            j++;
        }
    }
    free(L);
    free(R);
    print_list(a, len);
}

void merge_sort(int *a, int p, int r)
{
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q+1, r);
        merge(a, p, q, r);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {3, 41, 52, 26, 38, 57, 9, 49};
    //int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
    len = sizeof(a) / sizeof(int);
    merge_sort(a, 0, len-1);
    return 0;
}

各位可以尝试把它改进一下，去掉哨兵牌。

归并排序演示图片：

2013-07-09

数据结构和算法

常用的排序算法（二）——插入排序

插入排序的平均时间复杂度为O(nn)，最好的情况下为O(n)，最坏情况为O(nn)。

其基本机理与我们平时打牌时整理手中的牌的做法差不多。把小的牌插到左边，大的牌往右边移。

用C语言实现如下：

#include <stdio.h>

void print_list(int *list, int n)
{

int i;
printf("[ ");
for (i=0; i<n; i++) {
printf("%d ", list[i]);
}
printf("]\n");
}

void insertion_sort(int *base, int len)
{

int i, j, n;
int value;
for (j=1; j<len; j++) {
i = j - 1;
value = base[j];
while (i>=0 && base[i] > value) {
base[i+1] = base[i];
i--;
}
base[i+1] = value;
printf("step %d:", j);
print_list(base, len);
}
}

int main(int argc, char *argv[])
{
int a[] = {5, 2, 4, 6, 1, 3};
int len = sizeof(a) / sizeof(int);
insertion_sort(a, len);
return 0;
}

2013-07-06

数据结构和算法

常用的排序算法（一）——冒泡排序

前言：

自从毕业了之后就没怎么用到算法，以致于之前学的都忘得差不多了。最近决定抽空再把算法重新学习一下，虽然平时也用不上。
这次学习我是把算法导论、算法技术手册和数据结构(严蔚敏)这三本书混合着看。

正文：

冒泡排序的时间复杂度为O(n*n)，它的原理比较简单。基本思路就是从第1个元素开始，依次的把该元素与后一个元素进行比较，如果比后一个元素大则交换它们的位置；每1次全部比较完成之后，最大的那个元素就放在了最后。重复之前的操作，直到所有元素都排好序。

用C语言实现如下：

#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}

void bubble_sort(int *ar, int n)
{
    int i, j;
    int tmp;
    for (i=0; i<n-1; i++) {
        for (j=0; j<n-1; j++) {
            if (ar[j] > ar[j+1]) {
                tmp = ar[j];
                ar[j] = ar[j+1];
                ar[j+1] = tmp;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    int a[] = {5, 3, 16, 2, 10, 14};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    bubble_sort(a, len);
    printf("end: ");
    print_list(a, len);
    return 0;
}

冒泡排序演示图片：

2013-06-29

编程开发

SCons工具用法介绍

SCons是使用Python语言开发的一个软件自动构建工具，功能类似于UNIX上的make、autoconf与automake工具。它跨平台，能够帮助我们更方便，可靠，快速的构建软件。

与make命令和Makefile文件类似，scons也需要编写一个SConstruct文件（实际上也是一个python脚本），scons可以根据此文件自动完成依赖关系的推导及编译链接等过程。

下面通过一个简单的例子来介绍一下scons的用法，首先得先安装scons工具的gcc编译器。

新建一个hello.c文件，内容如下：

//hello.c
#include<stdio.h>

int main(){
printf(&quot;hello world!\n&quot;);
return 0;
}

然后再创建一个SConstruct文件，内容为：

1	Program('hello.c')

这两个文件放在同一目录下，再执行命令scons即可完成编译，并生成名为hello.o的中间文件和名为hello的可执行文件。

如果想要清除生成的文件，跟make clean类似可以执行scons –clean命令。

上面只是一个简单的例子，如果你的程序中使用的第三方库，编译时就需要手动指定链接库。

以gtk程序为例，编译一个名为gtk_test.c的源文件，SConstruct脚本可以用如下的方法。

env = Environment(CCFLAGS='-g')
env.ParseConfig('pkg-config --cflags --libs gtk+-2.0')

env.Program('gtk_test.c')

我个人感觉SConstruct比Makefile要更加简洁灵活，更多关于scons有用法以及SConstruct脚本的写法可以参考它的官方文档。

scons主页： http://www.scons.org
scons文档： http://www.scons.org/documentation.php

2013-05-19

教程

vim statusline设置

vim中默认的状态行，左边显示当前打开的文件名，右边显示当前所处的行列位置。
如果只需要默认的状态栏，这样就行了：
set laststatus=2 “ 总是显示状态栏
set ruler “ 在状态栏显示行号和列号

如果想根据自己的需求修改的话，可以用以下命令查看帮助信息。
:h statusline

我们可以使用以下命令来定义状态行：
:set statusline=format
这个format跟printf函数的参数有些相似。

例如以下命令就是设置在状态栏显示文件名。
:set statusline="%f"

例如想在状态栏显示当前的时间可以用这个命令。
:set statusline+=%-16{strftime(\"%Y-%m-%d\ %H:%M\")}

以下是format的参数列表

%(...%)     定义一个项目组。
%{n}*     %对其余的行使用高亮显示组Usern，直到另一个%n*。数字n必须从1到9。用%*或%0*可以恢复正常的高亮显示。
%&lt;     如果状态行过长，在何处换行。缺省是在开头。
%=     左对齐和右对齐项目之间的分割点。
%     字符%
%B     光标下字符的十六进制形式
%F     缓冲区的文件完整路径
%H     如果为帮助缓冲区则显示为HLP
%L     缓冲区中的行数
%M     如果缓冲区修改过则显示为+
%N     打印机页号
%O     以十六进制方式显示文件中的字符偏移
%P     文件中光标前的%
%R     如果缓冲区只读则为RO
%V     列数。如果与%c相同则为空字符串
%W     如果窗口为预览窗口则为PRV
%Y     缓冲区的文件类型，如vim
%a     如果编辑多行文本，这个字行串就是({current} of {arguments})，例如：(5 of 18)。如果在命令行中只有一行，这个字符串为空
%b     光标下的字符的十进制表示形式
%c     列号
%f     缓冲区的文件路径
%h     如果为帮助缓冲区显示为[Help]
%l     行号
%m     如果缓冲区已修改则表示为[+]
%n     缓冲区号
%o     在光标前的字符数（包括光标下的字符）
%p     文件中所在行的百分比
%r     如果缓冲区为只读则表示为[RO]
%t     文件名(无路径)
%v     虚列号
%w     如果为预览窗口则显示为[Preview]
%y     缓冲区的文件类型，如[vim]
%{expr}     表达式的结果

2013-04-14

Linux栏目

Linux下安装sudo工具

以gentoo为例，先执行命令安装sudo工具
# emerge sudo

然后再进行配置。sudo的配置文件是/etc/sudoers。应当永远使用visudo命令编辑/etc/sudoers文件。visudo会锁住sudoers文件，保存修改到临时文件，然后检查文件格式，确保正确后才会覆盖sudoers文件。必须保证sudoers格式正确，否则sudo将无法运行。

编辑/etc/sudoers文件，加入以下内容：

1 2	Defaults env_reset Defaults secure_path="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"

要为某个用户提供特权，使其可以使用sudo执行所有命令，在配置文件中加入：
用户名 ALL=(ALL) ALL

如果只想允许本地登陆的用户使用sudo：
用户名主机名=(ALL) ALL

允许admin用户组成员无密码使用sudo：
%admin ALL=(ALL) NOPASSWD: ALL

请把用户名替换为实际用户名称。

只为用户启用部分特权：
用户名主机名=/sbin/halt,/sbin/reboot -Syu
该用户只能使用sudo执行halt、reboot。

在~/.bashrc中加入 complete -cf sudo 开启sudo的自动补全。

2013-04-04

网络日志

好久没更新了

突然发现博客好久没有更新了，一是因为忙，二是因为懒，再是由于现在访问自己的博客还要开代理…………

2013-01-27

Linux栏目

Gentoo安装笔记

参考官方手册，并整理一下。http://www.gentoo.org/doc/zh_cn/handbook/
下载iso文件，并使用其进行引导系统。安装光盘上提供了几个内核。默认的是gentoo。
即使用boot:gentoo来启动安装光盘即可。

整个安装过程需要联网进行，请确保网络已经配置好了。

1、先创建一个分区，然后挂载到/mnt/gentoo目录下。

2、安装需要的安装文件
(1)、下载stage3 tarball文件，并解压到安装目录下，也就是/mnt/gentoo。
(2)、下载安装Portage文件。
# cd /mnt/gentoo
# tar xvf portage-lastest.bar.bz2 -C /mnt/gentoo/usr

3、配置编译选项
定义CFLAGS和CXXFLAGS变量

# nano -w /mnt/gentoo/etc/portage/make.conf

CFLAGS="-O2 -march=i686 -pipe"
# 两个变量使用相同的设置
CXXFLAGS="${CFLAGS}"

4、安装Gentoo基本系统
为了快速下载源代码，建议选择一个速度快的境像。我用的网易的源，在make.conf文件中添加以下内容。
GENTOO_MIRRORS="http://mirrors.163.com/gentoo/"

(1)、拷贝DNS信息
# cp -L /etc/resolv.conf /mnt/gentoo/etc

(2)、挂载proc和dev文件系统
# mount -t proc none /mnt/gentoo/proc
# mount -o bind /dev /mnt/gentoo/dev

(3)、进入新系统环境
# chroot /mnt/gentoo /bin/bash
# env-update
# source /etc/profile
# export PS1="(chroot)$PS1"

(4)、配置Portage
更新Portage树
# emerge --sync

修改/etc/locale.gen文件设置locale然后再执行命令locale-gen

5、配置内核
(1)、设置时区，我这用的是上海的时区。
# cp /usr/share/zoneinfo/Asia/Shanghai /etc/localtime

(2)、安装源码
# emerge gentoo-sources
然后内核源码就会下载到/usr/src/linux目录下。转到该目录进行内核编译配置。
# cd /usr/src/linux
执行以下命令进行手动配置，手动配置就要注意驱动都要选对，并且要编译进内核，不要编译成模块。反正我是编译了好几次系统都不能正常启动。最后我就使用自动配置。
# make menuconfig

自动编译内核首先先安装genkernel
# emerge genkernel
然后复制光盘上的内核配置文件到genkernel搜索配置文件的默认位置。

现在执行如下命令编译内核。这样编译出来的内核支持几乎所有配件，但是耗时较多。
# genkernel all
编译完成后将会在/boot目录下生成内核文件和initrd文件。

6、配置系统
(1)、文件系统信息
编辑/etc/fstab文件，设置分区的挂载。

(2)、网络信息
编辑/etc/conf.d/hostname文件，设置主机名。
编辑/etc/conf.d/net 文件，设置ip。
手动设置ip，设置 config_eth0和routes_eth0：
config_eth0=( “192.168.0.2 netmask 255.255.255.0 brd 192.168.0.255” )
routes_eth0=( “default via 192.168.0.1” )
使用DHCP，请定义一下config_eth0：
config_eth0=( “dhcp” )

创建启动脚本，并设置自动启动。

1
2
3

# cd /etc/init.d
# ls -s net.lo net.eth0
# rc-update add net.eth0 default

(3)、系统信息
设置root密码，并创建一个普通用户。
# passwd
# useradd users

7、安装一些系统工具
根据自己需求再安装一些系统工具。
(1)、系统日志工具
# emerge syslog-ng
# rc-update add syslog-ng default

(2)、守护进程
# emerge vixie-cron
# rc-update add vixie-cron default

(3)、网络工具
# emerge dhcpd
# emerge ppp

8、配置引导程序
Gentoo提供的引导程序有GRUB和LILO，我用的是GRUB。
安装Grub，请根据自己的情况进行调整。

# emerge grub
# grep -v rootfs /proc/mounts &gt; /etc/mtab
# grub-install --no-floppy /dev/sda
# update-grub -o /boot/grub/grub.conf

9、重启系统

1
2
3

# eixt
# umount /mnt/gentoo/{dev,proc,}
# reboot

2013-01-03

Linux栏目

Arch Linux 2012.12.01安装方法

自从上次我的Arch系统崩溃之后我就改用其它系统了，距离现在已有小半年了。突然发现Arch又更新了，于是下下来体验一下。
在新版的ArchLinux中已经不在使用AIF(Arch Installation Framwork)了，而是使用新的脚本工具(Arch Install Scripts)，https://github.com/falconindy/arch-install-scripts

新版的安装过程是通过网络安装，因此整个过程需要联网才行。

1、首先为Arch分配一个分区，然后挂载到/mnt目录。如果使用多个分区，还需要创建它们并正确挂载（/mnt/boot, /mnt/home, …），这样genfstab才能自动检测到它们。

2、安装基本系统
先编辑/etc/pacman.d/mirrorlist选择首先镜像。
然后使用pacstrap脚本安装基本系统。
# pacstrap /mnt base base-devel

3、安装引导器
安装一个Bootloader，Grub或者Syslinux。
(1)安装GRUB:
如果是BIOS用户执行命令：
# pacstrap /mnt grub-bios
如果是EFI用户执行命令：
# pacstrap /mnt grub-efi-x86_64

(2)安装Syslinux：
#pacstrap /mnt syslinux

4、配置系统
(1)生成fstab文件
# genfstab -p /mnt >> /mnt/etc/fstab

(2)chroot到新安装的系统中去
# arch-chroot /mnt

(3)进行一些系统配置
设置主机名：修改/etc/hostname文件，将主机名写入里面。
设置时区： cp /usr/share/zoneinfo/Asia/Shanghai /etc/localtime
设置locale：修改/etc/locale.gen文件，然后再执行命令locale-gen
创建一个初始的RAM disk： mkinitcpio -p linux
设置root用户的密码： passwd root
配置引导器，在我的电脑上是依次执行如下命令，这个请结合自己的情况进行设置：
# grub-install --no-floppy /dev/sda
# grub-mkconfig -o /boot/grub/grub.cfg

其余的根据自己的需要再进行设置。

5、重启进入新系统
先退出chroot，然后卸载之前挂载在/mnt的分区。
# umount /mnt
然后重启进入新系统并以root用户登陆。
现在一个基本的Arch系统就已经安装好了，接下来可以根据自己的需要来安装相应的软件。

6、安装应用软件
Arch系统刚安装好后发现居然连ifconfig命令都没有，可以使用如下命令安装：
# pacman -S net-tools dnsutils inetutils iproute2

安装Yaourt
在/etc/pacman.conf中添加以下内容：

1 2	[archlinuxfr] Server = http://repo.archlinux.fr/$arch

然后再执行命令: pacman -Syu yaourt

安装Xorg：
# pacman -S xorg-server xorg-xinit xorg-utils xorg-server-utils
安装显示驱动(根据自己的情况选择安装相应的驱动)：
# pacman -S xf86-video-fbdev
安装evdev，支持大部分即插即用设备
# pacman -S xf86-input-evdev
安装默认的测试环境：
# pacman -S xorg-twm xorg-xclock xterm
然后启动X会话，如果能够看到一个终端和一个时钟就表示已经安装成功了：
$ startx

2012-10-13

教程

使用vim在目录下查找字符串

vim有个vimgrep命令，跟linux下的grep类似。用法如下：
:vimgrep /{pattern}/[g][j] {file} …
{pattern}为要查找的字符串;
没有参数g的话,则行只查找一次关键字.反之会查找所有的关键字.
没有参数j的话,查找后,VIM会跳转至第一个关键字所在的文件.反之,只更新结果列表(quickfix).
{file}为要查找的文件，可以有多个。

例如，要在当前目录及其子目录中的python文件查找”import”字符串。
:vimgrep /import/ **/*.py
命令中的**表示递归查找。

{pattern}也可以用正则表达式。搜索结果保存在quickfix中，可以使用以下方法查看。

:cnext (:cn) 当前页下一个结果
:cprevious (:cp) 当前页上一个结果
:clist (:cl) 打开quickfix窗口，列出所有结果，不能直接用鼠标点击打开，只能看
:copen (:cope) 打开quickfix窗口，列出所有结果，可以直接用鼠标点击打开
:ccl[ose] 关闭 quickfix 窗口。
ctrl + ww 切换编辑窗口和quickfix窗口，在quickfix里面和编辑窗口一样jk表示上下移动，回车选中进入编辑窗口

zcat /proc/config.gz > /usr/share/genkernel/arch/x86/kernel-config