第一章 UNIX的前世今生

 

一、UNIX起源

 

Unix的诞生离不开一种于1965年由Advance research project agency(United States Department of Defence)支持，并聚集MIT、AT&T以及通用电气共同参与开发的分时系统MULTICS (MULTiplexed Information and Computing Service)。

MULTICS的主要设计目标是：

1、便利的终端使用——大量远程终端通过电话线接入计算机主机

2、高可靠的大型文件系统——大容量的用户信息共享；存储和构造层次化信息结构的能力

然而MULTICS研制难度超出所有人的预料，长期的研制工作达不到预期目标，1969年4月AT&T退出，通用电气公司也退出。最终，MIT坚持下来，MULTICS成功运行，成为商业产品。事实上MULTICS运行直到2000年，加拿大国防部关闭了最后一个正常运行中的MULTICS系统。

MULTICS的开发及其研究成果对随后的计算机操作系统有着巨大影响。1969年，已退出MULTICS项目的AT&T研究员人员Ken Thompson和Dennis M. Ritchie 在一台无人用的DEC PDP-7上，重新摆弄原先在MULTICS项目上设计的“空间旅行”游戏。为了使游戏能够在PDP-7上顺利运行，他们陆续开发了浮点运算软件包、显示驱动软件，设计了文件系统、实用程序、shell 和汇编程序。1970年，在一切完成后，给新系统起了个同MULTICS音相近的名字UNIX。

最初的UNIX是使用汇编语言编写，其中一些系统应用是使用B语言和汇编语言混合编写的，鉴于B语言并不善于进行系统编程，Ken Thompson和Dennis M. Ritchie在此基础上做了大量改进工作，并于1971年发明了C语言。1973年，UNIX用C语言全部重写，自此，UNIX正式诞生。1977年，Unix被几乎完全不变的移植到非PDP-7机上，开始广泛应用于各种大学和科研机构。

从历史上看，UNIX的流行具备以下几点重要因素：

首先，由于UNIX是用C语言编写，因此它是可移植的，UNIX是世界上唯一能在笔记本计算机、PC机、工作站直至巨型机上运行的操作系统；

第二，系统源代码非常有效，系统容易适应特殊的需求；

最后，也是最重要的一点，它是一个良好的、通用的、多用户、多任务、分时操作系统；

Ken Thompson和Dennis M. Ritchie因为其卓越的贡献于1983年获得图灵奖，并于1999年获得美国国家技术金奖。

然而由于UNIX强大的商业潜力，AT&T于1979年发布了最后一个UNIX广泛版本UNIX 7。1982年发布的UNIX III最终停止了向各个研究机构发布UNIX源代码的做法，而改为商业销售。随后又综合各个大学的研究版本发布了UNIX Syetem V Release 1。

Berkeley在UNIX商业化后延续了其BSD研究版的开发，其创立的TCP/IP协议机制几乎是现有所有系统TCP/IP实现的鼻祖。AT&T于1989年开发了UNIX Syetem V Release 4，并集成了当时多种UNIX变种版本，成为目前多数变种系统的前身。

AT&T与Berkeley在BSD是否侵权的问题上长期存在争执，直到UNIX被卖给Novell，双方最终才达成妥协，BSD得以在删除所有AT&T源代码的前提下继续开发。使得UNIX最终形成了两大技术流派：UNIX SVRx以及Berkeley Software Distribution。

 

二、UNIX发行版的比较

 

UNIX的发行版本众多，不过可以分为硬件流和软件流两种流派。

1、硬件流派

硬件流是指厂商所发布的UNIX仅能在自己研制的硬件系统中使用，硬件流的主要特点是：

系统和自家的硬件捆绑销售；

相对较封闭，不同厂家之间无法二进制兼容；

适合企业级应用；

性能和稳定性满足关键业务需求；

对管理员要求最高，但享有较好的维护支持；

总拥有成本(TCO)较高；

目前硬件流的代表有IBM的AIX、SUN的Solaris以及HP的HP/UX。

2、软件流派

UNIX源代码目前的版权属于SCO Group，并在此基础上发布了SCO Unix，其作为唯一合法的纯商业UNIX系统软件具有以下特点：

较好的x86平台兼容性，适合多种硬件架构；

适合网络服务的多种应用；

有版权；

对管理员要求较高，但也有部分商业支持；

总拥有成本(TCO)一般；

另外，开源项目中的UNIX版本已成为目前UNIX广泛流行的主要推动力量。包括了BSD衍生而来的FreeBSD、OpenBSD和NetBSD，以及Linux衍生来的RedHat（自v9.0后终止研发桌面版，进而开发RedHat Enterprise Linux商业系统）、Fedora（RedHat v9.0后由RedHat Inc.支持的开源项目）、Debian （早期的Linux发行版之一，拥有数量惊人的软件包支持）、SUSE（现由Novell维护的linux发行版）、Ubuntu（Debian衍生而来的一种较新的Linux发行版）、Mandriva（即Mandrake Linux，一种最初基于RedHat的衍生版本，其维护方Mandrakesoft Inc.于2005年被Conective Inc.收购）。开源项目下的BSD和Linux具有以下特点：

较好的x86平台兼容性，适合多种硬件；

从桌面到网络服务，适合多种应用，应用软件丰富；

源代码开放，不存在版权问题；

对管理员要求较高，商业支持少，但有社区支持；

总拥有成本(TCO)较低；

具有潜在的行业趋势；

 

三、UNIX和Linux

 

Unix的主要特点如下：

1、开放性

遵循世界标准规范，特别是遵循开放系统互连OSI国际标准。

2、多任务

允许多个程序同时执行。

3、多用户

允许多个用户从相同或不同终端上同时使用同一台计算机。

4、良好可移植性、高稳定性和强安全性

编译大都相同，具备良好的可移植性，历经长久考验，稳定安全。

5、功能强大、实现高效

使用户能方便地、快速地完成许多其他操作系统难以实现的功能。

6、卷式文件结构及外部设备文件化                                     

具有可装卸的树型分层结构文件系统 ，并分别赋予外部设备对应的文件名，用户可以像使用文件那样使用任一设备。

 

Linux的特点如下：

1、UNIX继承性

作为UNIX的子集，具备多任务，多用户，良好稳定性，良好安全性，符合POSIX标准等（POSIX可移植操作系统接口Portable Operating System Interface，缩写为 POSIX，是为了读音更像UNIX。电气和电子工程师协会Institute of Electrical and Electronics Engineers，IEEE最初开发 POSIX 标准，是为了提高 UNIX 环境下应用程序的可移植性）。

2、多平台

支持各种CPU，包括Intel，AMD，PowerPC，甚至SUN sparc等。

3、完善的网络协议

具备 从IPv4到IPv6,内置IPSEC, netfilter防火墙。

4、多种友好用户界面

Shell，GNOME, KDE等。

5、核心与应用分离、遵循GNU协议（GNU’s Not UNIX，由Richard Matthew Stallman于1983年发起的类UNIX组织，旨在推广自由软件系统，该协议框架下包含了许多著名软件GNU/Linux、Emacs、以及C编译器GCC等）。

Linux采用核心与应用分离，核心（Kernel），围绕核心的shell，x-windows，以及应用软件共同构成Linux系统。

 

接下来介绍UNIX的配置方法和常用领域的解决方案。

 

 对于UNIX我们不得不说，初次接触的兴奋和期望，半小时过去即烟消云散，恐怕还免不了赶紧回去膜拜ms大神。但当初步了解了这套已历经整整四十个春秋的体系冰山一角，看上去尚能自我安慰的知识框架仿佛突然变得渺小与脆弱：它拥有比ms丰富得多的经历和各领域科学家，它也从来不拒绝商业化——事实上它本来就是“商业”的，更为重要的是，未来似乎无论如何也和它脱离不了干系——只要在有“芯”的地方皆是如此。

 即日起我们将花一些时间连载一部有关于UNIX的文章，她是笔者根据宝贵的课件资料以及《Beginning Unix 1st》(清华译版)、《Advanced Programming in the UNIX Environment 2nd 》（cp电子版，原谅我对众多大部头实在头疼…）中的一些浅显易懂的内容总结而来的。其中覆盖了Unix介绍、配置、用户系统、文件系统、高级工具/命令、进程管理、shell/shell脚本编程、网络配置等纷繁复杂的内容，应用部分力争做到与c源程序并发讨论。

 连载的目的是深入对UNIX的理解并熟悉Linux编程，高手就不必在这里浪费时间…新手读者可以凑合看看。我们强调实践，但并不等于在屏幕前发呆，无论如何，手边一本名著经典和随时思考都是必不可少的。

 前面介绍了如何使用lex写一个词法分析器，为了证明上述程序的正确性，需生成与它对应的c语言代码，并编译成可执行程序。unix下使用这些工具非常简单（以至于两行commands就可以完成工作），在此就不做详细说明，接下来我们来面对ms留给我们的烂摊子……

 为了证明在win32下利用lex生成词法分析器有多复杂，我们选用parser generator 2和vc++6.0组合向大家展示ms强大的化神奇为腐朽的力量（依然不推荐win32用户使用vs平台进行此项工作）。

 parser generator可以在以下网址免费获取：http://www.bumblebeesoftware.com/downloads.htm

 vc++6.0？别告诉我你不知道怎么获取……

 首先启动pg2,要进行针对vc++6.0的配置工作:

 选择menu下的project->LibBuilder,Complers选则Visual C++(32-bit),并点击compiler properties,这时在Options内作如下设置:

Version:6

 Unicode:true

 treat wchar_t as Built-in type:False

 Compiler Bin directory: C:\PROGRAM FILES\MICROSOFT VISUAL STUDIO\VC98\BIN

 Compiler Bin directory(2):C:\PROGRAM FILES\MICROSOFT VISUAL STUDIO\COMMON\MSDEV98\BIN

 Compiler Include directory: C:\PROGRAM FILES\MICROSOFT VISUAL STUDIO\VC98\INCLUDE

 Compiler Include directory(2):C:\PROGRAM FILES\MICROSOFT VISUAL STUDIO\VC98\MFC\INCLUDE

 Compiler Library directory:C:\PROGRAM FILES\MICROSOFT VISUAL STUDIO\VC98\LIB

 Compiler Library directory(2):C:\PROGRAM FILES\MICROSOFT VISUAL STUDIO\VC98\MFC\LIB

 (注: 请读者按vc实际安装目录而定)选择完毕后点击OK,在父窗口中选择Build生成供vc使用的库文件.

 ……

 经过漫长等待库文件终于生成了…现在回到主界面,选择project->parserWizard,填入自己的lex工程名,选择vc++6.0(32-bit),进入下一步.Files选lex file only,其它均保持默认即可.填入lex源文件名后即可选择complete.

 这时程序会自动生成lex文件的框架,如果在前面的设置中还选择了create main function,文本中还会有几行简单的main函数.但是该文本对我们没有任何意义…直接将前文所述的源代码覆盖至此即可.

 现在选择project->compile file,build后就会生成lex源码对应的c语言source和include文件了.接下来启动vc++6.0进行相关配置.

 首先点击Tools->Options,切换至directory选项卡,分别在show directories for中的Include、Library和Source选项中添加如下信息（每项一条）：

C:\PROGRAM FILES\PARSER GENERATOR 2\CPP\INCLUDE

C:\PROGRAM FILES\PARSER GENERATOR 2\CPP\LIB\MSVC32

C:\PROGRAM FILES\PARSER GENERATOR 2\CPP\SOURCE

（注：应按pg的实际安装路径而定）现在新建win32 console application工程，并点击Project->Settings选项，Settings for先选择win32 debug。然后在C/C++选项卡的Proprocessor Definitions选项中添入,YYDEBUG，切换至Link选项卡在Object/library modules中添入yld.lib ylmtd.lib ylmtrd.lib。

 将Settings for切换至win32 Release重复上述操作，就完成了整个前期的所有配置工作……

 在工程中添加前面生成的source和include文件，直接build即可。现在，我们就可以按照PL/0的基本关键词写出一些简单的程序并加以词法分析了（事实证明这时的编译功能还十分微弱，但却是向前迈出一大步了）。

 学计算机的同学都要学习编译原理，理论是抽象了点，但最终目的毕竟只是让我们了解一下程序语言编译器的构造原理。

 尽管没有充分的证据显示lex+yacc能证明一个人学习cp程度的好坏（考试的作用就更难以拿来说明这些了），但好歹大家学过nfa，学过确定化，学过dfa化简，用c语言大概可以写出设定简单的词法分析程序了。

 然而教材上都是一些纯理论性的内容，实现技术的精粹还得去找洋人学。因而本科生只需掌握lex和yacc——这已经是为极限，再低就难以搞清楚cp和programming有什么关系…再高？说实话暂时已是心有余而力不足了…

 那么lex的作用大概就是这些，尽管在几乎所有的程序设计语言编译器中词法分析都是由语法分析程序不断调用而生效，但对于我们来说分别实现并作演示是再好不过。这就是本文介绍词法分析器lex的目的。

 一个lex源程序由四部分构成，基本框架如下：

%{

//包含的头文件、函数声明以及一些全局量的声明

%}

//词法定义

%%

//规则定义

%%

//自定义程序

 需要注意的是，带有%的分隔符必须顶格书写，词法分析和规则定义的基本形式为正规式。为了显示词法分析的最终成果，需要定义一个二元结构体，分别存储其单词内容以及归属类别，并存入定义好的目标文件中，同时按国际惯例显示源代码出错信息。

 现在给出一个PL/0语言（pascal语言的一种子集）的EBNF描述：

<prog> → program <id>；<block>

<block> → [<condecl>][<vardecl>][<proc>]<body>

<condecl> → const <const>{，<const>}

<const> → <id>:=<integer>

<vardecl> → var <id>{，<id>}

<proc> → procedure <id>（<id>{，<id>}）;<block>{;<proc>}

<body> → begin <statement>{;<statement>}end

<statement> → <id> := <exp>

               |if <lexp> then <statement>[else <statement>]

               |while <lexp> do <statement>

               |call <id>[（<exp>{，<exp>}）]

               |<body>

               |read (<id>{，<id>})

               |write (<exp>{，<exp>})

<lexp> → <exp> <lop> <exp>|odd <exp>

<exp> → [+|-]<term>{<aop><term>}

<term> → <factor>{<mop><factor>}

<factor>→<id>|<integer>|(<exp>)

<lop> → =|<>|<|<=|>|>=

<aop> → +|-

<mop> → *|/

<id> → l{l|d}   （注：l表示字母）

<integer> → d{d} 

 

注释：

<prog>：程序 ；<block>：块、程序体 ；<condecl>：常量说明；<const>：常量；

<vardecl>：变量说明 ；<proc>：分程序 ； <body>：复合语句 ；<statement>：语句；

<exp>：表达式 ；<lexp>：条件 ；<term>：项； <factor>：因子 ；<aop>：加法运算符；

<mop>：乘法运算符； <lop>：关系运算符

odd：判断表达式的奇偶性。

 利用上述文字中提取出的词法信息，我们可以建立一个简单的词法分析程序：

%{ /     coded by 韩翼 from nwu    Email:8621316@qq.com    */

include <stdio.h>

include <stdlib.h>

include <string.h>

define MAX_COUNT 10000     //最大可接受id数

int process();       //处理函数 int main(int argc,char argv); int nowline = 1;      //当前行数计数器 int errorno = 0;      //出错计数器 int flag = 0;       //分支标识 int count = 0;       //id计数器 char desfilename[32];     //目标文件名 char srcfilename;      //源文件名 FILE srcfile;       //源文件缓冲指针 FILE desfile;       //目标文件缓冲指针 struct result       //id标记二元组 {  char content;  char description; }result[MAX_COUNT]; %} d [0-9]          l [a-zA-Z] wr ([0-9]+)a-zA-Z integer [0-9]+ id a-zA-Z anotherline [\n] whitespace [\t]+ %% “program” { flag = 0; process(); } “const” { flag = 1; process(); } “:=” { flag = 2; process(); } “var” { flag = 3; process(); } “procedure” { flag = 4; process(); } “begin” | “end” { flag = 5; process(); } “if” | “then” | “else” | “while” | “call” | “read” | “write” { flag = 6; process(); } “+” | “-” { flag = 7; process(); } “” | “/” { flag = 8; process(); } “=” | “<>” | “<” | “<=” | “>” | “>=” { flag = 9; process(); } “(” | “)” | “,” | “;” { flag = 10; process(); } {wr} { flag = 13; process(); } {id} { flag = 11; process(); } {integer} { flag = 12; process(); } {anotherline} { nowline++; } {whitespace} { ; } “ ” { ; } . { flag = 14; process(); } %% int process() {  switch(flag)  {  case 0:   result[count].description = “<prog>”;   break;  case 1:   result[count].description = “<condecl>”;   break;    case 2:   result[count].description = “<op>”;   break;  case 3:   result[count].description = “<vardecl>”;   break;  case 4:   result[count].description = “<proc>”;   break;  case 5:   result[count].description = “<body>”;   break;  case 6:   result[count].description = “<statement>”;   break;  case 7:   result[count].description = “<aop>”;   break;  case 8:   result[count].description = “<mop>”;   break;  case 9:   result[count].description = “<lop>”;   break;  case 10:   result[count].description = “<bop>”;   break;  case 11:   result[count].description = “<identifier>”;   break;  case 12:   result[count].description = “<integer>”;   break;  case 13:   errorno++;   result[count].description = “<wrong integer or id>”;   printf(“%s(%d) : error ‘%s’ : wrong integer or identifier\n”,srcfilename,nowline,yytext);   break;  case 14:   errorno++;   result[count].description = “<unknown identifier>”;   printf(“%s(%d) : error ‘%s’ : unknown identifier\n”,srcfilename,nowline,yytext);   break;  }  result[count].content = yytext;  fprintf(desfile,“%d: %s\t%s \n”,count+1,result[count].content,result[count].description);  count++;  return 0; } int main(int argc,char argv) {   int i = 0;  if( argc != 2)  {   printf(“No sourcecode processed : parameter error\n”);   return 0;  }  srcfilename = argv[1];  strcat(desfilename,argv[1]);  while (desfilename[i] != ‘.’)  {   i++;  }  desfilename[i] = ‘\0’;  strcat(desfilename,“.pl0”);  if( (srcfile = fopen(argv[1],“r”)) == NULL )  {   printf(“No sourcecode processed : cannot open the file \”%s\“\n”,argv[1]);   return 0;  }  if( (desfile = fopen(desfilename,“a”)) == NULL )  {   printf(“No sourcecode processed : cannot write the file \”%s\“\n”,desfilename);   return 0;  }  yyin = srcfile;  yylex();  fprintf(desfile,“\n”);  fprintf(desfile,“completed! welcome to lex by mp77,this is only a demo for compile principle.\n”);  printf(“%s - %d error(s)\n”,desfilename,errorno);  printf(“completed! welcome to lex by mp77,this is only a demo for compile principle.\n”);  fclose(desfile);  fclose(srcfile);  return 0; }

 接下来我们会介绍如何利用lex工具生成本代码的C语言源代码，并使用vc6.0编译成win32 console程序。

 回家翻了翻“纲要”，觉得有必要修正一下了…校方一意孤行坚持进行期中考试， 结果是两周时间就写完两篇论文…好不容易回家一趟还得做lex…回学校后仅有一天时间去搞测试报告…期间笔试了三门课，还剩下日语口语…总之第一次觉得时间不够用，实在是暴汗…

 这月新闻多多：wow之争，庆幸当时删的彻底；猪瘟肆虐，还好感冒初愈尚存些许抵抗力；政法申博，当初在openlab看到徐州那个事已经感觉很是惊奇了，没想到这次兄弟学校直接上了门户首页（尽管页面存活了不到几个小时），觉得这下也该引起高层注意了吧…总之没什么值得炫耀的事情。

 现在就想着把一个月前承诺的大东北还了…就鼓励一下得…据说还要到6月才出结果…恐怕又是一出悲剧。

 下月我们会介绍一些编译原理方面的知识。

 抽空写了写GPCT 6th，由于空闲时间实在太少，对C#.net也就大概看了半天时间，代码终于越写越冗长…不过心疼自习时间急剧压缩，还是下决心release了。清明前去村里旧书店淘了几本思修、马原等书回家来看，可是《Programmer》上明明有“RIA战火纷争”呀，看来只能赶明天下午的校车了呵呵。

 持续时间没人能知道，也许做1600题的时候会出专题…不过那最快也是4个月以后的事情了。最近笔记本用的飞快…一周能写干6根笔…回家也是收集信息，不过感觉还是在学校充实一点…给人感觉可能是有点过，不过一年以后恐怕每个人都可以理解了吧。

二、AS3.0语法概要

我们知道，按照adobe的说法，AS3.0是完全依据ECMAScript 4.0（草案）标准的。尽管无意提起JavaScript和ActionScript的争端，但ECMA委员会延用v3.1标准已是板上钉钉的事实，似乎预示着Ajax和Flex即将实现不同目标的分离—在我看来这未必是一件坏事，当然，各方的众多支持者恐怕都不会放弃“吃着碗里，看着锅里”的想法。

AS3.0延用了Java的制式包含了许多内置类，如类型封装类Number、String、Boolean等，还有一些内置类如Array、Math和XML等定义了更多复杂的数据结构以及运算。所有的类，无论是内置类还是用户自定义类，都是由一个共同的类Object派生的。但是有一种特殊的变量被称为无类型变量，它们的定义方式如下：

var example;

var example:*;

它们可以用来存储一些特殊值，这是指定类型Object或其派生类所不具备的。声明并创建类的对象的语句如下:

var timeNow:Date = new Date();

new运算符的用法，和C++/Java是惊人的相似！

1、包和命名空间

包packge用于管理一段共享代码中的类文件，它的目的是使程序更易于被复用以及维护—这也是现代OOP的一个重要思想之一。下面一段代码用来创建一个简单类的包：

package samples

{

    public class SampleCode

    {

        public var sampleGreeting:String;

        public function sampleFunction()

        {

            trace(sampleGreeting + ” from sampleFunction()”);

        }

    }

}

注意包的名称samples，当编译器编译时会把类名称变为完全限定名称，如samples.SampleCode，其方法的调用也相应变成samples.SampleCode.sampleFunction()。

AS3.0还有一个特点，即包内不仅仅可以含有一个顶级类，还可以定义顶级变量、函数甚至语句，这些内容将可以被包内成员访问。同时在包的顶级只能允许public和internal两种访问说明符。

与Java不同的是，AS3.0不支持私有类和嵌套类，你会发现包内一般也只能定义一个类。这是因为对于一个.as文件，程序只允许调用其中的一个类，Java中只需将类定义为public即可，AS3.0中这个类必须是在包中。如果要实现类似私有类的定义，那么可以在同一文件的包外进行定义—例如上一篇中的包外类，这种用法在AS中很常见。

包是可以嵌套的，通常称其为嵌套包。嵌套包可以在逻辑上与父包相关，也可以不相关。有时我们定义嵌套包，仅仅是为了防止对同一类名的引用发生冲突。而且到目前为止，AS的作者还未对包赋予任何类似类继承的概念，例如下段代码。

package samples.sample1

{

    public class SampleCode

    {

    }

}

当我们在程序中同时导入了两个包时，以下调用会发生名称错误：

var object:SampleCode = new SampleCode();

只有当使用完全限定名称时才能避免此错误：

var object:samples.SampleCode = new samples.SampleCode(); //调用前一个类

调用包的方法也很简单，在程序头中输入以下代码：

import samples.*; //完整导入包

import samples.sample1.SampleCode; //直接指定类

一般提倡程序员使用第二种方法导入包，否则可能会引发类名冲突等问题，这一点上与Java有一定区别。

命名空间namespace是一种用来控制类、类的属性及其方法可见性的标识符，它也是OOP中一项重要的讨论内容。AS3.0中的命名空间分为五种，其中内置包括了public、private、protected 和 internal四种，另一种则可以由用户自定义。

首先介绍自定义的命名空间，我们通常需要三个简单步骤完成对命名空间的声明定义和使用，例如以下代码。

namespace v1; //声明一个命名空间

v1 function testNamespace():void{} //定义一个以v1为命名空间的函数

use namespace v1; //调用具有命名空间v1的函数

testNamespace();

v1::testNamespace() //或者利用限定运算符直接引用该函数

自定义命名空间的目标是使程序员自己定义成员的可见性。例如我们有不同的类分别位于不同的包中，而这些包是由不同的程序调用的。当某个方法需要无条件被其它类使用时，程序员可以将其声明为自定义命名空间，这样即实现了既定目标，又不至于令该方法成为一个公共方法。

2、变量

通过前面的例子我们可以知道，AS3.0中的变量声明基本遵循以下格式：

var i;

var i:int;

其中标识符var必须作为声明语句开端，当我们要赋值时，其基本形式和一般语言是相通的：

var i:int=10;

i=20;

这表示变量既可以在声明时被赋值，也可以单独赋值。例如数组的声明时赋值：

var example:Array=[“first”,”second”,”third”];

创建一个类的对象时var同样适用，例如：

var exam:ClassCode=new ClassCode();

多个变量的声明和赋值是可以放在同一语句内的，但细节上与其他语言有所区别。

var firstvar:int,secondvar:int,thirdvar:int;

var firstvar:int=1;secondvar:int=2,thirdvar:int=3;

研究变量的作用域是个有趣的问题，因为它并不仅仅是全局变量和局部变量区别。例如在C++或Java中就对变量作用域做出了严格限制：

int cFunction(int input)

{ //这是一个错误的语言示例

if(input>0)

{

int result=10;

}

else

{

result=5;

}

result=input+result;

return result;

}

以上程序段会发生编译错误，这是因为result声明的作用域仅仅在if语句块内，这就是所谓的块级作用域。而在AS3.0中并不错在类似的限制，这种情况的出现似乎得益于编译器对声明语句的“自动提升”机制，也就是说将函数中的全部变量声明语句自动提前到代码段前端执行，因此就导致了块级作用域的失效。

但是，AS的编译器仅仅对声明语句具备自动提升的功能，对赋值语句而言并不存在这些“待遇”，因此我们可能会遇到如下语句段：

function example:int()

{

num=10;

var num:int; //声明语句滞后，但本段程序是可以通过编译的

return num;

}

3、数据类型

AS3.0的数据类型种类较少，且比较特殊。不过值得注意的是，AS3.0的类型检查通常是在程序运行时执行的，这一类语言被称为动态类型语言（注意与动态语言的区别），例如Python。但是在Adobe Flash CS3 professional中编译器是可以选择运行在严格模式或标准模式下的（默认为严格模式），因此不同模式下编译器所遵循的编译规则也有不同。例如严格模式就要求在编译时也执行类型检查工作。

AS3.0的编译器标准模式扩展了运行时类型检查机制，将其扩展到了对实例化对象的检查，即允许以基类声明的对象最终按子类实例化。我们知道，在过去的编译器中，动态语义分析是几乎不可能实现的，因此许多OO语言为了实现对象对基类和子类方法的动态选择问题，制定了动态绑定的规则。但这似乎在AS3.0中变得更为简便了。

AS3.0共有七种基本数据类型，分别为：

Boolean，包含true和false两个值，默认为false；

int，表示32位整数，

Null，只包含一个值null，这是对String数据类型和定义所有复杂数据类型的初始值。null是一个极为特殊的值，如果将null赋给非String或复杂数据类型，则编译器会将其自动转换为相应的默认值；

Number，用于表示整数、无符号整数和浮点数，由于AS3.0本身含有int和uint类型，因此一般仅在需要用到浮点数表示时才会使用。Number的默认值为NaN，这在计算结果应当为数字而不是数字时返回的结果，例如除零运算；

String，用于表示16位字符序列，字符串在内部存储为unicode字符，String的值是不能被更改的。其默认值为null，另外空字符串”“与null尽管都表示无字符，但本质上并不相等；

uint用来表示32位无符号整数，默认为0；

void仅包含一个值undefine，当使用无类型变量时可以赋予undefine，但一般情况下void仅能在声明返回值类型时使用。

ActionScript内部类还定义了如下数据类型（尽管每种语言的表述方式可能不尽一致）：Object、Array、Date、Error、Function、RegExp、XML 和 XMLList，其中object是所有类的基类，其默认值为null。

4、数据类型转换

AS3.0的类型转换相当方便，其主要分为两种形式：

1）隐式转换，一般只在运行时发生。例如在赋值语句中、函数传参、函数返回值或者是表达式转换；

2）显示转换，一些转换在严格模式下并不能通过，例如下段代码：

var example:String=”150”;

var intexample:int=example;

这时只能应用显示转换来进行：

var intexample:int=int(example); //替换上段代码第二句

我们可以发现，AS3.0的显示类型转换是通过一种类似于类型名函数的方式进行的，事实上这些函数也是语言的内置函数，他们通过一类特殊算法实现了几乎所有类型的互相转换操作。但是一些转换规则需要引起注意：

int()和uint()执行浮点数“去尾制”，含有非数字字符则直接置0的规则。Boolean()只有在0时代表false，其余数字均代表true，通常值为null的字符串、未初始化的对象或空字符串（即值为”“）也将转换为false，有时Boolean可直接通过隐式转换完成。

在转换String()时，默认值为null的量将转换为”null”字符串，其他量直接转换为字符串类型。

5、动态类

动态类是一个特殊的机制。其作用是在运行时在对象中声明新的属性或方法，这在其他语言中还没有遇到（作者如此）。

动态类的声明需要关键字dynamic，例如：

dynamic class exampleClass

{

public property:int=200;

}

var varinstance:exampleClass=new exampleClass();

varinstance.property=100;

varinstance.newproperty:int=200; //新申请的属性

我们甚至可以为动态类定义新的方法：

exampleClass.getValue = function()

{

return this.property;

}

应当注意这里用到了this关键字，这是因为通过动态类方式产生的属性或方法永远不能引用私有属性或方法，即使引用了公共属性或方法，也需要用this关键字，或者使用类名加限定符的方式。

（树、图补完篇）

 

    本篇的主要目的是对树和图部分内容中的代码进行分析，涉及构造哈夫曼树、图的几种主流应用算法等问题。本篇结束后假期系列的基本数据结构部分就暂告一段落了。

   

构建哈夫曼树

 

    现在讨论构建哈夫曼树的算法实现问题。在前文已经对构造哈夫曼树的算法思路有了一定的介绍，易知哈夫曼树中没有度为1的结点，因而一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。其结点结构分别是权值域、双亲序号、左子女序号、右子女序号。各结点存储在一维数组中，0号单元不用，从1号位置开始使用。

    对于有n个叶子结点的哈夫曼树，结点总数为2n-1个，为实现方便，将叶子结点集中存储在前面部分1-n个位置，而后面的n-1个位置中存储其余非叶子结点。

    我们给出静态三叉链表实现的哈夫曼树类型C语言描述：

    #define N 20

    #define M 2*N-1

    typedef struct

{

    int weight;

    int parent;

    int LChild;

    int RChild;

}HTNode,HuffmanTree[M+1];

使用上述结构实现创建哈夫曼树算法：

void CrtHuffmanTree(HuffmanTree ht,int w[],int n)

{

    for(i=1;i<=n;i++)

    {

        ht[i]={w[i],0,0,0}  //初始化1—n单元的叶结点

}

m=2*n-1;    //统计结点总数

for(i=n+1;i<=m;i++) //从n+1至m个结点为非叶结点

{

    select(ht,i-1,&s1,&s2); //从ht中选择两个parent为0且weight最小的结点，将其序号分别赋值给s1、s2返回

    ht[i].weight=ht[s1].weight+ht[s2].weight;   //计算每次结合后根结点的权值

    ht[s1].parent=i;    //将s1、s2的父结点指定为第i个结点

    ht[s2].parent=i;

    ht[i].LChild=s1;    //对第i个结点的左右子女结点赋值

    ht[i].RChild=s2;

}

}

 

计算哈夫曼编码

 

    我们知道，构建哈夫曼树的最终目的是求解哈夫曼编码，从而方便信息传输和数据压缩。因此基于哈夫曼树的哈夫曼编码计算算法就显得尤为重要了。

    void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n)

    {

        char *cd;

        cd=(char*)malloc((n+1)*sizeof(char));   //初始化空间

        cd[n-1]=”\0”;                         //首先存放结束符

        for(int i=1;i<=n;i++)

        {

            start=n-1;          //编码起始位置

            c=i;               

            p=ht[i].parent;     //从叶结点开始倒推

            while(p!=0)

            {

                –start;        //倒推一层，判断左0右1，再推一层，直到根结点

                if(ht[p].LChild==c)

                {

                    cd[start]=’0’;

}

else

{

    cd[start]=’1’;

}

c=p;

p=ht[p].parent;

}

hc[i]=(char*)malloc((n-start)*sizeof(char));    //建立哈夫曼编码存放空间

strcpy(hc[i],&cd[start]);

}

free(cd);

}

 

深度优先的简单路径算法

 

    在图这一部分中，简单路径是指任意两结点路径中不含相同结点的一条。为求解图的简单路径，需要先对图中所有结点进行统一标识，每访问一个结点，则更改该结点标识符，从而达到求简单路径的目的。

    算法外围的核心是给所有结点统一赋值，并且建立对应于结点且独立的带值空间。下面给出用深度优先搜索寻找从u到v的简单路径算法C语言描述。

    void DFS_path(Graph *G,int u,int v)

{

    int j;

    for(j=firstadj(G,u);j>=0;j=nextadj(G,u,j))

    {

        if(pre[j]==-1)      //默认结点标识为-1，一旦使用过即将标识符置为u

{

            pre[j]=u;

            if(j==v)

            {

                print_path(pre,v);

}

else

{

        DFS_path(G,j,v);

}

}

}

}

 

生成树

 

生成树涉及到很多实际应用，例如搭桥问题…但利用MST性质求MST（Minimum Spanning Tree）还分别有Prim和kruskal两种角度不同的算法。

Prim算法通常被称为“加点法”，这是因为算法是在一个初始化为空的结点空间中，判断能令(u,v)最短的u对应的v结点，然后加入到空的结点空间中，反复执行直到该结点空间与图的结点空间相等。

Kruskal算法是根据权值最小的边，同时必须确保两个顶点不在同一个结点集合内，故有时Kruskal算法也被称为“加边法”。事实上以上两种算法除却初始化的部分，真正涉及到原理的代码段就已经非常简单了。

 

总结

 

对于拓扑排序、关键路径、最短路径等问题，读者应重点参照“图的应用”这一节连载，其原理已经比较详细，但由于经典算法时间复杂度高，已经有越来越多的专家学者对此提出了许多改进方案，并给出了许多算法解决方案，因此在此基础上参照相关科技文献，才能确保算法的实用性。

2010考研复习纲要

 

本纲要初定于2009年2月21日星期六，是2008-2009学年度大学三年级第二学期开学后第六天。制定本纲要的目的是对2010年全国硕士研究生入学统一考试复习工作进行全面规划、安排，同时对复习期间附带其它的学习项目进行评估。

 

目标学校：暂定，由于信息收集工作的原因，本项于2009年5月31日前确定。

 

目标专业、方向：计算机科学与技术专业、计算机软件与理论方向（方向正式录取后才能最终确定）。

 

考试科目及教材：

 

高等数学（同济大学第五版），工程数学线性代数（同济大学第三版），概率论与数理统计（浙江大学第三版）、数据结构（高等教育出版社C语言版、清华大学C++版）、计算机组成原理（白中英第四版）、计算机操作系统（西电汤子瀛第二版）、计算机网络（清华大学出版社吴功宜，备选电子工业出版社谢希仁第五版）、思想道德修养与法律基础（高等教育出版社）、中国近现代史纲要（西北大学出版社、备选高等教育出版社）、马克思主义原理基本概论（高等教育出版社）、毛泽东思想、邓小平理论和三个代表重要思想概论（高等教育出版社）。

 

具体考试科目介绍（严格依据2009年全国硕士研究生入学统一考试大纲）：

 

1、  数学一（满分150分，考试时间为180分钟）

a)         试卷内结构：高等数学55%，工程数学线性代数22%、概率论与数理统计22%。

b)        试卷题型结构：单项选择题8题*4分，填空题6题*4分，解答题9题共94分。

2、  政治（满分100分，考试时间为180分钟）

a)         试卷内结构：由于课程改革，试卷结构将在2010年考研政治大纲公布后确定。

b)        试卷题型结构：单项选择题16题*1分，不定向选择题17题*2分，问答题10题*4分，二选一论述题10分。

3、  英语（满分100分，考试时间为180分钟）

a)         词汇量要求：2009考研英语大纲要求的词汇量为5500词，但根据各方数据为了全面应对考试，考生应具备8000左右的词汇量，达到大学英语专业四级的词汇水平。

b)        试卷题型结构：完型填空（20题*0.5分），阅读（A阅读理解20题*2分，B新题型5题*2分，C翻译5题*2分），作文（书信小作文10分，图画大作文20分）。

4、  计算机学科专业基础综合考试（满分150分，考试时间为180分钟）

a)         试卷内结构：数据结构45分，计算机组成原理45分，操作系统35分，计算机网络25分。

b)        试卷题型结构：单项选择题80分（40题，每小题2分），综合应用题70分。

 

参考书目及辅导班计划

 

       由于参考书目众多且辅导班较为庞杂，因此这里仅列出重点要求。另一些已列书目可能会包含在辅导班计划之内，例如政治任汝芬系列。

       数学：2010数学复习全书（数学一，李永乐），2010数学历年试题解析（数学一，李永乐），全真模拟400题（李永乐）。

       英语：历年考研英语真题解析及复习思路（新华出版社，张剑），2010考研英语词汇星火式巧记速记精练（新华出版社，马德高）、2010考研英语阅读理解精读200篇（高等教育出版社，胡敏）。

       政治：任汝芬教授考研政治序列之一、序列之二、序列之三（西安交通大学出版社），启航考研政治20天20题（中国市场出版社，每年１月初出版）。

       计算机学科专业基础综合：算法与数据结构考研试题精析（第二版）、计算机组成原理—学习指导与习题解答（唐朔飞），计算机网络知识要点与习题解析（哈尔滨工程大学出版社），操作系统学习指导和考试指导（浙江大学出版社，李善平）。

       根据目前所掌握的信息并结合2009年时间安排情况，辅导班重点关注考研政治（西安人信学校），数学（西安海文学校）、英语两科按照2009年5月31日之前的基础复习情况以及之后的初步评估最终决定。

 

复习时间流程

 

       由于7月初开始需要进行为期四个半月的实习项目，因此时间安排上比较紧凑，同时仍要考虑到辅导班的日程安排，因此规划如下。

 

2009年1月11日至2009年5月31日，重点完成对高等数学、线性代数、概率论与数理统计三门课的课本复习，同时进行英语8000词汇的记忆工作，力争在时间内初步解决。

 

2009年6月1日至2009年8月31日，开展暑期强化工作，除了继续基础阶段的强化外，要开始进行专业课的基础复习工作（在暑期实习期间完成）。

 

2009年9月1日至2009年11月30日，继续强化基础课程，并开始进行专业课强化复习。开始政治课全面复习，期间考虑申报最终阶段辅导班。

 

2009年12月1日至考试前夕，对整个复习流程进行总结，并根据复习期间积累的重点习题册和真题进行最后复查，政治课进行强化复习。

 

考研复习期间学习项目计划

 

       尽管复习任务艰巨，情况复杂，但不应忽视对本专业上层能力的扩展。2009年6月31日前应重点学习ActionScript3.0编程、计算机算法设计部分（C/C++版），2009年7月1日起开始重点学习实习有关内容（预计为VC++，MFC）、设计模式、C#（ASP.NET）。以上内容应在2010年２月底以前全部完成。

 

总结

 

为了不产生误导作用，本文自发布起将设置隐藏。根据以往统考惯例，2010年的研招考试预计将在2010年1月9日至10日进行，本纲要的作者可在2010年1月9日以前对本纲要进行任何修改，但需保留原计划内容并标明修改时间，2010年2月底（距制定时间一周年以后）本纲要的隐藏设置将解除。