为了作为纪念,也为了了却多年来的一个遗憾,我找到一本Brain Kernighan和Dennis Ritchie合著的英文版的The C Programming Language。到2月5日终于读完了这本书。
不知道国内有多少程序员,是从谭浩强先生的那本《C语言程序设计》接触C语言的。我在这里不做评价。我本人看过不止一本C语言的教科书,K&R的这本书和其他教科书比较起来可谓是特点鲜明。
第一点,即是优点也是缺点。就是这本书不是给程序设计初学者写的!也许由于两位作者都是顶级大师的缘故吧,他们驾驭问题,解决问题的能力远非初学者 所能想象。如果没有算法和数据结构的基本功,没有计算机体系结构的理解,看这本书所得到的就苍白很多了。随便举些书中的例子,Shell排序,快速排序, 二分查找,二叉树,Hashing表,这些在大多数C语言教科书中难得一见的好例子比比皆是。这些例子,即是一个有十多年编程经验的程序员看来仍感到简介 和赏心悦目。遗憾的是初学者很难体会到这点。
第二点,我们看很多“XXX程序设计语言”的时候,看多了就会感觉雷同:常量,变量,表达式,函数,IO和库,顶多加上面向对象的一些内容。 K&R的这本书里面也有这些内容,但是他们强调C语言的特点。有时作者会提到Fortrain和Pascal,对比他们概念的异同。同我最为赞叹 的是有一章,两位作者干脆用C语言写了一个简化的C语言声明解释器,这就是编译原理中lexing和parsing的典型例子。这种类似于元编程的方式, 一下子让读者忍不住看附录的BNF语法表述,令人印象深刻。另外书中每一章节都配有习题,有的题目的工程难度还很大。
第三点,这本书是一本“打开”黑盒的书,许多人使用C语言,使用C语言的库函数,这些库函数就像是一个一个的黑盒。究竟里面是什么?很多其他书籍都 略过不谈。K&R不仅谈,而且详细给出实现,从printf到IO,甚至专门设有一章拿Unix做例子,讲System call。给出了malloc和free的实现,这些往往要在操作系统的书籍中才会谈到。而K&R把他们浓缩到薄薄200多页的书中。看这本书真 是物超所值!
最后,我吹毛求疵谈两点不同意见:一个是6.6节中Hash表的例子,作者用单向链表作为hash表中的实际存储内容来解决冲突问题,在插入一个新 元素时,会调用lookup先遍历链表检查该元素是否存在,若不存在,为避免再次遍历链表,特意把新元素插入到表头。我个人觉得,此时插入到表尾部更自然 一些,做法就如同二叉树的插入:一开始不调用lookup,而是直接从hash到的地址遍历查找,当发现到达表尾部时,就插入该元素。
还有一个是unsigned,作者在第50页就直接使用了int bitcount(unsigned x)。读者不免怀疑,是否unsigned 意味着unsigned int,全书都没有提,只有在211页的附录中才有这个规定的参考。
最后,无疑这是一本好书,奇书!值得不断的重读。
http://liuxinyu99.wordpress.com/2012/02/07/tcpl/��дC����Ҳд��һЩ�ˣ�������ԭ��������û�з�������Ȿ�飬������Ϊ��
����Ŀ̫��ͨ�ˡ������������ˡ�������ҲҪȥ������
������������뵽������һ������ڿ����飬����������ͬ��֮����������
����ͽ��ͣ�SICP����������Scheme��˼·��ĺ�һ����鼮 ��һ����Ϊ��
MIT�ľ���̲ġ��Ƽ�����Ȥ��ͬ־Ҳ���Զ�һ����
Peter
On Feb 8, 12:56 pm, rockeet febird <rock...@gmail.com> wrote:
> 插到链表尾部,需要 trace 前一个结点,有 trace 和无 trace 的链表遍历/顺序查找,性能上还是有差距的。
>
> On Feb 7, 6:31 pm, Xinyu LIU <liuxiny...@gmail.com> wrote:
>
>
>
> > Hi,
>
> > 2011年10月初,各大新闻报纸都在报道Steve Jobs辞世的消息。人们觉得失去了一个天才。实际上我们失去了不止一个天才,Dennis
> > Ritchie,C语言的发明人,Unix系统的作者之一,图灵奖获得者也辞世了。
>
> > 为了作为纪念,也为了了却多年来的一个遗憾,我找到一本Brain Kernighan和Dennis Ritchie合著的英文版的The C
> > Programming Language。到2月5日终于读完了这本书。
>
> > 不知道国内有多少程序员,是从谭浩强先生的那本《C语言程序设计》接触C语言的。我在这里不做评价。我本人看过不止一本C语言的教科书,K&R的这本书和其他教-科书比较起来可谓是特点鲜明。
>
> > 第一点,即是优点也是缺点。就是这本书不是给程序设计初学者写的!也许由于两位作者都是顶级大师的缘故吧,他们驾驭问题,解决问题的能力远非初学者
> > 所能想象。如果没有算法和数据结构的基本功,没有计算机体系结构的理解,看这本书所得到的就苍白很多了。随便举些书中的例子,Shell排序,快速排序,
> > 二分查找,二叉树,Hashing表,这些在大多数C语言教科书中难得一见的好例子比比皆是。这些例子,即是一个有十多年编程经验的程序员看来仍感到简介
> > 和赏心悦目。遗憾的是初学者很难体会到这点。
>
> > 第二点,我们看很多"XXX程序设计语言"的时候,看多了就会感觉雷同:常量,变量,表达式,函数,IO和库,顶多加上面向对象的一些内容。
> > K&R的这本书里面也有这些内容,但是他们强调C语言的特点。有时作者会提到Fortrain和Pascal,对比他们概念的异同。同我最为赞叹
> > 的是有一章,两位作者干脆用C语言写了一个简化的C语言声明解释器,这就是编译原理中lexing和parsing的典型例子。这种类似于元编程的方式,
> > 一下子让读者忍不住看附录的BNF语法表述,令人印象深刻。另外书中每一章节都配有习题,有的题目的工程难度还很大。
>
> > 第三点,这本书是一本"打开"黑盒的书,许多人使用C语言,使用C语言的库函数,这些库函数就像是一个一个的黑盒。究竟里面是什么?很多其他书籍都
> > 略过不谈。K&R不仅谈,而且详细给出实现,从printf到IO,甚至专门设有一章拿Unix做例子,讲System
> > call。给出了malloc和free的实现,这些往往要在操作系统的书籍中才会谈到。而K&R把他们浓缩到薄薄200多页的书中。看这本书真 是物超所值!
>
> > 最后,我吹毛求疵谈两点不同意见:一个是6.6节中Hash表的例子,作者用单向链表作为hash表中的实际存储内容来解决冲突问题,在插入一个新
> > 元素时,会调用lookup先遍历链表检查该元素是否存在,若不存在,为避免再次遍历链表,特意把新元素插入到表头。我个人觉得,此时插入到表尾部更自然
> > 一些,做法就如同二叉树的插入:一开始不调用lookup,而是直接从hash到的地址遍历查找,当发现到达表尾部时,就插入该元素。
>
> > 还有一个是unsigned,作者在第50页就直接使用了int bitcount(unsigned x)。读者不免怀疑,是否unsigned
> > 意味着unsigned int,全书都没有提,只有在211页的附录中才有这个规定的参考。
>
> > 最后,无疑这是一本好书,奇书!值得不断的重读。http://liuxinyu99.wordpress.com/2012/02/07/tcpl/
>
> > --
> > Larry, LIU Xinyuhttps://sites.google.com/site/algoxy/https://github.com/liuxinyu95/Al...- Hide quoted text -
>
> - Show quoted text -
> > > Larry, LIU Xinyuhttps://sites.google.com/site/algoxy/https://github.com/liuxinyu95/Al...Hide quoted text -
刘兄肯定是受 functional programming 的影响深了……
这里循环也不算太烦:
struct node *insert(struct node* lst, char* x) {
if (lst == NULL) {
lst = (struct node *)malloc(sizeof(struct node));
lst->val = strdup(x);
} else {
struct node *p = lst;
while (p->next) p = p->next;
p->next = insert(NULL, x);
}
return lst;
}
这句话没用,lst 不是引用。
struct Node
{
struct Node* next;
int value;
};
#define HASH 17
struct Node* table[HASH];
struct Node* makeNode(int x)
{
struct Node* newNode = malloc(sizeof(struct Node));
newNode->next = NULL;
newNode->value = x;
return newNode;
}
struct Node* findLast(struct Node* p, int x)
{
while (p->next != NULL)
{
if (p->value == x)
return NULL;
p = p->next;
}
if (p->value == x)
return NULL;
else
return p;
}
void insert(int x)
{
struct Node* p = table[x % HASH];
if (p == NULL)
{
table[x % HASH] = makeNode(x);
}
else
{
struct Node* last = findLast(p, x);
if (last)
last->next = makeNode(x);
}
}
On Feb 8, 9:06 pm, emacs...@gmail.com wrote:
> On Wed, Feb 08, 2012 at 06:27:01PM +0800, Xinyu LIU wrote:
> > sorry 那个==0反了,去掉即可。
>
> > 2012/2/8 Xinyu LIU <liuxiny...@gmail.com>
>
> > Hi,
>
> > 之所以说是像二叉树插入那样,是因为我优先考虑了递归:
>
> > /* insert to tail, recursive manner*/
> > struct node* insert(struct node* lst, char* x){
> > if(lst == NULL){
> > lst = (struct node*)malloc(sizeof(struct node));
> > lst->val = strdup(x);
> > }
> > else if(strcmp(lst->val, x)==0)
> > lst->next = insert(lst->next, x);
> > return lst;
> > }
>
> > 在hash桶冲突非worst case时,这个递归的开销不大。但是程序简单了很多。
>
> > 2012/2/8 rockeet febird <rock...@gmail.com>
> 刘兄肯定是受 functional programming 的影响深了......
struct Node {
struct Node* next;
int val;
};
// if write this function inline, head shouldn't be a Node**
// it should be a *Reference* in C++, any Node** is not needed
struct Node* find_insert_beg(struct Node** head, int val) {
struct Node* p;
for (p = *head; p; p = p->next)
if (p->val == val)
return p;
p = (struct Node*)malloc(sizeof(struct Node));
p->next = *head;
p->val = val;
return *head = p;
}
// Is there any other elegant code without Node** pp?
struct Node* find_insert_end(struct Node** head, int val) {
struct Node **pp, *p;
for (pp = head; p = *pp; pp = &p->next)
if (p->val == val)
return p;
p = *pp = (struct Node*)malloc(sizeof(struct Node));
p->next = NULL;
p->val = val;
return p;