[OT][TCPL]The C Programming Language

77 views
Skip to first unread message

Xinyu LIU

unread,
Feb 7, 2012, 5:31:10 AM2/7/12
to pon...@googlegroups.com
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 Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY

Matrix Le

unread,
Feb 7, 2012, 5:42:23 AM2/7/12
to pon...@googlegroups.com
大一初学C语言,“胆大包天”用这本书做教材。看到第二章就碰的头破血流,怀疑自己的智商

Jawley

unread,
Feb 7, 2012, 11:12:58 AM2/7/12
to pon...@googlegroups.com
C语言本身就不适合作为初学者入门,再用一本难度大的书,可想而知。

另外跑个题,公众更感慨Steve Jobs而不是Dennis Ritchie,一方面是前者更贴近公众,另一方面更重要的是,Jobs是英年早逝,仅56岁,本来还可以做出更多东西,逝世前几个月还活跃在第一线。而后者已经70岁,算寿终正寝,该做的事也做完了。所以两件事情不太一样。

Peter Xu

unread,
Feb 7, 2012, 9:13:18 PM2/7/12
to pon...@googlegroups.com
�� 2012/2/7 18:31, Xinyu LIU �:
> Hi,
>
> 2011��10�³����������ű�ֽ���ڱ���Steve Jobs��������Ϣ�����Ǿ���ʧȥ��
> һ����š�ʵ��������ʧȥ�˲�ֹһ����ţ�Dennis Ritchie��C���Եķ���
> �ˣ�Unixϵͳ������֮һ��ͼ�齱�����Ҳ�����ˡ�
>
> Ϊ����Ϊ���ҲΪ����ȴ��������һ���ź������ҵ�һ��Brain Kernighan��
> Dennis Ritchie�����Ӣ�İ��The C Programming Language����2��5�����ڶ�
> �����Ȿ�顣
>
> ��֪�������ж��ٳ���Ա���Ǵ�̷��ǿ������DZ���C���Գ�����ơ��Ӵ�C����
> �ġ��������ﲻ�����ۡ��ұ��˿���ֹһ��C���ԵĽ̿� �飬K&R���Ȿ���
> ����̿���Ƚ�������ν���ص�������
>
> ��һ�㣬�����ŵ�Ҳ��ȱ�㡣�����Ȿ�鲻�Ǹ������Ƴ�ѧ��д�ģ�Ҳ������
> ��λ���߶��Ƕ�����ʦ��Ե�ʰɣ����Ǽ�Ԧ���⣬���������� ��Զ�dz�ѧ��
> �����������û���㷨����ݽṹ�Ļ���û�м������ϵ�ṹ����⣬��
> �Ȿ����õ��ľͲ԰׺ܶ��ˡ�����Щ���е����ӣ�Shell ���򣬿�������
> ���ֲ��ң���������Hashing�?��Щ�ڴ����C���Խ̿������ѵ�һ��ĺ�����
> �ȱȽ��ǡ���Щ���ӣ�����һ����ʮ�����̾���ij��� Ա�����Ըе���� ��
> ������Ŀ���ź����dz�ѧ�ߺ�����ᵽ��㡣
>
> �ڶ��㣬���ǿ��ܶࡰXXX����������ԡ���ʱ�򣬿����˾ͻ�о���ͬ��������
> ���������ʽ������IO�Ϳ⣬���������������һЩ ���ݡ� K&R���Ȿ��
> ����Ҳ����Щ���ݣ���������ǿ��C���Ե��ص㡣��ʱ���߻��ᵽFortrain��
> Pascal���Ա����Ǹ������ ͬ��ͬ����Ϊ��̾ ������һ�£���λ���߸ɴ���C
> ����д��һ���򻯵�C��������������������DZ���ԭ����lexing��parsing�ĵ�
> �����ӡ��������� ��Ԫ��̵ķ�ʽ�� һ�����ö����̲�ס����¼��BNF����
> ��������ӡ����̡���������ÿһ�½ڶ�����ϰ�⣬�е���Ŀ�Ĺ����ѶȻ��ܴ�
>
> ����㣬�Ȿ����һ�����򿪡��ںе��飬�����ʹ��C���ԣ�ʹ��C���ԵĿ⺯
> ����Щ�⺯�������һ��һ���ĺںС�����������ʲô���� �������鼮�� ��
> ��̸��K&R����̸��������ϸ���ʵ�֣���printf��IO������ר������һ����
> Unix�����ӣ���System call�������malloc��free��ʵ�֣���Щ����Ҫ�ڲ���
> ϵͳ���鼮�вŻ�̸������K&R������Ũ��������200��ҳ�����С����Ȿ����
> ���ﳬ��ֵ��
>
> ����Ҵ�ë���̸���㲻ͬ���һ����6.6����Hash������ӣ������õ���
> ������Ϊhash���е�ʵ�ʴ洢�����������ͻ���⣬ �ڲ���һ���� Ԫ��ʱ����
> ����lookup�ȱ����������Ԫ���Ƿ���ڣ��������ڣ�Ϊ�����ٴα������?
> �������Ԫ�ز��뵽��ͷ���Ҹ��˾��ã���ʱ�� �뵽��β������Ȼ һЩ������
> ����ͬ�������IJ��룺һ��ʼ������lookup������ֱ�Ӵ�hash���ĵ�ַ�����
> �ң������ֵ����β��ʱ���Ͳ����Ԫ�ء�
>
> ����һ����unsigned�������ڵ�50ҳ��ֱ��ʹ����int bitcount(unsigned x)��
> ���߲��⻳�ɣ��Ƿ�unsigned ��ζ��unsigned int��ȫ�鶼û���ᣬֻ����211
> ҳ�ĸ�¼�в�������涨�IJο���
>
> �����������һ�����飬���飡ֵ�ò��ϵ��ض���Hi, Larry,

��дC����Ҳд��һЩ�ˣ�������ԭ��������û�з�������Ȿ�飬������Ϊ��
����Ŀ̫��ͨ�ˡ������������ˡ�������ҲҪȥ������

������������뵽������һ������ڿ����飬����������ͬ��֮����������
����ͽ��ͣ�SICP����������Scheme��˼·��ĺ�һ����鼮 ��һ����Ϊ��
MIT�ľ���̲ġ��Ƽ�����Ȥ��ͬ־Ҳ���Զ�һ����

Peter

rockeet febird

unread,
Feb 7, 2012, 11:56:27 PM2/7/12
to TopLanguage
插到链表尾部,需要 trace 前一个结点,有 trace 和无 trace 的链表遍历/顺序查找,性能上还是有差距的。

Shuo Chen

unread,
Feb 8, 2012, 12:09:19 AM2/8/12
to TopLanguage
no,
对于这个问题,只需要看当前节点,如果当前节点的 next 为空,则 append to 当前节点即可。
我猜原书插在头部的原因是为了优化访问,如果新插入的元素的查询几率更高,那么插在头部查起来会比较快。

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 -

rockeet febird

unread,
Feb 8, 2012, 12:47:03 AM2/8/12
to TopLanguage
不使用二级指针,无法写出一个简单、优雅的链表尾部插入代码(需要考虑初始为空链表的情况)。而考虑空链表并且不使用二级指针,链表头部插入的代码是非
常 trivial 的。

> > > Larry, LIU Xinyuhttps://sites.google.com/site/algoxy/https://github.com/liuxinyu95/Al...Hide quoted text -

Xinyu LIU

unread,
Feb 8, 2012, 5:24:15 AM2/8/12
to pon...@googlegroups.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 <roc...@gmail.com>

Xinyu LIU

unread,
Feb 8, 2012, 5:27:01 AM2/8/12
to pon...@googlegroups.com
sorry 那个==0反了,去掉即可。

2012/2/8 Xinyu LIU <liuxi...@gmail.com>

emac...@gmail.com

unread,
Feb 8, 2012, 8:06:04 AM2/8/12
to pon...@googlegroups.com

刘兄肯定是受 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;
}

Shuo Chen

unread,
Feb 8, 2012, 8:23:07 AM2/8/12
to TopLanguage
> > lst = (struct node*)malloc(sizeof(struct node));

这句话没用,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 的影响深了......

Xinyu LIU

unread,
Feb 8, 2012, 10:31:17 PM2/8/12
to pon...@googlegroups.com
Hi

你没有注意到最后lst被return了么?

2012/2/8 Shuo Chen <gian...@gmail.com>

rockeet febird

unread,
Feb 9, 2012, 4:49:03 AM2/9/12
to TopLanguage
这就是为什么我说不用二级指针(某种程度上类似于trace)难以写出优雅的 insert_end。下面的代码对空链表和非空链表的处理是完全相同
的。

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;

Reply all
Reply to author
Forward
0 new messages