1、C语言是通用计算机编程语言，兼有高级和低级语言的功能，语法简洁，应用广泛。有良好的跨平台特性。适合编写系统软件和应用软件。为了更好地理解书中案例，本章对C语言中相对复杂的数组、结构、指针类型变量的应用予以回顾。前言目录运行环境01数组与结构02指针03递归04运行环境PARTONE2.1运行环境Dev-C+是Windows平台下的开源C+编程环境。它集成了GCC、MinGW32等众多自由软件，界面类似VisualStudio，但体积要小的多。开发环境包括多页面窗口、工程编辑器以及调试器等，在工程编辑器中集合了编辑器、编译器、连接程序和执行程序，提供高亮度语法显示，以减少编辑错误，还有完善的调试
2、功能，能够适合初学者与编程高手的不同需求，是学习C或C+的首选开发工具。C语言程序设计一般步骤为：（1）分析问题，设计解决方案；（2）编写C语言程序代码；（3）上机调试（编辑、编译、链接、执行）。通常，一个提供给程序员使用的专业函数库由以下部分组成：u头文件（*.h）：函数原型、宏常量定义等。u库文件（*.lib）：函数的二进制代码。u动态链接库（*.dll）：专业函数库，程序运行时调用。数组与结构PARTTWO2.2.1数组在语言中，数组与结构均属于构造数据类型，即每个数组或结构可以包含多个数组或结构元素，这些元素可以是基本数据类型也可以是构造类型。数组与结构的定义与使用相对于简单数据类型复
3、杂。2.2.1数组1数组的定义把具有相同类型的若干变量按有序的形式组织起来，这些按序排列的同类数据元素的集合称为数组。按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。inta5，定义了一个整数型数组，数组名为a，数组的大小为5，即有5个元素：a0，a1，a2，a3，a4。2数组使用中的注意事项数组使用中需注意以下几点：（1）C语言中数组元素的下标从0开始。（2）在相同作用域内，数组名不能和程序中其它变量名相同。（3）数组的类型实际上是指数组元素的取值类型。对于同一个数组，其所有元素的数据类型都是相同的。（4）不能在方括号中用变量来表示元素的个数，但可以是符号
4、常数或常量表达式。3数组元素的初始化数组元素的初始化即对数组元素赋初值。对全部数组元素赋初值，可以省略方括号内的数组长度值。例如：inta5=1,2,3,4,5;或者：inta=1,2,3,4,5;表示定义了整型数组a，a中有5个元素，它们的初值分别是：a0=1、a1=2、a2=3、a3=4、a4=5。对数组的前面部分元素赋初值，不可以省略方括号内的数组长度值。例如：inta5=1,2;表示整型数组a中有5个元素，其中数组元素a0的初值为1，a1的初值为2，a2、a3、a4、a5的初值为默认值0。例2.1求Fibonacci数列的前30项并输出它们。注：Fibonacci数列定义为：F(0)=
5、1，F(1)=1，F(n)=F(n-1)+F(n-2)，即1，1，2，3，5，8，13，21，34，55，89，#includeusingnamespacestd;intmain()inti;intf30=1,1;/初始化数组前2个元素for(i=2;i30;i+)fi=fi-1+fi-2;for(i=0;i30;i+)coutfiendl;2数组使用中的注意事项数组使用中需注意以下几点：（1）C语言中数组元素的下标从0开始。（2）在相同作用域内，数组名不能和程序中其它变量名相同。（3）数组的类型实际上是指数组元素的取值类型。对于同一个数组，其所有元素的数据类型都是相同的。（4）不能在方括号中
6、用变量来表示元素的个数，但可以是符号常数或常量表达式。2.2结构1结构的定义结构的定义结构体是用户自定义的新数据类型，在结构体中可以包含若干个不同数据类型的数据项，从而使这些数据项组合起来反映某一个信息。struct结构体名数据类型成员名1；数据类型成员名2；数据类型成员名n；例如：定义结构体student描述学生信息：structstudentlongid;/学号charname20;/姓名intsex;/性别intage;/年龄charaddress80;/家庭2.2结构 2结构体变量的声明结构体变量的声明（1）定义结构时声明struct student long id;char name
7、20;char addr30;student1,student2;（2）定义结构体后声明struct student long id;char name20char addr30;struct student s1,s2；/*声明结构体变量s1,s2 */（3）使用typedef 语句定义结构体 typedef struct long id;char name20;char addr30;student;student s1;student并非结构体变量，而是结构体类型(相当于struct student)。student就是一个新的类型名，并且是结构体类型名。3结构体数据成员的访问一个结构体
8、中包含多个数据成员，成员变量可以是简单数据类型或者数组和结构。可以通过以下方式访问结构体数据成员。（1）通过结构体变量名访问数据成员（2）通过结构体指针来访问数据域。例2.2设计student结构体变量，访问并输出结构体数据成员。#include#includetypedefstruct/*定义结构体student*/longid;charname20;charsex;intage;charaddress80;charphone20;student;intmain()/通过结构体变量名访问数据成员students1;/声明创建一个结构体变量s1/s1.id=98;/为s1的数据子域提供数据s1
9、.age=21;strcpy(s1.name,”李明”);/输出结构体变量s1的内容printf(“n学号:%d”,s1.id);printf(“n姓名:%s”,s1.name);printf(“n年龄:%d”,s1.age);/通过结构体指针来访问数据域student*s2;/声明指针变量ps2=(student*)malloc(sizeof(student);/分配存储单元，首地址赋给p指针s2-age=20;(*s2).id=100;printf(“n学号:%d”,s2-id);printf(“n年龄:%d”,s2-age);指针PARTTHREE指针是语言中广泛使用的一种数据类型，运用
10、指针编程是语言最主要的风格之一。使用指针可以使程序简洁、紧凑、高效；有效地表示复杂的数据结构；能很方便地使用数组和字符串；动态分配内存，直接访问内存地址；得到多于一个的函数返回值等，极大地丰富了语言的功能。正确理解和使用指针也是初学者在语言编程中的主要难点之一。2.3.1 指针的定义及运算1指针变量的定义C语言中有各种类型的变量，变量的类型决定所分配内存单元的大小，如：整型int是2字节，长整型long是4字节。每一个变量在内存中都有一个存储位置，这个位置就是该变量的地址，对变量值的存取是通过地址进行的。C语言中用指针变量来存放另一变量的地址。格式为：*；例如：以下pi，pa，pp均为指针变量
11、。int*pi;/pi为指向整型变量的指针char(*pa)3;/pa为指向数组空间的指针int*pp;/pp为指向指针变量的指针指针的类型是它所指向变量的类型，而不是指针本身数据值的类型，类型的不同，并不影响指针本身空间大小的不同（都是内存地址值），但却决定了指针所指向的空间的不同，也带来了对指针所指向空间的不同操作。2指针变量的运算（1）指针的引用和赋值定义一个指针后，必须先给它赋值后才能引用，否则易出错。体会以下操作运算，理解取地址运算符&，指针运算符*的操作。inti,*p1,*p2;i=6;p1=&i;/赋给同类型的变量地址值p2=p1;/赋给同类型的指针变量的值*p1=6;/给p1
12、所指向的变量赋值6*p2=3;/给p2所指向的变量赋值3（2）指针的加减运算指针的类型是它所指向变量的类型，指针的加减运算对应了指针所指向的空间的变化。例如：int a10,*p;p=a;/p指向数组a中的a0元素 p=p+1;/这时p指向a1指针和数组分别有如下的特征。指针：动态分配，初始空间小。数组：索引方便，初始空间大。指针的值是数据存放位置的地址，指针可以随时指向任意类型的内存块，它的特征是可变。数组的本质是一系列的变量。数组名对应着一块内存，其地址与容量在生命期内保持不变，只有数组的内容可以改变。实际应用中数组的维数有时是需动态生成的，所以常用指针来操作动态内存。当数组作为函数的参数
13、进行传递时，该数组自动退化为同类型的指针。2.3.2 数组指针和指针数组 1数组指针数组指针是指向数组的指针，例如：int(*p)5;()优先级高，首先说明p是一个指针，指向一个整型的一维数组，这个一维数组的长度是5，也可以说是p的步长。也就是说执行p+1时，p要跨过5个整型数据的长度。如要将二维数组赋给指针，应这样赋值：inta34;int(*p)4;/该语句是定义一个数组指针，指向含4个元素的一维数组。p=a;/将该二维数组的首地址赋给p，也就是a0或&a00。p+;/该语句执行过后，也就是p=p+1，p跨过行a0指向了行a1所以数组指针也称指向一维数组的指针，亦称行指针。2指针数组指针数
14、组是指针构成的数组。首先它是一个数组，数组的元素都是指针，数组占多少个字节由数组本身的大小决定，每一个元素都是一个指针。例如：int*p5。优先级高，先与p结合成为一个数组，再由int*说明这是一个整型指针数组，它有5个指针类型的数组元素。这里执行p+1时，则p指向下一个数组元素。注意：p=a；这样赋值是错误的，因为p是个不可知的表示，只存在p0、p1、.p4，而且它们分别是指针变量可以用来存放变量地址。但可以*p=a;这里*p表示指针数组第一个元素的值，即a的首地址的值。在编程中，选择使用指针数组主要有如下两个原因：各个指针内容可以按需要动态生成，避免了空间浪费。各个指针呈数组形式排列，索引
15、起来非常方便。指向结构体变量的指针就是该结构变量所占据的内存段的起始地址。指针变量也可以用来指向结构体数组中的成员。C语言提供了指向结构体变量的运算符-，例如p-num表示指针p当前指向结构体变量中的成员num。p-num和(*p).num等价。分析以下结构体指针运算。structstudent*p;p-n/得到p指向的结构体变量中的成员n的值p-n+/p指向的结构体变量中的成员n的值，用完该值后使它加1+p-n/p指向的结构体变量中的成员n的值，并使之加1，然后再使用它2.3.3 结构体指针结构体指针1函数指针 指针变量可以指向变量地址、数组、字符串、动态分配地址，同时也可指向函数，每一个函
16、数在编译时，系统会分配给该函数一个入口地址，函数名表示这个入口地址，指向函数的指针变量称之函数指针变量。函数指针可以用来调用函数和作为参数传递。例如：intfun(int，char);/p是函数指针，指向一个参数为int，char的函数，该函数返回一个整数。int(*p)()；pfun；2.3.4 函数指针与指针函数2指针函数 函数返回值可以是int、char、float等，也可以为地址值。返回值是地址值的函数称指针函数。当一个函数声明其返回值为一个指针时，实际上就是返回一个地址给调用函数，以用于需要指针或地址的表达式中。例如：float*fun()；/fun是一个指针函数，它返回一个指向fl
17、oat型数据的指针。float*p；pfun(a)；递归PARTFOUR递归是解决很多复杂问题的有效设计方法。所谓递归即一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，通过递归可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。能采用递归描述的算法通常有这样的特征：u原始规模为N的问题可转化为解决方法相同的新问题。u新问题的规模比原始问题小。u新问题又可转化为解决方法相同的规模更小的新问题，特别地，当规模N=1时，能直接得解。递归程序的执行过程可分为递推和回归两个阶段。2
18、.4.1 递归的定义递归的定义递归分直接递归和间接递归两种。若在一个函数的定义中出现了对自身的调用，称之为直接递归。例如：funa()funa()；若一个函数f的定义中包含了对函数g的调用，而g的实现过程又调用了f，即函数调用形成了一个环状调用链，这种方式称之为间接递归。例如：funa()funb()；funb()funa();2指针数组指针数组是指针构成的数组。首先它是一个数组，数组的元素都是指针，数组占多少个字节由数组本身的大小决定，每一个元素都是一个指针。例如：int*p5。优先级高，先与p结合成为一个数组，再由int*说明这是一个整型指针数组，它有5个指针类型的数组元素。这里执行p+1
19、时，则p指向下一个数组元素。注意：p=a；这样赋值是错误的，因为p是个不可知的表示，只存在p0、p1、.p4，而且它们分别是指针变量可以用来存放变量地址。但可以*p=a;这里*p表示指针数组第一个元素的值，即a的首地址的值。在编程中，选择使用指针数组主要有如下两个原因：各个指针内容可以按需要动态生成，避免了空间浪费。各个指针呈数组形式排列，索引起来非常方便。1问题定义是递归的有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。例2.3用递归算法计算10的阶乘。阶乘的定义：写成函数即为：这种函数定义形式是用阶乘
20、函数自己本身定义了自身，故是一种递归定义。2.4.2 应用递归的问题类型#include using namespace std;long fact(int n)long y;if(n=0)return 1;else y=fact(n-1);return n*y;int main()long jc;jc=fact(10);coutjcendl;2数据结构是递归的数据结构是递归的 有些变量其数据结构即包括递归说明。例如链表的结点结构定义为：struct node int data;struct node*next;对于递归数据结构，采用递归方法编写算法简单有效。例2.4求链表中的最大整数的递归算
21、法。#includeusingnamespacestd;structLNodeintdata;LNode*next;intGetMax(LNode*L,intMax)if(L=NULL)returnMax;if(L-dataMax)Max=L-data;returnGetMax(L-next,Max);intmain()LNode*L;LNode*p;intn;intMax=-32556;coutn;cout请输入n个数:n;for(inti=0;ip-data;p-next=L-next;L-next=p;cout链表中最大数为：n;coutGetMax(L,Max);return0;3问题
22、的求解方法是递归的问题的求解方法是递归的 有些问题在求解过程中需要采用递归方法。例如：有序数组中查找某一数据是否存在于数组中的折半查找算法，其求解过程便是一个递归求解的过程。即不断在前一次区间一半的搜索区间范围内重复着与前一次搜索相同的操作。例2.5 二分法查找的递归实现#includeusingnamespacestd;intsearch(int,int,int,int);intmain()intkey;intword=1,3,6,9,12,14,17,19,22,24,25;intleft=0;intright=sizeof(word)/sizeof(int)-1;/计算数组长度写得不正确
23、intresult;key=9;result=search(word,left,right,key);cout要查找的数的序号为：resultright)return-1;elseintmiddle=(left+right)/2;if(amiddle=key)returnmiddle;elseif(keyamiddle)/这里key是和amiddle比较，而非middle;right=middle-1;returnsearch(a,left,right,key);elseleft=middle+1;returnsearch(a,left,right,key);回溯法也叫试探法，每次试着往前走，
24、一直走到不通，然后撤回，重新试探。递归方法一般都有回溯的过程。回溯法的要素：(1)状态:作为递归的值参。(2)边界条件:作为递归的结束条件。(3)递归范围:作为for循环的初值和终值。(4)约束条件:满足解的条件。2.4.3 递归与回溯递归与回溯例例2.6 N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。分析：由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探；按行放置皇后，每一行放一皇后；对每一行所放置的皇后按列进行试探；若某个位置能放，则放，否则试放下一个位置；若某一行没有
25、任何一个位置可放，则表示前面的皇后没放好，需要回溯。若n个皇后都放好了，则得到了一个解。#define N 8#include iostream.h#include math.hint solutionN，sols;int place(int row)/判与前面行上放置的皇后有否位置冲突 int j;for(j=0;j row;j+)if(abs(row-j)=abs(solutionrow-solutionj)|solutionj=solutionrow)return 0;else return 1;/无冲突返回1，否则返回0voidqueens(introw)intk;if(N=row)s
26、ols+;for(k=0;kN;k+)cout(k+1，solutionk+1);coutendl;elseinti;for(i=0;iN;i+)solutionrow=i;if(place(row)queens(row+1);voidmain(void)queens(0);coutTotalSolutions:solsendl;运行结果显示若N=8，八皇后问题有92个解。#define N 8#include iostream.h#include math.hint solutionN，sols;int place(int row)/判与前面行上放置的皇后有否位置冲突 int j;for(j
27、=0;j row;j+)if(abs(row-j)=abs(solutionrow-solutionj)|solutionj=solutionrow)return 0;else return 1;/无冲突返回1，否则返回0将递归算法转化为非递归算法可以采用如下方法：(1)通过分析，跳过分解过程，直接用循环结构的算法实现求解过程，大多采用迭代方法。(2)利用栈保存参数，由于栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。1递归与迭代递归是自顶向下逐步分解问题，最后自下向顶计算。迭代是自下向顶的计算过程，每一个递归算法总有一个迭代算法对应，效率上，迭代效率高，递归低。2.
28、4.4 递归与非递归程序的转换递归与非递归程序的转换例例2.7 用迭代法求10!#include using namespace std;int main()int i,s,n;s=1;n=10;for(i=1;i=n;i+)s=s*i;coutsendl;迭代过程：1!=1 2!=1!*2 3!=2!*3 n!=(n-1)!*n 2栈的应用递归函数在执行过程中其实是用栈保存未完成的工作，栈是一种先进后出，后进先出的数据结构，在第三章中会涉及到。栈在适当的时候从中取出并执行，系统保存了工作的数据和状态，数据就是函数的局部变量，#define N 8#include iostream.h#include math.hint solutionN，sols;int place(int row)/判与前面行上放置的皇后有否位置冲突 int j;for(j=0;j row;j+)if(abs(row-j)=abs(solutionrow-solutionj)|solutionj=solutionrow)return 0;else return 1;/无冲突返回1，否则返回0
