（1） C语言的函数和参数传递
在着手开始学习数据结构与算法设计方法之前，我们先回顾一些C语言基础，这会有利于我们以后基于C语言的编程和分析，虽然其中有许多你可能已经非常熟悉了。
1.1 函数与参数（传值、引用）
【1】传值参数：
考察函数Ex_1(程序1.1)，a,b,c都是函数Ex_1的形式参数（formal parameter），类型均为整形，如果以下调用Ex_1(1, 2, x)，它的返回结果还是一个整数：
----------------------------------------------------------------------------------------------------------------------
程序1.1
int Ex_1(int a, int b, int c)
{
return (a + b ) / c ;
}
当Ex_1(1, 2, x)被执行时，a的值被赋为第一个参数1，b的值被赋为第二个参数2，而需要注意的是，c的值会被赋为x，但如果x不是int类型，那么首先会先进行强制类型转换。例如x = 3.7是float型，那么c会被赋值成int(3.7) = 3。在该程序段中（程序1.1），a, b, c都是传值参数（value parameter），但这种形式传值时，首先要判断原参数的类型分别能否合a, b, c的类型相同，如果不同就进行强制类型转换，当然这里假设这种转换是允许的。在这种形式的传入参数时，函数体调用或操作的只是原参数的一份拷贝，而不会修改原参数的值。
【2】引用参数：
为了书写和理解方便，我们以后会不加说明的在程序段中直接使用到C++的引用传递参数形式。在程序1.1中使用的传值参数的用法会增加程序的开销，比如调用Ex_1(int a, int b, int c)传入参数时系统需要赋值一份拷贝，而在返回时却又要释放这些拷贝，假设函数Ex_1()被调用一千次，则需要复制和释放传值参数a、b、c各3000次，显然这会带来效率的降低！使用引用参数（reference parameter）会是解决这个问题的好办法。
----------------------------------------------------------------------------------------------------------------------
程序1.2
int Ex_2(int &a, int &b, int &c)
{
return (a + b ) / c ;
}
考察程序1.2中函数Ex_2(x, y, z)。其中x, y, z的类型分别和Ex_2中的参数a, b, c相同，那这些原参数x, y, z将分别会被赋对应的别名（alias）a, b, c。也就是相当于原来叫x, y, z的三个人再给他们分别起另外一个名字分别是a, b, c称呼他们。因此在函数Ex_2()中，对a,b,c的操作相当于对原来的x,y,z直接进行操作，只是现在称呼的名字不同而已。而且引用参数只能传变量而不能传常量，比如调用Ex_2(1, x, y)是非法的，还和传值参数不同，该程序段(程序1.2)在调用时没有额外复制三个参数的拷贝，函数返回是也没有再释放它们，因此提高了效率。但是需要特别注意的是，引用参数会改变原参数的值，而参值参数不会，所以在选择参数传递形式时，需要特别注意二者的区别。
----------------------------------------------------------------------------------------------------------------------
程序1.2.1
void Swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
程序1.2.2
void Swap_ERR(int a, int b)
{
int temp;
temp = a;
a = b;
b = temp;
}
----------------------------------------------------------------------------------------------------------------------
上面程序段目的是想完成交换两个变量的功能，在程序1.2.1中是引用参数，而程序1.2.2中是传值参数。可以实验，Swap成功交换两个变量，而用传值参数的Swap_ERR是错误的。
传值和引用参数的区别（表1.1）
-------------- 传 值 引 用
调用 效率 低 高
改变原参数 否 是
1.2 函数与递归
递归函数（recursive function）是一个自己调用自己的函数。递归函数包括两种，直接递归(direct recursive)和间接递归(indircet recursive)。直接递归是指函数F的代码中直接包含了调用F的语句；而间接递归是指函数F调用了函数G，G又调用了H，如此进行下去，直到F又被调用。对于函数F (n) 的一个递归定义（假定是直接递归），要想使它成为一个完整的定义，必须满足如下两个条件：
• 定义中必须包含一个基本部分(base)，也就是递归终止条件。递归终止条件可能有一个或多个。
• 在递归部分(recursive component)中，该部分的参数必须重复运用，直至出现F的基本部分，也就是不断重复递归直至该递归函数终止。
1.2.1 例子（1）
比如一个求N!的数学公式（公式1.1）：
1 [n <= 1]
f(n) =
n * f(n – 1) [n > 1]
该公式（公式1.1）中，基本部分即递归终止条件是 1 [n <= 1]，而递归部分是n * f(n – 1) [n > 1]，写成C程序就是
----------------------------------------------------------------------------------------------------------------------
程序1.3
/*f(n) = n! ，见数学公式1.1*/
int f(int &n)
{
if (n <= 1)
return 1; //递归终止部分
else
return n * f(n - 1); //递归部分，反复修改参数直到递归终止
}
----------------------------------------------------------------------------------------------------------------------
假设调用f(4)求4！的值，则该递归过程为：
f(1) = 1 //递归终止的返回值
f(2) = 2 * f(1)//利用f(1)的返回结果再求出f(2)=2*f(1)=2的值并返回
f(3) = 3 * f(2)//依次类推，本层返回值直接需要利用到上层的计算结果
f(4) = 4 * f(3)//f(3)的值还未知，于是递归求f(3)的值
故得出解是f(4) = 24。
1.2.2 例子（2）
再看一个求斐波那切(Fibonacci)数列的递归例子，数学公式(公式1.2)是：
1 [n <= 1]
Fib(n) = 1 [n = 2]
Fib(n – 1) + Fib(n – 2) [n > 3]
该公式（公式1.2）的基部分（终止条件）有2个，分别是1 [n <= 1], 与1 [n = 2]，但也可以合并成1 [n <= 2]的基部分：
----------------------------------------------------------------------------------------------------------------------
程序1.4
/*f(n)是求Fibonacci数列的值，见数学公式1.2*/
int f(int &n)
{
if (n <= 2)
return 1; //递归终止部分
else
return Fib(n –1) * Fib(n - 2); //递归部分，反复修改参数直到递归终止
}
----------------------------------------------------------------------------------------------------------------------
程序1.4的递归过程也是类似的，先不断修改递归参数直到满足终止条件，然后从终止条件所在的最低层开始逐层返回，最后返回的所要求的Fib(n)的值。如果调用dest = Fib(4); 请自行模拟该递归过程及其所带回的返回值。
1.2.3 递归与非递归的区别（补充部分）
任何“递归程序”都可以通过程序员自己控制系统堆栈转为“非递归程序”实现（注：递归程序是不能等同于递归数学公式）。而且，并非所有的递归数学公式都可以转为非递归公式，比如已证明的双递归函数（如Ackmann函数）不存在非递归数学公式。但某些递归公式是可以转为非递归的，比如求n!的值，实际可以转为递推公式来解决对于计算机程序来说效率更高。
可以看到，使用递归函数来编程的明显好处是清晰易懂，因为递归通常有严格的数学公式依据，而且反之，使用递归的程序或算法也容易用数学归纳法证明其正确性（但这里不多叙述）。同时也需要看到递归程序明显不足之处是在进行函数递归时需要不断的在内存中保存/恢复现场，这将大大增加系统的开销。但是由于现代计算机的速度和内存容量的不断增大，所以这些开销有时候并不十分重要。所以在选择递归结构进行程序设计时，要考虑到“可理解性和效率”之间的关系。
2） 什么是数据结构
数据结构专门研究数据的各种表示、数据类型及其它们之间的关系集合，其研究范围主要包括各种数据结构的性质，即他们的物理结构、逻辑结构以及施于其上的操作。数据结构是信息的载体，算法是处理信息的步骤，通常可以认为：程序 ＝ 算法 ＋ 数据结构。
数据结构的分类（表1.2）
简单类型 整型、实型、字符型、布尔型 静态数据类型
构造类型 数组、结构体、集合、字符串 静态数据类型
文件、指针 动态数据类型
线性结构 数组、链表、栈、队列、串 ――――――
非线性结构 树、图 ――――――
【注：以下引自starfish原作的文章】
1.何谓数据结构?
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。
数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。
2.数据结构主要研究什么？
数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。
3.什么是数据？什么是结构？什么是逻辑结构和物理结构？
数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。通常来说，一个数据结构DS 可以表示为一个二元组：
DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part)
这里D是数据元素的集合（或者是“结点”，可能还含有“数据项”或“数据域”），S是定义在D（或其他集合）上的关系的集合，S = { R | R : D×D×...}，称之为元素的逻辑结构。
逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的（全序关系），树(偏序或层次关系)和图（局部有序(weak/local orders)）是非线性结构。
数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射： P:(D,S) --> M
存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。
P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。
因此，我们至少可以得到4×4种可能的物理数据结构：
sequential (sets)
linked lists
indexed trees
hash graphs
（并不是所有的可能组合都合理）
4.数据结构(DS)上的操作:
所有的定义在DS上的操作在改变数据元素（节点）或节点的域时必须保持DS的逻辑和物理结构。
5. DS上的基本操作：
任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和他的所有基本操作看作一个整体——称之为模块。我们可以进一步将该模块抽象为数据类型（其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法），称之为ADT。作为ADT，堆栈和队列都是一种特殊的表，他们拥有表的操作的子集。对于DATs的高级操作可以被设计为（不封装的）算法，利用基本操作对DS进行处理。
6.好的和坏的DS：
如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如果没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作，要访问图的所有结点，则必须按照某种顺序来依次访问所有节点（要形成一个偏序），必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。
树是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归的结构都可以被转化为（或等价于）树形结构。
（3） 自学数据结构与算法推荐书目（仅推荐作者看过的）
1． 《C程序设计》 谭浩强 C语言
2． 《C专家编程》 C语言
3． 《数据结构算法与应用-C++语言描述》 C++语言
4． 《算法与数据结构》 王晓东 类PASCAL描述
5． 《数据结构》 严蔚敏 类C描述
6． 《算法导论》 类PASCAL描述
7. 《DELPHI算法与数据结构》 Julian Bucknall PASCAL
本文地址：http://com.8s8s.com/it/it28621.htm