Home About us Products Services Contact us Bookmark
:: wikimiki.org ::
程序设计语言

程序设计语言

程序设计语言，是一组用来定义计算机程序的语法规则。它是一种被标准化的交流技巧，用来向计算机发出指令。一种计算机语言让程序员能够准确地定义计算机所需要使用的数据，并精确地定义在不同情况下所应当采取的行动。 程序设计语言原本是被设计成专门使用在计算机上的，但它们也可以用来定义算法或者数据结构。正是因为如此，程序员才会试图使程序代码更容易阅读。 设计语言往往使程序员能够比使用机器语言更准确地表达他们所想表达的目的。对那些从事计算机科学的人来说，懂得程序设计语言是十分重要的，因为在当今所有的计算都需要程序设计语言才能完成。 在过去的几十年间，大量的程序设计语言被发明、被取代、被修改或组合在一起。尽管人们多次试图创造一种通用的程序设计语言，却没有一次尝试是成功的。之所以有那么多种不同的编程语言存在的原因是，编写程序的初衷其实也各不相同；新手与老手之间技术的差距非常大，而有许多语言并对新手来说太难学；还有，不同程序之间的运行成本（）各不相同。 有许多用于特殊用途的语言，只在特殊情况下使用。例如，PHP专门用来显示网页；Perl更适合文本处理；C语言被广泛用于操作系统和编译器的开发（所谓的系统编程）。 高级程序设计语言（也称高级语言）的出现使得计算机程序设计语言不再过度地倚赖某种特定的机器或环境。这是因为高级语言在不同的平台上会被编译成不同的机器语言，而不是直接被机器执行。最早出现的编程语言之一FORTRAN的一个主要目标，就是实现平台独立。 虽然大多数的语言可以既被编译（）又被解译（），但大多数只在一种情况下能够良好运行。在一些编程系统中，程序要经过几个阶段的编译，一般而言，后阶段的编译往往更接近机器语言。这种常用的使用技巧最早在1960年代末用于BCPL，编译程序先编译一个叫做“0代码”的转换程序（），然后再使用虚拟器转换到可以运行于机器上的真实代码。这种成功的技巧之后又用于Pascal和P-code，以及Smalltalk和二进制码，虽然在很多时候，中间过渡的代码往往是解译，而不是编译的。 如果所使用的翻译的机制是将所要翻译的程序代码作为一个整体翻译，并之后运行内部格式，那么这个翻译过程就被成为编译。因此，一个编译器是一个将人可阅读的程序文本（叫做源代码）作为输入的数据，然后输出可执行文件（）。所输出的可执行文件可以是机器语言，由计算机的中央处理器直接运行，或者是某种模拟器的二进制代码。 如果程序代码是在运行时才即时翻译，那么这种翻译机制就被称作解译。经解译的程序运行速度往往比编译的程序慢，但往往更具灵活性，因为它们能够与执行环境互相作用。参见解译语言。

特点

每一种程序设计语言可以被看作是一套包含语法、词汇和含义的正式规范。 这些规范通常包括：
- 数据和数据结构
- 指令及流程控制
- 引用机制和重用
- 设计哲学 大多数被广泛使用或经久不衰的语言，拥有负责标准化的组织，经常会晤来创造及发布该语言的正式定义，并讨论扩展或贯彻现有的定义。

数据和数据结构

现代计算机内部的数据都只以二元方式储存，即开-关模式()。现实世界中代表信息的各种数据，例如名字、银行账号、度量以及同样低端的二元数据，都经由程序设计语言整理，成为高端的概念。 一个程序中专门处理数据的那个系统被称为程序语言的型态系统()；对型态系统的研究和设计被称为型态理论()。语言可以被分为静态型态系统()，例如C++和Java，和动态型态系统()，例如Lisp，JavaScript，Tcl和Prolog。前者可被进一步分为包含宣告型态()的语言，即每一个变量和函数的型态都清楚地宣告，或type-inferred语言（例如MUMPS，ML）。 大多数语言还能够在内置的型态基础上组合出复杂的数据结构型态（使用数组，列表，堆栈，文件等等）。面向对象语言（，又译作“物件导向语言”）允许程序员定义新的数据型态，即“对象”或“物件”（），以及运行于该对象的函数（）和方法（）。 除了何时以及如何确定表达式和型态的联系，另外一个重要的问题就是语言到底定义了哪些型态，以及允许哪些型态作为表达式的值。诸如C编程语言之类的低端语言允许程序命名内存位置、内存区域以及编译时的常量；ANSI C甚至允许表达式返回结构值（）。功能性的语言一般允许变量直接使用运行时计算出的值，而不是指出该值可能储存的内存地址。

指令及流程控制

一旦数据被确定，机器必须被告知如何对这些数据进行处理。较简单的指令可以使用关键字或定义好的语法结构来完成。不同的语言利用序列系统来取得或组合这些语句。除此之外，一个语言中的其他指令也可以用来控制处理的过程（例如分支、循环等）。

引用机制和重用

引用的中心思想是必须有一种间接设计储存空间的方法。最常见的方法是通过命名变量。根据不同的语言，进一步的引用可以包括指向其他储存空间的指针。还有一种类似的方法就是命名一组指令。大多数程序设计语言使用宏调用、过程调用或函数调用。使用这些代替的名字能让程序更灵活，并更具重用性。

程序设计语言的历史

二十世纪四十年代当计算机刚刚问世的时候，程序员必须手动控制计算机。当时的计算机十分昂贵，唯一想到利用程序设计语言来解决问题的人是德国工程师楚泽（）。 几十年后，计算机的价格大幅度下跌，而计算机程序也越来越复杂。也就是说，开发时间已经远比运行时间来得宝贵。 于是，新的集成、可视的开发环境越来越流行。它们减少了所付出的时间、金钱（以及脑细胞）。只要轻敲几个键，一整段代码就可以使用了。这也得益于可以重用的程序代码库。

常见的程序设计语言


- APL、A＋和J
- Ada
- 汇编语言
- AWK
- Basic、Fortran
- VBScript
- Brainfuck
- C、C＋＋
- C＃
- Clipper
- COBOL
- dBase
- PASCAL、Delphi
- Forth
- FoxPro
- F＃
- Fava
- IDL
- Java
- JavaScript
- J#
- LISP
- LOGO
- Modula
- Perl
- PHP
- PL/I
- Prolog
- Python
- Ruby
- Scheme
- Smalltalk
- SQL
- Tcl/Tk
- Visual Basic
- Visual FoxPro
- XML

参见


- 计算机科学课程列表
- 程序设计语言列表
- 编译器
- Hello World程序
- 脚本语言
- 維基程序員 category:人工語言 ja:プログラミング言語

计算机程序

计算机程序或者软件程序（通常简称程序）是指一组指示计算机每一步动作的指令，通常用某种程序设计语言编写，运行于某种目标体系结构上。打个比方，一个程序就像一个用汉语（程序设计语言）写下的红烧肉菜谱（程序），用于指导懂汉语的人（体系结构）来做这个菜。 通常，计算机程序要经过编译和链接而成为一种人们不易理解而计算机理解的格式，然后运行。未经编译就可运行的程序通常称之为脚本程序。

程序的运行

为了一个程序运行，计算机加载程序代码，可能还要加载数据，从而初始化成一个开始状态，然后调用某种启动机制。在最低层上，这些是由一个引导序列开始的。 在大多数计算机中，操作系统例如Windows等，加载并且执行很多程序。在这种情况下，一个计算机程序是指一个单独的可执行的映射，而不是当前在这个计算机上运行的全部程序。

冯诺依曼体系结构

在一台基于最常见的冯诺依曼体系结构(又称Harvard Architecture)的计算机上，程序从某种外部设备，通常是硬盘，被加载到计算机里。 如果计算机选择冯诺依曼体系结构，那么程序就被加载入内存。 指令序列顺序执行，直到一条跳转或转移指令被执行，或者一个中断出现。所有这些指令都会改变指令寄存器的内容。 基于这种体系计算机如果没有程序的支持将无法工作。一个计算机程序是一系列指令的集合。 程序里的指令都是基于机器语言；程序通常首先用一种计算机程序设计语言编写，然后用编译程序或者解释执行程序翻译成机器语言。 有时，程序也可以用汇编语言编写，汇编语言实质就是表示机器语言的一组记号－在这种情况下，用于翻译的程序叫做汇编程序(Assembler)。

程序和数据

程序已经被定义了。如何定义数据呢？数据可以被定义为被程序处理的信息。当我们考虑到整个计算机系统时，有时程序和数据的区别就不是那么明显了。中央处理器有时有一组微指令控制硬件，数据可以是一个有待执行的程序（参见脚本编程语言），程序可以编写成去编写其它的程序；所有这些例子都使程序和数据的比较成为一种视角的选择。有人甚至断言程序和数据没有区别。 编写一个程序去生成另外一个程序的过程被称之为原编程()。它可以被应用于让程序根据给定数据生成代码。单一一个程序可能不足以表示给定数据的所有方面。让一个程序去分析这个数据并生成新的程序去处理数据所有的方面可能会容易一些。就是一例支持这种编程模式的程序语言。 在神经网络里储存的权重是一种数据。正是这些权重数据，跟网路的拓扑结构一起，定义了网络的行为。人们通常很难界定这些数据到底表示什么或者它们是否可以由程序来代替。这个例子以及跟人工智能相关的其它一些问题进一步考验程序和数据的区别。

算法

算法指解决某个问题的严格方法，通常还需辅以某种程度上的运行性能分析。算法可以是纯理论的，也可以由一个计算机程序实现。理论算法通常根据复杂性分为不同类别；实现的算法通常经过颇析()以测试其性能。请注意虽然一个算法在理论上有效可行，但是一个糟糕的实现仍会浪费宝贵的计算机资源。（更详细信息，参见算法信息论，）

开发

编写程序是以下步骤的一个往复过程：编写新的源代码，测试、分析和提高新编写的代码以找出语法和语义错误。从事这种工作的人叫做程序设计员。由于计算机的飞速发展，编程的要求和种类也日趋多样，由此产生了不同种类的程序设计员，每一种都有更细致的分工和任务。软件工程师和系统分析员就是两个例子。现在，编程的长时间过程被称之为“软件开发”或者软件工程。后者也由于这一学科的日益成熟而逐渐流行。 因此，如今程序设计员可以指某一领域的编程专家，也可以泛指软件公司里编写一个复杂软件系统里某一块的一般程序员。一组为某一软件公司工作的程序员有时会被指定一个程序组长或者项目经理，用以监督项目进度和完成日期。大型软件通常经历由系统设计师的掌握的一个长时间的设计阶段，然后才交付给开发人员。牛仔式的编程（未经详细设计）是不为人所齿的。 两种当今常见的程序开发方式之一是项目组开发方式。使用这种方式项目组里每一个成员都能对项目的进行发表意见，而由其中的某一个人协调不同意见。这样的项目组通常有10个左右的成员，这样做是为了便于管理。第二种开发方式是结对开发。

参见


- 程序员
- 卸载程序
- 源代码
- 電子計算機
- 计算机软件
- 程序设计语言
- 編程典範
- 固件
- 操作系统
- 图灵机
- 系统需求

外部链接


- [http://www.webopedia.com/TERM/P/program.html Definition of Computer program @ Webopedia]

参考文献

#Eric Baum What is Thought MIT Press 2004 ISBN 0-262-02548-5 #- Chapter Two: The Mind is a Computer Program Category:计算机软件 Category:程序设计 ja:プログラム ko:프로그램 simple:Computer program

计算机

電子計算機，--电脑，是一种电子化的计算工具。在中國大陆也經常用計算機來指代電子計算機。就目前而言，電子計算機是根据预先设定好的程序来进行信息处理的一种设备。電子計算機分为巨型计算机（又称“超级计算机”）、大型计算机、中型计算机、小型计算机、微型计算机（简称“微机”，其中包括个人计算机，PC），已经逐步进入社会各个领域，尤其是进入了家庭和个人领域，极大地改变了社会的日常面貌。

定义

上述对于電子計算機的定义包括了许多只能计算或是只有有限功能的特定用途的设备。然而当说到现代電子計算機，最重要的特征是，只要给予正确的规划，任何電子計算機都可以模拟其他任何的行为（只受限于電子計算機本身的存储容量和执行的速度）。据此，现代電子計算機相对于早期的電子計算機也被称为通用型電子計算機。

分类

为了定义什么是電子計算機，对所有计算设备进行分类是必然的。下面的章节介绍几种不同的分类方法。这些分类方法必须一起使用才能准确无误的描述一台特定的電子計算機。

按用途分类

这是最明显的分类法。電子計算機制造商通常用这种方法来描述他们的产品；用户用同样的方法来描述与他们交流的机器。例如：
- 巨型计算机
- 小巨型计算机
- 超級计算机
- 大型计算机
- 企业应用服务器
- 小型计算机
- 工作站
- 个人计算机或者台式机
- 膝上型电脑或者笔记本电脑
- 个人数字助理
- 可以穿戴的电脑 按用途分类很通俗，但是也导致它的不确定性，因为仅仅当前广泛使用的设备被包含进来了。電子計算機发展的快速性意味着其新用途层出不穷，当前的定义很快就过时。许多不再被人使用的電子計算機的类型，例如微分分析器，通常不被列入分类条目之中。所以，必须采用其他分类方法来明白无误的定义電子計算機这条术语。

按制造技术分类


- 机械式电脑
- 半电子—半机械式
- 电子式
- 晶体管式
- 半导体集成电路式

按设计特点分类

现代電子計算機综合了许多基本的设计特点，这些特点是许多贡献者在很多年里逐渐开发出来的。设计特点经常独立于实现技术。现代電子計算機的综合性能来源于这些特点互相作用的方式。一些重要的设计特性罗列如下：

数字式和模拟式

设计一种電子計算機时需要有一个基本的决定，即这种電子計算機应该是数字式还是模拟式的。数字式处理离散的数字性或者符号性值，而模拟式仍然应用于一些特殊目的的领域，例如机器人和回旋加速器的控制。其他的途径，象脉冲计算和量子计算，也是可能存在的；但是他们或者用于很特殊的目的或者仍然处于试验阶段。

二进制和十进制

在数字式计算的发展历程中，一个重大的设计进步是引入了二进制作为内部的数字系统。这种方法避免了那些基于其他数字系统的電子計算機中必须的复杂的进位机制，例如十进制系统。采用二进制的好处是简化了实现算术功能和逻辑运算的设计。

按功能分类

对不同的计算设备分类的最好办法可能是按他们的内在能力分类，而不是按他们的用途，实现技术，或者设计特性来分类。電子計算機按能力可以分为三大类：只能计算一种函数的单用途设备，可以计算有限范围内的函数的特殊用途设备，以及我们天天使用的通用设备。过去電子計算機这个词用来描述所有这些类型的机器，但是现在口语中的用法通常特指通用電子計算機了。

通用電子計算機

按定义来说，一台通用電子計算機能用来解决任何问题，只要这个问题可以用程序来表示。然而，程序运行的是有一些实际的限制的：電子計算機的存储能力，问题的大小，以及运行的速度。在1934年，艾伦·图灵证明了：给定正确的程序，任何通用電子計算機可以模拟其他任何电脑的行为。他的数学证明是纯粹理论上的，因为那时候还没有通用電子計算機存在。这个证明的意义是深远的：例如，从理论上说，现在的通用電子計算機能够模拟任何未来制造的通用電子計算機的行为，尽管速度很慢。 通用電子計算機也称作完备的图灵机，它经常被用来作为定义现代電子計算機的能力上限。然而，这种定义是有问题的。几种过分单纯化的计算设备已经展现出完备的图灵机特性。但是他们都处于一种幽默化表达的“图灵沥青陷阱”（？）状态，一种什么都是有可能的，但是和实用性一点都不沾边。现代電子計算機不仅仅是理论上的通用化，而且是实用化的通用工具。 从1930年代中期到1940年代后期，许多人在开发现代的、数字的、电子的，通用電子計算機。许多试验型的机器被造了出来并且可能是图灵完备化的。这些机器在当时都被宣称为第一台電子計算機，然而它们都只有有限的处理通用问题的能力，所以他们的设计最终都被抛弃了。

存储程序電子計算機

特殊用途電子計算機

单用途電子計算機

按操作类型分类

電子計算機也可以按用户操作的方式来分类。有两大类操作方式：批处理和交互式处理。

嵌入式電子計算機

从1980年代起，许多的家用设备，不只包括电视游戏控制器，而且延伸到移动电话、录相机、PDA和许多其他的工业、电子设备，都内嵌有特定用途的電子計算機。这些電子計算機也通常被称之为“微控制器”或者嵌入式計算機。

个人计算机

就目前而言，一般人所提到的计算机都是指个人计算机。

大型计算机

巨型计算机

成指数级增长的电脑的发展

划分不同种電子計算機的难度因为它的计算能力的指数增长更加复杂化。粗略估计，从1900年到现在，计算设备的计算能力（按1000美元能够买到的设备在每秒种内处理运算指令的数量）每一年半到两年就增加一倍。英特尔公司的创始人之一，戈登·E·摩尔在1965年首次描述了電子計算機发展的这种特性（参考摩尔定律）。快速发展的電子計算機制造工程技术维持了这种指数级的能力增长。与这种能力增长携手并进的另一过程是戏剧化的小型化过程。第一代的電子計算機，例如ENIAC(出现于1946年)，都是一些重达数吨，占据好几间房间，需要多个操作员来维持它们正常工作的庞然大物。这些大家伙太贵了，以至于只有政府和大型机构才能够买得起。它们也的确太怪异了，当时的人们都认为几台，或者几十台这样的机器就能够满足全世界的需求了。相比之下，现代電子計算機比第一代前辈多了几个数量级，更加多才多艺，而且便宜、小巧，还随处可见。

電子計算機是如何工作的

自从1940年代第一台電子計算機问世以来，大部分的電子計算機仍采用冯·诺依曼结构体系，虽然其相关技术已经发生了翻天覆地的变化。 冯·诺依曼结构将一个電子計算機系统分为四个主要部分：算术逻辑单元、控制器、存储器和输入输出设备。这些部分是通过总线连接起来的。

参看


- 電子計算機的历史
- 计算机图片
- 电脑游戏
- 计算机软件
- 计算机网络 Category:计算机硬件 ja:コンピュータ ko:컴퓨터 ms:Komputer nb:Datamaskin simple:Computer th:คอมพิวเตอร์

算法

Category:代数 Category:算法 算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。 算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法的历史

“算法”的中文名稱出自周髀算經；而英文名稱 Algorithm 来自于9世纪波斯数学家比阿勒·霍瓦里松的名字al-Khwarizmi，因為比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。 第一次编写算法是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。

算法的特征

#输入，一个算法必须有零个或多个输入量。 #输出，一个算法应有一个或多个输出量，输出量是算法计算的结果。 #确定性，算法的描述必须无歧义，以保证算法的执行结果是确定的。 #有穷性，算法必须在有限步骤内实现。注：此处“有限”不同于数学概念的“有限”，天文数字般的有限对于实际问题并无意义。 #有效性（亦称可行性），能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

形式化算法

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。 一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

算法的复杂度

算法的时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n的函数f（n），算法的时间复杂度也因此记做 T（n）=O（f（n）） 因此，问题的规模n越大，算法执行的时间的增长率与f（n）的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

算法的空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

非確定性多項式時間(NP)

算法的实现

算法不单单可以用计算机程序来实现，也可以在神经网络、电路或者机械设备上实现。

例子一

这是算法的一个简单的例子。 我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”： # 首先将第一颗豆子放入口袋中。 # 从第二颗豆子开始检查，直到最后一颗豆子。如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。 # 最后口袋中的豆子就是所有的豆子中最大的一颗。 下面是一个形式算法，用近似于编程语言的伪代码表示 给定：一个数列“list"，以及数列的长度"length(list)" largest = list[1] for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest 符号说明:
- = 用于表示赋值。即：右边的值被赋予给左边的变量。
- List[counter]用于表示数列中的第counter项。例如：如果counter的值是5，那么List[counter]表示数列中的第5项。
- <= 用于表示“小于或等于”。

例子二

求两个自然数的最大公约数 设两个变量 M 和 N #如果 M < N，则交换 M 和 N #M 被 N 除，得到余数 R #判断 R＝0，正确则 N 即为“最大公约数”，否则下一步 #将 N 赋值给 M，将 R 赋值给 N，重做第一步。 用“BASIC 代码”表示－－ If M < N Then Swap M,N Do While R <> 0 R = M Mod N M = N N = R Loop Print N

算法设计和分析的基本方法


- 分治法
- 动态规划
- 贪心法（亦作饕餮法）

算法的分类


- 基本算法
  - 枚举
  - 搜索
    - 深度优先搜索
    - 广度优先搜索
    - 启发式搜索
    - 遗传算法
- 数据结构的算法
- 数论与代数算法
- 计算几何的算法
  - 凸包算法
- 图论的算法
  - 哈夫曼编码
  - 树的遍历
  - 最短路径算法
  - 最小生成树算法
  - 最小树形图
  - 网络流算法
  - 匹配算法
- 动态规划
- 其他
  - 数值分析
  - 加密算法
  - 排序算法
  - 检索算法
  - 随机化算法
  - 关于并行算法，请参阅并行计算一文。

参见


- 计算机科学课程列表 ja:アルゴリズム ko:알고리즘 th:อัลกอริทึม

数据结构

算法＋数据结构＝程序
— 尼古拉斯·沃斯
数据结构（Data Structure）是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。数据结构往往同高效的检索算法和索引技术有关。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。 在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：
- 信息的表示
- 信息的处理 而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。数据的结构，直接影响算法的选择和效率。 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑。一个数据元素由若干个数据项组成。数据项是数据的不可分割的最小单位。有两类数据元素：一类是不可分割的原子型数据元素，如：整数"5"，字符 "N" 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项："年"、"月"和"日"组成，则称"出身日期"为组合项，而其它不可分割的数据项为原子项。 关键字指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。 数据对象是性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。 数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。 数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。 数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。 数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。 算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新的排序等。 数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、结构类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。 计算机中表示数据的最小单位是二进制数的一位，叫做位。我们用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。元素或结点可看成是数据元素在计算机中的映象。 一个软件系统框架应建立在数据之上，而不是建立在操作之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。 对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。 不同的数据结构其操作集不同，但下列操作必不可缺： #结构的生成； #结构的销毁； #在结构中查找满足规定条件的数据元素； #在结构中插入新的数据元素； #删除结构中已经存在的数据元素； #遍历。 抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。抽象数据类型可用以下三元组表示：（D，S，P）。D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT的定义为： ADT 抽象数据类型名 ADT 抽象数据类型名; 抽象数据类型有两个重要特性：
- 数据抽象
  - 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
- 数据封装
  - 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

常用的数据结构


- 离散结构
  - 集合
    - 并查集
    - 字典
      - 有序字典
- 线性结构
  - 线性表
    - 顺序表
    - 链表(鍵結串列）
      - 单链表
      -
- 静态单链表
      -
- 跳表 (Skip list)
      - 双链表
      - 循环链表
      -
- 单循环链表
      -
- 双循环链表
  - 散列表(哈希表或雜湊表)
  - 栈(堆疊)
  - 队列（佇列）
    - 链队列
    - 循环队列
    - 优先队列 (有时使用堆来实现)
  - 双端队列
  - 串
  - 跳跃表
- 非线性结构
  - 数组
    - 二维数组（矩阵）
      - 稀疏矩阵
  - 广义表
  - 树形结构
    - 二叉树（二元樹）
      - 哈夫曼树（最优二叉树）
      - 线索二叉树
      - 二叉排序树
      -
- 平衡二叉树
      -
  - AVL树
      -
  - 红黑树
      -
    - AA树
      -
  - 伸展树
      -
- 线段树
      - 堆
      -
- 二叉堆
      -
- 二项堆
      -
- 斐波纳契堆
      -
- 配对堆
    - 森林
    - B树
      - 2-3-4树
    - 剖析树
    - 后缀树
    - Trie
    - 四叉树 (Quadtree)
    - 八叉树 (Octree)
    - kd树
    - 生成树
      - 最小生成树
  - 图状结构（网状结构）
    - 有向图
      - 有向网 (带权有向图)
      - 有向无环图 (DAG)
      -
- AOE网 (带权有向无环图)
      -
- AOV网
    - 无向图
      - 无向网 (带权无向图)
    - 连通图
      - 强连通图
    - 完全图
    - 稀疏图
    - 稠密图
    - 表示方法
      - 邻接矩阵
      - 邻接表
      - 十字链表
      - 邻接多重表
- 其他数据结构
  - 标签联合
  - 联合
  - 框架
  - 数据库和“表”

相关条目


- 算法
- 计算机科学
- 计算机科学课程列表

参考文献


- Cliford A. Shaffer／张铭等译：数据结构与算法分析（C++版，第二版），电子工业出版社 ISBN 7-5053-7646-2/TP.4425 [http://www.china-pub.com/computers/common/info.asp?id=6469]
- 严蔚敏 吴伟民著：数据结构（C语言版），清华大学出版社 ISBN 7-302-02368-9/TP.1185 [http://www.welan.com/html/00/32100.Html] Category:数据结构 ja:データ構造 ko:자료구조 th:โครงสร้างข้อมูล

PHP

right PHP 是一种流行的开放源代码的编程语言，主要用于开发服务器端应用程序及动态网页。PHP原始的缩写是“Personal HomePage”，现在官方正式定为“PHP: Hypertext Preprocessor”的递归缩写。 著名的PHP程序有phpBB和MediaWiki等。PHP可以用于替代微软的ASP/VBScript/JScript体系、Sun微系统公司的JSP/Java体系，以及CGI/Perl等。它是一种嵌入HTML页面中的脚本语言。 PHP在Web服务器上运行。当PHP脚本被客户端请求时，被请求的程序开始执行，并把执行的结果返回给客户端的网页浏览器。发送给客户端浏览器的内容是普通的HTML文本，不包含PHP代码。这是与嵌入HTML的客户端脚本（例如JScript/VBScript等）的最主要的区别。 在有了PHP-GTK扩展的支持后，现在的PHP已经可以被用来编写--了。

发展历史

1994年，Rasmus Lerdorf首次设计出了PHP程序设计语言。 1995年6月，Rasmus Lerdorf在Usenet新闻组comp.infosystems.www.authoring.cgi上发布了PHP 1.0 声明。 1996年4月，Rasmus Lerdorf在Usenet新闻组comp.infosystems.www.authoring.cgi上发布了PHP第二版声明。 相比PHP 1 单纯的标签置换代码，PHP第二版含有了可以处理更复杂的嵌入式标签语言的解析程序。 1997年，Tel Aviv 公司的Zeev Suraski 和 Andi Gutmans 自愿重新编写了底层的解析引擎，其他很多人也自愿加入了PHP的其它部分而工作，从此PHP成为了真正意义上的开源项目。 1998年6月，PHP.net发布了PHP 3.0 声明。发布以后，用户数量才真正开始了飞涨。 2000年5月22日，PHP 4.0 发布。该版本的开发是由希望对PHP的体系结构做一些基本改变的开发者推动的，这些改变包括将语言和Web服务器之间的层次抽象化，并且加入了线程安全机制，加入了更先进的两阶段解析与执行标签解析系统。这个新的解析程序依然由Zeev Suraski 和 Andi Gutmans 编写，并且被命名为Zend Engine。

Hello World程序

下面是一个在标准输出设备上输出Hello World的简单程序，这种程序通常作为开始学习编程语言时的第一个程序：

PHP的特性

虽然PHP可以作为单独的CGI进程运行，但是目前的主流是将PHP作为Web服务器的模块来使用。一般的CGI方式运行时，每处理一个请求就要启动一个CGI进程，当请求繁忙时，这将给服务器带来繁重的负担。作为Web服务器的模块运行就可以很好地降低服务器的负担，提高处理效率。但CGI的安全性更好，由于CGI在单独的进程中运行，即便崩溃，也不会影响Web服务器，但作为模块，如果PHP崩溃，那么Web服务器也会崩溃。 PHP不是线程安全的，所以PHP的官方手册不推荐使用Apache 2.0的多线程模式。 PHP可以在Unix、Linux、Windows等多种操作系统上运行。支持的Web服务器包括常见的Apache、IIS、Netscape/iPlanet等。 PHP支持目前流行的大多数数据库应用程序，例如Infomix、InterBase、mSQL、MySQL、Oracle、PostgreSQL、Sybase、ODBC、SQLServer等。

使用PHP开发的程序


- MediaWiki — Wiki 程序
- phpBB — 论坛程序
- PmWiki — Wiki 程序
- vBulletin — 论坛程序
- WordPress — 内容管理系统
- plog — 多用户内容管理系统
- phpwind — 论坛程序

PHP-GTK扩展

PHP-GTK是面向PHP的、绑定了GTK+的一个扩展。它提供了对于GTK+类和函数的面向对象的访问，极大地简化了编写客户端跨平台图形用户界面程序的工作。

相关链接


- [http://www.php.net PHP 主页]
- [http://gtk.php.net PHP-GTK 主页]
- [http://php.freehostingguru.com PHP 完全中文手册]
- [http://www.phpe.net/articles/364.shtml PHP 安装指南]
- [http://php.freehostingguru.com/funcindex.php.php PHP 函数索引]
- [http://apmserv.s135.com/ 自动搭建Apache+PHP+MySQL平台的工具]
- [http://www.appservnetwork.com/ Apache+MySql+PHP等的Windows安裝包]

PHP反对者观点


- [http://www2.uuzone.com/blog/555080192/34691.htm 为什么PHP令人不爽（对于大型系统）]
- [http://shiningray.cnblogs.com/archive/2005/08/09/210631.html "PHP 对比 PERL"]

与PHP相关的资源


- [http://twpug.net 台湾PHP联盟]
- [http://phpv.net PHP5研究室]
- [http://www.phpe.net 超越PHP] als:PHP ja:PHP Hypertext Preprocessor ko:PHP ms:PHP th:ภาษาพีเอชพี

Perl

Perl（Practical Extraction and Report Language）是一种脚本语言。 最初的设计者为拉里·沃尔（Larry Wall），它於1987年12月18日發表。Perl借取了C、sed、awk、shell scripting以及很多其他程式語言的特性。 Perl原名pearl。在這個語言官方發表前，拉里·沃尔發現已經有個程式語言“pearl”，便改變將這個程式語言的名字改成Perl。Perl這個名字，出現了一些backronym的建議，包括充滿幽默感的“Pathologically Eclectic Rubbish Lister”。今日，“Practical Extraction and Report Language”出現了在很多有關Perl的資料裏，包括官方的man pages。它的名字第一個字母大写（Perl）時就指這個程式語言，無大写字母（perl）時就指它的直譯器。將Perl寫成“PERL”是不適當的，因為它並非一個縮寫字。 Perl具有动态语言的强大灵活的特性，并起提供了许多冗余语法，也因此获得了write-only的“美誉”，因为许多Perl程序的代码令人难以阅读。但Perl同样可以将代码书写得像Python等语言一样优雅。 Perl主要应用在Unix平台和网页中(PHP,CGI)。Perl拥有海量的模块支持，在解决问题时非常方便。CPAN是Perl模块的集中营。 Perl6正在开发中，它将会与现在的Perl版本有很大不同。 和C一樣，在Perl界，難以讀懂的程式碼大賽是個有名的活動。近似難以讀懂的程式碼，但方向不同，Perl Poetry是可以被perl編譯的詩。新的詩經通常會在[http://www.perlmonks.org/index.pl?node=Perl%20Poetry Perl Monks]網站發表。 另一個Perl hackers的有趣活動是寫JAPHs。

Perl的歷史


- 1987/10/18發表Perl 1.0
- 1994年發表Perl 5 始具有OOP的作法
- 5.8.0 版開始, Perl 具備了Unicode (萬國碼) 支援
  - 將 Big5 編碼的檔案轉成 Unicode, 祗需鍵入下列指令: perl -Mencoding=big5,STDOUT,utf8 -pe1 < file.big5 > file.utf8
  - Perl 也內附了 ``piconv, 一支完全以 Perl 寫成的字碼轉換工具程式, 用法如下: piconv -f big5 -t utf8 < file.big5 > file.utf8 piconv -f utf8 -t big5 < file.utf8 > file.big5
- 2003年發表了Perl 6

競爭對手

因為許多Perl程序的代碼難以閱讀，加上它的面向对象功能被視為不是真正的面向对象，於是很多人拿Perl和其他動態語言來比較。 最常見是比較對象是Python，有人寫了篇文章叫[http://www.garshol.priv.no/download/text/perl.html What's wrong with Perl]，指出Perl的缺點，鼓勵別人學Python。著名黑客埃里克·斯蒂芬·雷蒙寫[http://www.linuxjournal.com/article.php?sid=3882 Why Python?]，該文中一個重要的比較對象就是Perl。 Ruby的作者甚至直認他想Ruby作為Perl的後繼者。

Perl的Hello World程序

下面是一个在标准输出设备上输出Hello World的简单程序，这种程序通常作为开始学习编程语言时的第一个程序： 
#!/usr/local/bin/Perl
print "Hello, world!\n";

外部链接


- [http://www.perl.com/ Perl.com]
- [http://dmoz.org/Computers/Programming/Languages/Perl/ dmoz on Perl]
- [http://www.perl.org/ Perl.org]
- [http://www.pm.org/ Perl Mongers], 全球各地的使用者組織
- [http://www.perlmonks.org Perl Monks], 一个很活跃的Perl社区
- [http://activestate.com/ ActiveState]，Microsoft Windows上的Perl
- [http://www.cpan.org/ CPAN - Comprehensive Perl Archive Network]，Perl程式的集中地
- [http://search.cpan.org/ 搜寻CPAN]
- [http://www.perlchina.org/ 中国Perl协会]
- [http://www.perlhk.org/ 香港Perl推广组]
- [http://member.perlchina.org/ member.perlchina.org] PerlChina.org 会员中心 - 通过标签和地域聚合人
- [http://wiki.perlchina.org/ wiki.perlchina.org] PerlChina.org 的 wiki 站点，中文翻译 Category:脚本语言 ja:Perl ko:펄

C编程语言

C，是一种通用的程序设计语言，它主要用来进行系统程序设计。具有高效、灵活、功能丰富、表达力强和移植性好等的特点，在程序员中备受青睐。 C语言是由UNIX的研制者丹尼斯·里奇（Dennis Ritchie）和肯·汤普逊（Ken Thompson）于1970年研制出的B语言的基础上发展和完善起来的。C语言可以广泛应用于不同的操作系统，例如UNIX、MS-DOS、Microsoft Windows及Linux等。C语言是一种面向过程的语言，同时具有高级语言和汇编语言的优点。在C语言的基础上发展起来的有支持多种程序设计风格的C++语言，网络上广泛使用的Java、JavaScript，微软的C#等。 1983年，美国国家标准委员会（ANSI）对C语言进行了标准化，于1983年颁布了第一个C语言标准草案（83 ANSI C)，后来于1987年又颁布了另一个C语言标准草案（87 ANSI C）。最新的C语言标准是在1999年颁布并在2000年3月被ANSI采用的 C99 ，但由于未得到主流编译器厂家的支持，直到2004年C99 并未被广泛使用，增加了若干新特性后 C99 已经逐渐让C语言和C++分道扬镳。

C语言的特色


- C语言是系统程序语言。
- C语言保留了低级语言的特性，例如涉及内存的指针。
- 使用了预处理机制，使得程序里可以通过包含例如宏处理的方式来处理源程序。 C语言的不足可以由C语言发展而来的更新的编程语言改进。Cyclone语言的拥有提防对于内存错误的特性。C++和Objective C提供了用于面向对象的编程结构。Java和C#增加了面向对象的结构使得对内存的管理自动化。

C語言的主要特性


- C語言保留了低階語言的特性，例如涉及記憶體的指针。
- C語言通過參數在函數裏傳遞數值。
- 使用了預處理機制，使得程式裏可以通過包含例如巨集處理的方式來處理根源程式。
- C語言提供了一套標準庫，這些庫裏提供了十分有用的功能。 但是並不是所有的這些特性都是有效的。例如，預處理通常作爲一個獨立的程式被處理，這使得预處理的程式並不一定被完全編譯。 雖然C是高階語言，但是它同時擁有一些組合語言的特性，對其他的語言來說這是接近低階語言的特點。例如，在C語言裏，程式師可以對電腦記憶體進行管理。在默認的情況下，C語言不會對陣列的範圍進行檢查，也就是說即使陣列越界，C語言也不會作出錯誤提示。對電腦記憶體的管理使得程式员可以编出更快捷、更有效的程式，這對於設備驅動程式來說尤爲重要。但是這也使得程式容易産生令人討厭的“臭蟲”，例如緩衝器溢出錯誤。然而，這些錯誤可以由一些工具來避免。 C語言的不足可以由从C語言發展而來的更新的編程語言改進。Cyclone語言的擁有提防對於記憶體錯誤的特性。C++和Objective C提供了用於面向物件的編程結構。Java和C#增加了面向物件的結構使得對記憶體的管理自動化。 近年来，由于Java的编译技术有了极大的提高，采取许多C和C++不能采用的动态编译技术，使得Java的性能日益突出。

C语言的历史

C语言的第一次发展在1969年到1973年之间。C之所以被称为C是因为C语言的很多特性是由一种更早的被称为B语言的编程语言中发展而来的。 到了1973年，C语言已经可以用来编写Unix操作系统的内核。这是第一次用C语言来编写操作系统的内核。丹尼斯·里奇和Brian Kernighan在1978年出版了《C程序设计语言》（The C Programming Language，经常简称为“白皮书”或“K&R”）。 1980年以后，贝尔实验室使得C变得更为广泛的流行，使得C一度成为了操作系统和应用程序编程的首选。甚至到今天，它仍被广泛用于编写操作系统以及作为广泛的计算机教育的语言。但目前Java程序员的数量已经超过了C程序员和C++程序员的总和。2005年4月，C++之父称C++用户超过300万。 　　分析机构EvansData定期对开发人员展开调查，其调查结果与Stroustrup提出的C++正在扩张的说法相违背。EvansData的数据显示，以C++为工具的开发人员在整个开发界所占的比例由1998年春天的76%下降至2004年秋的46%。 Forrester最新的调查显示，C++、微软VisualBasic和Java是众多公司产品体系的首选语言。对100家公司的调查显示，C/C++、VisualBasic和Java在产品体系中的使用比例分别是59%、61%和66%。 http://tech.sina.com.cn/it/2005-04-25/1042592385.shtml http://www.yesky.com/SoftChannel/72343471356116992/20050425/1940294.shtml 而据路透社2004年6月报道，java程序员在那时就已经超过了420万，java程序员在一年内增长了120万。按最保守的估计，现在java程序员也有500万 http://news.ccidnet.com/pub/article/c1366_a125565_p1.html 1980年代晚期，布贾尼·斯特劳斯特卢普和贝尔实验室为C语言添加了面向对象的特性.这种语言成为了C++。C++现在广泛应用的在Microsoft Windows下运行的商业应用程序的编制，然而C仍然是UNIX世界的热门编程语言。

C语言的版本

K&R C

C不断的从它的第一版本进行改进。在1978年，Kernighan和里奇的《C程序设计语言》第一版出版。它介绍了下面的有关C语言版本的特性：
- struct数据类型
- long int数据类型
- unsigned int数据类型
- 把运算符=+改为+=，依次类推。因为=+使得编译器混淆。 在以后的几年里，《C程序设计语言》一直被广泛作为C语言事实上的规范。在这本书中，C语言通常被表述成“K&R C”。（第二版的包括了ANSI C标准） K&R C通常被作为C编译器所支持的最基本的C语言部分。虽然现在的编译器并不一定都完全遵循ANSI标准，但K&R C作为C语言的最低要求仍然要编程人员掌握。但是无论怎样，现在使用广泛的C语言版本都已经与K&R C相距甚远了，因为这些编译器都使用ANSI C标准。 //....

ANSI C和ISO C

1989年，C语言被ANSI标准化。（ANSI X3.159-1989）。标准化的一个目的是扩展K&R C。这个标准包括了一些新的特性。在K&R出版后，一些新的特征被“非官方”的加到C语言中。
- void函数
- 函数返回struct或union类型
- void
- 数据类型 在ANSI标准化自己的过程中，一些新的特征被加了进去。ANSI也标准了函数库。ANSI C标准被ISO（国际标准化组织）采纳成为ISO 9899。ISO的第一个版本文件在1990年出版。

C99

在ANSI标准化后，C语言的标准在一段相当的时间内都保持不变，尽管C++继续在改进。（实际上，Normative Amendment1在1995年已经开发了一个新的C语言版本。但是这个版本很少为人所知。）标准在90年代才经历了改进，这就是ISO9899:1999（1999年出版）。这个版本就是通常提及的C99。它被ANSI于2000年三月采用。 在C99中包括的特性有：
- 对编译器限制增加了，比如源程序每行要求至少支持到 4095 字节，变量名函数名的要求支持到 63 字节 (extern 要求支持到 31)
- 预处理增强了。例如：
  - 宏支持取参数 #define Macro(...) __VA_ARGS__
  - 使用宏的时候，参数如果不写，宏里用 #,## 这样的东西会扩展成空串。(以前会出错的)
  - 支持 // 行注释（这个特性实际上在C89的很多编译器上已经被支持了）
- 增加了新关键字 restrict, inline, _Complex, _Imaginary, _Bool
  - 支持 long long, long double _Complex, float _Complex 这样的类型
- 支持 <: :> <% %> %: %:%: ，等等奇怪的符号替代，D&E 里提过这个
- 支持了不定长的数组。数组的长度就可以用变量了。声明类型的时候呢,就用 int a[
- ] 这样的写法。不过考虑到效率和实现，这玩意并不是一个新类型。所以就不能用在全局里，或者 struct union 里面，如果你用了这样的东西，goto 语句就受限制了。
- 变量声明不必放在语句块的开头，for 语句提倡这么写 for(int i=0;i<100;++i) 就是说，int i 的声明放在里面，i 只在 for 里面有效。
- 当一个类似结构的东西需要临时构造的时候，可以用 (type_name) 这有点像 C++ 的构造函数
- 初始化结构的时候现在可以这样写: struct hehe[] = ; struct hehe = // 3,4 是对 .c,.d 赋值的
- 字符串里面，\u 支持 unicode 的字符
- 支持 16 进制的浮点数的描述
- 所以 printf scanf 的格式化串多支持了 ll / LL (VC6 里用的 I64) 对应新的 long long 类型。
- 浮点数的内部数据描述支持了新标准，这个可以用 #pragma 编译器指定
- 除了已经有的 __line__ __file__ 以外，又支持了一个 __func__ 可以得到当前的函数名
- 对于非常数的表达式，也允许编译器做化简
- 修改了对于 / % 处理负数上的定义，比如老的标准里 -22 / 7 = -3, -22 % 7 = -1 而现在 -22 / 7 = -4, -22 % 7 = 6
- 取消了不写函数返回类型默认就是 int 的规定
- 允许 struct 定义的最后一个数组写做 [] 不指定其长度描述
- const const int i; 将被当作 const int i; 处理
- 增加和修改了一些标准头文件, 比如定义 bool 的 定义一些标准长度的 int 的 定义复数的 定义宽字符的 有点泛型味道的数学函数 跟浮点数有关的 。 里多了一个 va_copy 可以复制 ... 的参数。 里多了个 struct tmx 对 struct tm 做了扩展
- 输入输出对宽字符还有长整数等做了相应的支持 但是各个公司对C99的支持所表现出来的兴趣不同。当GCC和其它一些商业编译器支持C99的大部分特性的时候，微软和Borland却似乎对此不感兴趣。

C语言的Hello World程序

下面是一个在标准输出设备上输出Hello World的简单程序，这种程序通常作为开始学习编程语言时的第一个程序： #include   int main(void)

进一步了解C

C语言由函数和变量组成。C的函数就像是Fortran中的子程序和函数。 在C语言中，程序从main开始执行。main函数通过调用和控制其他函数进行工作。例如上面的printf。程序员可以自己写函数，或从库中调用函数。在上面的return 0;使得main返回一个值给调用程序的外壳，表明程序已经成功运行。 一个C语言的函数由返回值、函数名、参数列表（或void表示没有返回值）和函数体组成。函数体的语法和其它的复合的语句部分是一样的。

复合语句

C语言中的复合语句的格式为： 复合语句可以使得几个语句变成一个语句。 但一般情况下，我们不推荐这样多个语句顺序书写， 因为这样会使其可读性减弱，加大代码维护难度。

条件语句

C语言有三种条件语句形式。两种是if，另一种是switch。 两种if包括： if (条件表达式) 语句； 以及 if (条件表达式) 语句； else 语句； 在条件表达式中，任何非零的值表示条件为真；如果条件不满足，程序将跳过if后面的语句，直接执行if后面的语句。但是如果if后面有else，则当条件不成立时，程序跳到else处执行。 switch通常用于对几种有明确值的条件进行控制。它要求的条件值通常是整数或字符。与switch搭配的条件转移是case。使用case后面的标值，控制程序将跳到满足条件的case处一直往下执行，直到语句结束或遇到break。通常可以使用default把其它例外的情况包含进去。如果switch语句中的条件不成立，控制程序将跳到default处执行。switch是可以嵌套的。 switch (<表达式>)

循环语句

C语言有三种形式的循环语句： do <语句> while (<表达式>); while (<表达式>) <语句>; for (<表达式1> ; <表达式2> ; <表达式3>) <语句>; 在while和do中，语句将执行到表达式的值为零时结束。在do...while语句中，循环体将至少被执行一次。这三种循环结构可以互相转化： for (e1; e2; e3) s; 相当于 e1; while (e2) 当循环条件一直为真时，将产生死循环。

跳转语句

跳转语句包括四种：goto，continue，break和return。 goto语句是无条件转移语句： goto 标记 标记必须在当前函数中定义，使用“标记：”的格式定义。程序将跳到标记处继续执行。由于goto容易产生阅读上的困难，所以应该尽量少用。 continue语句用在循环语句中，作用是结束当前一轮的循环，马上开始下一轮循环。 break语句用在循环语句或switch中，作用是结束当前循环，跳到循环体外继续执行。但是使用break只能跳出一层循环。在要跳出多重循环时，可以使用goto使得程序更为简洁。 当一个函数执行结束后要返回一个值时，使用return。return可以跟一个表达式或变量。如果return后面没有值，将执行不返回值。

在C99中运算符号

数据类型

基础数据类型

注意：以下是典型的数据位长和范围。但是编译器可能使用不同的数据位长和范围。这取决于使用的编译器。请参考具体的参考手册。 在头文件和中说明了基础数据的长度。float，double和long double的范围就是在IEEE 754标准中提及的典型数据。

数组

如果一个变量名后面跟着一个有数字的中括号，这个声明就是数组声明。字符串也是一种数组。它们以ASCII的NUL作为数组的结束。 例如： :int myvector [100]; :char mystring [80]; :float mymatrix [3] [2] = :int notfull [3][3] = (
- ) :char lexicon [10000] [300] ; /
- 共一万个最大长度为300的字符数组。
- / :int a[3][4]; 上面最后一个例子创建了一个数组，但也可以把它看成是一个多维数组。注意数组的下标从0开始。这个数组的结构如下：
例子(
- )创建了一个3
- 3的二维数组,初始化时有些元素并未赋值.如下: :1 0 0 :1 2 3 :4 5 0
为0的位置的数值是随机的.

指针

如果一个变量声明时在前面使用
- 号，表明这个变量是一个指针。 例如： :int
- pi; /
- 指向整型数据的指针
- / :int
- api[3]; /
- 由指向整型数据的指针构成的数组，长度为3
- / :char
  - argv; /
- 指向一个字符指针的指针
- / 储存在指针中的地址所指向的数值在程序中可以由
- 读取。例如，在第一个例子中，
- pi是一个整型数据。这叫做引用一个指针。 另一个运算符&，叫做取地址运算符，它将返回一个变量、数组或函数的存储地址。因此，下面的例子： :int i,
- pi; /
- int and pointer to int
- / :pi = &i; i和
- pi在程序中可以相互交替使用，直到pi被改变成指向另一个变量的指针。

字符串

要使用字符串并不需要引用库，但是C标准库确实包含了一些用于对字符串进行操作的函数，使得它们看起来就像字符串而不是数组。使用这些函数需要引用头文件。
- strcat(dest, source) - 连接两个字符串，把source加到dest末尾。
- strchr(s, c) -在字符串c中找出字符s第一次出现的位置。当没有找到时，返回Null。
- strcmp(a, b) - 比较字符串a和b的大小。如果两个字符串相同，返回0；如果a>b，返回正数；如果a，返回负数。
- <- 把source中的n个字符追加到dest后面。null后面的值将不会被添加。
- strncmp(a, b, n) - 比较字符串a和b中n个字符的大小。如果两个字符串相同，返回0；如果a>b，返回正数；如果a，返回负数。
- strncpy(dest, source, n) - 把字符串source拷贝到字符串dest中。（最多拷贝n个）
- strrchr(s, c) - 在s中查找最后一次出现c的位置。返回这个位置。如果找不到，返回null。

文件输入/输出

在C语言中，输入和输出是经由标准库中的一组函数来实现的。在ANSI/ISO C中，这些函数被定义在头文件中。

标准输入/输出

有三个标准输入/输出是预定义的：
- stdin 标准输入
- stdout 标准输出
- stderr 输入输出错误 这些定义在运行过程中是自动的打开和关闭的，所以它们并不需要进行显式定义。 下面的这个例子显示了一个过滤程序（filter program）是怎样构成的。 #include   int main()

传递命令行参数

在命令行赋予程序的参数将通过在main()函数中定义一个整型参数（int）和一个指向字符指针的指针型参数（char
  - ）来实现，前者传递命令行参数的个数，后者传递命令行参数内容。习惯上将这两个参数分别命名为argc和argv。程序文件名被作为第一个命令行参数。 对于下列程序： #include   int main(int argc, char
  - argv) 输入命令（假设该程序生成C:\TC\a.exe）： a one two three 则会得到下面的输出结果： 
0:C:\TC\A.EXE
1:one
2:two
3:three
C语言的标准库

以下列出由C语言提供的标准函数库,函数库通过#include进行引用。 在C89标准中:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 在95年的修正版中
-
-
- 在C99中增加了六个函数库
-
-
-
-
-
-

C语言的保留关键字

参见


- 计算机科学课程列表 ja:C言語 ko:C 프로그래밍 언어 ms:Bahasa pengaturcaraan C th:ภาษาซี

操作系统

操作系统（Operating System，简称OS） 是计算机系统中负责支撑应用程序运行环境以及用户操作环境的系统软件，同时也是计算机系统的核心与基石。 它的职责通常(但并非绝对)包括对硬件的直接监管、对各种计算资源(如内存、处理器时间等)的管理、以及提供诸如作业管理之类的面向应用程序的服务等等。 操作系统的理论是计算机科学中一个古老而又活跃的分支，而操作系统的设计与实现则是软件工业的基础与核心。

今天的操作系统　

到2005年6月为止，用于通用计算机上的分布的操作系统主要两个家族：类Unix家族和微软Windows家族。 主机系统和嵌入式操作系统使用多样的系统，并且很多和Windows和Unix都没有直接的联系。 类Unix家族包括多个组织的操作系统，其中有几个主要的子类包括System V，BSD和Linux。这里'Unix'是一个商标，开发组织允许使用操作系统在一个定义前提下自由地开发。这名字是通用大型设置操作系统类似组织Unix。Unix系统运行在从巨型机到嵌入式系统的多种机器架构上。Unix 主要使用于重要的商务服务器系统以及学院和工程环境中的工作站之上。和Unix不同，自由软件比如Linux 和 BSD 逐步开始流行，并且开始进入桌面操作系统领域。和一些Unix操作系统不同，像惠普公司的HPUX和IBM公司的AIX是设计仅运行在客户购买的设备上，其中有一些特殊的（比如SUN公司的Solaris）可以运行在客户购买设备和基于工业标准的PC上。APPLE公司的Mac OS X是一个BSD特例，以取代早期小型市场上的苹果公司Mac OS，众多流行的Unix操作系统正在走向一体。 微软公司的Windows操作系统家族起源于早期的IBM PC环境中的MS-DOS，现在版本是基于新的Windows NT内核，第一次是在OS/2中制定。和Unix不同，Windows只能运行在32位和64位的x86 CPU（如Intel或者AMD的芯片）上，尽管早期有版本运行于DEC Alpha，MIPS 和 PowerPC体系结构。今天Windows是一个流行的操作系统，在全球桌面市场中占有90%左右的份额，同时在中低端服务器市场也有广泛的应用，如Web服务器和数据库服务器。 译者提示：NT是 New Technology 而不是 Network Technology，这点很多人都出现过误解. 大型机系统，比如IBM公司的Z/OS，和嵌入式操作系统比如QNX , eCOs 和 PalmOS都是和Unix和Windows无关的操作系统，而Windows CE ,Windows NT Embedded 4.0 和 Windows XP Embedded 都是和Windows相关的。 老的操作系统停留在市场包括类似IBM Windows的OS/2;来自惠普的VMS(以前的DEC);苹果公司的Mac OS操作系统，非Unix先驱苹果公司Mac OS X；和AmigaOS，第一个图形用户界面的操作系统，包括对于普通用户的高级的多媒体能力.

功能

操作系统位于底层硬件与用户之间，是两者沟通的桥梁。用户可以通过操作系统的用户界面，输入命令。操作系统则对命令进行解释，驱动硬件设备，实现用户要求。

结构

操作系统理论研究者有时把操作系统分成四大部分：
- 驱动程序 - 最底层的、直接控制和监视各类硬件的部分，它们的职责是隐藏硬件的具体细节，并向其他部分提供一个抽象的、通用的接口。
- 内核 - 操作系统之最核心部分，通常运行在最高特权级，负责提供基础性、结构性的功能。
- 支承库 - （亦作“接口库”）是一系列特殊的程序库，它们指责在于把系统所提供的基本服务包装成应用程序所能够使用的编程接口（API），是最靠近应用程序的部分。例如，GNU C运行期库就属于此类，它把各种操作系统的内部编程接口包装成ANSI C和POSIX编程接口的形式。
- 外围 - 所谓外围，是指操作系统中除以上三类以外的所有其他部分，通常是用于提供特定高级服务的部件。例如，在微内核结构中，大部分系统服务，以及UNIX/Linux中各种守护进程都通常被划归此列。 当然，本节所提出的四部结构观也绝非放之四海皆准。 例如，在早期的微软视窗操作系统中，各部分耦合程度很深，难以区分彼此。 而在使用外核结构的操作系统中，则根本没有驱动程序的概念。 因而，本节的讨论只适用于一般情况，具体特例需具体分析。 操作系统中四大部分的不同布局，也就形成了几种整体结构的分野。 常见的结构包括：简单结构、层结构、微内核结构、垂直结构、和虚拟机(虛擬機器Virtual Machine)结构。

简单结构

很多商用操作系统都没有清晰的整体结构，系统中的各个部件混杂在一起。 这些操作系统往往是由很小的实验性的项目逐步演化而来的，因而宏观结构非常模糊。 MS-DOS就是一个很好的例子，在设计之初，MS-DOS的设计目标是在比较有限的硬件资源上运行比较有限的应用程序，开发人员很可能都没有预料到它日后在市场上的巨大成功，因而模块之间的相对独立性几乎被忽略。 相似的情况也发生在UNIX家族之中。 早期的UNIX因为受限于当时的硬件能力，也一直都是采用非常简单的、 随着UNIX的不断发展这样结构也很快成为了UNIX演进的瓶颈。 其他采用这种简单结构的操作系统还包括PalmOS 5以前的PalmOS，以及很多其他的小型的嵌入式操作系统。

层结构

微内核结构

垂直结构

虚拟机结构

分类

内核结构

:主条目: 内核 内核是操作系统最核心最基础的构件，因而，内核结构往往对操作系统的外部特性以及应用领域有着一定程度的影响。 尽管随着理论和实践的不断演进，操作系统高层特性与内核结构之间的耦合有日趋缩小之势，但习惯上，内核结构仍然是操作系统分类之常用标准。 内核的结构可以分为 单内核(monolithic kernel)， 微内核(microkernel)， 超微内核(nanokernel)， 以及外核(exokernel)等。 详情参见操作系统内核。 单内核结构是操作系统中各核心部件杂然混居的形态，该结构于二十世纪六十年代（亦有二十世纪五十年代初之说，尚存争议），历史最长，是操作系统内核与外围分离时的最初形态。 微内核结构是二十世纪八十年代产生出来的较新的内核结构，强调结构性部件与功能性部件的分离。 二十世纪末，基于微内核结构，理论界中又发展出了超微内核与外内核等多种结构。 尽管自二十世纪八十年代起，大部分理论研究都集中在以微内核为首的“新兴”结构之上，然而，在应用领域之中，以单内核结构为基础的操作系统却一直占据着主导地位。 在众多常用操作系统之中，除了QNX和基于Mach的UNIX等个别系统外，几乎全部采用单内核结构，例如Linux，大部分的Unix，以及Windows（微软声称Windows NT是基于改良的微内核架构的，尽管理论界对此存有异议）。 微内核和超微内核结构主要用于研究性操作系统，还有一些嵌入式系统使用外核。 基于单内核的操作系统通常有着较长的历史渊源。 例如，绝大部分UNIX的家族史都可上溯至二十世纪六十年代。 该类操作系统多数有着相对古老的设计和实现 （例如某些UNIX中存在着大量七、八十年代的代码）。 另外，往往在性能方面略优于同一应用领域中采用其他内核结构的操作系统 （但通常认为此种性能优势不能完全归功于单内核结构）。

通用与专用、嵌入式

去

实时与非实时

“实时操作系统”（Real Time OS）泛指所有据有一定实时资源调度以及通讯能力的操作系统。而所谓“实时”，不同语境中往往有着非常不同的意义。某些时候仅仅用作“高性能”的同义词。但在操作系统理论中“实时性”所指的通常是特定操作所消耗的时间（以及空间）的上限是可预知的。比如，如果说某个操作系统提供实时内存分配操作，那也就是说一个内存分配操作所用时间（及空间）无论如何也不会超出操作系统所承诺的上限。实时性在某些领域非常重要，比如在工业控制、医疗器材、影音频合成、以及军事领域，实时性都是无可或缺的特性。 常用实时操作系统有QNX、VxWorks、RTLinux等等，而Linux、多数UNIX、以及多数Windows家族成员等都属于非实时操作系统。操作系统整体的实时性通常依仗内核的实时能力，但有时也可在非实时内核上建立实时操作系统，很多在Windows上建立的实时操作系统就属于此类。 在POSIX标准中专有一系用于规范实时操作系统的API，其中包括POSIX.4、POSIX.4a、POSIX.4b（合称POSIX.4） 以及POSIX.13等等。符合POSIX.4的操作系统通常被认可为实时操作系统（但实时操作系统并不需要符合POSIX.4标准）。

多任务与单任务

16位、32位、64位

所谓16位、32位、64位等术语有时指总线宽度，有时指指令宽度(在定长指令集中)，而在操作系统理论中主要是指内存寻址的宽度。如果内存的寻址宽度是16位，那么每一个内存地址可以用16个二进制位来表示，也就是说可以在64KB的范围内寻址。同样道理32位的宽度对应4GB的寻址范围，64位的宽度对应16 Exabyte的寻址范围。内存寻址范围并非仅仅是对操作系统而言的，其他类型的软件的设计有时也会被寻址范围而影响。但是在操作系统的设计与实现中，寻址范围却有着更为重要的意义。 在早期的16位操作系统中，由于64KB的寻址范围太小，大都都采用“段”加“线性地址”的二维平面地址空间的设计。分配内存时通常需要考虑“段置换”的问题，同时，应用程序所能够使用的地址空间也往往有比较小的上限。 在32位操作系统中， 4GB的寻址范围对于一般应用程序来说是绰绰有余的， 因而，通常使用一维的线性地址空间，而不使用“段”。

参看


- 操作系统内核
- 实时操作系统-分时系统-多任务-嵌入式系统-单一用户-多用户
- 对称多处理并行计算(SMP)-集群(Cluster)-分布式计算
- 操作系统列表
- 64位操作系统
- 计算机科学课程列表

部分操作系统


- FreeBSD
- MS-DOS
- GNU/Linux
- Mac OS
- Windows
- Windows NT
- UNIX
- 其他操作系统

外部链接


- als:Betriebssystem ja:オペレーティングシステム ko:운영 체제 ms:Sistem pengoperasian simple:Operating system th:ระบบปฏิบัติการ zh-min-nan:Chok-gia̍p hē-thóng

编译器

编译器，是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能识别，运行的低级机器语言的程序。编译器将源程序（Source program）作为输入，翻译产生使用目标语言（Target language）的等价程序。源程序一般为高级语言（High-level language），如Pascal，C++等，而目标语言则是汇编语言或目标机器的目标代码（Object code），有时也称作机器代码（Machine code）。 一个现代编译器的主要工作流程如下：
- 源程序（source code）→预处理器（preprocessor）→编译器（compiler）→汇编程序（assembler）→目标程序（object code）→连接器（链接器，Linker）→可执行程序（executables]）

工作原理

翻译是从源代码（通常为高级语言）到能直接被计算机或虚拟机执行的目标代码（通常为低级语言或机器言）。然而，也存在从低级语言到高级语言的编译器，这类编译器中用来从由高级语言生成的低级语言代码重新生成高级语言代码的又被叫做反编译器。也有从一种高级语言生成另一种高级语言的编译器，或者生成一种需要进一步处理的的中间代码的编译器（又叫级联）。 典型的编译器输出是由包含入口点的名字和地址以及外部调用（到不在这个目标文件中的函数调用）的机器代码所组成的目标文件。一组目标文件，不必是同一编译器产生，但使用的编译器必需采用同样的输出格式，可以链接在一起并生成可以由用户直接执行的可执行程序。

编译器种类

编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高级语言作为输入，输出也是高级语言的编译器。例如: