Nov 7
#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) , 阅读(3549) | 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) , 阅读(10418) | 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) , 阅读(4390) | 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) , 阅读(2645) | 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";
        }  
    }  
}
?>
Aug 17

关于delete 不指定

felix021 @ 2009-8-17 15:07 [IT » 程序设计] 评论(4) , 引用(0) , 阅读(4480) | Via 本站原创
前两天在Dutor(或者是Ivan?)的Blog看到了一篇文章:
关于free和delete http://www.dutor.net/index.php/2009/08/free-delete/

以前没有仔细考虑过这个问题,因此和Sandy讨论了一下,得出了初步结果,总结一下放在这里吧。

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

先看一段代码:
#include<iostream>
class T{
public:
    int *a;
    T() {
        a = new int[1048576];
        std::cout << "T()" << endl;
    }
    ~T() {
        delete[] a;
        std::cout << "~T()" << endl;
    }
};

int main() {
    T *a = new T;
    delete (char*)a;
}

这段代码的前面还是比较好理解的,关键在于,这最后的 delete (char *)a; 它究竟做了什么事情?
1. 它释放了多少内存——是释放了一个char*指向的内存,还是当初new分配的那些内存?
2. 它是否调用了class T的析构函数?

下面是我和Sandy的讨论结果,针对以上两个问题的分析,以及一点延伸的探讨。

1. 释放了多少内存。
回头想想C提供的malloc/free函数,这小俩口处理的都是void*类型的指针,而且当free时只要告诉其指针即可。
也就是说,malloc函数多做了一些事情,让程序在某处记住了分配的内存大小,当free时,对应找到这个大小进行释放。
因此我们有理由认为,new/delete这对黑白脸做法也是类似的(没有小心求证,如果不对,请大牛指出):
-- new从堆上申请内存,是先进行记录,包括新内存的地址以及申请的长度,然后才把地址返回给申请者。
-- delete根据释放者提交的地址,在记录中查找这个地址,然后找到其长度,然后回收内存。。
故此我们认为,它释放的内存是new分配的那些内存,与传入的指针类型无关。

2. 是否调用了相应的析构函数。
这个问题很容易验证,把上面的程序跑一遍就可以了。
结果就是,输出了 "T()" 这一行,说明只调用了构造函数而没有调用析构函数。
仔细想想,其实这很容易理解。
隐约记得STL之父(Or C++之父?)说过一句话,你有很多事情做,但是编译器没有。
C++编译器被设计成帮你完成了很多琐碎的事情,很典型的一件事就是,编译期类型推导。
因此你在cout的时候也不需要指定输出类型(%d%x%c...)
new一个东西以后不需要像malloc那样进行强制类型转换了,还自动调用class 的构造函数,
delete一个指向class的指针时,也根据指针的类型自动添加了调用该class析构函数的代码。
而上面给出的代码,最终交给delete的是一个char *类型的指针
因此编译器添加的代码就不会涉及到class T的析构函数。
如果你是转换成另一个class Q的指针,那么就会调用Q的析构函数。有兴趣的话可以自己写程序证实一下。

3. 它会导致严重的后果吗?
答案是会。
比如上面给出的程序,造成了内存泄漏:预期在析构函数中释放的 T::a 指向的内存,但是析构函数最终没有被执行。

4. 它会导致更严重的后果吗?
答案还是会。
这一点是Sandy提出来的:在C++中,operator new/delete是可以被重载的。
如果一个class的operator new/delete被重载了,它将以它自己的方式去管理(分配/回收)内存。
比如说以内存池的方式;或者是在栈上进行分配的内存。
如果你使用这种方式去delete一个改变了类型的指针,那么结果就是,采用了不同的管理方式去回收这个内存。
——就好比你malloc出来的内存被delete掉了
传说中的换妻啊。。。后果就是对方崩溃了。。。嗯。

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

这个问题到这里差不多了,实际使用中应该不会有谁这么脑残的吧,嗯。
进行这样的一些分析,主要是希望能够更深入地理解C++这一块的内容。

还没有确切解决的疑问就是第一个——
new/delete 释放的内存块大小是否关乎指针类型?希望有大牛释疑。

另外顺便提一下,我觉得当在C++中需要使用对class进行强制类型转换的时候,
应该好好考虑一下,这程序是不是在设计上出了什么问题,因为这么做会增加程序的耦合性。
当然,在某些时候你的确会需要用到这种做法,因为这样可以增加程序的动态性(许多Java程序依赖于此)。
Jul 26
1. 选中收件箱和发件箱


2. 菜单->操作->导出文本


3. 把导出的短信都放在一个目录下面


4. 在目录下放一个convertencoding.php,内容为:
<?php
$dir = scandir(".");
foreach($dir as $file){
    if(substr($file, -3) != "txt") continue;
    echo $file, "\n";
    $str = file_get_contents($file);
    $str = iconv("GB18030", "UTF-8", $str);
    file_put_contents($file, $str);
}
?>
然后$ php convertencoding.php 运行之。


5. 另一个php脚本,用于提取和指定的人的聊天记录
Jul 26

php数组按键排序 不指定

felix021 @ 2009-7-26 15:47 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(5373) | Via 本站原创
遇到一个问题:
有一个数组,其中每个元素都包含time和content两个子元素,需要按time字段排序。

记得以前是搞过这个东西的,有个专门的函数,貌似就是array_multisort来搞。
查了一下mannual,发现例子实在太晦涩,看起来很不爽。
于是干脆自己实现一个,只需要提供一个排序函数即可。
效率可能低一些,但是用起来舒服多了。。

//调用例子(cmp函数可以自己重写):
mysort($array_name, 0, count($array_name) - 1, cmp);

function cmp($i, $j){
    return $i['time'] < $j['time'];
}

function mysort(&$arr, $s, $e, $func){
    $i = $s; $j = $e; $tmp = $arr[$s];
    if($s < $e){
        while($i != $j){
            while($i < $j && $func($tmp, $arr[$j])) $j--;
            if($i < $j){
                $arr[$i] = $arr[$j];
                $i++;
            }
            while($i < $j && $func($arr[$i], $tmp)) $i++;
            if($i < $j){
                $arr[$j] = $arr[$i];
                $j--;
            }
        }
        $arr[$i] = $tmp;
        mysort($arr, $s, $i-1, $func);
        mysort($arr, $i+1, $e, $func);
    }
}
分页: 9/21 第一页 上页 4 5 6 7 8 9 10 11 12 13 下页 最后页 [ 显示模式: 摘要 | 列表 ]