1、第第2 2章章 C C程序设计语言基础程序设计语言基础C程序设计语言作为本书中数据结构的算法描述语言程序设计语言作为本书中数据结构的算法描述语言，既具有高级语言的特点，又具有汇编语言的特点，被广，既具有高级语言的特点，又具有汇编语言的特点，被广泛应用于系统软件设计和应用软件设计，并且经久不衰。泛应用于系统软件设计和应用软件设计，并且经久不衰。本章主要目的是复习本章主要目的是复习C程序设计语言的一些重点和难点，程序设计语言的一些重点和难点，为数据结构的学习扫清障碍。为数据结构的学习扫清障碍。2.1 2.1 开发环境介绍开发环境介绍C程序设计语言（也常称为程序设计语言（也常称为C语言）的开发环境有
2、语言）的开发环境有LCC、Turbo C2.0、Visual C+、Borland C+等多种，本等多种，本节主要介绍常使用的节主要介绍常使用的Turbo C2.0和和Visual C+6.0开发环境开发环境。2.1.1 Turbo C 2.02.1.1 Turbo C 2.0开发环境介绍开发环境介绍1 运行运行Turbo C2.02 Turbo C2.0环境设置环境设置3 Turbo c2.0的使用的使用2.1.2 Visual C+6.02.1.2 Visual C+6.0开发环境介绍开发环境介绍用用Visual C+6.0编写编写C语言程序，需要两个步骤：一语言程序，需要两个步骤：一是建
3、立一个控制台项目；二是在该控制台项目中添加一个是建立一个控制台项目；二是在该控制台项目中添加一个.C的文件。的文件。2.2 2.2 递归与非递归递归与非递归一个较大的程序包含若干个具有独立的功能的模块，一个较大的程序包含若干个具有独立的功能的模块，每一个模块实现一个特定的功能，这才是良好的程序设计每一个模块实现一个特定的功能，这才是良好的程序设计风格。在风格。在C语言中，通过函数实现模块的功能，一个语言中，通过函数实现模块的功能，一个C语言语言程序由一个主函数和若干个函数组成。递归是程序由一个主函数和若干个函数组成。递归是C语言程序语言程序设计中常见的函数调用形式，也是学习设计中常见的函数调用
4、形式，也是学习C语言的一个重点语言的一个重点和难点。和难点。2.2.1 2.2.1 函数的递归调用函数的递归调用函数的递归调用指的是在调用一个函数的过程中，又函数的递归调用指的是在调用一个函数的过程中，又出现了对函数自身的调用，这种函数称为递归函数。其中出现了对函数自身的调用，这种函数称为递归函数。其中，递归调用分为直接递归调用和间接递归调用。一个函数，递归调用分为直接递归调用和间接递归调用。一个函数在函数定义体内直接调用自己称为直接递归调用，一个函在函数定义体内直接调用自己称为直接递归调用，一个函数在经过一系列的中间调用，通过其他函数调用自己的称数在经过一系列的中间调用，通过其他函数调用自己
5、的称为间接递归调用。为间接递归调用。函函 数数 func()函函 数数 func()函函 数数 func1()函函 数数 func2()函函 数数 func3()2.2.2 2.2.2 递归应用举例递归应用举例下面我们以一个例子讲解递归的调用。下面我们以一个例子讲解递归的调用。2.2.3 2.2.3 一般递归转化为非递归一般递归转化为非递归通过分析递归实现求通过分析递归实现求n个自然数的和，我们可以把它个自然数的和，我们可以把它转化为非递归实现。转化为非递归实现。迭代与递归迭代与递归：迭代和递归是程序设计中常用的两种结：迭代和递归是程序设计中常用的两种结构。任何能使用递归解决的问题都能使用迭代
6、的方法解决构。任何能使用递归解决的问题都能使用迭代的方法解决。迭代和递归的区别是：迭代使用的是循环结构，递归使。迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。使用递归能够使程序的结构更清晰，设用的是选择结构。使用递归能够使程序的结构更清晰，设计出的程序更简洁、程序更容易让人理解。计出的程序更简洁、程序更容易让人理解。2.3 2.3 指针指针指针是指针是C语言中最难掌握的概念，但同时也是最重要语言中最难掌握的概念，但同时也是最重要的概念。指针常常用在函数的参数传递和动态分配内存中的概念。指针常常用在函数的参数传递和动态分配内存中，在数据结构中，指针的使用也非常频繁。指针常常与地
7、，在数据结构中，指针的使用也非常频繁。指针常常与地址、变量、数组和函数联系在一起。本节的主要学习内容址、变量、数组和函数联系在一起。本节的主要学习内容是大家常常容易混淆的概念，包括指针变量、指针变量的是大家常常容易混淆的概念，包括指针变量、指针变量的引用、指针与数组、函数指针与指针函数。引用、指针与数组、函数指针与指针函数。2.3.1 2.3.1 指针变量指针变量指针是一种变量，也称指针变指针是一种变量，也称指针变量，它的值是内存地址。一般的变量，它的值是内存地址。一般的变量通常直接包含一个具体的值，例量通常直接包含一个具体的值，例如整数、浮点数和字符。指针包含如整数、浮点数和字符。指针包含的
8、是变量的地址，而变量又拥有自的是变量的地址，而变量又拥有自己的具体值。变量名直接引用了一己的具体值。变量名直接引用了一个值，指针是间接地引用了一个值个值，指针是间接地引用了一个值。一个变量的地址称为该变量的一个变量的地址称为该变量的“指针指针”。如果有一个变量用来存。如果有一个变量用来存放另一个变量的地址，则称这个变放另一个变量的地址，则称这个变量为指针变量。在量为指针变量。在C语言中，变量语言中，变量在使用前都需要提前声明。在使用前都需要提前声明。2.3.1 2.3.1 指针变量指针变量int q=5,*qPtr;qPtr=&q;2.3.2 2.3.2 指针变量的引用指针变量的引用指针变量和
9、变量一样，都可以对数据进行操作，指针指针变量和变量一样，都可以对数据进行操作，指针变量的操作主要是通过取地址运算符变量的操作主要是通过取地址运算符&和指针运算符和指针运算符*进行进行实现的。例如，实现的。例如，&a指的是变量指的是变量a的地址，的地址，*ptr表示变量表示变量ptr所指向的内存单元存放的内容。所指向的内存单元存放的内容。例例2_3 变量与指向该变量的指针演示程序。变量与指向该变量的指针演示程序。2.3.3 2.3.3 指针与数组指针与数组1指向数组元素的指针指向数组元素的指针int a5=10,20,30,40,50;int*aPtr;2.3.3 2.3.3 指针与数组指针与数
10、组指针引用数组元素的应用举例。指针引用数组元素的应用举例。例例2_4 用指针引用数组元素并打印输出。用指针引用数组元素并打印输出。2.3.3 2.3.3 指针与数组指针与数组2数组指针数组指针int(*p)4;int a34=1,2,3,4,5,6,7,8,9,10,11,12;p=a;2.3.3 2.3.3 指针与数组指针与数组数组指针的应用举例。数组指针的应用举例。例例2_5 用指针引用数组元素并打印输出。用指针引用数组元素并打印输出。2.3.3 2.3.3 指针与数组指针与数组3指针数组指针数组指针数组是一个数组，数组中的元素是指针类型的数指针数组是一个数组，数组中的元素是指针类型的数据
11、。也就是说，指针数组中的元素，每一个都是一个指针据。也就是说，指针数组中的元素，每一个都是一个指针变量。指针数组的定义如下：变量。指针数组的定义如下：int*p4;C P r o g r a m m i n g L a n g u a g e 0A s s e m b l y L a n g u a g e 0J a v a L a n g u a g e 0N a t u r a l L a n g u a g e 02.3.3 2.3.3 指针与数组指针与数组指针数组的应用举例。指针数组的应用举例。例例2_6 用指针数组保存字符串并将字符元素并打印输用指针数组保存字符串并将字符元素并打印输
12、出。出。2.3.4 2.3.4 函数指针与指针函数函数指针与指针函数函数指针与指针函数也是常常容易混淆的概念。与数函数指针与指针函数也是常常容易混淆的概念。与数组指针和指针数组类似，前者强调的指针，后者强调的是组指针和指针数组类似，前者强调的指针，后者强调的是函数。函数。1函数指针函数指针2指针函数指针函数2.3.4 2.3.4 函数指针与指针函数函数指针与指针函数函数指针应用举例。函数指针应用举例。例例2_7 通过一个函数求两个数的和，并通过函数指针通过一个函数求两个数的和，并通过函数指针调用该函数。调用该函数。void main()int a=3,b=5;int(*fun)(int,int
13、);printf(%d+%d=%dn,a,b,Sum(a,b);/*通过函数名调用通过函数名调用*/fun=Sum;/*函数指针指向求和函数函数指针指向求和函数*/printf(%d+%d=%dn,a,b,(*fun)(a,b);/*函数指针调用函数函数指针调用函数*/int Sum(int m,int n)return m+n;2.3.4 2.3.4 函数指针与指针函数函数指针与指针函数函数指针应用举例。函数指针应用举例。例例2_8 函数指针作为函数参数，实现冒泡排序的升序函数指针作为函数参数，实现冒泡排序的升序排列和降序排列。排列和降序排列。2.4 2.4 参数传递参数传递在在C语言中，函
14、数的参数传递的方式通常有两种：一语言中，函数的参数传递的方式通常有两种：一种是传值的方式，另一种是传地址的方式。参数传递通常种是传值的方式，另一种是传地址的方式。参数传递通常是我们经常遇到的情况。本节主要学习的内容包括传值调是我们经常遇到的情况。本节主要学习的内容包括传值调用、传地址调用。用、传地址调用。2.4.1 2.4.1 传值调用传值调用在函数调用时，一般情况下，调用函数和被调用函数在函数调用时，一般情况下，调用函数和被调用函数之间会有参数传递。调用函数后面括号里面的参数是实际之间会有参数传递。调用函数后面括号里面的参数是实际参数，被调用函数中的参数是形式参数。传值调用是建立参数，被调用
15、函数中的参数是形式参数。传值调用是建立参数的一个副本并把值传递给形式参数，在被调用函数中参数的一个副本并把值传递给形式参数，在被调用函数中修改形式参数的值，并不会影响到调用函数实际参数的值修改形式参数的值，并不会影响到调用函数实际参数的值。2.4.2 2.4.2 传地址调用传地址调用C语言通过指针（地址）实现传地址调用。如果在调语言通过指针（地址）实现传地址调用。如果在调用函数时，需要在被调用函数中修改参数值，则需要把实用函数时，需要在被调用函数中修改参数值，则需要把实际参数的地址传递给形式参数。下面我们还以求两个整数际参数的地址传递给形式参数。下面我们还以求两个整数的较大者来说明参数传地址调
16、用方式的使用及传递情况。的较大者来说明参数传地址调用方式的使用及传递情况。2.4.2 2.4.2 传地址调用传地址调用例例2_12 编写一个函数求两个整数的较大者和较小者，用传编写一个函数求两个整数的较大者和较小者，用传地址方式实现。地址方式实现。&a3&b4ab&a3&b4ab&a&bxy*x*y2.4.2 2.4.2 传地址调用传地址调用&a4&b3ab&a&bxy*x*y&a4&b3ab2.4.2 2.4.2 传地址调用传地址调用例例2_13 把数组中的把数组中的n个元素的值分别扩大个元素的值分别扩大5倍，要求倍，要求数组名作为参数。数组名作为参数。2.5 2.5 结构体与联合体结构体与
17、联合体结构体和联合体（或称共用体）是自定义的数据类型结构体和联合体（或称共用体）是自定义的数据类型。常用于处理非数值型数据，在数据结构中，使用非常广。常用于处理非数值型数据，在数据结构中，使用非常广泛，如链表、队列、树等。本节的主要学习内容包括结构泛，如链表、队列、树等。本节的主要学习内容包括结构体、联合体及它们的使用。体、联合体及它们的使用。2.5.1 2.5.1 结构体的定义结构体的定义结构体是用其他类型构造出来的数据类型。结构体类结构体是用其他类型构造出来的数据类型。结构体类型常常用于存储文件中的记录。如果仅仅用型常常用于存储文件中的记录。如果仅仅用C语言中基本语言中基本的数据类型，是无
18、法进行描述的。的数据类型，是无法进行描述的。stu1.age=20;stu1.name=Wang Chong;stu1.number=1234;stu1.sex=m;stu1.score=89.0;2.5.2 2.5.2 指向结构体的指针指向结构体的指针指针可以指向整型、浮点型、字指针可以指向整型、浮点型、字符等基本类型变量外，同样也可以指符等基本类型变量外，同样也可以指向结构体变量。指向结构体变量的指向结构体变量。指向结构体变量的指针的值是结构体变量的起始地址。指针的值是结构体变量的起始地址。指针可以指向结构体，也可以指向结构针可以指向结构体，也可以指向结构体数组。指向结构体的指针和指向变体
19、数组。指向结构体的指针和指向变量和指向数组的指针的用法类似。量和指向数组的指针的用法类似。2.5.3 2.5.3 联合体及应用联合体及应用与结构体一样，联合体也是一种派生的数据类型。但与结构体一样，联合体也是一种派生的数据类型。但是与结构体不同的是，联合体的成员共享同一个存储空间是与结构体不同的是，联合体的成员共享同一个存储空间。union uchar x;float y;double z;2.6 2.6 动态内存分配与释放动态内存分配与释放动态内存分配与释放经常用在数据结构中的链表、树动态内存分配与释放经常用在数据结构中的链表、树和图结构。动态内存分配在需要时进行分配，不需要时即和图结构。动
20、态内存分配在需要时进行分配，不需要时即释放，不需要提前分配。本节的主要学习内容包括内存的释放，不需要提前分配。本节的主要学习内容包括内存的动态分配与释放及链表。动态分配与释放及链表。2.6.1 2.6.1 内存动态分配与释放内存动态分配与释放内存的动态分配需要使用内存的动态分配需要使用malloc函数、函数、free函数和函数和sizeof运算符实现。运算符实现。函数函数malloc的原型是：的原型是：void*malloc(unsigned int size);函数函数malloc的作用是在内存中分配一个长度为的作用是在内存中分配一个长度为size的连的连续存储空间。函数的返回值是一个指向分
21、配空间的起始位续存储空间。函数的返回值是一个指向分配空间的起始位置的指针。如果分配空间失败，则返回置的指针。如果分配空间失败，则返回NULL。函数函数malloc和和free一般成对使用，在使用完内存空间一般成对使用，在使用完内存空间时，要记得用时，要记得用free将内存空间释放。使用函数将内存空间释放。使用函数malloc时，最时，最好要测试是否分配成功。已经释放掉的内存，不可以重新好要测试是否分配成功。已经释放掉的内存，不可以重新使用。使用。2.6.2 2.6.2 链表链表链表是一种常用的数据结构。链表通过自引用结构体链表是一种常用的数据结构。链表通过自引用结构体类型的指针成员指向结构体本
22、身建立起来。自引用结构体类型的指针成员指向结构体本身建立起来。自引用结构体包含一个指针成员，该指针指向与结构体一样的类型。包含一个指针成员，该指针指向与结构体一样的类型。abcd/结点结点headabcd/结点结点head头结点头结点2.6.2 2.6.2 链表链表2.6.2 2.6.2 链表链表2.7 2.7 小结小结本章主要介绍了本章主要介绍了C程序设计语言的基础，本章的内容程序设计语言的基础，本章的内容也是数据结构学习的一个基础。本章首先对目前常用的也是数据结构学习的一个基础。本章首先对目前常用的C语言开发环境语言开发环境Turbo C 2.0和和VC 6.0做了介绍。接着本章围做了介绍
23、。接着本章围绕着绕着C语言中的难点进行了介绍，并给出了例子。其中包语言中的难点进行了介绍，并给出了例子。其中包括函数的递归，指针，参数传递，结构体，最后还介绍了括函数的递归，指针，参数传递，结构体，最后还介绍了链表及操作。链表及操作。函数的递归是函数的递归是C语言及算法设计中经常遇到的问题，语言及算法设计中经常遇到的问题，递归可以把复杂的问题变成与原问题类似且规模小的问题递归可以把复杂的问题变成与原问题类似且规模小的问题加以解决，使用递归使程序的结构很清晰，更具有层次性加以解决，使用递归使程序的结构很清晰，更具有层次性，写成的程序简洁易懂。使用递归只需要少量的程序就可，写成的程序简洁易懂。使用递归只需要少量的程序就可以描述解决问题需要的重复计算过程，大大减少了程序的以描述解决问题需要的重复计算过程，大大减少了程序的代码量。代码量。
