程序设计 - Felix021 - 招人好难啊

Nov 19

类TeX的UBB表格函数

felix021 @ 2009-11-19 02:29 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3220) | Via 本站原创

引用

UBB内容为（开头那个下划线不需要加）：
[_table]
l | r | l | c | r
左对齐|右对齐|左对齐|<a href="javascript:alert(12345)">居中啦啦啦</a>|右对齐
1|23|456|7890[newline]1234|0000
abcd|efg|hi|[-]|j
1|[-]|[-]|1|1
[/table]

效果：

左对齐	右对齐	左对齐	<a href="javascript:alert(12345)">居中啦啦啦</a>	右对齐
1	23	456	7890 1234	0000
abcd	efg	hi	j
1	1			1

PHP代码：

Nov 18

数据结构：栈

felix021 @ 2009-11-18 23:56 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(6155) | Via 本站原创

花点时间总结一下“栈”相关的内容。希望对于初学栈的同学会比较有帮助。

另外，其中涉及的一些内容也是书本上不会涉及到，或者是零零散散写出来的。看看总没坏处。

--------------传说中的分割线-------------

数据结构：栈

内容纲要
1. 什么是栈
2. 栈的实现(C语言)
  a) 数组实现
  b) 单链表实现
  c) 两种实现的对比
3. 栈的应用
  a) 在函数调用中的作用
  b) 在局部变量存储中的应用
    * 栈空间和系统维护的堆空间的对比
  c) 在算法中的应用

点击查看更多...(阅读全文)

Nov 8

重温八皇后问题

felix021 @ 2009-11-8 13:58 [IT » 程序设计] 评论(3) , 引用(0) , 阅读(5888) | Via 本站原创

    如果从大一算起，写C已经有3年了。其实高中也写过，但是基本可以忽略不计。代码量，比起acm/icpc正规军来说，当然还是少得多；但是应该也有几万行了。写了这么多代码，也看了不少算法，感觉就是，这样的经验需要时间的积淀。曾经觉得很难的问题，现在已经在脑子里豁然开朗。就比如八皇后问题，上一次研究它，是2007年6月的事情。那会儿应该能想的清楚了，但是对于那时候的我而言，回溯算法仍然是比较难以理解的（记得有一次想写一个生成全排列的程序，写了半天都不对，最后还是让sandy写了一个标程抄了两遍，才逐渐理解）。差不多2年半过去了，再回首这个八皇后，发现思路非常清晰，很快就把代码写出来了。

    废话完回到这个问题上。它的两个难点在于：1. 如何判断某一个位置是否可以放置一个皇后；2. 回溯。

    如果给这个8*8的矩阵上个坐标，横向(rows)为i = 0 to 7，纵向(columns)为j = 0 to 7。那么可以发现，在每一条斜线(/)方向上，每一个格子的横纵坐标之和(i + j)是一个固定值，从左上到右下的斜线，其值依次是0~14 (0+0; 0+1,1+0; 0+2,1+1,2+0; ... ; 6+7,7+6; 7+7)。同样地，，在每一条反斜线(\)方向上，每一个格子的横坐标与纵坐标的关系是， (i + (7 - j))是固定值，从右上到左下的斜线，其值依次是0~14。

    因此，在开始寻找方案之前，给横、纵、斜线、反斜线方向各设置一个数组，所有元素初始化为0（表示可以放置），那么，在将皇后放置到(i, j)之前检查rows[i]、cols[j]、slash[i+j]、bslash[i+7-j]是否都为0，就可以判断这个位置能否放置皇后。由于放置的过程是从上到下一行一行放的，所以这个rows数组实际上可以去掉。这样第一个难点就解决了。（p.s. bslash -> backslash）

    第二个难点，回溯，这个我觉得不是很容易能说清楚的。简单地说，需要回溯的就是前面提到的cols/slash/bslash数组。一行一行地来：每一行从第一个位置开始查找，当找到一个有效位置，放置一个皇后，将对应的值置为1（以后的位置就可以检测是否可放），然后继续查找下一行的位置（递归调用）；如果下一行没有合适的位置（递归返回），将对应的位置重置为0，然后查找这一行下一个位置。

    这个问题实在不是一个有难度的问题，我居然扯了这么多。可见我现在多闲啊。俗话说的好：经常扯蛋有助于预防蛋疼。

    下附代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 8

int count;
int rows[N],    cols[N],    slash[2 * N - 1], bslash[2 * N - 1];
//每行放的位置，纵向不可放，斜向不可放（/），斜向不可放(\)

void place(int i) {
    int j;
    for (j = 0; j < N; ++j) {
        if (cols[j] == 0 && slash[i + j] == 0 && bslash[i + (N-1) - j] == 0) {
            rows[i] = j;

            cols[j] = 1;
            slash[i + j] = 1;
            bslash[i + (N-1) - j] = 1;

            if (i == N - 1) {
                /*
                int k;
                for (k = 0; k < N; ++k) {
                    printf("%d ", rows[k]);
                }
                printf("\n");
                */
                count++;
            }
            else {
                place(i + 1);
            }

            //回溯
            cols[j] = 0;
            slash[i + j] = 0;
            bslash[i + (N-1) - j] = 0;
        }
    }
}

int main () {

    memset(rows, 0, sizeof(rows));
    memset(cols, 0, sizeof(cols));
    memset(slash, 0, sizeof(slash));
    memset(bslash, 0, sizeof(bslash));

    count = 0;
    place(0);
    printf("count = %d\n", count);
    return 0;
}

Nov 7

Kruskal贪心算法求最小生成树

felix021 @ 2009-11-7 02:35 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(5661) | Via 本站原创

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

/*
* Kruskal贪心算法求最小生成树(heap+并查集)
* 测试输入数据：

6 10 //6个顶点10条边
1 5 2  //从顶点1到顶点5的边权重为2
2 4 3
4 5 1
0 3 6
2 3 7
5 2 6
4 0 7
1 3 5
1 2 4
3 5 9

*/

struct edge {
    int start, end, weight;
};

void siftdown (struct edge *a, int n, int i) {
    struct edge t;
    if (i < 1 || i > n) return;
    while (i * 2 <= n) {
        i *= 2;
        if (i + 1 <= n && a[i].weight > a[i + 1].weight) i++;
        if (a[i].weight < a[i/2].weight ) {
            t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else {
            break;
        }
    }
}

void siftup (struct edge *a, int n, int i) {
    struct edge t;
    if (i < 1 || i > n) return;
    while (i > 1) {
        if (a[i].weight < a[i/2].weight) {
            t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else {
            break;
        }
        i /= 2;
    }
}

void makeheap(struct edge *a, int n) {
    int i;
    for (i = n / 2; i >= 1; --i) {
        siftdown(a, n, i);
    }
}

struct edge pop(struct edge *a, int *n) {
    struct edge t;
    t = a[1];
    a[1] = a[*n];
    (*n)--; //第二次挂在这里，不能写*n--(*n; n-=1;), 要写(*n)--
    siftdown(a, *n, 1);
    return t;
}

void dump(struct edge *a, int n) {
    int i;
    for (i = 0; i < n; ++i) {
        printf("edge (%d, %d), %d\n", a[i].start, a[i].end, a[i].weight);
    }
}

void initUnionSet(int a[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        a[i] = i;
    }
}

int getFather(int a[], int x) {
    return a[x] == x ? x : (a[x] = getFather(a, a[x]));
}

void merge(int a[], int x, int y) {
    x = getFather(a, x);
    y = getFather(a, y);
    a[x] = y;
}

int haveCommonAncestor(int a[], int x, int y) {
    return (getFather(a, x) == getFather(a, y) ? 1 : 0);
}

int main () {
    int m, n, i, k, *father;
    struct edge *input, *output, t;

    scanf("%d%d", &m, &n);
    input = (struct edge *)malloc(sizeof(struct edge) * (n + 1));
    for (i = 1; i <= n; ++i) {
        scanf("%d%d%d", &input[i].start, &input[i].end, &input[i].weight);
    }
    makeheap(input, n);
    dump(input+1, n);
    printf("end input\n");

    int n1 = n;
    output = (struct edge *)malloc(sizeof(struct edge) * (m - 1));
    father = (int *)malloc(sizeof(int) * n);
    initUnionSet(father, m);
    k = 0;
    printf("\nStart:\n");
    while (n1 > 0) {
        t = pop(input, &n1);
        printf("edge (%d,%d), %d ", t.start, t.end, t.weight);
        if (0 == haveCommonAncestor(father, t.start, t.end)) {
            printf("added in\n");
            output[k] = t;
            k++;
            merge(father, t.start, t.end);
            if (k == m - 1) {
                printf("~~ok~~\n");
                break;
            }
        }
        else {
            printf("ignored\n");
        }
    }
    printf("\nresult:\n");
    dump(output, k);

    free(input);
    free(output);
    free(father);
    return 0;
}

注：下面这段代码是之前写的，写了一个简单的链表+插入来实现，本来是想用队列式链表然后再排序的，但是太麻烦了，干脆直接插入排序，所以那个tail也就一点用也没有了（用在tree那个list里看起来还更NC）。其实更好的办法应该是根据输入的n动态分配足够的空间，全部输入以后然后用heap或者用qsort。

点击查看更多...(阅读全文)

Nov 4

基数排序

felix021 @ 2009-11-4 00:57 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(4076) | Via 本站原创

好久没有写了，写错了好久，后来发现是挂在指针上了，真杯具。

#include <stdio.h>
#include <stdlib.h>
#ifdef __GNUC__
    #define WARN_IF_UNUSED __attribute__ ((warn_unused_result))
#else
    #define WARN_IF_UNUSED
#endif

struct node {
    int v;
    struct node *next;
};

struct linklist {
    struct node *head;
    struct node *tail;
};

WARN_IF_UNUSED int init(struct linklist ll[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        ll[i].head = (struct node *)malloc(sizeof(struct node));
        if (ll[i].head == NULL) {
            return 0;
        }
        ll[i].head->next = NULL;
        ll[i].tail = ll[i].head;
    }
    return 1;
}

void dump(struct linklist *ll) {
    struct node *p = ll->head->next;
    while (p != NULL) {
        printf("%d ", p->v);
        p = p->next;
    }
    printf("\n");
}

WARN_IF_UNUSED int push(struct linklist *ll, int v) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (p == NULL) {
        return 0;
    }
    p->v = v;
    p->next = NULL;
    ll->tail->next = p;
    ll->tail = p;
    return 1;
}

int isEmpty(struct linklist *ll) {
    return (ll->head->next == NULL) ? 1 : 0;
}

int pop(struct linklist *ll) {
    if (isEmpty(ll)) {
        exit(1);
    }
    struct node *p = ll->head;
    ll->head = p->next;
    free(p);
    return ll->head->v;
}

void radixSort(int a[], int n) {
    struct linklist ll[10];
    int flag, i, j, t, fact = 1;
    if (init(ll, 10) == 0) {
        exit(2);
    }
    do {
        printf("---------------\n");
        flag = 0;
        for (i = 0; i < n; ++i) {
            t = a[i] / fact % 10;
            flag += !!t;
            //printf("%d: %d\n", a[i], t);
            if (push(&ll[t], a[i]) == 0) {
                exit(2);
            }
        }
        for (i = 0, j = 0; i < 10; ++i) {
            printf("%d: ", i);
            dump(&ll[i]);
        }
        for (i = 0, j = 0; i < 10; ++i) {
            while (isEmpty(&ll[i]) == 0) {
                a[j] = pop(&ll[i]);
                j++;
            }
        }
        fact *= 10;
    }while (flag != 0);
}

int main() {
    int a[] = {26,62,187,32,8754359,45324,54654,0,331,321312,12,4324,87,98};
#define N (sizeof(a) / sizeof(int))
    radixSort(a, N);
    int i;
    for (i = 0; i < N; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Oct 29

GNU的tail源码阅读笔记

felix021 @ 2009-10-29 12:52 [IT » 程序设计] 评论(3) , 引用(0) , 阅读(11236) | Via 本站原创

---# GNU的tail源码阅读笔记

---++ 获取源码

tail和head等原本是属于textutils软件包的，后来被统一合并到coreutils软件包中了。coreutils的主页是：http://www.gnu.org/software/coreutils/，可以从这里下载到所有的源码。如果你使用的是Ubuntu系统，还可以直接运行命令 apt-get source coreutils 直接从源中获取代码。

---++ 编译

先编译一下。跟其他开源软件基本上一致，先./configure一下，没有问题的话就make之。make结束以后，生成的可执行文件就在src目录下面

---++ 阅读

为了方便阅读，先ctags -R一下，生成tags；然后vim src/tail.c就打开了源码。代码比较细碎，零零散散2000多行，花了两三个小时才看完，大致读懂了代码的主干流程，这里记录一下。

   * 初始化，有些乱七八糟的initialize_main/set_program_name/setlocale/bingtextdomain/textdomain都可以忽略，没做什么实事。atexit还算有点用，设置了退出的时候要把stdout关闭。
   * 解析命令行参数。先上了个obsolete_parse_option(option都不加个复数s)，貌似是为了兼容以前的命令行参数方式（posix2_version在200112这个版本以前的）。然后又来一个parse_options，这个就是按照man里面的格式来解析参数了。具体的参数man tail就可以看到，不多说。
   * 判断一下输入是不是源于stdin，如果是的话，修改一下file和n_files。
   * 然后给文件结构体分配空间，填进去每个文件的名字，然后是一个循环，调用tail_file来输出每个文件(传入结构体F[i]的指针)的内容
      看看tail_file:
      * 打开文件，失败的话当然就over了，return
      * 看看要不要输出文件名(可以在命令后参数指定-q, -v)
      * 调用tail函数输出需要输出的内容。tail函数根据是要输出行还是输出字符(命令行参数-c)来决定调用tail_lines还是tail_bytes。
         * tail_lines: 如果是输出末尾n行，就调用file_lines函数，从文件的末尾开始，往前找到要开始输出的位置，调用dump_remainder输出；如果要输出第n行以后的内容，就调用start_lines跳过前n行，也是调用dump_remainder输出。
         * tail_bytes和tail_lines的结构基本相同，不过那个函数是start_bytes了。
      * 如果有-f参数(follow, 不断输出文件中新增加的内容), 检查一下文件的状态；否则就可以关闭了
   * 如果指定了-f参数，那么执行if(forever && n_viable)这一段。其中n_viable是可以继续tail的文件的数量。
      * 如果linux内核支持inotify特性（监控文件的变化，并发出通知），那么调用tail_forever_inotify函数来跟踪文件的变化（添加inotify的watch，然后用select来处理）。
      * 否则使用tail_forever函数，做法是循环输出每个文件新增加的内容（上次读取的时候记录一下读取的位置），然后nanosleep一段时间（默认是1.0s）。

Oct 19

对照一下两段代码

felix021 @ 2009-10-19 00:22 [IT » 程序设计] 评论(6) , 引用(0) , 阅读(4841) | Via 本站原创

    unsigned int a = 1;
    int b = 0;
    while (a + b >= 0) {
        b--;
    }

#gcc -S a.c -o a.S
然后看到对应这些代码

    movl  $1, -4(%ebp)
    movl  $0, -8(%ebp)
L2:
    movl  -4(%ebp), %eax
    leal  -8(%ebp), %eax
    decl  (%eax)
    jmp  L2

阿牛如果有兴致的话，不妨研究一下AT&T的汇编。

Sep 15

PHP 递归处理文件

felix021 @ 2009-9-15 12:34 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(2904) | Via 本站原创

突然发现这代码我写过n遍了，真不爽。。。

<?php

$dirname = "ooxx";
$pattern = 'google';
$replace = 'baidu';
$DontReplace = true;

replace_rec($dirname);

function replace_rec($dirname, $layer = 0){
    global $DontReplace;
    static $cnt = 0;
    $dir = scandir($dirname);
    natcasesort($dir);
    foreach($dir as $item){
        if($item == '.' || $item == '..') continue;
        $path = "$dirname/$item";
        if(is_dir($path)){
            replace_rec($path, $layer+1);
        }else if(is_file($path)){
            $str = file_get_contents($path);
            if(strpos($str, $pattern) === false) continue;
            if($DontReplace == false){
                $str = str_replace($pattern, $replace, $str);
                file_put_contents($path, $str);
            }
            $cnt++;
            for($i = 0; $i < $layer; $i++) echo '  '; echo "$cnt: $path\n";
        }else{
            echo "UNKNOWN TYPE\n";
        }
    }
}
?>

Felix021