THU软院七字班参加谌老师的《程序设计基础》(C语言)同学参考,程序设计学习兴趣小组第一小组资料。

程序设计基础(C语言课程)个人讲义

仲晨(THSS#7)

http://heymu.com

第一章: 编程思想与基本编程学习的建议

为啥要学编程?

这其实是一件不是太容易说清楚的问题,如果说编程就是一门课,就太不能突出它的地位了。编程不仅是我们的第一门“专业课”,而且是我们专业特别基础的一项工 具,也可以说是我们的软件专业之所以不是“信息学与数学专业”的原因吧。编程思想其实就是计算机思想,人通过编程这项工具获得了对计算机的控制权,能够让 计算机为人的需要而运作。当自己拥有了控制计算机的工具的时候,随你想象自己能干什么吧。

大学编程课程与初高中信息竞赛的关系

我最早是认为这两者是差不多的,到了开学的时候又觉得两者有挺大的差别(是否研究算法),现在反而又觉得两者关系还是比较密切的。在天津师范大学李学武教授所写的《关于NOIP复赛的若干问题的思考》一文中说到两条很有借鉴意义的问题(NOIP是全国性的分区联赛,像我们江苏每年会有四五百人参加复赛的,属于纯普及性的竞赛):

第一,“NOIP复赛是一种难度很大的比赛,NOIP复赛普及组(也就是初中组)的试题在难度上超过了现行的大学程序设计教材中的大部分例题和习题的难度,而且至少有部分题目是新编的,是在任何参考书上找不到的。”文中估计天津师范大学计算机专业学生在大学一年级学完C语言后,组织一次相当于NOIP初中复赛难度的考试,在三个小时内能做好四题中的两题的,恐怕不会超过1/10。我提这一点不是说参加过信息竞赛就多么了不起(这里涉及研究算法的问题),就我的感觉,我们的程序设计还是要求比较高的,其实参加过或者没有参加过高中的信息竞赛都无所谓,当年参加的人也不过是从十分紧张的时间里抽出时间傻傻地学而已,这也证明了编程这种课程只要注意方法、多多练习,就可以很快地达到很娴熟的程度。

第二,“NOIP复赛是规范化的考试,黑箱测试是评定成绩的唯一手段”,所谓黑箱测试是指近年来规范化信息竞赛中使用的纯机器测试手段,隔绝各种可能的作弊手段、控制内存使用、严格控制运行时间、输入和输出都必须严格遵守格式。大概是05年时,我所在市的一名选手在复赛时把最简单一题的输出文件名中的a打成了e ,这一定是0分。当时我们自己编bat文件试验测试的时候都是用fc /b来对比输出文件和标准输出文件的!(fc是windows对比文件的函数,而加上/b是用二进制对比,所以任何多余或缺少的空格、回车什么的都算错)这一点其实对我们来学习编程也是特别重要的,计算机能够帮助我们做很多很多的事,但是也特别脆弱,我们编程的时候必须按照C语言规范和题目来严格要求自己,细心和服从“命令”是重要的原则。

编程到底是在干一件什么事?

编程,说简单了只是写代码而已,但是怎么样能让写出来的数百数千数万行的代码真正能够解决问题?

我最近突然想起这件事,有一点点的想法,请多批评。

我觉得编程实际上是干两件事:让电脑模仿人的思想让人模仿电脑的思想

举例说明,对于“求10000000以内的所有质数”这样的题目,所谓的前期设计算法过程就是运用人的思想找出一个恰当的运算方法,这种想法在一定程度上需要适合电脑的运算,但是更主要的是人所希望进行的过程(的确,编程里有好多经典算法,但很多同学落入几个狭窄的编程方法里了,比如做那种几个人说话有真有假来判断的题,就非要设个ta、tb、tc……,然后加起来等于几),在你确定使用什么算法的时候,首先你要保证自己能够使用这个算法来计算(对于一些简单而能够手工测试的情况),否则电脑更不可能算出来,挨个判断简单判断质数肯定不会是一个特别好的办法(时间上承受不了),而Eratothenes筛法是比较好的方法,当我想出(或理解)这个算法后,我可以手工来做求10以内的质数,于是人要让电脑来模仿这个算法的过程,分别做“建立数组”、“筛质数”、“输出结果”这几件事。而当我需要让电脑来真正解决这个问题的时候,则需要按照电脑的思想来做,也就是按照电脑能够正确理解的做法来决定应当怎么做,C语言里计算机是一条一条地执行命令,那么我们也要把算法的做法转换成符合C语言结构的语句。有同学写出if ( a = = b ; b = = c; c = = d ) 和 if (a = = (0 | 1)) (表示a为0或者1) 的语句,我佩服他那么有创造性。

要想让电脑来模仿人的思想,首先你必须坚持自己的算法思想千万不能迷失在代码之中得过且过只会去模仿书上的例题只想赶快把这道题做完就算完了

要想让人来模仿电脑的思想,首先你必须放弃自己的数学或生活的表示方法一定要沉迷在这种语言中怎么简单怎么来要去模仿书上或者其他的例题尽快把这道题做完

以上这两点说出来在语言上几乎是相反的了,这或许就是初学编程麻烦的地方,我们需要慢慢在失败和成功中磨练,知道什么时候该怎么干。

当我们成功通过语言这一关的时候就能很容易地来展现自己的想法了,那其实是学一门语言的终极目的和最大成就。

编程=语法+算法+数据结构

一般来说,编程界会说“编程=算法+数据结构”,但是对于初学者,语法常常成为一个难关。

简单地说,算法就是对于某个问题要对哪些数据进行哪些处理,数据结构就是对于这些数据要怎么高效地存起来(高效是指存放后更容易进行需要的操作),而语法就是怎么具体来做这件事。

这说明编程是一项系统工程,某些题目做不出来并不是自己完全没有学好,只是有一些要点暂时还没有涉及到。这本身就是慢慢积累的过程。

说到这,我肯定让大家更迷茫了,肯定有人偷偷问:

编程有没有捷径?

答案很简单:有。

编程真的是一件特别有技巧性的事,因为它所完成的任务就是具有技巧性和创造性的事。

编程有一些学习技巧是和其它课程学习相同的,比如看一些参考书,还有很多学习方法是很特别的。

我想出了几个很小但是应当很有用的方法,大家可以尝试一下。

1.整理语法:

C语言的语法还是很多很杂的,如果想专门去记忆会很麻烦。我记性不好,就找本子记下来,省得去翻那么厚的书,记个右面的图形就可以说明For语句的用法了。还有一些注意点、小技巧,很简短地记录下来。

以后忘记了语法或者要点,都可以很方便地翻出来看,省得哗哗翻书,找来找去。

其实也可以称之为“读书笔记”,在网上我找到一份署名“松江游子”的人写的《〈C程序设计〉读书笔记》,总体还算不错,大家可以参考这种格式:

2.读程序写结果

这其实是初高中信息竞赛的题型之一,一般就是给一段比较短的代码(不超过50行吧),再给一组输入的数据,要求写出应当的输出结果。说实话,做这种题目是很痛苦的,特别是那种有算法的题目,因为首先要熟悉语句,然后能通过几个简单的例子带入进行试验,理解清楚这个算法的意义(此时几乎是需要理解通所有的语句),然后再把需要的结果通过算法甚至数学方法就是出来。这一点可以参见过去几年的NOIP初赛普及组(C语言)、提高组(C语言)的试题,还有流传的一些经典代码。这一点我正在收集整理。

3.软件Debug与人工Debug

用VC++等软件提供的Debug功能来“从顶到底”(或称“从大到小”)进行调试时一件必须的事,同时也是一件需要长期使用练习才能真正掌握的功能。这一点在后文再具体说。

相对于用软件Debug,人工的Debug似乎是更有用的一项工作。俗话说:“千金难买回头看”,我好多时候也是会写完一段程序就根本不想去看了,任凭它错好了。其实真正在编写程序的时候,会有做一项很荣耀的工作一样,也希望不断完善程序,做得完美,因而会不断回头去看,甚至要欣赏自己的算法。所谓的“人工Debug”就是拿几组数据手工按照自己所写的算法来计算一遍,这可比软件Debug要强大多了,这能让自己重新审视自己的算法和其中出现的问题。这一点需要耐心(我常看到一些同学在那里不断按F5,得不到答案就难过伤心,马上找人来给他找错误,还在嘴里不断说“这肯定没错呀!”,我不太清楚世界上是否存在没有bug的程序),同时也需要在“读程序写结果”锻炼出来的功力。

有资料么?

答案也很简单:有。

这需要对照之前所说的各种方面学习的需要来说:

1.可以参看的源程序
历年的NOIP初赛里有好多优秀的源程序,都可以拿来看。各种书籍上也有好多源程序。

2.题目
历年的NOIP复赛题对于我们来说可能在算法上稍难一点,那么同样也可以在许多书籍上看到对应的题目,题目不需要多少的,因为每种算法只要真正做过一遍就基本掌握了。至于网上题库,它的好处就是用起来很完善,有对应的数据和自动测试,我觉得可以尝试一下一些比较简单的题,不要抠有算法难度的题。我原来做过USACO,似乎这题库前半部分的题还算简单。也做过同济的题库(当时只有这个是中文的),靠前的那些题也是比较正常的难度。但是说实话,这些所谓真实锻炼完全可以靠自己的耐心和认真来实现,只要你愿意自己对自己的程序负责,就可以逐步熟悉编程。

3.语法书
我们的教材似乎有点乱,可以看谭浩强的书呀,或者找《The C Programming Language》(或其中文版)之类的(这些书大多有电子版),其实也都差不多,我曾说,够厚就可以了……只要能包含足够的内容。

4.算法书
基本算法有好多,其实现在去看高中竞赛的那些教材也不丢人,当时我们江苏省里出了一套《全国青少年信息学奥林匹克联赛培训教材》(我有全套电子版),其中的中级本和高级本的算法还算不错,不过是Pascal语言的,看完之后能学会很多算法,顺便还把Pascal学会了,嘿嘿。而最棒的《计算机程序设计艺术》(1~4卷)和《算法导论》,IOI国家队教练刘汝佳、黄亮的《算法艺术与信息学竞赛》,吴文虎教授的很多算法书,这些大都难度太大了,几乎没必要看,不过也可以用来查一些算法。简单的C语言描述的算法书我还真没注意,不如还是随时上网去查一些算法吧。

5.数据结构书
清华严蔚敏教授《数据结构》有C语言描述的版本,同时也有很直观生动的演示课件,等到语法学得差不多的时候可以拿来看看。

特别强调一点,我们并不需要在算法、数据结构方面达到很高的层次,所以只要学一些简单的就可以了,别一呼拉都学完……

以上这些东西都可以找到很好的电子版本,我也正在整理,不急。

第二章: C语言概述

当代最优秀的程序设计语言

早期的C语言主要是用于UNIX系统。由于C语言的强大功能和各方面的优点逐渐为人们认识,到了八十年代,C开始进入其它操作系统,并很快在各类大、中、小和微型计算机上得到了广泛的使用。成为当代最优秀的程序设计语言之一。后来由C衍生出来的C++、C#,包括编程语法差不多的Java、asp、asp.net等都成为了各个变成领域的优秀语言。CSDN借用国外的编程社区2007年9月做的统计,目前Java占编程语言使用的21.701%,C语言紧随其后,占14.908%。

C语言的特点

C语言是一种结构化语言。它层次清晰,便于按模块化方式组织程序,易于调试和维护。(这一点或许对于大型程序工程是对的,但由于C语言十分灵活,对于具体的语句一定要加倍努力,千万不能自己想什么就是什么,我开始怀念Pascal了……)

C语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型,便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址,进行位(bit)一级的操作。由于C语言实现了对硬件的编程操作,因此C语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发,也适合于应用软件的开发。

此外,C语言还具有效率高,可移植性强等特点。因此广泛地移植到了各类各型计算机上,从而形成了多种版本的C语言。(据说C语言比起汇编效率仅多了10%,而Pascal之类的语言或许要多上30%以上吧,Java就不评价了)

C语言版本

早期常用的标准C语言系统有以下几种:·Microsoft C ·Borland Turbo C  ·AT&T C这些C语言版本不仅实现了ANSI C标准,而且在此基础上各自作了一些扩充,使之更加方便、完美。一般来说Borland公司的TC比较经典,但是过于古老(16 位的)。网上好多C源代码都是TC下的。

MinGW (gcc for Window$)、Open Watcom C/C++、Digital Mars C/C++ compiler、Borland C/C++ 5.5、M$ Visual C++ Toolkit 2003、lcc等都是目前比较常见的编译器。而IDE(开发系统)有VC++、Dev-C++、Visual MinGW、MinGW Studio、lcc-Win32。

我们课程使用的VC++是兼容C语言的windows下用户使用系统,小心它与TC的一些不兼容性(比如TC中graphics.h在VC++中不存在,因为这东东原本也并非ANSI C的标准)。近年来的NOIP和NOI竞赛似乎是使用Dev-C++ ,我没用过,但觉得总要比VC++好……同时VC++还不是免费软件,所以建议能一起来使用Dev-C