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;
}
#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
好久没有写了,写错了好久,后来发现是挂在指针上了,真杯具。
#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;
}
#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源码阅读笔记
---++ 获取源码
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)。
---++ 获取源码
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
unsigned int a = 1;
int b = 0;
while (a + b >= 0) {
b--;
}
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
movl $0, -8(%ebp)
L2:
movl -4(%ebp), %eax
leal -8(%ebp), %eax
decl (%eax)
jmp L2
阿牛如果有兴致的话,不妨研究一下AT&T的汇编。
Sep
15
突然发现这代码我写过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";
}
}
}
?>
$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
前两天在Dutor(或者是Ivan?)的Blog看到了一篇文章:
关于free和delete http://www.dutor.net/index.php/2009/08/free-delete/
以前没有仔细考虑过这个问题,因此和Sandy讨论了一下,得出了初步结果,总结一下放在这里吧。
---传说中的分割线---
先看一段代码:
这段代码的前面还是比较好理解的,关键在于,这最后的 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程序依赖于此)。
关于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;
}
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,内容为:
5. 另一个php脚本,用于提取和指定的人的聊天记录
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 运行之。$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);
}
?>
5. 另一个php脚本,用于提取和指定的人的聊天记录
Jul
26
遇到一个问题:
有一个数组,其中每个元素都包含time和content两个子元素,需要按time字段排序。
记得以前是搞过这个东西的,有个专门的函数,貌似就是array_multisort来搞。
查了一下mannual,发现例子实在太晦涩,看起来很不爽。
于是干脆自己实现一个,只需要提供一个排序函数即可。
效率可能低一些,但是用起来舒服多了。。
有一个数组,其中每个元素都包含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);
}
}
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);
}
}