目录CONTENTS第1章C/C 语言概述1
1.1程序的基本框架1
1.2变量2
1.2.1变量的定义2
1.2.2变量的赋值3
1.2.3变量的引用3
1.3C/C 语言的数据类型3
1.4常量5
1.5运算符和表达式6
1.5.1算术运算符6
1.5.2赋值运算符8
1.5.3关系运算符8<p> </p> <p> </p> <p>目录CONTENTS第1章C/C 语言概述1</p> <p>1.1程序的基本框架1</p> <p>1.2变量2</p> <p>1.2.1变量的定义2</p> <p>1.2.2变量的赋值3</p> <p>1.2.3变量的引用3</p> <p>1.3C/C 语言的数据类型3</p> <p>1.4常量5</p> <p>1.5运算符和表达式6</p> <p>1.5.1算术运算符6</p> <p>1.5.2赋值运算符8</p> <p>1.5.3关系运算符8</p> <p>1.5.4逻辑运算符9</p> <p>1.5.5位运算符9</p> <p>1.5.6sizeof运算符12</p> <p>1.5.7类型强制转换运算符13</p> <p>1.5.8运算符的优先级13</p> <p>1.6注释14</p> <p>1.7分支语句15</p> <p>1.7.1if语句15</p> <p>1.7.2switch语句17</p> <p>1.8循环语句19</p> <p>1.8.1for语句19</p> <p>1.8.2while语句20</p> <p>1.8.3dowhile语句20</p> <p>1.8.4break语句21</p> <p>1.8.5continue语句21</p> <p>1.9函数22</p> <p>1.9.1函数的定义22</p> <p>1.9.2函数的调用23</p> <p>1.9.3参数传递和返回值24</p> <p>1.9.4库函数和头文件25</p> <p>1.10标准输入输出25</p> <p>1.10.1printf函数(标准输出函数)25</p> <p>1.10.2scanf函数(标准输入函数)26</p> <p>目录第 11 章程序设计导引及在线实践(第2版)1.11全局变量和局部变量27</p> <p>1.12数组28</p> <p>1.12.1一维数组28</p> <p>1.12.2二维数组30</p> <p>1.12.3数组的初始化31</p> <p>1.12.4数组越界32</p> <p>1.13字符串33</p> <p>1.13.1字符串常量33</p> <p>1.13.2用字符数组存放的字符串34</p> <p>1.14指针36</p> <p>1.14.1指针的基本概念36</p> <p>1.14.2指针运算39</p> <p>1.14.3���指针40</p> <p>1.14.4指向指针的指针41</p> <p>1.14.5指针和数组41</p> <p>1.14.6字符串和指针43</p> <p>1.14.7void指针44</p> <p>1.14.8函数指针45</p> <p>1.14.9指针和动态内存分配47</p> <p>1.14.10误用无效指针50</p> <p>1.15结构50</p> <p>1.15.1“结构”的概念50</p> <p>1.15.2结构变量的定义51</p> <p>1.15.3访问结构变量的成员变量52</p> <p>1.15.4结构变量的初始化52</p> <p>1.15.5结构数组52</p> <p>1.15.6指向结构变量的指针53</p> <p>1.15.7动态分配结构变量和结构数组55</p> <p>1.16文件读写55</p> <p>1.16.1用fopen打开文件56</p> <p>1.16.2用fclose关闭文件56</p> <p>1.16.3用fscanf读文件,用fprintf写文件57</p> <p>1.16.4用fgetc读文件,用fputc写文件58</p> <p>1.16.5用fgets函数读文件,fputs函数写文件59</p> <p>1.16.6用fread读文件,用fwrite写文件60</p> <p>1.16.7用fseek改变文件读写的当前位置63</p> <p>1.17C语言标准库函数64</p> <p>1.17.1数学函数64</p> <p>1.17.2字符处理函数65</p> <p>1.17.3字符串处理和内存操作函数65</p> <p>1.17.4字符串转换函数66</p> <p>1.18命令行参数66</p> <p>1.19C/C 编码规范67</p> <p>1.19.1标识符命名注意事项68</p> <p>1.19.2程序的书写格式68</p> <p>1.19.3注释的写法70</p> <p>1.19.4一些好的编程习惯71</p> <p>第2章简单计算题73</p> <p>2.1例题: 鸡兔同笼73</p> <p>2.2例题: 棋盘上的距离74</p> <p>2.3例题: 校门外的树77</p> <p>2.4例题: 填词78</p> <p>2.5例题: 装箱问题80</p> <p>练习题82</p> <p>第3章数制转换问题85</p> <p>3.1相邻数字的基数等比: 确定进制85</p> <p>3.2相邻数字的基数不等比: skew数87</p> <p>练习题89</p> <p>第4章字符串处理90</p> <p>4.1简单的字符串操作示例90</p> <p>4.2例题: 统计字符数91</p> <p>4.3例题: 487327993</p> <p>4.4例题: 子串96</p> <p>4.5例题: Caesar密码99</p> <p>练习题101</p> <p>第5章日期和时间处理104</p> <p>5.1例题: 判断闰年104</p> <p>5.2例题: 细菌繁殖107</p> <p>5.3例题: 日历问题112</p> <p>5.4例题: 玛雅历113</p> <p>5.5例题: 时区间时间的转换116</p> <p>练习题120</p> <p>第6章模拟121</p> <p>6.1例题: 约瑟夫问题121</p> <p>6.2例题: 花生问题123</p> <p>6.3例题: 显示器126</p> <p>6.4例题: 排列130</p> <p>练习题133</p> <p>第7章高精度计算136</p> <p>7.1例题: 大整数加法136</p> <p>7.2例题: 大整数乘法138</p> <p>7.3例题: 大整数除法141</p> <p>7.4例题: 麦森数145</p> <p>练习题148</p> <p>第8章枚举149</p> <p>8.1枚举的基本思想149</p> <p>8.2简单枚举的例子: 生理周期150</p> <p>8.3数学模型中包括多个变量的例子: 称硬币151</p> <p>8.4搜索空间中解不**的例子: **立方154</p> <p>8.5遍历搜索空间的例子: 熄灯问题156</p> <p>8.6优化判断条件的例子: 讨厌的青蛙160</p> <p>练习题165</p> <p>第9章递归167</p> <p>9.1递归的基本思想167</p> <p>9.2例题: 全排列168</p> <p>9.3例题: 八皇后问题170</p> <p>9.4例题: 逆波兰表达式174</p> <p>9.5例题: 四则运算表达式求值175</p> <p>9.6例题: 放苹果179</p> <p>9.7例题: 简单的整数划分问题180</p> <p>9.8例题: 算24181</p> <p>9.9例题: 红与黑184</p> <p>9.10例题: 二叉树186</p> <p>9.11例题: 拯救少林神棍187</p> <p>练习题193</p> <p>第10章动态规划196</p> <p>10.1什么是动态规划196</p> <p>10.2动态规划解题的一般思路199</p> <p>10.3例题: *长上升子序列200</p> <p>10.4例题: 帮助Jimmy202</p> <p>10.5例题: *长公共子序列206</p> <p>10.6例题: 神奇口袋208</p> <p>10.7例题: 灌溉草场210</p> <p>10.8例题: 方盒游戏215</p> <p>10.9例题: 美妙栅栏221</p> <p>练习题225</p> <p>第11章链表228</p> <p>11.1单向链表、链表结点的插入228</p> <p>11.2带表头的单向链表、链表的搜索232</p> <p>11.3双向链表、链表结点的排序235</p> <p>11.4循环链表、链表结点的删除238</p> <p>11.5链表的应用: 计算每个作业的运行时间241</p> <p>练习题247</p> <p>第12章二叉树249</p> <p>12.1二叉树的建立250</p> <p>12.2基于递归的二叉树遍历254</p> <p>12.3平衡二叉树257</p> <p>练习题263</p> <p>附录A北京大学程序在线评测系统介绍264</p> <p>A.1POJ的使用情况264</p> <p>A.2POJ的主要功能265</p> <p>A.3使用本书结合POJ进行教学时的用法266</p> <p>附录B本书题目在POJ上的编号267</p> <p>致谢271</p>显示全部信息前 言主任: 李晓明副主任: 蒋宗礼卢先和委员: (按姓氏笔画为序)马华东马殿富王志英王晓东宁洪刘辰孙茂松李仁发李文新杨波吴朝晖何炎祥宋方敏张莉金海周兴社孟祥旭袁晓洁钱乐秋黄国兴曾明廖明宏秘书: 张瑞庆
本书主审: 李晓明
本 书 序PREFACE主任: 李晓明副主任: 蒋宗礼卢先和委员: (按姓氏笔画为序)马华东马殿富王志英王晓东宁洪刘辰孙茂松李仁发李文新杨波吴朝晖何炎祥宋方敏张莉金海周兴社孟祥旭袁晓洁钱乐秋黄国兴曾明廖明宏秘书: 张瑞庆<br /><br />本书主审: 李晓明<br />本 书 序PREFACE<br />本书是一本与众不同的程序设计入门教材,实践性极强,不论对于高等学校计算机专业的学生,还是非计算机专业的学生,都非常适用。目前绝大部分程序设计入门教材的主要内容就是详细介绍一门程序设计语言,这对于高等学校计算机专业的学生是远远不够的;对于非计算机专业的学生也略显肤浅。许多大学本科计算机专业的课程设置,在程序设计语言和数据结构这两门课之间,并无空间进行基础算法的教学,这就容易导致学生由于基本技能缺失而在学习数据结构课程时产生困难,或难以学精。对于非计算机专业的学生来说,如果仅掌握一门程序设计语言的语法规则,写几个打印由星号组成的三角形之类的“玩具”程序,而对计算机科学的基础与灵魂——算法一无所知,不明白计算机到底是怎么解决问题的,那么在日后的工作中,不但不可能自己编写实用程序,甚至不能敏感地及时意识到哪些问题适合用计算机处理,可以交给计算机专业人士来做。本书将程序设计语言和*基本的算法思想相结合,能够有效避免上述现象。本书的*大特点是和“北京大学程序在线评测系统”紧密结合,具有极强的实践性。“北京大学程序在线评测系统”(Peking University Online Judge System,POJ)是一个免费的公益性网上程序设计题库,网址为http://acm.pku.edu.cn/JudgeOnline(注意这里的网址区分大小写)。它包含2000多道饶有趣味的程序设计题目,题目大部分来自ACM/ICPC国际大学生程序设计竞赛,很多题目就反映工作和生活中的实际问题。这些题目有易有难,比如*简单的题A B Problem就是给出两个数,输出它们的和。用户可以针对某个题目编写程序并提交,POJ 会自动判定程序的对错。本书的所有例题和课后习题大都精选自POJ题库,难度较低,学生做习题时可以将自己的程序提交给POJ,几秒钟之内即可知道是对还是错。作为教学支持,每位学生在POJ上可以建立自己的账号,教师在POJ上一眼就能看到学生是否已经完成布置的习题,这几乎将教师评判学生作业的工作量减少到零。POJ对于程序的正确性评判是极为严格的,学生的程序根据POJ给出的输入数据进行计算并输出结果,POJ在服务器端编译、运行学生提交的程序,取得输出结果和标准答案对比,必须一个字节都不差,程序才能够通过。这对于培养严谨、周密的程序设计作风极为有效,学生必须考虑到每一个细节和特殊边界条件,而不是大体上正确就能够通过。传统的人工评判是难以做到这一点的。本书的另一特点是在叙述中穿插了许多精心编制的思考题,特别适合教师进行启发式教学。思考题没有答案,以便教师引导学生进行讨论。程序设计导引及在线实践(第2版)本书还有一个亮点,就是在许多例题后都会总结学生在完成该题时容易犯的典型错误,让学生少走弯路。这些错误都总结自学生在POJ上提交的程序,因而具有典型性。本书中代码的风格也很值得一提。许多程序设计教程,其编写者虽有丰富的教学经验,但却不一定具有实际的软件开发经历,因而书中的例子程序往往在变量命名、代码效率等程序设计风格方面不是很在意,只求正确即可,教学代码的痕迹明显。而本书的作者除了具有多年的教学经验以外,还从事过多年的软件开发。李文新教授是国内**个自主研制的地理信息系统开发环境GeoUnion的主要设计者和核心代码编写者之一,曾经担任过图原空间信息技术有限公司和长天科技有限公司的总工程师。她目前是中国计算机学会信息学奥林匹克竞赛科学委员会的科学委员,是ACM/ICPC竞赛北京大学代表队的原任教练和现任领队。余华山副教授多年来一直从事支持高性能计算的程序开发与运行环境的研究工作,是集群并行程序开发与运行平台P_HPF系统的主要研制者之一,主持开发了计算网格协同平台 Harmonia系统。在中国教育科研网格China Grid公共软件支撑平台CGSP的研制过程中,他是总体设计的主要负责人之一,并负责CGSP信息服务系统的设计和实现。郭炜老师的专业研究方向是计算机辅助教学,他独立开发了《我爱背单词》等系列**英语学习软件,同时还担任教练,和李文新教授一起率领北京大学ACM/ICPC国际大学生程序设计竞赛队在国际竞赛中取得了较好名次。本书中的例子程序的代码风格优美、注释完备、可读性强,以此作为范例,对培养良好的程序设计风格,日后在团队开发中赢得同事的信任和喜爱十分有益。在这个提倡创新的年代,本书是特别富有创意的,希望并相信读者能够喜欢。<br />2007年8月北京大学教授原教育部高等学校计算机科学与技术教学指导委员会副主任21世纪大学本科计算机专业系列教材编委会主任<br />前言FOREWORD计算机程序是通过在计算机内存中开辟一块存储空间,并用一个语句序列不断修改这块存储空间上的内容,*终得到问题的答案的方法来解决实际问题的。计算机程序一般需要用一种具体的程序设计语言表达出来。一种计算机语言通过定义变量的形式给出了申请内存的方式,并通过表达式和赋值语句给出了对内存中的数据进行运算和修改的方法,通过分支和循环语句提供了用不同方式安排语句序列的能力。大部分计算机语言还提供了基础函数库来完成一些常用的计算和数据处理的功能。使用计算机程序解决实际问题,首先要能够将一个具体问题抽象成一个可计算的问题,并找出可行的计算过程;其次是掌握一门程序设计语言,将设计的计算过程写成具体的代码在机器上运行。作者总结了多年计算机程序设计类课程的教学经验,认为在程序设计课程的教学中应该把握5个基本的教学环节: **,让学生充分理解计算机程序在内存中的运行原理和过程。在程序运行过程中任意时刻都清楚语句运行到了哪里,以及当前存储数据的内存区的内容是什么。只有清楚这些,才能在程序调试过程中及时地找到出错位置,并修改错误,*终让程序按照设计者的意图执行。第二,以一门**程序设计语言为例,让学生了解该设计语言使用哪些语句定义变量,哪些语句修改变量,变量有哪些基本类型,每种类型的变量占多大的存储空间,不同类型的变量可以进行哪些运算,哪些语句用来控制语句序列的分支和循环,如何用简单变量组合出复杂变量(如数组或结构体),如何控制复杂的计算过程(如通过函数实现分而治之),有哪些库函数是可用的,等等。第三,讲授一些常用的、基本的计算过程,使得学生在解决复杂问题之前,手上有一些可用的基本方法。例如,如何通过分支和循环语句模拟一个手工计算的过程,进行不同数制转换时可以选定一个共同的基数进行转换,字符串处理的问题应该多使用库函数,处理日期问题时可以用一个数组来存储每个月的天数,这样可以很方便地处理不规则的数据,等等。第四,围绕一些具体的问题实例,让学生学会通过分析问题抽象出数学模型,从而设计出计算过程和中间数据的存储方式,*终实现代码并调试成功。学生只有通过这样一个完整的程序设计过程的训练,才能充分理解写程序是要干什么,并且学会判断什么样的问题适合用计算机来解决。第五,学生学习效果的检验方式直接决定了*终的教学效果。如果想让学生真正学会独立动手写出正确的程序,就必须采取上机考查的方式,要求学生针对实际问题写出*终可以正确运行并能解决问题的程序。 本书的内容安排充分体现了上述的教学理念。为了方便理解例题中的代码,本书先用1/3的篇幅简明扼要地介绍C/C 语言的基本语法,包括变量的定义,变量的值的修改,基本的变量类型,用基本类型的变量构造数组、结构体等复杂的数据类型,定义表达式,控制语句序列,以及常用的C语言标准库函数。程序设计导引及在线实践(第2版)之后所有的内容都采用以问题为**的讲述方式。首先用近1/3的篇幅讲述面对不同类型的常见问题,应该如何抽象计算过程,并将计算过程写成具体代码。这些问题包括简单计算问题、数制转换问题、字符串处理问题、日期和时间处理问题、计算过程模拟问题等。接着用近1/4的篇幅讲述了计算机程序设计中常用的但不同于数学计算方法的三种算法思想: 枚举、递归和动态规划。本书的*后两章讲述了如何用基本的数据类型构造一些稍微复杂的数据结构: 链表和二叉树,作为本书向数据结构递进的序曲。配合本书的教学,我们使用了北京大学在线评测系统,书中所有的例题和练习题都在该系统上,学生可以随时针对某一题目编写程序并提交给系统,几秒钟内就可以获得正确与否的回答。我们也利用该系统进行学生的期中、期末考试,学生必须现场在给定的时间内完成从问题分析到代码实现的全部过程才能通过考试。为了测试程序在不同数据输入下的正确性,该系统中的题目大部分采用输入多组测试数据的形式,所以在书中会看到每个程序都要读入多组数据进行处理。这些测试数据是彼此独立的,可以读入一组,处理一组并输出结果,然后再读入下一组。本书作者分工如下: 李文新编写第1章中的1.1、1.2、1.4、1.7、1.8、1.9节,第2章,第5章,第9章中的9.3、9.4、9.6、9.10节,以及附录A和附录B。郭炜编写第1章中的1.3、1.5、1.6、1.10~1.19节,第6章,第7章,第9章中的9.1、9.2、9.5、9.7、9.8和9.9节,以及第10章。余华山编写第3章、第4章、第8章、第11章和第12章。由于水平和精力所限,书中难免存在不当之处,恳请专家和读者批评指正。<br />作者2016年9月于燕园显示全部信息媒体评论评论免费在线读