程序设计与算法基础(1)

《程序设计与算法基础(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计与算法基础(1)潘爱民2006/9/18Contactinfo潘爱民Pan.Aimin@microsoft.com孙方成Fangcheng.sun@gmail.com提纲程序设计概述语言基础：C基本数据结构——list程序设计(programming)概述什么是程序(program)软件的执行流，可以理解为指令流，也涉及到环境的信息：输入、输出、存储介质软件(software)代码和数据，融入了各种知识，算法，经验，等许多无形的东西由人来设计程序，是程序设计之艺术计算机是如何工作的机器代码程序在哪里脑子里的程序纸带上的程序磁带中的程序软盘上的程序光

2、盘上的程序硬盘上的程序内存中的程序哪一条指令，哪一个数据单元？刚开始那个？上一个？下一个？还是最后那个？第0个？第1个？——编号索引——一维，还是二维？地址(address)，可寻址的(addressable)每条指令，每个数据单元都有地址在有些语言中，称为“指针(pointer)”，或者“引用(reference)”内存，外存机器有内存，要执行的代码，以及在执行过程中要用到的数据都在内存中机器也有外存，很多种，像硬盘、U盘、CD-ROM，等等一般而言，外存比内存大得多，对于计算机的运行，内存是必不可少的CPU直接操作内存中的数据，而外存中的数据被换到内存

3、中以后，才能被CPU使用计算机会做什么计算，加减乘除，位操作，浮点运算挪内存中的数据单元简单智力题：两个空桶，一个能盛5升水，一个能盛3升水，请问如何准确地量出4升水？从机器代码开始工作现在，这种能力接近于特异功能了，虽然实际上，正常人都能学得会在汇编语言上工作能够精准地控制计算机做最微小的事情，控制力很强，但工作效率低下时钟频率的提高，人已经无法手工处理如此巨量的指令进入高级语言用高级语言来告诉计算机该做什么通过编译器，把高级语言的语句翻译成计算机的指令高级语言更加接近于人们的思考方式，和人们对问题的数学描述主流的语言：Basic，Fortran，Pa

4、scal，C/C++，Java，C#，Python，等等语言和算法把想法变成用程序语言来描述的程序代码进入程序设计(programming)，俗称编程序算法是一种知识的积累，用于完成一些常见的任务熟练掌握常用的算法是大学期间的学习任务之一对于某些算法，清楚其细节，包括其在各种情形下的性能表现程序设计是一门艺术在程序设计过程中，除了程序和代码本身，还有许多相关的东西程序设计中的思想结构化的思想面向对象的思想类型泛化的思想虚拟机的思想你的程序是一件艺术品：如何迎接同行审视的目光？写代码的层次按照任务指示，写一个没有下家的程序只要正确地完成功能写一个给大量用户使

5、用的程序考虑到用户的各种意外行为，要健壮写一个可复用的程序组件对接口的理解和实现，包括错误处理写一个代码库，供自己及同伴使用预知客户的行为，库的扩展性写一个开源软件你的面子全在程序上了代码的好与坏——一段低质量代码voidHandleStuff(CORP_DATA&inputRec,intcrntQtr,EMP_DATAemprRec,double&estimRevenue,doubleytdReveneue,intscreenX,intscreenY,COLOR_TYPE&newColor,COLOR_TYPE&prevColor,StatusType&

6、status,intexpenseType){inti;for(i=0;i<100;i++){inputRec.revenue[i]=0;inputRec.expense[i]=corpExpense[crntQtr][i];}updateCorpDatabase(empRec);estimRevenue=ydtRevenue*4.0/(double)crntQtr;newColor=prevColor;Status=SUCCESS;if(expenseType==1){for(i=0;i<12;i++)profit[i]=revenue[i]–expen

7、se.type1[i];}elseif(expenseType==2){profit[i]=revenue[i]–expense.type2[i];}elseif(expenseType==3)profit[i]=revenue[i]–expense.type3[i];}参考《CodeComplete》(2ndEdition)，列举了10多个问题代码的好与坏——好的代码取自于WindowsKernel中的一段代码课程内容第一周概述语言基础C基本数据结构-list第二周基本数据结构-stack/queue摸底第三周Sort算法复杂度第四周Tree(1)第五周

8、Tree(2)第六周hash第七周其他算法：recurrence&