引子

数据结构的处理方法是从这些具体应用中抽象出共性的数据组织与操作方法，进而采用某种具体的程序设计语言实现相应的数据存储与操作。

利用程序设计语言实现抽象类型的方法：

1. 数据存储C语言即其他高级语言提供了数据组织的几种基本实现方式，包括数组、链表、结构体等。数据的存储方法是与要实现的操作密切相关的。没有最好的存储方式，只有最合适的存储方式。2. 操作实现操作的实现需要利用程序设计语言提供的另一个功能，即流程设计功能。任何高级程序设计语言都提供了一种的基本流程控制语句，即分支控制语句（如 if-else、switch）和循环控制语句（如 for、while、do-while语句）。分支控制结构、循环控制结构加上程序自然的语句顺序执行结果，是实现任何算法流程的基本结构。

模块化程序设计方法以功能块为单位进行程序设计。
模块化的目的是为了降低程序结构的复杂度，使程序设计、调试和维护等操作简单化。
函数是程序设计语言提供的模块化程序设计的基本手段。

数据存储基础

变量是数据存储的基本单位，而变量是有类型的。
C语言定义了几种基本的数据类型：整型、实现（浮点型）、字符型等。
还提供了构造赋值数据类型的手段，如数组、结构、指针等，为有限能力的程序设计语言表达客观世界中多种多样的数据提供了良好的基础。

数组

数组是最基本的构造类型，它是一组相同类型数据的有序集合。
数组中的元素在内存中连续存放，每个元素都属于同一种数据类型，用数组名和下标可以唯一地确定数组元素。
一维数组定义的一般形式为：

类型名  数组名[数组长度]

数组元素的引用要指定下标，形式为：

数组名[下标]

定义数组是，也可以对数组元素赋值。其一般形式为：

类型名  数组名[数组长度]={初值表}；初值表中依次放着数组元素的初值。

C语言支持多维数组，最常见的多维数组是二维数组，主要用于表示二维表和矩阵。
二维数组的定义形式为：

类型名 数组名[行长度][列长度]

引用二维数组的元素要指定2个下标，即行下标和列下标，形式为：

数组名[行下标][列下标]

二维数组的元素在内存中按行有限方式存放，即先存放第0行的元素，再存放第1行的元素……其中每一行的元素再按照列的顺序存放。

数组的应用离不开循环。

数组具有随机存取元素效率较高的优点，即存取第 i 个元素只需常数时间。也就是说，存取A[i]所需时间与下标 i 无关。

类型定义 typedef

用typedef语句来建立已经定义好的数据类型的别名：

typedef 原有类型名  新类型名

利用typedef来建立基本数据类型的别名能够使得程序具有更好的可阅读性和移植性。

指针

使用指针可以对复杂数据进行处理，能对计算机的内存进行分配控制，在函数调用中使用指针还可以返回多个值。

定义指针变量的一般形式为：

类型名  *指针变量名

指针变量用于存放变量的地址。
定义指针变量时，除了指针变量名，还需要说明该指针变量（如P）所指向的内存空间上所存放数据的类型（如 float）。

指针被定义后，必须将指针和一个特定的变量进关联后，才可以使用指针，也就是说，指针变量也要先赋值再使用，当然指针变量被赋的值应该是地址。

1. 指针的基本运算
通过指针访问变量，这些操作由去地址运算符 & 和间接访问运算符 * 完成。
此外，相同类型的指针还能进行赋值和比较。
指针可以同整数进行加、减操作。
两个类型相同的指针也可进行相减操作，表示两个指针之间相隔的变量个数。
两个相同类型指针还可以使用关系运算符比较大小。
2. 指针与数组
在C语言中，数组名本身就是数组的基地址，即第1个元素（下标为0）的地址。
不同：指针是以地址作为值的变量，而数组名的值是一个特殊的固定地址，可以把它看作是指针常量，不能改变指针常量（数组名）的值。

3. 用指针实现内存动态分配
变量在使用前必须被定义且安排好存储空间（包括内存中起始地址和存储单元大小）。
需要一种可以根据运行时的时间存储需求来动态分配适当存储区的机制。为此C语言提供了动态存储管理，允许程序动态申请和释放存储空间。

在动态分配方面，C语言提供了一组标准函数，定义在 stdio.h里面，主要有：

(1) 动态存储分配函数 void * malloc(unsigned size)：
在内存的动态存储区中分配一连续空间，其长度为size。（2）动态存储释放函数 void free(void * ptr)：
释放由动态存储分配函数申请到的整块内存空间，ptr为指向要释放空间的首地址。

为保证动态存储区的有效利用，在动态分配的存储块不再使用时，就应及时将它释放。
特别注意：
（1）指针只有被赋值以后才能被正确使用。
（2）在C语言中，指针的算术运算只包括两个相同类型的指针相减以及指针加上或减去一个整数，其他的操作如指针相加、相乘和相除，或指针加上和减去一个浮点数都是非法的。

结构

结构类型是一种允许程序员把一些数据分量聚合成一个整体的数据类型，它能够把有内在连续的不同类型的数据统一成一个整体，使它们相互关联。
结构又是一个变量的集合，可以按照与成员类型变量相同的操作方法单独使用其变量成员。
结构与数组的区别在于，数组的所有元素必须是相同类型的，而结构的成员可以是不同的数据类型。

结构类型定义的一般形式为：

struct 结构名{类型名  结构成员名1;类型名  结构成员名2;……类型名  结构成员名n;
};

C语言中定义结构体变量的一种方式：先定义一个结构类型，再定义一个具有这种结构类型的变量，基本形式是：

struct 结构名 结构变量名表;

结构变量也可以初始化，即在定义时对其赋初值。

1. 结构变量的使用
   使用结构变量主要就是对其成员进行操作。在C语言中，使用结构成员操作符“ . ”来引用结构成员，格式为：

    结构变量名.结构成员名
   

2. 结构数组
   结构数组是结构与数组的结合，与普通数组的不同之处在于每个数组元素都是一个结构类型的数据，包括各个成员项。
   结构数组的定义方法与普通数组的定义方法相同，此时的类型是结构。
   在定义结构数组时，也可以同时对其进行初始化，其格式与二维数组的初始化类似。
   对结构数组元素成员的引用是通过使用数组下标与结构成员操作符“ . ”相结合的方式来完成的，其一般格式为：

    结构数组名[下标].结构成员名
   

3. 结构指针
   结构指针就是指向结构类型变量的指针。
   有了结构指针，既可以通过该指针访问结构，也可以通过指针直接访问结构成员，具体有两种形式：

（1）用 * 方式访问，形式

	（* 结构指针变量名）.结构成员名

（2）用指向运算符“ -> ”访问指针指向的结果成员，形式：

	结构指针变量名->结构成员名

结构指针也可以作为函数参数传递。

4. 共同体
   共同体类型是指将不同的数据项组织成一个整体，它们在内存中占用同一段存储单元。
   其定义形式为：

    union 共用体名{类型名  成员名1;类型名  成员名2;……类型名  成员名n;};
   

共同体变量的长度等于最长的成员的长度。

链表

链表是一种常见而重要的基础数据结构，也是实现复杂数据结构的重要手段。
它不按照线性的顺序存储数据，而是由若干个同一结构类型的“结点”依次串接而成的，即每一个结点里保存着下一个结点的地址（指针）。
使用链表结构可以克服数组需要预先知道数据大小的缺点，可以充分利用计算机内存空间，实现灵活的内存动态管理。
同时链表由于增加了结点的指针域，空间开销比较大。

链表有很多中不同的类型：单向链表、双向链表以及循环链表。

单向链表的结构
一个表头变量head，用来存放链表首结点的地址，链表中每个结点由数据部分和下一个结点的地址部分组成，即每个结点都包含指向下一个结点的指针。
链表中的最后一个结点称为表尾，其下一个结点的地址部分的值为NULL（表示为空地址）。
链表的各个结点在内存中可能是不连续存放的，具体存放位置由系统分配。

“给定一个单链表”，就是给定一个指向该链表头结点的指针，所以“单链表类型”Listk可以定义为链表结点结构的指针，即：

typedef PtrToNode List;

链表是一种动态数据结构。
在进行动态存储分配的操作中，C语言提供了几个常见的函数：malloc()、free()。

单向链表的常见操作

（1）插入结点在单向链表head的某个结点p之后插入一新结点的基本过程是：首先找到正确位置p，然后申请新结点t 并对 t 的结点信息赋值，最后将t 插在p之后。将结点t插在结点p之后的语句为：t->Next = p->Next;p->Next = t;注意：上述两个语句的顺序不能颠倒。如果需要在链表的头上插入一个结点t，其基本语句是：t->Next = head;head = t;（2）删除结点从单向链表head中删除一个结点的基本过程是：首先找到被删除结点的前面一个结点p，然后删除p之后的那个结点。基本语句为：t = p->Next;p->Next = t->Next;free(t);注意：删除一个结点后必须释放该结点的空间，为此在上述语句中首先将待删除结点保留在t中，最后再释放t。如果删除的是链表的第一个结点，其基本语句是：t = head;head = head->Next;free(t);(3) 单向链表的遍历对单向链表最常见的处理方式是逐个查看链表中每个结点的数据并进行处理，因此，链表的遍历是非常基础的链表程序设计方法。单向链表遍历的基本程序结构为：p = head;while(p! = NULL){……对p所指的结点信息进行处理；……p = p->Next;}(4) 链表的建立应用链表进行程序设计时，往往需要先建立一个链表。建立链表的过程实际上就是不断在链表中插入结点的过程。在构建表时，有两种常见的插入结点方式：1.在链表的头上不断插入新结点； 2. 在链表尾部中插入结点的过程。

双向链表
单向链表的构成使得结点访问要按链的指向进行，某一个单元的后继单元可以直接通过链指针（Next指针）找到，而要找到其前驱单元，必须从链头开始查找。
如果结点增加一个指针域指向其前驱结点，将在牺牲空间代价的前提下，减少操作的代价。
这种在单向链表基础上增加指向前驱单元指针（Previous指针）的链表叫做双向链表。

流程控制基础

表达数据处理的过程，即程序的控制过程。
任何程序都可以将程序模块通过三种基本的控制结构进行组合来实现。
这三种基本的控制结构是顺序、分支和循环。
顺序结构是一种自然的控制结构，通过安排语句或模块的顺序就能实现。
C语言为分支控制提供了 if-else和switch两类语句，而为循环控制提供了for、while和do-while三类语句。
上述3种控制方式称为语句级控制。它实现了程序在语句间的跳转。
函数调用时刻传递零个或多个参数，函数被调用的结果将返回给调用函数。这种涉及函数定义和调用的控制称为单位级控制。
所以，程序设计语言的另一个功能就是提供单位级控制的手段，即函数的定义与调用手段。

分支控制

if-else语句
if-else语句的一般形式为：

if-else(表达式)语句1;
else语句2；

if-else语句首先求解表达式，如果表达式的值为“真”，则执行语句1；如果表达式的值为“假”，则执行语句2。 if-else语句的else部分可以省略。

通过多个二路分支语句 if-else 的嵌套组合实现多路选择，其一般形式为：

if(表达式1)语句1;
else  if (表达式2)语句2；……
else  if(表达式n-1)语句n-1;
else语句n；

在C语言中，else 和 if 的匹配准则是： else 与最靠近它的、没有与别的else匹配过的 if 相匹配。

switch语句

switch语句可以处理多分支选择问题，典型的形式是：

switch(表达式)
{	case 常量表达式1: 语句段1; break;case 常量表达式2：语句段2; break;……case 常量表达式n：语句段n; break;default:       语句段n+1; break;
}

该switch语句首先求解表达，如果表达式的值域某个常量表达式的值相等，则执行该常量表达式的相应语句段，如果表达式的值与任何一个常量表达式的值都不相等，则执行default后的语句段。
当碰到break语句时，跳出switch语句。

在switch语句所有的语句段末尾使用break，可以简单清晰地实现多分支选择。

循环控制

C语言提供了三种循环语句：for 、while、do-while。

for语句

在C语言中，for语句是一种常用的循环语句。它的一般形式为：

for (表达式1; 表达式2; 表达式3)循环体语句;

for语句先计算表达式1；再判断表达式2，若值为“真”，则执行循环体语句，并接着计算表达式3，然后继续判断表达式2，如此循环；若值为“假”，则结束循环，继续执行for的下一条语句。

while语句

while语句的一般形式为：

while (表达式)循环体语句；

对应while语句，当表达式的值为“真”时，循环执行，直到表达式的值为“假”，循环中止，并继续执行while的下一条语句。

while语句的构成简单，只有1个表达式和1个循环体语句，分别对应循环的两个核心要素：循环条件和循环体。
循环体的实现一般包括4个部分，即初始化、条件控制、重复 的操作以及通过改变某些量的值最终改变条件的真假性，使循环能正常结束。

可以把for语句改写成while语句：表达式1;
while (表达式2)
{for 的循环体语句;表达式3;
}

do-while语句
do-while 语句是先执行循环体，后判断循环条件。
其一般形式为：

do
{循环体语句;
}
while(表达式)

do-while语句第一次进行循环时，首先执行循环体语句，然后再检查循环控制条件，即计算表达式，若值为“真”，继续循环，直到表达式的值为“假”，循环结束，执行do-while的下一条语句。
do-while语句的使用方法和while语句类似，语句中的表达式可以是任意合法的表达式，使用时要另加初始化部分，循环体语句必须包含能最终改变条件真假的操作。

do-while语句适合于先循环后判断循环条件的情况，一般在循环体的执行过程中明确循环控制条件。
它每执行依次循环体后，在判断条件，以决定是否进行下一次循环。

break 语句和 continue 语句
break语句强制循环结束，一旦执行了break语句，循环提前结束，不再执行循环体中位于其后的其他语句。只有条件满足时，才执行break跳出循环。

continue语句的作用是跳过循环体中continue后面的语句，继续下一次循环。
continue语句一般也需要与 if 语句配合使用。

continue语句和break语句的区别在于，break结束循环，而continue只是跳过后面语句，继续循环。
break除了可以终止循环外，还用于结束switch语句，而continue只能用于循环。

嵌套循环
嵌套循环（或多重循环）是指大循环中嵌套了小循环。
在处理许多比较复杂问题时经常会使用嵌套循环，三种循环（for、while、do-while）都可以相互嵌套。

函数与递归

函数是一个完成特定工作的独立程序模块。
程序中一旦调用了某个函数，该函数就会完成一些特定的工作，然后返回到调用它的地方。
函数包括库函数和自定义函数两种。

函数定义的基本形式是：

函数类型  函数名(形参表)             /*  函数首部 */
{函数实现过程;                   /*  函数体 */
}

函数的定义包括函数首部和函数体两部分。其中，函数首部由函数类型、函数名和形参表组成；函数体包括函数实现过程和return语句（return 表达式;），体现为以对大括号内的若干条语句。

注意：在函数定义时，若不说明函数类型（即函数类型缺省），该函数的类型被缺省定义为 int。

函数的调用

定义一个函数后，就可以在程序中调用这个函数。调用函数时，将实参传递给形参并执行函数定义中所规定的程序过程，以实现相应的功能。

函数调用的一般形式为：

函数名(实参表)

实参可以是常量、变量和表达式。
函数定义中的参数被称为形参，函数调用时的参数被称为实参。
形参和实参必须一一对应，要求两者数量相同、类型一致。
在程序运行中，有点函数调用时，将实参的值按依次传给形参，这就是参数传递。

函数声明的一般格式为：

函数类型   函数名(参数表);

设计函数时，需要注意的原则：
（1）函数功能的设计原则：
结合模块的独立性原则，函数的功能要单一，不要设计多用途的函数，否则会降低模块的聚合度。

（2）函数规模的设计原则：
函数的规模要小，尽量控制在50行代码以内，这样可以使得函数更易于维护。
（3）函数接口的设计原则：
结合模块的独立性原则，函数的接口包括函数的参数（入口）和返回值（出口），不要设计过于复杂的接口，合理选择、设置并控制参数的数量，尽量不要使用全局变量，否则会增加模块的耦合度。

递归函数
函数自己调用自己的形式称为函数的递归调用，带有递归调用的函数也称为递归函数。
递归函数进行程序编程的两个关键点：
（1）递归出口：
即递归的结束条件，到何时不再递归调用下去。
（2）递归式子：
当前函数结构与准备调用的函数结果之间的关系，如求阶乘函数 Factorial(N) = N * Factorial(N-1)。

学习参考资料：

《数据结构》 第2版