指针指针

七月 20th, 2010

今天由一个函数加深了对指针的理解,是这么一个函数:

void BST_Delete(BITREE y) //删除节点y
{
    if (y->lch==NULL && y->rch==NULL && y->p)
    {
        if(y==(y->p)->lch) (y->p)->lch=NULL;
        else (y->p)->rch=NULL;
    }
    else if (y->rch==NULL && y->p)
    {
        if(y==y->p->lch) y->p->lch=y->lch;
        else y->p->rch=y->lch;
    }
    else if (y->lch==NULL && y->p){
        if(y==y->p->lch) y->p->lch=y->rch;
        else y->p->rch=y->rch;
    }
    else    {
        BITREE t=BST_Successor(y);
        y->data=t->data;
        BST_Delete(t);
        y=t;//y=NULL

    }
    free(y);
}

在最后一个else内,如果二叉搜索树中有左右孩子,那么找这个删除节点的后继,把内容互换,然后删除后继 节点,因为后继节点一定只有一个孩子或者没有孩子。最后只有一个free()操作其实是为了代码简洁,可以把前面每一个else if后面加一个free, 最后不写free()操作。但是这么写运行起来会有问题,y=t,就是所指向的地址相同,但是因为是 递归操作,t指向的地址在调用BST_Delete(t)的时候已经被free掉了,所以如果再删除一次就会 出现内存错误,修改方法是y=NULL,或者修改函数参数,用指针引用的形式 void BST_Delete( BITREE& y),然后再在free(y)后面增加一句y=NULL。以前以为两次调用free(p)是不会出现问题的,free()在释放掉p指向的内存以后,会 自动将p赋值为NULL,其实没有这部分操作。

前些天还看到一个面试题目,malloc申请的空间用delete删除会有什么问题?一般来说没有问题, 内存会释放掉,而且即使是有析构函数的对象指针,用delete删除的时候同样会调用析构函数。这说明 c++的delete操作其实是在c的基础增加了一些操作,先调用析构函数,然后释放空间。良好的编程风格 就是free/malloc,new/delete一一对应,甚至不要出现一次调用,多次释放,像上面那样的因为递归 而产生的多次释放并不是很好发现

doubanclaim7b9a5a463dd61147

《Concrete Abstractions》的一些解答

七月 20th, 2010

这本书名中文名字叫什么呢,有本《具体数学》,那么这本书“具体抽象”,矛盾了。副标题是An Introduction to Computer Science Using Scheme。可以看出这是本引论性质的计算机理论书籍。《冒号课堂》里面说过,编程中最重要的能力是抽象的能力,这本书也在培养这么一种能力,并且能代 码实现去辅助说明。这本书是美国一个大学用的一本教材(具体哪个忘记了,可以到书的主页上去看看),貌似很多大学都使用scheme作为第一门程序设计语 言,历史悠久,属于Lisp变种。像这种函数式语言虽然效率不是很高,但是语法简单,而且功能强大,支持多种程序设计方法。在这里程序就是数据,数据就是 程序,在sicp中一段不长的scheme代码就能成为一个scheme解释器。Scheme很简单,和下棋一样,人们能很快就学会其语法,这里有个很好 的教程t-y-scheme。 貌似以前美国很多大学都是用这个作为第一门程序设计语言来教学,现在用Python的更多了,函数式语言还是在渐渐被遗忘。作为引论性质的课程,广度和高 度都达到一定程度,甚至让学生站了语言设计者的角度去思考问题。其中的主线是:过程抽象,数据抽象,和状态抽象。内容涉及:递归和推导,迭代,高阶函数, 数据结构,泛型操作,实现程序设计语言,动态规划,面向对象范型等等。SICP包含这些内容,并且思想上更深入。所以先大概看看这本书对于阅读SICP(《计算机程序的构造和解释》)有很大的帮助。

大学的时候看到第五章,做了其中大部分习题,有些题目很有启发。我大四的时候做的1~5章的练习题。在这里下载。不保证所有的解法都是正确并最好的,网上这本书的相关资料比较少,而SICP的解答到是有比较多可以参考。

《深度探索C》笔记

七月 20th, 2010

最名不副实的关键字 static

这个关键字在C语言里面有两个作用,C++对这个关键词进行了扩展。

1:修饰变量,又分为局部变量和全局变量,被修饰的变量都存储在静态的内存区域。 修饰静态变量,那么只有在这个文件内可以引用它,在其他文件里面即使使用extern也不能进行访问。所以一般是放在文件头部分。 修饰局部变量,只有在定义的函数内访问,函数外不能访问,即使是在同文件内。

2:修饰函数,在函数前面添加static,那么这个函数只能在该文件内使用。这样,不同人编写的函数,如果不在同文件内,可以不用担心函数名字 相同。

main.c

int main()
{
   Func();
   reutrn 0;
}

Def.c

static void Func()
{
  printf("Func called\n");
}

编译: gcc main.c Def.c -o main 链接错误

变量的命名

min-length&&max-information

低精度数据向高精度数据扩展。

被冤枉的关键字 sizeof 用法:sizeof(int), sizeof(i), sizeof i;

if ,else float类型值与0值比较,定义一个很小的数,在某个范围内。同时不要在一个很大的浮点数和很小的浮点数之间进行运算。

循环注意点

嵌套循环中,长循环放在内,短循环放在外面,这样可以减少cpu跨切循环层的次数,利用cpu cache。 循环里面的代码尽量短,一般不超过20行。如果不行就改为循环调用函数。

void

主要作用在于对函数参数的限定和函数返回值的限定。不能对void进行算法操作。

const

修饰指针的时候的记法,就近原则。 const int *p ; p可变,指向的对象不可变 int const *p ; p可变,指向的对象不可变 int* const p; p不可变,指向的对象可变

struct 和class的区别

在C++中struct关键字与class一般可以通用,一个区别就是struct的成员默认情况下是public的,而class的是private的。

union

一个union只配置一个足够大的空间来容纳最大的数据成员,union的作用在于压缩空间。

存储的大小端:

union
{
  int i;
  char a[2];
}*p,u;

int main()
{
  p=&u;
  p->a[0]=0x39;
  p->a[1]=0x38;
  printf("%d\n",p->i);
  PrintBinary(14393);
  PrintBinary(56);
  PrintBinary(57);
  if(CheckSystem()==1)
    printf("Little endian\n");
  else
    printf("Big endian\n");

  return 0;
}

11100000111001
111000
111001
Little endian  低字节存储在低地址

指针,访问内存的钥匙

前段时间听过一个面试题,就是如何读写某人地址,答案就是指针?

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

int main()
{
    int i=0;
    int* pp=&i;
    printf("%x\n",pp);
    int* p=(int*)0x12ff60;
    printf("%x\n",p);
    *p=1;
    printf("%d\n",i);
    getchar();
    return 0;
}

这段代码在vc中编译是能够运行的,但是在gcc中不行,gcc中编译后i的地址并不是固定的,这样直接给指针赋值,写指向的地址出现访问越界。

a和&a的区别

int main()
{
  int a[5]={1,2,3,4,5};
  int* ptr=(int*)(&a+1);
  int* p=(int*)(&a);
  printf("%x\n",ptr);
  printf("%x\n",p);
  printf("%d,%d\n",*(a+1),*(ptr-1));
  return 0;
}

bfeae860 bfeae84c 2,5 说明ptr和a的地址相差5*4=20个byte。 定义数组int a5; a表示的是数组中首元素的地址,&a才是数组的首地址,两者的值是一样的,但是意义却不同。

数组当作函数参数传递

传递的是指针,也就是数组的地址,但注意如果把指针本身传递进函数的时候进行了数组的拷贝,传递的是一个拷贝。

void func(char* p)
{
  char c=p[3];
  *(p+3)='X';
  printf("%c\n",c);
}

int main()
{
  //char* p="abcdef";
  char p[]="abcdefg";
  func(p);
  printf("%s\n",p);
  return 0;

}

注意上面的区别,如果是char* p=”abcdef”,那么p为main函数的局部变量,”abcdef”的存储空间在静态内存中,func函数中可以通过指针p去访问其内容, 但如果改变其内容会发生访问越界。而char p[]=”abcdefg”,其数组的内容是在栈上。

内存管理

静态区:保存自动全局变量和 static 变量(包括 static 全局和局部变量)。静态区的内容 在总个程序的生命周期内都存在,由编译器在编译的时候分配。 栈(堆栈):保存局部变量。栈上的内容只在函数的范围内存在,当函数运行结束,这些内容 也会自动被销毁。其特点是效率高,但空间大小有限。 堆:由 malloc 系列函数或 new 操作符分配的内存。其生命周期由 free 或 delete 决定。 在没有释放之前一直存在,直到程序结束。其特点是使用灵活,空间比较大,但容易出错。

The Game of Life

七月 20th, 2010

简介

Game of Life是Princeton的一个数学家发明的游戏,这个不像一般的小游戏,有胜负,这只是一个规则很简单的模拟游戏, 规则很简单,但是过程和结果都很有趣,大三时看到一个同学实现过,去年无聊时也写了个实现,挺好玩的,最后形成的图案很有趣。

rule

平面中的一个小方格分为生和死的状态,规则是:

  1. 如果一个死的细胞周围有三个细胞是活的,在下一轮中这个位置出现一个活的细胞。
  2. 如果一个活的细胞周围有两个或者三个活的细胞,在下一轮中或者,否则下轮中该细胞死掉。
  3. 其他情况该位置维持不变。

这里的 周围 是指一个方格的周围8个位置。 规则很简单,结果也很完美,甚至是符合现实世界中生命的生死规律,一个群种只有在保持平衡的状态下才能实现良性循环。

不可能有一种初始状态使得活着的细胞数量一直增加,如果你找到一种,可以向原作者所要一笔钱,哈哈。
不管初始状态如何,真个世界在经过一段时间的演变之后都会逐渐稳定下来。
稳定的状态有很多中,分为静止的和“颤抖”的。

另外发现一些的简单规律:
并不是初始或者的数目越多最后或者的数目就越多,测试表明初始或者的数目为总量的一半的时候活着的比较多。

还有很多规律在其主页上可以找到。

实现

我这个是Linux下OpenGL实现的,红色代表死的细胞,蓝色代表活着的细胞。

初始化以后

稳定以后世界

Emacs: keyboard macros

七月 17th, 2010

宏编辑

以前知道Emacs有一个keyboard macros,不过一直没认真看一下,今天算是粗略懂了一些。宏编辑很早就有了,很多编辑器都有这种功能,word好像是有的,不过没用过,格式刷算宏编辑不?甚至Emacs 的起名有一种说法就是 Edit MACroS,最初是作为一个叫作TECO编辑器上的一套宏而编写,然后就是重写了N次,现在Emacs上还有个模拟TECO的模式:)。kbd macros就是把一系列要做的动作集合成一个,然后可以执行多次。以前有时在网上拷贝代码,但是前面都加有行好,不编辑一下不能编译,这种情况 就可以用这个kbd macro一下就解决了。 先来一个例子,比如说有这么一段文字:

Newton, Isaac
Einstein, Albert
Maxwell, James
Turing, Alan
...

现在要变成这个样子

Isaac Newton
James Maxwell
Alan Turing
...

在Emacs下可以执行下面一系列快捷键来处理一行。

action key
到行首 C-a
剪切第一个word, M-d
删除下面两个空格 DEL DEL
到行尾 C-e
插入一个空格 SPC
粘贴 C-y
到下一行 C-n

定义一个kbd macro

如果行数不多,那么敲几下键盘就可以了,如果是很多行呢,总不可能一直这样用手动的吧。上次遇到那个几百行的代码,每 行前面都有一个表示行数目的数字,一狠心写了个C程序来处理,囧。为了不让手指报废,定义一个kbd macro是很快速的方法。也就是在我处理的一行的之前按F3(或者”C-x (” ),在处理第一行的时候Emacs已经在记录这即个命令,结束完一行的处理就可以按F4(或者”C-x )”。这样就已经完成了定义。

使用宏

定义好以后下面的很多行都可以使用这个宏去操作,只要按C-x e就是执行上一次定义的宏,C-u 20 C-x e执行20次,甚至可以选中一个区域然后执行M-x apply-macro-to-region-lines (或者 C-x C-k r)。但这个时候宏里面别加go-to-the-next-line,因为上面这个命令就已经是逐渐移动区域的每一行,执行上面的宏,如果再加goto命 令就会跳过一些行。另外还可以手动编辑这个宏,命令M-x edit-kbd-macro,会让你选择要编辑的宏,比如说选刚才保存的那个宏,得到:

;; Keyboard Macro Editor.  Press C-c C-c to finish; press C-x k RET to cancel.
;; Original keys: C-a M-d 2*C-d C-e SPC C-y C-n
Command: last-kbd-macro
Key: none
Macro:
C-a			;; move-beginning-of-line
M-d			;; kill-word
2*C-d			;; delete-char
C-e			;; move-end-of-line
SPC			;; self-insert-command
C-y			;; yank
C-n			;; next-line

编辑完后按C-c C-c完成。

如果这个操作经常会用到(比如清楚带行号的代码),还可以把这个操作保存下来,以后都可以用。在.emacs或者自己的配置文件中增加:

(fset 'foo
   [?\C-a ?\M-d delete delete ?\C-e ?  ?\C-y ?\C-n])
然后可以把这个函数绑定个快捷键,或者直接M-x调用。

乱想想

七月 15th, 2010

哈哈,终于还是弄了独立空间,yo2还在崩溃中,没前的还没转过来。新的空间速度不错,服务也可以,可是在教育网内不能访问,算了,教育网内能访问的就那么几个。

中午下了场雨,可还是很闷,下午在看《The Practice of Programming》,不错的书。两天没去实验室了,那里闷得慌。这个月还是打算在学校待着,8月份回家一趟。昨天一个校友从上海回来,大家一起聊了会,对他们那公司挺感兴趣的,准备有机会去面试一下。这些天经常睡不着,睡着也做梦。我就是这样,在生活的链接点比较焦虑,比如说升学时,这会是找工作了。一些朋友会说,你那么当心干什么,找份工作应该不难,况且你又平常又不是懒人,还是学了点东西的。呵呵,我是天生有点悲观吧,总会忍不住去想结果。这会倒比较轻松,工作有好坏之分么,适合自己的工作才是最好的吧,做自己想做的领域才会有激情,现在工作的愿望比两年前强多了。同时我也比较能看得到自己的弱点。我很清楚自己不是想搞科研,可能也不是很适合。对于写论文,我更倾向于写代码。我不适合做市场,同人打交道好像要比同机器打交道要难。我不适合做管理,尽管有时候想改变自己的一些性格特点,现在回想起来勉强自己做的那些并没什么好的效果。总之,既然想搞所谓的挨踢行业,想走技术路线,那还是好好的坚持吧,The lyf so short, the craft so long to lerne.. 在学校还能好好看看想看的书,以后就是MOP了,珍惜珍惜!

控制自己的思绪和情绪是件比较重要的事情,“憩于理性,行于热情”这是我所期望的,抓紧时间好好享受这段最后的单调的校园生活。面包会有的,哼哈。

Pages: Prev 1 2 3 4 5 6 7 8 9 10 Next