C语言详解笔记

C 语言详解(Problem Solving and Program Design in C)笔记摘要前言本书主要讲述两大部分：程序设计思想的介绍和C语言语法。第一章 C 概述C是一种高级程序设计语言，它是由Dennis Ritche于1972年在AT&T Bell实验室开 发出来的，起初是作为在UNIX操作系统下编程的工具而设计的，它的最初使用者就是理 解操作系统和底层机器复杂性的程序员。1.1 C语言要素1.1.1 预处理指令一般程序包括两部分：预处理指令和主函数。预处理指令(prepeocessor directive)是为 C预处理器(preprocessor)提供指令的命令，预处理器的工作是在C程序编译前修改程序 文本。常用的指令： # include 和 # define。每个C实现中都包含了一些实用函数和符号的集合，称之为库。C的ANSI (American National Standard Institute,美国国家标准学会)标准要求在每个C实现中提供特定的标准库。 例如：#include vstdio.h,它使预处理器在编译前将标准头文件的定义插入到程序中#define K 1.069,将常量宏(constant macro) K与1.069关联起来，该指令让预处理器在编译开始之 前，用1.069代替C程序文本中的每一个K。在执行中C程序不能改变用常量宏定义的数 值。1.1.2 主函数每个 C 程序都有一个主函数，其余行组成了函数体，函数体包含两部分：声明和可执 行语句。声明(declaration):程序的一部分，告知编译器程序中的存储单元名称。可执行语 句(executable stament):被转换为机器语言指令，并由计算机执行的程序行。Int main( void)函数体Int表明函数执行完成时向操作系统返回一个整数值，void表示函数执行前不向操作系 统接受数据。1.1.3 保留字保留字(reserved word) :C中有特殊含义的字。例如：int void double return01.1.4 标准标识符标准标识符(standard identifier)拥有特殊含义的字，但程序员可以重新定义(但不建 议重新定义)。1.1.5 用户自己定义的标识符遵从以下原则：1. 标识符只能由字母、数字和下划线组成。2. 标识符不能以数字开头。3. C保留字不能用作标识符。4. 在C标准库中定义的标识符不能被重新定义。1.1.6 大小写字母C 编译器区分大小写。1.1.7 编程风格为用户定义的标识符选择一个有意义的名称，这样标识符在使用时就比较容易理解。如 果一个标识符由两个以上的单词组成，那么他们之间用下划线连接。为了避免混淆不适用名 称相似的标识符，尤其应该避免选择两个仅有大小写字母区别的标识符，也不要用两个仅有 下划线区别的标识符。1.2 变量声明和数据类型1.2.1 变量声明变量声明将程序中使用的所有变量名告知编译器，同时告诉编译器，在每个变量中将会 存储什么类型的信息以及信息在内存中如何表示。1.2.2 数据类型1. int 型表示的数值范围从-32767 到+32767。2. double 型1.23e5表示1.23乘以10的5次幕。3. char 型Char 型可以表示数字、字母和专用符号。1.3 可执行语句函数中的可执行语句跟在声明之后，他们用于编写算法及其细化的C语句。C编译器 将可执行语句翻译为机器语言。当程序运行时，计算机会执行语句的机器语言版本。1.3.3 输入/输出操作和函数输入函数scanf和输出函数printf, printf (格式字符串，输出列表)，举个例子： printf(“that equals %f kilometers.n,kms), %f 是占位符。1. 多个占位符 格式字符串可以拥有多个占位符。如果调用printf的输出列表有多个变量,那么格式字符串将包含同样数量的占位符。C以从左到右的顺序对占位符和变量进 行 匹 配 。 举 个 例 子 ： printf ( ”Hi%C%C%C _ your ageis %dn”,letter_1,letter_2,letter_3,age)；2. scanf函数 格式：scanf(“c%d”,&letter-1,&age);在程序执行时，函数将用户在键盘 上输入的数据复制到内存中。格式字符串中的占位符对应输入列表中的变量，变量前面 有取地址符号&。占位符的顺序必须与变量列表中的变量顺序一致。1.3.4 return(0)语句将控制由程序交给操纵系统。小括号中的0被认为是函数main的执行结果，该值表明 执行的程序没有错误。1.4 算术表达式1.4.1 运算符/和%当操作数是两个正整数时， / 计算除法运算的整数部分；当操作数是 double 型时， /计 算运算的真实值。 %取余运算。1.4.2 混合类型赋值语句同时拥有 int 型和 double 型操作数的表达式是混合类型表达式，其结果的数据类型是 double 型。将 double 型赋给 int 型时，小数部分会丢失。1.4.3 强制类型转换 将希望的数据类型放在表达式前面的括号内，从而转换表达式的类型。要注意整数除法的使 用。1.4.4 多个运算符的表达式一元运算符：拥有一个操作数的运算符；二元运算符：需要两个运算符。1.5 在程序输出中格式化数值1.5.1 格式化 int 型%数字d,数字表示输出整数所用的列数。1.5.2 格式化 double 型%m.nf其中m表示整个域宽的数，包括小数点在内，n是希望的小数位数，以四舍五入的 方式舍去。在格式字符串占位符中忽略总的域宽是合法的，例如：格式为%3.2d 3.14159=3.14 采用%.nf的格式可以消除数据前面的前导空白。1.6 交互模式、批处理模式和数据文件交互模式(interactive mode)：用户通过输入(键入)数据来响应提示符的一种程序运行模 式。批处理模式(batch mode):程序从预先准备好的数据文件中得到数据的一种程序运行模式。第二章 函数的自顶向下设计自顶向下设计(top_down design):将问题分解为主要的子问题，然后解决子问题以得到最 初问题的解决方案。2.1 无参函数2.1.1 函数原型Ftype fname (void)ftype表示函数的返回值类型，void为无返回值；fname表示函数名。2.1.2 函数定义写函数体 几个不常用的数学函数：Ceil(x):返回不小于x的最小整数fabs(x)：返回double型参数的绝对值Floor(x)：返回不大于x的最大整数pow(x,y)：返回x的y次幕2.2 带输入参数的函数每当执行函数调用语句时，系统就会为该函数分配内存空间作为数据存储空间。包含在函数 数据域中的是用于存储形参和任何在函数中声明的局部变量的存储单元。当函数终止时，函 数数据域就丢失了，当函数再次被调用时会重新产生新的数据域。第三章 选择结构：if语句和switch语句3.1 控制结构控制结构：单个指令结合成的具有一个入口点和一个出口点的逻辑单元。3.1.1 逻辑运算符&：与| ：或 ！：非 C 语言认为任何非零值为 true.3.1.2 运算符优先级 从高到低：函数调用!、+、-、&（一元运算符）* / % + - = = != & | =3.1.3 比较字符 先比较字符长度，长度相同看第一个字符，第一个字符相同再看第二个；3.2 if 语句 一个选项形式：if （条件）语句；两个选项形式： if （条件）语句；else语句；3.3 具有复合语句的 if 语句 也就是由多条执行语句，此时要有大括号； 内聚函数：执行单个操纵的函数。3.4 使用常量宏来增强程序的可读性和可维护性。3.5 if 嵌套格式：if（条件1）语句 1；else if（条件 2）语句 2；else if（条件 n）语句 n;else语句；3.6 swtich 语句格式：swtich（条件表达式） case 1:语句 1； break;case 2:语句 12； break;case n:语句 n break;default:语句 n；第四章 循环 暂跳过第五章 模块化编程当函数调用执行时，计算机将在该函数数据区为每一个形式参数分配内存空间，每个实参的 值都存储在其对应的形参的内存空间中，并且函数体可以对该值进行操作。存根：不是所有函数都能够在同一时间完成，存根的使用使我们能够调试和测试主程序流程 和已经完成的部分。单元测试：对单个函数进行测试。第六章 简单数据类型强制类型转换：例如：有int型的dl=4.nl=5，有double型的frac,表达式frac=dl/nl,先计算dl/nl的值为0,然后再将结果转化成double型为0.0,而表达式frac= (double) dl/(double)nl，先将dl 转换为 4.0， nl 转换为 5.0再进行计算，结果为 0.8。枚举类型：程序员在类型声明中制定列表值的一种数据类型。 /*枚举声明的格式如下： */typedef enummonday,tuesday,wednesday,thursday,friday,saturday,sundayday_t;枚举常量Monday表示为整数0,常量Tuesday表示为1等等。注意：只有标识符可以出现在这种类型的值的列表中。注意不要在其他类型中再次使用这些 标识符。第七章 数组数据结构(data structure):在同一个名称下存储的相关数据项的组合；数组(array)：相同类型数据项的集合；7.1 数组声明和引用声明格式：元素类型 anamesize;元素类型anamesize=初始化列表；数组引用：aname下标,下标可以是int型任意表达式。7.2 数组参数7.2.1 形参数组：数组位于子函数的参数列表中 当一个没有下标的数组名出现在函数调用的实参列表中时 实际存储在函数相应的形参中的 是数组元素的起始地 。例如： void fill_array(int list,int n,int in_value) ,实际调用函数fill_array()时，形参list实际存储了实参数组的首地址，所以这样调用函数也是正确的： fill_array(&x0,10,l),表示给10个元素的数组x的每个元素赋值为1。7.2.1 数组作为输入参数在形参数组声明时加上限定词const用于通知C编译器该数组只是函数的一个输入，函数 不能修改该数组。例如：int get_max(const int list,int n)，表示找到用n个元素数组中的最大 元素。7.2.3 返回数组结果例如： void add_arrays(const double ar1,const double ar2,double arson,int n)int n;for(i=0;ivn;i+) arsumi=ar1i+ari;，调用函数 add_arrays(x,y,x_plus_y,n)仔细观察会发现，调用add_arrays时,在访问输入参数数组x和y,以及访问输出数组x_plus_y 之间的表示方法上没有不同。具体地说，不需要在输出数组阐述名前面加上&运算符。前面 讨论过,C语言总是将数组元素首地址存储在相应的形参中，以便将整个数组作为阐述传递。 由于输出参数arsum在声明时没有带const限定词，因此函数add_arrays会自动拥有存取和 改变相应参数组的权限。7.2.4 栈栈是一个只有顶端元素可以被访问的数据结构。出栈(pop)：从栈中移走顶端元素。压栈 (push)，在栈中插入一个新元素。7.3 数组搜索与数组排序 略第八章 字符串8.1 字符串基础8.1.1 声明并初始化字符串字符串时作为数组实现的，因此声明字符串变量和声明 char 型数组一样。例如： char string_var20,声明了一个可以容纳0到29个字符长的字符串，其中一位被空字符0占据， 空字符标记字符串结束。8.1.2使用printf和scanf进行输入和输出例如：printf(“*%8s*%3s*n”,short”,strings)，第一个字符串在一个 8 列字段右对齐 显示。第二个字符串比指定的字段宽度长，因此字段被扩展到刚好容纳该字符串而没有填充 空白。要想左对齐，在占位符前面加上“-”号。Scanf使用注意，为字符串数组输入数据时，由于本身传递的就是字符串数组的首地址，所 以无需加取地址符号。8.2 字符串库函数8.2.1 字符串赋值函数strcpy将第二个参数对应的字符串复制到第一个参数。函数strncpy()可以指定赋值字符 的个数。8.2.2 其他函数Strcat ()将第二个参数追加到第一个参数的末尾。Strcmp()按字母顺序比较s1和s2：如果s1超前s2返回负数(s1中字母在字母顺序表中排 在 s2 的前面)，相等返回零，否则返回正数。Strlen() 返回字符串的长度8.3 较长的字符串：拼接和整行输入8.3.1 拼接字符串库函数strcat和strncat将第二个字符串参数的全部或部分添加到第一个字符串参数之 后，从而改变第一个参数。8.3.2 字符和字符串注意区分字符a和字符串” a”。8.3.3 输入一个完整的行函数fgets()接受三个参数一一输出字符串参数、将要存储的最大的字符数和数据源文件指 针。函数fgets不会从数据文件中读取超过n-1个字符，并且存储的最终字符总是“0”。但 是，最后一个字符前一个字符不一定是“n”。8.4 字符串比较函数strcmp(strl,str2),比较两个字符串，最从下面两条原则：1. 如果str1,str2前n个字符匹配并且str1n和 str2n是第一对不匹配的字符，如果且 str1nvstr2n,那么strl小于str2，函数返回-1，反之返回+1，如果两个字符串各个 字符相同，那么返回 0.2. 如果str1比str2段，并且str1所有字符与str2的对应字符相同，那么str1vstr2。8.5 指针数组声明方法：数据类型 *数组名称数组大小8.6 字符操作C提供了字符输入输出程序作为stdio库的一部分，并且还在库中提供了用于字母分析和转 换的扩展函数集合，这个哭通过包含头文#引用。8.6.1 字符输入输出Stdio库包含了一个名为getchar()的程序，它用于从标准输入源获得下一个字符，该标准输 入源和scanf用的输入源一样。Getchar()不接受任何参数并返回输入的字符作为结果。实际上getchar()返回值的类型是into8.6.2 字符分析和转换Isalpha()参数是不是字母表中的一个字母Isdigit()参数是不是一个数字Islower()参数是不是一个小写字母Isupper()参数是不是一个大写字母Ispunct()参数是不是一个标点符号Isspace()参数是不是空格、执行或制表符等空白字Tolower()大写字母转换成小写字母Toupper()小写字母转换成大写字母结果为真时返回非零值，结果为假时返回0。9 递归(recursive) 函数调用自身称为递归。10 结构体和共同体10.1 用户自定义结构体类型数据库是存储在计算机内存或硬盘文件中的信息集合，可以细分为记录10.1.1 结构体类型定义语法： typedef strcutType1 id_list1;Type2 id_list2;Typen in_listn; struct_type;为了避免混淆，自定义结构体的名字以_t结束。Typedef语句本身不分配内存，为了给结构化的数据对象分配存储空间需要声明变量。 分层结构体(hierarchical structure)：成员是机构体类型的结构体。10.1.2 操作结构化数据对象的单个成员 可以通过直接成员选择运算符来引用一个结构体的成员。直接成员选择运算符 (direct component selection operator) 为实现对成员的引用，介于结构类型变量和成员之间的句点符 号。运算符的优先级与结合性优先级符号运算符名称结合性最咼A f().下标、函数调用、成员运算符左+ -自加自减的后缀形式左+ ! + & *自加自减的前缀形式、逻辑非、一兀正负、取 地址、指针运算符右(类型名)强值类型转换右* / %乘法、除法、取余左+ -二元关系运算符加减左 =关系运算符左1r=!=相等性、不等性运算符左&逻辑与左II逻辑或左最低=+= -= *= /= %=赋值运算符右10.1.3 操作整个结构体 整个结构体可以直接进行赋值操作。10.2 结构体类型数据作为输入/输出参数 当结构体变量作为输入参数传递给一个函数时，结构体所有成员的值均复制给函数相应形参 的成员；当这样的变量用作输出参数时，必须使用取地址运算符。例如：Void print_planet(planet_t pl)Printf( “%sn,pl.name);Printf(“Equatorial diameter: %.0f kmn”,pl.diameter);也可以定义指向结构体的指针,例如:planet_t *plnp;plnp为指向结构的指针，可以利用(*plnp). 成员变量 来访问结构体的数据成员。也可以利用间接成员选择运算符-来访问结构体的成员变量,例如: plnp-name10.3 返回值为结构体类型的函数C 处理结构体的方法和处理简单数据类型的机制非常一致,而与处理数组的方式大大不同。 指的是传递参数时直接传递结构体,不用加取地址符。10.4 结构体数组数组的组成元素为结构体。声明方式为:结构体名称 数组名称元素个数；注意:结构体 数组作为出入参数或者返回值时,传递的还应该是指针。10.5 共同体共同体(union)： 一种数据结构，所有成员共用一块内存，允许把一块内存解释成多种方式。定义方式：typedef union变量类型 变量名；变量类型 变量名； 共同体名称；声明共同体以后，当前只有一个成员变量有效，分配内存空间的大小由共同体中最大的成员 决定。第 11 章 文本文件和二进制文件11.1 输入输出文件C 可以处理两种文件：文本文件和二进制文件。文本文件是在辅助存储器(例如磁盘)中保 存的一个已命名的字符集合。为标记文本文件结束，计算机会在文件的最后一个字符之后放 置一个特殊的文件结束符标记为EOF。11.1.1 键盘和屏幕作为文本流Stdi n：指向键盘输入流的系统文件指针Stdout、stderr:指向屏幕输出流的系统文件指针。转义序列W换行t制表f换页它回车W 退格C中的用表示11.1.2 printf 输出占位符说明%O将整数转换为八进制输出%X将整数转换为十六进制输出%e/E科学技术法表示的小数输出一个号符号每个占位符都可以与一个数值域宽结合，用于指定该数值显示时所占据的最小列数。如果数 值为正，那么要显示的数值在该域中是右对齐；如果数值为负值，那么要显示的数值在该域 中是左对齐。11.1.3 文件指针变量 将一个非标准的文本文件用于输入和输出之前，必须声明一个文件指针变量，并给它一个值。系统必须在允许存取之前准备好输入或输出的文件。文件指针变量的声明和初始化如下：FILE *infilep;FILE *outfilep;Infilep=fopen(“b:data.txt”,”r”); Outfilep=fopen(“b:results.txt”,”w”);文件指针是F ILE结构类型的地址，它包含了存取由f open打开的文件的必要信息, 而且必须存储在FILE*类型的变量中。空指针：值为NULL的指针。11.1.4 获取文件指针参数的函数比较标准文件的I/O与用户定义的文件指针的I/O行存取stdin和stdout的函数可以存取任何文本文件的函数1Scanf(“ d, &num);Fscanf(infilep,%d, &nu m);2Printf(“Number=%dn” ,num);Fprintf(outfilep,Number=%dn ,num);3Ch=getchar();Ch=getc(infilep);4Putchar(ch);Putc(ch,outfilep);11.1.5 关闭文件当程序不再使用一个文件时，应当通过调用带有文件指针的库函数fclose关闭该文件。11.2 二进制文件 当使用文本文件存储数据时，程序必须花费相当多的精力将输入文件中的字符流转换为二进 制整数、double型的尾数和指数，以及字符串，这是它们在内存中的表示形式。为了将数据 存储在一个输出文本文件中，程序还必须在一次地花费时间将内部数据转换为字符流。 Sizeof :确定存储某个数据类型所需字节数的运算符。注意：在一台计算机上产生的二进制文件在另一种型号的计算机上几乎是不可读的；使用 fwrite 产生的二进制文件必须使用 fread 读取，使用 fprintf 产生的文本文件必须使用 fscanf 这样的文本文件输入函数读取。关于文件操作的几点注意：1. 处理文件之前先声明文件指针变量；2. fscanf fprintf getc putc 只用于文本 I/O，而函数 fread 和fwtite只用 于二进制文件；3. 使用文件名的唯一文件操作是调用f open；第十二章 大型程序设计12.1 使用抽象处理复杂问题12.1.1 过程抽象：主函数由一系列函数调用组成，每个函数分别实现的编程技术。强大的函 数库的存在对于降低大型系统的复杂性非常有益。一旦一个函数的目标和参数表明确了，这 个函数可以被所有程序员共享，而每个程序员不必关心程序实现的具体细节。12.1.2 数据抽象：通常我们只关心数据对象的类型和在这些数据对象上执行的操作，而不必 过多关心数据对象是如何表示和存储在内存当中的。数据抽象是指将数据对象的逻辑视图 (存储的内容)与物理视图(信息如何存储)分开。12.1.3 信息隐藏 在设计顶层，设计者将重点放在如何使用数据对象和运算符上；在设计的底层，设计者解决 实现细节。防止高层模块直接访问底层模块的实现细节的过程称为信息隐藏。12.1.4 可重用代码主要是封装的概念(encapsulate),将数据对象及其运算符作为一个单元进行包装。12.2 个人库：头文件使用C语言预处理指令#include使得个人库也称为可利用的库。产生个人库必须先产生头文件包含关于一个库的所有信息的文本文件，头文件常见内容包括：1. 总结库效用的注释块(就是注释说明)；2. 常量宏定义；3. 类型定义(比如说结构体)；4.说明每个库函数目的的块注释和如下的函数声明格式：extern prototype。12.3 个人库：实现文件头文件和实现文件是个人库中两个基本的源文件。头文件描述库函数做什么，而实现文件给 出函数如何完成。12.4 五种存储类12.4.1 auto 存储类形参和函数的局部变量属于auto存储类，在函数调用时自动分配存储空间到栈上，在函数 返回时释放存储空间。13.4.2 extern 存储类这意味着他们对于连接器是可见的，编译器为了翻译函数调用，需要知道有关函数的重要信 息：它的返回类型、它有多少个参数、以及参数的数据类型，语句 extern prototype 的目的 就是提供这类信息。该语句不产生extern存储类的函数，它仅仅通知编译器存在这样的函数, 并告知编译器连接器去哪里找到它。12.4.3 全局变量 全局变量的作用域从变量声明处一直到源文件结束(除非是在函数中将同样的名称声明为形 参或局部变量)，可由程序中的多个程序访问 。12.4.4 static 类型 在程序执行之前只分配一次存储空间的变量的存储类，知道整个程序终止以前，该空间始终 不会被释放。12.4.5 register 类型它与auto很接近，并且只能用于局部变量和参数。声明为register是为了通知编译器存储单 元将会被频繁使用。该存储类的一个较好的应用场合是作为大型数组下标的变量。12.5 函数退出Exit(O)：使用数值0调用exit函数表示没有故障，函数执行成功。Exit(1)：使用数值1调用exit函数表示是一些故障导致了退出。12.6 条件编译由于 C 语言禁止头文件的重复说明，因此要为头文件设计条件编译，格式为：#if !defined (NAME_H)#define NAME_H头文件#endif12.7 定义带参数的宏定义的形式为： #define macro_name(parameter list) macro body;第十三章 动态数据结构是在程序执行时扩展和收缩的结构。 节点：动态分配内存的结构，连接在一起形成一个复合结构。13.1 指针13.1.1 作为函数参数的指针 主要是研究了函数输出参数的指针的使用，通过将变量地址传递给函数，就给函数提供了将 某个结果存储在该变量中的一种方法。此时，在函数体中操作的不应该是指针而是指针的间 接数值即指针指向的变量。13.1.2 表示数组和字符串的指针 牢牢记住：数组和字符串(实际上也是数组)在作为参数使用时，只能通过传递数组和字符 串指针(首地址)来实现，使用没有下标的数组名也可以作为指针使用。13.1.3 指向结构体的指针 结构体作为输入参数时，可以将整个结构体作为形参；结构体作为输出参数时，必须使用指 针来传递。13.2 动态内存分配 这里介绍指针的另一种应用环境作为一种访问内存块的方法，该内存块是为了相应一个 明确的程序要求而分配的。可以调用C语言的内存分配函数malloc()为变量动态分配空间，返回指向分配块的指针, 此时的指针类型为void *型，需要强制转换为所需的数据类型。堆(heap)： malloc函数在其中动态分配存储块的内存区域；栈(stack)：在其中分配和收回函数数据区的内存区域；13.2.1 使用 calloc 动态分配数组使用函数calloc可以为任何内部或用户定义类型分配单个内存块。为动态产生一个数组，使 用函数calloc，函数有两个参数：所需的数组元素和每个元素的大小。函数返回的也是指针, 同样也要对指针进行强制类型转换。举一个例子：Char *string1;Int str_size;String1=(char *)calloc(str_size,sizeof(char);13.3 链表链表(Linked list)： 一个节点序列，其中除了最后一个节点外的每个节点都包含下一个节点的 地址。13.3.1 带指针成员的结构体 为了建立一个动态链表，需要使用带有指针成员的节点。适合链表节点的类型定义为：Typedef struct node_sChar current3;Int volts;Struct node_s *linkp; node_t;Struct node_s和node_t是等效的，由于定义指针时编译器还没有看到node_t,所以要用stuct node_s。13.3.2 链表节点带指针的结构体定义好以后， 可以声明任意多个链表节点： node_s *n1_p,node_s *n_2,node_s *n3_p；再通过赋值语句 nl_p-linkp=n2_p;n2_p-linkp=n3_p;来形成类表结构。 然而在末端任然有一个未定义的linkp成员，链表在此处需要结束，在C语言中，空表由指 针NULL表示，空表指没有结点的表，在C中由指针NULL表示，NULL的值为0。指向第一个结点的指针称为表头，通过表头可以访问链表中每个元素。13.3.3 链表的优点 可以很容易删除和插入一个结点，插入结点时需要修改插入点前点的指针指向，并将新点的 指针指向它后面的结点。删除结点应该改变结点前一点指针的指向。13.4 链表运算符13.4.1 遍历链表(traversing a list) 从表头开始，顺序处理链表中的每个结点。可以利用递归调用或者是循环实现。13.5 用链表表示栈 栈：一种数据结构，最后入栈的数据项最先处理。13.6 用链表表示队列队列：元素在一端插入，而在另一段移出的数据结构。队列是一种先进先出的数据结构。我 们需要跟踪队列的首个结点和最后一个结点，他们分别是队列的前端和末端。这是因为队列 中移出结点时需要访问前端，而加入一个结点需要访问末端。另外，我们需要能够找出队列 大小，最好不遍历所有表结点。13.7 有序表 每个元素的位置由其关键成员的值所决定的一个数据结构，关键值构成了一个升序或降序的 序列。13.8 二叉树 几个基本概念：叶子结点(leaf node)：没有后继结点的二叉树结点；根结点(root node)：二叉树中的第一个结点；左子树(left subtree)：数中根结点的左指针所指向的那部分；右子树(right subtree)：树中跟几点的右指针所指向的那部分；13.8.1 二叉查找树将数据用一种可以非常有效地实现检索的方法进行存储的树结构。在二叉查找树中存储的每 一项都拥有唯一的关键码值。二叉查找树或为空，或其特性为：根结点中的数据项的关键码值大于其左子树中每项的关键 码值，而且小于其右子树中每项的关键码值。另外，它的左右子树必须都是二叉树。13.8.2 搜索二叉查找树先与根结点的关键码值比较，如果小于根结点的关键码值，那么搜索根结点的左子树，反之， 搜索根结点的右子树，这样依次进行下去。13.8.3 建立二叉树二叉查找树从根结点开始向下建立，因此必须将第一个数据项存储在根结点中。为了存储随 后的每一个数据，必须正确找到它的父结点，将一个新的结点连接到它的父结点，然后再将 该数据项存储在该新节点中。如果数据的关键码值已经出现在树中，那么这个数据便不能插 入。13.8.4 显示二叉树中序遍历(inorder traversal):按键值顺序显示二叉树中的数据项。第十四章 使用进程和线程的多进程 如果程序之间相互依赖并且一有序和可预测的方式出现，那么采用单进程来执行程序就足够 了。但是，当任务间不相互依赖，或者任务的顺序不能预测，就必须以允许个任务独立运行 的方式编写程序。例如：使用带有多个窗口的图形用户界面的程序。现代操作系统利用称为多任务的概念，允许编写可被分成相互独立操作的多个任务的程序。多任务(multitasking)：将程序分成多个相互独立操作的任务。14.1 多任务14.1.1 串行程序设计和并行程序设计 并行程序设计：同时执行多个程序。串行程序设计：编写一个程序指令的序列，其中每一条指令都依赖于前一条指令的完成。 通过使用调度和优先级就能够完成多任务。14.1.2 分时多任务分时(time sharing)：通过为每个系统用户分配一部分CPU时间来执行并行程序设计。14.1.3 抢占式多任务PC机已经进化到包括能中断正在运行的程序并且指导CPU运行另外一个程序(即操作系统) 的硬件，这被称为抢占式多任务，因为一个运行中的程序可以随时被硬件中断系统抢占，允 许可预测的、独立于运行中程序的、基于优先级标准可调整的方式访问CPU。抢占式多任 务使CPU看起来好像是每次运行了多于一个程序，尽管CPU在任何给定的时刻只能处理单 条程序指令。这被称作伪并行。程序看起来是同时并行运行的，但它们实际上是轮流共享 CPU 的。14.1.4 时间片和并行不同的操作系统采用不同的调度算法确定调度顺序以及为每个程序分配的CPU时间片持续 的时间，这些算法基于以下一些因素：程序代码的复杂度、程序相对于其他程序的优先级、 该程序被访问的频率等。时间片(time slice)：在并行编程环境下为每个程序分配的CPU时间的数量。 当给定的程序的时间片结束时，该程序的状态信息被保存(以便下一个时间片到来时它能够 从停止的地方执行)，被调度的下一个程序的状态信息被恢复，该程序的机器指令开始执行， 这被称为上下文切换。因为CPU运转很快，所以上下文切换很快很频繁，以至CPU看起来 好像同时运行了所有的程序，产生了并行的假象。14.2 进程正在执行的程序的每个唯一的实例被称为进程并且给它一个唯一的标识，称为进程ID,它 由操作系统确定。进程ID可被一个进程用来与另一个进程进行交互，以获得信息或与其他 进程通信。子进程(child process)：当前执行的进程创建的进程；父进程(parent process)：已创建一个或多个的子进程的当前执行的进程；