第一章结构体与共用体

设计程序最重要的一个步骤是选择一个表示数据的好方法。在多数情况下，使用简单的变量甚至数组都是不够的。C使用结构体变量进一步增强了表示数据的能力。结构体是可能具有不同值的集合；联合体和结构体很类似，不同之处在于联合体的成员共享一段存储空间。这样的结果是，联合体可以每次存储一个成员，但无法同时存储全部的成员。枚举是一种整数类型，它的值由程序员来命名。结构体是最重要的一种类型，所以本章主要介绍结构体类型以及结构体变量的定义、初始化、引用以及其他应用，最后简单介绍共用体以及枚举等相关知识。

●1.1结构体数据类型表示数据的需求

实际生活中我们经常碰到信息统计的题目。比如学生成绩管理题目：要求输入学生的学号、姓名、五门课的成绩，并计算每个学生五门课的平均分，并按平均分计算名次，若平均分相同则名次并列。最后输出统计结果。题目中计算平均分和排序我们前面的章节中分析过此类题目，所以单就每个学生的平均成绩或者根据成绩排出名次我们都应该比较熟悉。根据前面学习的知识，我们可以定义一个整型数组保存学生的学号，然后再定义一个二维的字符数组保存学生的姓名，最后我们定义一个数值型的二维数组保存每个学生五门课的成绩。可最好的方式不是将数据分割存储，而是作为一个整体存放。那就需要一种新的结构形式，其中既可以包括字符串，又可以包括数值型数据，还可以保存这些信息。C语言的结构体就满足了这种需要。

●1.2结构体类型与结构体变量的定义

实际生活中我们经常碰到信息统计的题目。比如学生成绩管理题目：要求输入学生的学号、姓名、五门课的成绩，并计算每个学生五门课的平均分，并按平均分计算名次，若平均分相同则名次并列。最后输出统计结果。题目中计算平均分和排序我们前面的章节中分析过此类题目，所以单就每个学生的平均成绩或者根据成绩排出名次我们都应该比较熟悉。根据前面学习的知识，我们可以定义一个整型数组保存学生的学号，然后再定义一个二维的字符数组保存学生的姓名，最后我们定义一个数值型的二维数组保存每个学生五门课的成绩。可最好的方式不是将数据分割存储，而是作为一个整体存放。那就需要一种新的结构形式，其中既可以包括字符串，又可以包括数值型数据，还可以保存这些信息。C语言的结构体就满足了这种需要。

●1.3结构体变量的引用与赋值

对结构体类型变量的引用是通过结构体类型变量的成员来实现的。引用结构体类型变量成员的一般形式为：结构体类型变量名.成员名需要引用到最低级。结构体变量的赋值需要根据最低级成员变量的数据类型来赋值。

●1.4结构体变量的初始化及实例

结构体类型变量的初始化和其他类型变量一样，也可以在定义时进行初始化。而且结构体变量的初始化形式类似于一维数组初始化的语法。

●1.5结构体数组

结构体数组是结构体与数组的结合，与普通数组的不同之处在于每个数组都是一个结构体类型。结构体类型数组的每一个元素是同一结构体类型的变量。

●1.6指向结构体类型的指针（上）

一个指针变量用于指向一个结构体类型变量时，称之为结构体类型指针变量。结构体类型指针变量中的值是所指向的结构体类型变量的首地址，通过结构体类型指针可以访问该结构体类型变量。

●1.7指向结构体类型的指针（下）

一个指针变量用于指向一个结构体类型变量时，称之为结构体类型指针变量。结构体类型指针变量中的值是所指向的结构体类型变量的首地址，通过结构体类型指针可以访问该结构体类型变量。

第二章文件

在程序设计中，往往要对大量数据进行处理。许多程序在实现过程中，依赖于把数据保存到变量中，而变量是通过内存单元存储数据的，数据的处理完全由程序控制。当一个程序运行完成或者终止运行，所有变量的值不再保存。另外，一般的程序都会有数据输入与输出，如果输入输出数据量不大，通过键盘和显示器就可方便解决，而当数据较多时就极为繁琐。例如，学生成绩管理系统要用到学生的学号、姓名以及课程成绩等数据，对于一个几千人的中等规模的院校，可能要对几万到几十万个数据进行处理，数据量很大。文件是解决上述问题的有效办法，它通过把数据存储在磁盘文件中，得以长久保存。每次运行程序时从磁盘文件中读取数据，程序的输出数据也存入磁盘中，这就为程序运行提供了很大方便。为此，C语言提供了一系列对磁盘文件进行的操作。本章将重点介绍文件的概念、文件的分类以及文件操作的相关函数，包括fopen()、fclose()、fgetc()、fputc()、fprintf()、 fscnaf()、fgets()、 fputs()、exit()、fflush()、fread()、fwrite()、rewind()、fseek()、feof()。

●2.1文件概述

文件是指一组相关数据的有序集合，文件通常是驻留在外部存储介质（如磁盘等）上的，在使用时才调入内存。比如 stdio.h 就是一个包含一些有用信息的文件的名称。与计算机内存存储数据不同，文件通常对应于程序的地址空间之外的存储器，比如U盘或硬盘。存取数据的细节都是由操作系统来实现的，程序员只需要考虑的是如何在C程序中处理文件。从文件编码的角度，文件可分为文本文件和二进制文件两种。

●2.2如何使用文件

在Ｃ语言中，用一个指针变量指向一个文件，该指针称为文件指针。通过文件指针可以对文件进行各种操作。定义文件指针的一般形式为：FILE *指针变量标识符；对文件进行操作时需要使用fopen()函数在打开一个文件，文件操作后需要使用fclose()关闭一个文件。

●2.3文本文件的读写（上）

对文件的读和写是最常用的文件操作，Ｃ语言中提供了多种文件读写函数，使用文件操作函数都要求包含头文件stdio.h。字符读写函数fgetc()和fputc() 字符串读写函数（fgets和fputs）

●2.4文本文件的读写（下）

对文件的读和写是最常用的文件操作，Ｃ语言中提供了多种文件读写函数，使用文件操作函数都要求包含头文件stdio.h。字符读写函数fgetc()和fputc() 字符串读写函数（fgets和fputs）

●2.5二进制文件的读写

fscanf(文件指针，格式字符串，输入表列)；fprintf(文件指针，格式字符串，输出表列)；fread(buffer，size，count，fp)；fwrite(buffer，size，count，fp)；

●2.6文件操作的其他函数

• rewind()函数把文件内部位置指针移到文件首部。• fseek()函数移动文件内部位置指针到指定位置。• ftell函数用于获得文件当前位置指针的位置。• fflush函数用于刷新缓冲区。

第三章链表

在程序设计的基本工具中，可以实现批量数据存储的结构主要有两类，一是前面介绍过的数组，可以通过连续的地址空间来存放批量数据；二是链表，通过其所包含的多个结点实现对批量数据的存储。用数组来存储批量数据，必须预先指定数组的大小（即定义数组的长度），如果事先不能确定元素的个数，就必须要定义一个尽可能大些的数组，以便能够满足可能的存储需求。但这样做又会带来另一个问题：如果实际数组元素没有那么多的话，便造成了大量的存储空间的浪费。如果用链表来存储批量数据，就可以避免数组空间使用带来的问题，因为链表本身是一种动态的存储结构，不需要预先指定空间大小，可以根据运行的需要动态地分配与释放内存。本章在介绍动态内存分配的基础上，重点介绍单链表的概念、操作以及基本的应用。

●3.1内存划分与内存分配方式

一个由C编译的程序占用的内存分为以下几个部分。1.栈区（stack）：由编译器自动分配、释放，通常用于存放函数的参数值、局部变量的值等。2.堆区（heap）：一般由程序员分配、释放，若程序员不释放，程序结束时可能由操作系统回收。3.全局区（静态区）（static）：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。4.文字常量区：常量字符串放在这个区域里，程序结束后由系统释放。5.程序代码区：存放函数体的二进制代码。

●3.2C的内存分配函数（上）

对堆内存的动态分配与释放是通过系统提供的一组库函数来实现的，它们在stdlib.h（或malloc.h）头文件中声明，主要有malloc、calloc、free、realloc函数。

●3.3C的内存分配函数（下）

对堆内存的动态分配与释放是通过系统提供的一组库函数来实现的，它们在stdlib.h（或malloc.h）头文件中声明，主要有malloc、calloc、free、realloc函数。

●3.4单链表的建立--逆序建单链表

链表是实现批量数据存储表示的重要结构，链表有多种形式，这里主要介绍最基本的链表结构——单链表。单链表中的每一个数据元素是通过一个称之为“结点”的结构来存储表示的，每个结点占据一个内存空间，多个结点所占的存储空间是离散的，结点之间通过专门的指针相互链接构成一个整体。从本质上看，链表就是一个结点的序列。要应用单链表，首先应该建立单链表。单链表的实质是一个结点的序列，建立单链表实质上就是逐个生成每一个结点，并把结点插入链表的过程。可见，单链表的建立是一个结点插入的过程，只不过需要插入的不是一个结点，而是多个结点而已。但多个结点的插入方式是相同的，因此可以借助循环过程来实现。单链表的建立可以有两种方式，一种是按照输入的元素的顺序依次排列每一个结点，被称为顺序建链表。另一种是按照输入元素的相反顺序来排列结点，被称为逆序建链表。

●3.5单链表的建立--顺序建单链表

链表是实现批量数据存储表示的重要结构，链表有多种形式，这里主要介绍最基本的链表结构——单链表。单链表中的每一个数据元素是通过一个称之为“结点”的结构来存储表示的，每个结点占据一个内存空间，多个结点所占的存储空间是离散的，结点之间通过专门的指针相互链接构成一个整体。从本质上看，链表就是一个结点的序列。要应用单链表，首先应该建立单链表。单链表的实质是一个结点的序列，建立单链表实质上就是逐个生成每一个结点，并把结点插入链表的过程。可见，单链表的建立是一个结点插入的过程，只不过需要插入的不是一个结点，而是多个结点而已。但多个结点的插入方式是相同的，因此可以借助循环过程来实现。单链表的建立可以有两种方式，一种是按照输入的元素的顺序依次排列每一个结点，被称为顺序建链表。另一种是按照输入元素的相反顺序来排列结点，被称为逆序建链表。

●3.6单链表结点的基本操作 （上）

单链表与数组的不同之处还体现在单链表是一个动态存储的结构，可以在需要时再分配空间，用完后马上释放空间。而且，与数组做元素插入、删除需要移动元素不同，单链表无论是插入还是删除元素，都不需要做元素的移动，实现过程非常简洁。要在单链表中插入一个元素时，如果已经确定了该元素的插入位置，需要做的事情只有两点：一是为要插入的元素分配空间，生成一个新结点；二是通过指针域的修改，把新结点插入到链表中。

●3.7单链表结点的基本操作（下）

与结点的插入相类似，结点的删除也不需要作元素的移动，而只需要作指针的修改即可。并且作为动态分配的存储结构，当链表的结点不再需要时，可以在删除结点时将其所占的内存空间释放。要删除结点，首先要找到被删结点的前一个结点，然后再对这前一个结点实施指针的修改操作。

●3.8单链表的应用1-逆置

与数组的逆置要求类似，单链表的逆置，就是把单链表的结点按照相反的顺序存放

●3.9单链表的应用2-拆分

单链表的归并是将几个链表合并成一个链表，单链表的拆分与归并相反，是将一个单链表拆分成几个小的链表。根据之前的经验可知，这是一个建立多个子链表的过程，建子链表的过程可以根据题目的要求选择顺序或逆序的方式，结点来源于原始的大链表。为此，可以为各个子链表分别建立各自只包含头结点的空链表，然后依次访问原始链表取得每一个结点，根据结点的特征确定在哪个子链表进行插入。当原始链表访问结束后，所有的结点也分别在自己的子链表上完成了插入，一个链表就拆分成了几个子链表。

●3.10单链表的应用3-归并

对于已经存在的多个单链表，有时需要将它们合并成一个大的单链表，这类问题称为单链表的归并。其中应用较多的是有序单链表的归并，即将多个结点有序排列的单链表合并成一个大的单链表，合并后生成的新的单链表结点仍然按照结点有序排列。下面以两个有序单链表的归并为例来探讨这类问题的解决方法。由于是生成一个新链表，所以这仍然是一个类似建新链表的过程，与刚刚提到的链表逆置相同，新链表的结点来源不是新分配的空间与新输入的数据，而是来源于旧的链表。与逆置不同之处只不过在于逆置的结点来源是一个旧的链表，而归并的结点来源是两个旧的链表而已。由于新链表的结点要求有序排列，而两个旧的链表又已经是有序的序列，因此取结点时要从两个链表的第一个结点开始取起，至于到底选择哪一个结点往新链表做结点插入，要通过比较其大小来确定。为此，在两个旧链表中要分别设置两个指针，起到类似逆置程序的指针p与指针q的作用。同时，新链表的结点插入是由小到大逐个实现的，每次结点的插入位置都是尾结点的后端，因此建链表的方法得用顺序建链表的方式而不是逆序建链表的方式。需要设置好新链表的尾指针，能够始终标记新链表的尾结点的位置。

●3.11循环链表与约瑟夫环

一般单链表的最后一个结点的指针为NULL，如果操作中需要对单链表结点中的数据重复地访问，访问到最后一个结点后再回到第一个结点，这时，可以让最后一个结点的指针域存放第一结点的地址，也就是最后一个结点的后继指针又指向了第一个结点，这样的链表称为循环链表。循环链表的运算与单链表的运算基本一致。两者的区别有以下几点：1.建立一个循环链表时，必须使其最后一个结点的指针指向头结点，而不是像单链表那样置为NULL。此种情况还适用于在最后一个结点后插入一个新的结点。2.循环链表判断是否到表尾的条件，是判断该结点链域的值是否是头结点，当链域值等于头指针时，说明已到表尾。而非像单链表那样判断链域值是否为NULL。

第四章递推与递归

递推是计算机数值计算中的重要算法，递推的思路是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。递归算法在可计算性理论中占有重要地位，也是算法设计中的比较巧妙的方法，它写出的程序较简短，可以使某些看起来不易解决的问题变得容易解决，在程序设计中常常有着独特的作用。

●4.1递推算法的基本思想（母牛的故事、茶叶蛋）

递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，这样的问题可以采用递推法来解决。递推法有两种形式，其中已知初始值，通过递推关系式求出最终结果的递推方式称为顺推法；已知最终结果，通过递推关系式求出初始值的递推方式称为倒推法。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来可以将递推算法看成是一种特殊的迭代算法。（在解题时往往还把递推问题表现为迭代形式，用循环处理。所谓“迭代”，就是在程序中用同一个变量来存放每一次推算出来的值，每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值，这种方法称为迭代。）递推分倒推法和顺推法两种形式。

●4.2递推实例之骨牌问题

顺推案例。

●4.3递推实例之马兰过河卒

顺推案例。

●4.4递归的基本原理

递归是指在函数执行过程中出现对自身的调用的编程方法。 一个函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

●4.5递归的基本过程

递归是从问题的目标状态出发，通过自身的递归关系，层层递进，不断把问题的规模缩小，最终达到问题的边界条件（已知的初始状态）的解题方法。

●4.6递归实例之汉诺塔

通过该案例，学习递归算法的分析、归纳和设计的过程。

●4.7递归实例之青蛙过河

通过该案例，学习递归算法的分析、归纳和设计的过程。

第五章贪心与动态规划

随着程序设计中处理的数据量越来越大，对数据处理的高效率需求也越来越迫切，在这一背景下，算法在程序设计中的作用显得尤其重要。贪心策略、动态规划等一系列运筹学模型纷纷运用到程序设计中，产生了解决各种现实问题的有效算法。贪心法（又称贪婪算法）是指：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。将一个问题分解成为子问题求解，并且将中间子问题的结果保存起来以避免重复计算的方法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划求解的问题，必须满足最优解的每个局部解也都是最优的。

●5.1贪心算法的基本思想

随着程序设计中处理的数据量越来越大，对数据处理的高效率需求也越来越迫切，在这一背景下，算法在程序设计中的作用显得尤其重要。贪心策略、动态规划等一系列运筹学模型纷纷运用到程序设计中，产生了解决各种现实问题的有效算法。贪心法（又称贪婪算法）是指：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。将一个问题分解成为子问题求解，并且将中间子问题的结果保存起来以避免重复计算的方法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划求解的问题，必须满足最优解的每个局部解也都是最优的。一般贪心问题求解的基本思路框架：1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的局部最优解合成原来问题的一个解。

●5.2贪心算法之删数问题

通过案例学习贪心算法的设计方法。

●5.3贪心算法之活动选择问题

通过案例学习贪心算法的设计方法。

●5.4贪心算法之最小区间覆盖问题

通过案例学习贪心算法的设计方法。

●5.5动态规划的基本思想

在用分治递归法设计程序时，为了解决一个大的问题，我们总是想方设法把它分成两个或多个更小的问题；然后分别解决每个小问题；再把各小问题的解组合起来，即可得到原问题的解；小问题与原问题相比较，通常是性质相似但规模更小的问题，所以一般可用递归的方法来解决，如hanoi塔问题和快速排序都是应用这种方法的典型例子。然而对有些问题而言，当把其分解成若干个子问题，使之能够从这些子问题的解得到原问题的解时，子问题的数目会比较多，如果把每个子问题再继续分解，必将得到更多的子问题，以至于最后解决问题需要耗费的时间呈指数增长。往往在这类问题中子问题的数目其实只有多项式个，于是在上述算法中，一定有些子问题被重复计算了许多次。如果我们能够保存已解决的子问题的答案，而在需要时简单查一下，就可以避免大量的重复计算，从而得到多项式时间的算法。为了实现上述方法，通常用一个数组来记录所有已解决的子问题的答案。无论子问题以后是否被用到，只要它被计算过，就将其结果存入数组中，这种方法在程序设计中被称为动态规划。

●5.6动态规划算法之数字三角形问题

通过案例学习动态规划算法的设计方法。

●5.7动态规划算法之最长公共子序列问题

通过案例学习动态规划算法的设计方法。

●5.8动态规划算法之最长上升子序列问题

通过案例学习动态规划算法的设计方法。