前言 1.存在的问题 最近十多年来,软件产业和互联网产业的迅猛发展,给人们提供了用武之地,同时也给 软件工程教育提岀了巨大的挑战。表面上看起来,通过灌输知识可以让人具有很强的考试能 力,却往往经不起用人单位的检验(笔试和机试)。虽然大家都知道,教育的本质在于培养 人们深入挖掘的创造力、好奇心、独特的思考能力和解决工程技术的能力,但实际上我们的 教学实践与教育理念背道而驰。 代码的优劣不仅直接决定了软件的质量,还将直接影响软件成本。软件成本是由开发成 本和维护成本组成的,而维护成本却远高于开发成本,蛮力开发的现象比比皆是,大量来之 不易的资金被无声无息地吞没,整个社会的资源浪费严重。 2.核心域和非核心域 个软件系统封装了若干领域的知识,其中一个领域知识代表了系统的核心竞争力,这 个领域被称为“核心域”,其它领域称为“非核心域”。虽然更通俗的说法是“业务”和“技 术”,但使用“核心域”和“非核心域”更严谨 非核心域就是别人的领域,比如,底层驱动、操作系统和组件,即便你有一些优势,那 也是暂时的,竞争对手也能通过其它渠道获得。非核心域的改进是必要的,但不充分,还是 要在核心域上深入挖掘,让竞争对手无法轻易从第三方获得。因为在核心域上深入挖掘,达 到基于核心域的复用,这是获得和保持竞争力的根本手段。 要达到基于核心域的复用,有必要将核心域和非核心域分开考虑。因为过早地将各个领 域的知识混杂,会增加不必要的负担,从而导致开发人员腾不出脑力思考核心域中更深刻的 问题。由于待解决的问题的规模一旦变大,而人脑的容量和运算能力有限,因此必须分而治 之,因为核心域与非核心域的知识都是独立的。比如,一个计算器要做到没有漏洞,其中的 问题也很复杂。如果不使用状态图对领域逻辑显式地建模,再根据模型映射到实现。而是直 接下手编程,领域逻辑的知识靠临时去想,最终得到的代码肯定破绽百出。其实有利润的系 统,其内部都是很复杂的,千万不要幼稚地认为“我的系统不复杂”。 3.利润从哪里来? 早期创业时,只要抓住一个机会,多参加展会,多做广告,成功的概念就很大。在互联 网时代,突然发现入口多了,聚焦用户的难度越来越大。当产品面临竞争时,你会发现“没 有最低只有更低”。而且现在已经没有互联网公司了,携程变成了旅行社,新浪变成了新媒 体..机会驱动、粗放经营的时代已经过去了。 Apple之所以成为全球最赚钱的手机公司,关键在于产品的性能超越了用户的预期,且 因为大量可重用的核心领域知识,综合成本做到了极致。Yourdon和Constantine在《结构 化设计》一书中,将经济学作为软件设计的底层驱动力,软件设计应该致力于降低整体成本。 人们发现软件的维护成本远远高于它的初始成本,因为理解现有代码需要花费时间,而且容 易出错。同时改动之后,还要进行测试和部署。 更多的时候,程序员不是在编码,而是在阅读程序。由于阅读程序需要从细节和概念上 理解,因此修改程序的投入会远远大于最初编程的投入。基于这样的共识,让我们操心的 系列事情,需要不断地思考和总结使之可以重用,这就是方法论的源起。 通过财务数据分析,由于决策失误,我们开发了一些周期长、技术难度大且回报率极低 的产品。由于缺乏科学的软件工程方法,不仅软件难以重用,而且扩展和维护难度很大,从 而导致开发成本居高不下。 显而易见,从软件开发来看,软件工程与计算机科学是完全不同的两个领域的知识。其 主要区别在于人,因为软件开发是以人为中心的过程。如果考虑人的因素,软件工程更接近 经济学,而非计算机科学。如果不改变思维方式,则很难开发出既好卖且成本低的产品。 4.优秀人才在哪里? 学徒模式是过去建造大师传承技艺的方法,而现在指导和辅导却成为了一项被忽略的活 动,团队成员得不到所需的支持。技术领导人不仅要引导整个项目,而且还要为员工提供必 需的协助。除此之外,指导和辅导提供了一种增强员工技能的方式,帮助他们完善自己的职 业生涯。这种协助有时候是技术性的,有时候是软技能。 可悲的是,在我们的行业里,许多优秀的开发者在转向管理岗位之后,就放弃了对技术 的追求,甚至再也不写代码了。因而团队中失去了最有价值的技术领导和导师,今天的开发 者还会在继续重蹈覆辙。很多优秀的导师都消失了,让开发者到哪里去获得经验呢?未来的 优秀人才从哪里来? 5.告知读者 这本书如同培训讲师的教案,仅仅是我和同事们的读书笔记和程序设计实践的心得,并 不是一本从零开始编写专著或图书。其中的很多内容并非我们原创,而是重用了一些公开出 版物的内容,详见本书的参考文献。 企业训练新员工时,最好采取短期的、集中式的、封闭式的方法。将员工集中在一个安 静而偏僻的地方,不准上网但可以讨论和申请得到指导,只有这样才能将人逼出来。同时建 议两人一组,采用结对的方式学习、编程和编写文档,因为两个脑袋比一个脑袋更聪明 6.丛书简介 这套丛书命名为《嵌入式软件工程方法与实践丛书》,其最新动态详见www,zlg.cn(周 立功旗下企业:广州致远电子有限公司)。 第一套目前已经完成三本,包括《程序设计与数据结构》、《面向接口的编程一一基于 AMteal&LPC824》和《面向对象的分析与设计》,第二套包括《面向接口的编程一一基于 AWorks&ARM9》(适用于各种ARM内核)、和《面向对象的分析与设计》,第三套包括 《面向接口的编程一一基于Linux&ARM9》(适用于各种ARM9以上内核)和《面向对象 的分析与设计》,第四套包括《C艹-现代程序设计》、《面向接口的编程一一基于 AWorks&ARM9》(适用于各种ARM9以上内核)、《面向接口的编程一一基于Liux》(适 用于各种ARM9以上内核)和《面向对象的分析与设计》,还在写作中的内容包括测试与 持续集成。 虽然这是一套仅作为内部培训和客户咨询的培训教程,但如果MEta和AWorks平台, 就没有这套丛书的成形。尽管这套丛书历时12年五易其稿,但仍然还在不断地完善和修订 之中,因此当前仅作为V0.1版本发布。 周立功 2017年4月28日 目录 第1章程序设计基础 思想的力量 1.1.1过程主题… 1.1.2思维差异 1.1.3语言的鸿沟 变量与指针. 2299 12.1变量 12.2值的表示形式 12 1.2.3数据的输入输出 指针变量与指针的指针 22 1.3.1声明与访问 .22 1.3.2变量的访问 5 1.3.3指针的指针 28 简化表达式 29 1.4.1逻辑表达式 30 1.4.2综合表达式… 14.3条件表达式 .32 共性与可变性分析 15.1分析方法 33 1.5.2建立抽象 34 1.5.3建立接口 ,34 1.54实现接 7 1.5.5使用接口 数组与指针 中:中中:中:中:中::中:中:中:中中中:中 1.6.1数组与指针 39 162数组的访问形式 14 1.6.3泛型编程. 47 数组的数组与指针 1.7.1指向数组的指针 1.7.2二维数组 56 1.7.3将二维数组作为函数参数 58 1.8 字符串与指针 中:中中:中:中:中::中:中:中:中中中:中 1.8.1字符常量 1.8.2字符串常量 .64 1.8.3指针数组 73 1.9 动态分配内存 1.9.1malloch函数 79 1.9.2calloc函数 1.9.3fre函数 1.9.4realloc函数 第2章程序设计技术 83 函数指针与指针函数 21.1函数指针 21.2指针函数 .85 21.3回调函数 8 21.4函数指针数组 5 结构体 96 22.1内存对齐 96 2.22内含基本数据类型 223内置函数指针 22.4嵌套结构体 108 22.5结构体数组 2.3 栈与函数返回 中:中中:中:中:中::中:中:中:中中中:中 114 23.1堆栈 114 232入栈与出栈 115 2.3.3函数的调用与返回 116 栈ADT 117 24.1不完全类型 117 2.42抽象数据类型 243开闭原则(OCP) 129 第3章算法与数据结构. 135 算法问题 135 3.1.1排序 .135 3.1.2搜索 137 3.1.3O记法 138 单向链表 143 3.2.1存值与存址 .143 322数据与pnext分离 15 3.2.3接口 3.3双向链表 166 3.3.1添加结点 .169 332删除结点 172 3.33遍历链表… 4迭代器模式 176 34.1迭代器与容器 .176 342迭代器接口 177 34.3算法的接口 3.5 哈希表 186 3.5.1 问题.… 186 5 哈希表的类型 189 3.53哈希表的实现 3.6 队列ADT .198 3.6.1建立抽象 198 建立接口 3.6.3实现与使用接口 200 第4章面向对象编程 208 4.1 OO思想 208 4.1.1职责转移… 208 OO机制 4.1.30O收益 210 4.2 类与对象 2l1 4.2.1对象.… 211 4.2.2类 212 4.2.3封装 215 4.3 继承与多态 221 4.3.1抽象 221 4.3.2继承. 222 4.33职责驱动设计 224 4.34多态性 227 4. 虚函数 230 44.1二叉树 230 4.42表达式算术树 230 4.4.3虚函数 238 4.5 框架与重用 242 4.5.1框架 4.5 契约 243 4.53建立契约 244 454教条的危害 244 附录A参考文献 ·c;4···非 247 嵌入式软件工程方法与实践丛书一程序设计与数据结构(www,zIg.cn) 第1章程序设计基础 本章导读 在学习程序设计时,很多初学者常常会陷入这样的误区,他们总将阻碍个人成长的原因 归结为缺少机会。其实问题的根源在于缺乏方法论,很少有人将“知其然自知所以然”作为 自己的学习准则,进而也就谈不上熟练掌握多种编程风格。 其实,程序设计中的数据结构和算法是围绕各种类型的数据和需求展开的,而完成这些 工作的载体便是各种各样的变量。因此只要抓住变量的三要素(即变量的类型、变量的值和 变量的地址)并贯穿始终,则一切问题迎刃而解。 11思想的力量 《思想者》是法国雕塑家罗丹创作的雕像,他更多的是在强调其核心的内涵—思想,人 类的整合思想。尤其在20世纪初,人们把它作为一种改造世界力量的象征。显而易见,思 想的力量是伟大而无穷的,无论是做大事还是做小事,无不和思想息息相关。 11.1过程主题 限制与抽象化 结构化编程的“限制”和“抽象化”是人类处理复杂软件的有效方法之一,为了使程序 变得简单且容易理解,EdsgerDijkstra提倡禁止使用goto,并将程序控制流程限制为“顺序 分支和循环”三种组合。虽然面向结构的编程实现了控制流程的结构化,使程序流程结构化 了,但要处理的薮据并没有结构化。虽然面向过程的编程降低了程序的复杂性,但随着数据 的类型越来越多,分别管理程序处理内容和处理数据对象所带来的程序复杂性也越来越高。 当需要将一部分计算任务独立实现时,可以将其定义为一个函数,因为这样可以实现计 算逻辑的分离,通过使用函数名使代码更清晰,且利用函数使得同样的代码在程序中可以多 次使用,且减少调试程序的工作量。 由于实际的应用程序中可能会用到成千上万个函数,为了得到正确的结果,必须保持处 理和数据的一贯性,人们想到了薮据抽象技术。数据抽象是数据和处理方法的结合,对数据 的处理和操作,必须通过事先定义好的方法进行。于是面向过程编程引入了较为抽象的模块 的概念,因此可以说程序是由模块构成的,而模块又是由函数构成的,一个模块就是一个过 程。由于不同结构中的数据是由函数或过程管理的,因此在设计程序时就可以对这些模块分 别进行抽象、设计、编码和测试,最后将这些模块有机地组合在一起形成一个完整的程序 2.功能分解法 通常解决复杂问题的方法都是从分析问题开始,将一个大问题分解为多个小问题,分成 多个子模块,解决每个小问题,实现每个子模块。最后通过主函数按照某种次序调用这些子 模块,组织业务逻辑流程,最终解决问题。象这样从问题岀发,自顶向下逐步求精利用算法 作为基本构建块构建复杂系统的开发方法称为结构化或面向过程编程 怎样编写更容易应对多变需求的代码呢?与其编写一个大函数,不如使之更加模块化 即用模块化封装变化。虽然模块化有助于提髙代码的可理解性,使代码也更容易维护,但模 块化也无法包治百病,因为模块化存在两个问题,即低内聚和高耦合。 假设要给main中调用的每个子过程增加一个参数,以便传递某个额外的信息。同时每 个子过程又要将这个信息传递给自己的子过程,这种现象就是我们熟知的串联改变。串联改 嵌入式软件工程方法与实践丛书一程序设计与数据结构(www,zIg.cn) 变是指某个过程的变化会传递到其子过程中,并由这些子过程继续往下延续直到所有的分解 层次。显然,在面对软件维护时,包括软件测试、调试和升级等,自顶而下的设计方法存在 致命的缺陷。因为面向过程编程强调从软件的功能特性岀发思考问题,将系统划分为多个功 能模块,同时尽量确保模块之间的耦合度最小。其实这种方式并不能很好地模拟现实世界 其思维方式存在先天的缺陷 在面向过程编程时,经常会遇到这样的问题,一个bug修改好了,另一个地方又出问题 了,因而许多bug源于修改代码。实际上在理清楚代码的运行原理,寻找bug和防止岀现不 良副作用上,花费了大量的时间,而修改bug的时间是很短的。由于不良副作用产生的bug 是最难发现的,如果让一个函数处理很多不同的数据,一旦需求发生变化,则出现的问题会 更多。需求变更会对软件开发和维护工作产生极大的影响,因为只关注函数,将会导致一连 串难以避免的变化。 既然用户的需求总是在变化之中,我们将无法阻止变化。与其抱怨变化,不如改变开发 过程,从而更有效地应对变化,面向对象编程就是这样作为对抗软件复杂性的手段岀现的。 11.2思维差异 学习的最高境界是“知其然知其所以然”,但真正达到这个层次的人并不多,这是每个 人梦寐以求的人生目标。如果你已经进入了这样的化境,则一切问题迎刃而解。将不再受限 于年纪,且与性别无关 其实,牛人和普通人的差距并非知识和经验的多少,而是思维方式的不同。为何编程语 言、操作系统、控制论等都是美国人发明的呢?他们似乎天生具备自上而下分析问题的直觉 和从特殊到一般的泛化思维。美国之所以在IT领域今天处于绝对领先的地位,完全是因为 教育的结果。 我们时常以美国白领计算能力太差作为笑料,认为中国教育重在练“基本功”,掩盖忽 略培养学生“创造力和思维能力”的问题。而美国教育极其重视“创造力”的培养,让学生 根据个人的兴趣而学。比如,选6个学期的物理和数学,只选2个学期的化学和生物。不仅 可以在校选修大学课程,而且还可以利用假期到任何大学学习,比如,哲学、Java。 中国的课堂要举手发言,美国的课堂鼓励自由发言。中国的教育采取灌输式,考试采取 填鸭式;中国的考试则如临大敌,单人单桌,主监副监严防紧守。美国的教育善于启发学生, 推动学生不断提出新问题。美国经常采取开卷考试,只要一周内交卷即可。中国考试的主要 目的是为了淘汰,而美国的考试目的在于寻找自身存在的不足查漏补缺,以利于今后的发展。 如果中国的学生不同意老师的结论会受到批评,而在美国的课堂上则会受到表扬。中国 学生盲目崇拜老师和权威,而美国老师很喜欢和学生一起聊天,他们是要好的朋友关系。中 国的中学生一年有8个月上课,每天在校11个小时左右。而美国学生每年只有1000个小时 左右,且上学时间短课业负担少,让学生们有更多自由的时间,做自己感兴趣的事。 由于创造力的不足和思维能力的差异,导致我们在很多问题的认识上出现大量的知识盲 点或黑洞,将严密的科学知识割裂开来成为了知识孤岛。即便你非常努力学习,甚至花费更 多的时间到企业实习,但依然难以获得更大的突破。 在自我训练的过程中,我深刻地体会到,对问题的研究经常会感受到传统思维的影响 而《异类》一书指出,“人们眼中的天才之所以卓越非凡,并非天资超人一等,而是付出了 持续不断的努力,一万小时的锤炼是任何人从平凡变成超凡的必要条件。”我开始感到迷茫, 因为我花费的时间,又何止一万小时呢? 113语言的鸿沟 开发人员对问题域的认识是一种思维活动,而人类的任何思维活动都是借助于他们熟悉 嵌入式软件工程方法与实践丛书一程序设计与数据结构(www,zIg.cn) 的某种自然语言进行的。而软件系统的最终实现必须用一种计算机能够阅读和理解的语言描 述系统,这种语言就是编程语言。 人们所习惯使用的自然语言和计算杋能够理解及执行的编程语言之间存在很大的差距, 这种差距被称为“语言的鸿沟”,实际上也是认识和描述之间的鸿沟。也就意味着,一方面 人们借助自然语言对问题域所产生的认识远远不能被杋器理解和执行,另一方面机器能够理 解的编程语言又很不符合人们的思维方式。因此开发人员需要跨越两种语言之间的这条鸿 沟,即从思维语言过度到描述语言。 之所以学习和开发的成本很高,主要是理解困难所造成的,所以必须建立一种用于沟 通的通用语言,因为构建通用语言的过程就是自我思维训练和建立逻辑推理的过程。 变量和指针 2016年初,几个要好的朋友要我帮忙教他们的孩子编程,四个已经毕业的学生,经过 测试考试成绩为0。首先从变量的三要素开始学起,大家一起建立一套通用语言。比如: intiNum=0x64 最初的词汇有变量的类型int、变量名iNum和变量的值0x64,接着编写第一个只有几 条语句的简单程序,详见程序清单1.1。 程序清单1.1输出变量的地址和变量的值 include intmain(intargc,charargv) 2345678 intiNum=0x64 printf("%x,%xn",&iNum,iNum) return0 通过运行结果可以清楚地看到,0x64存储在0x22FF74内存单元中。虽然使用&运算符 可以获取变量ium在内存中的地址,但&iNum是一个孤 立的概念。 变量地址Num—变量名 &iNum 当将地址形象化地称为“指针”时,即可通过该指针0x22FF74 0x64 变量值 找到以它为地址的内存单元。于是词汇表中又多了一个新 存储单元 的成员一一指针,同时还多了一条新的语句——&iNum 图1.1变量与指针 是指向int变量ium的指针,该语句标识了“指针与变量”之间的关联关系。理解指针的 最好方法之一是绘制图表,变量与指针的关系详见图1.1。 虽然这几位学生的基础很差,但毕竞在校还是认真听了课的。因此只要稍微提醒一下, 依然还能记得一些概念。既然通过&iNum就能找到变量iNum的值0x64,那么如何存放 &iNum呢?定义一个存放指针&iNum的(指针)变量。比如 intiNum=0x64 int*ptr=&iNum 助记符变量地址存储单元 &iNum0×22FF74 0x64 现在词汇表中有多了一个新的成员 指针&pr0×2F70(2Fap INum←ptr 变量,即ptr是指向int的指针(变量),“int*” 类型名是指向int的指针类型,详见图1.2。虽然有 图1.2变量的存储与引用 时也将指针变量泛化为指针,但要根据当前所处的环境而定。