零基础学数据结构(第2版)

    陈锐 等著

    ISBN：978-7-111-46861-5

    本书纸版由机械工业出版社于2014年出版，电子版由华章分社(北京

    华章图文信息有限公司)全球范围内制作与发行。

    版权所有，侵权必究

    客服热线：+ 86-10-68995265

    客服信箱：service@bbbvip.com

    官方网址：www.hzmedia.com.cn

    新浪微博 @研发书局

    腾讯微博 @yanfabook目录

    前言

    第一篇 基础知识

    第1章 数据结构概述

    1.1 为什么要学习数据结构

    1.2 基本概念和术语

    1.3 数据的逻辑结构与存储结构

    1.4 抽象数据类型及其描述

    1.5 算法

    1.6 算法分析

    1.7 学好数据结构的秘诀

    1.8 习题

    第2章 C语言基础

    2.1 C语言开发环境

    2.2 递归与非递归

    2.3 指针

    2.4 参数传递

    2.5 结构体与联合体

    2.6 链表

    2.7 小结2.8 习题

    第二篇 线性数据结构

    第3章 线性表

    3.1 线性表的定义及抽象数据类型

    3.2 线性表的顺序表示与实现

    3.3 线性表的链式表示与实现

    3.4 循环单链表

    3.5 双向链表

    3.6 静态链表

    3.7 综合案例：一元多项式的表示与相乘

    3.8 小结

    3.9 习题

    第4章 栈

    4.1 栈的定义与抽象数据类型

    4.2 栈的顺序表示与实现

    4.3 栈的链式表示与实现

    4.4 栈的典型应用

    4.5 栈与递归

    4.6 小结

    4.7 习题

    第5章 队列5.1 队列的定义与抽象数据类型

    5.2 队列的顺序存储及实现

    5.3 队列的链式存储及实现

    5.4 双端队列

    5.5 综合案例：动画模拟停车场管理系统

    5.6 小结

    5.7 习题

    第6章 串

    6.1 串的定义及抽象数据类型

    6.2 串的顺序表示与实现

    6.3 串的堆分配表示与实现

    6.4 串的块链式存储表示与实现

    6.5 串的模式匹配

    6.6 小结

    6.7 习题

    第7章 数组

    7.1 数组的定义及抽象数据类型

    7.2 数组的顺序表示与实现

    7.3 特殊矩阵的压缩存储

    7.4 稀疏矩阵的压缩存储

    7.5 稀疏矩阵应用举例7.6 稀疏矩阵的十字链表表示与实现

    7.7 小结

    7.8 习题

    第8章 广义表

    8.1 广义表的定义及抽象数据类型

    8.2 广义表的头尾链表表示与实现

    8.3 广义表的扩展线性链表表示与实现

    8.4 小结

    8.5 习题

    第三篇 非线性数据结构

    第9章 树

    9.1 树的相关概念及抽象数据类型

    9.2 二叉树的相关概念及抽象数据类型

    9.3 二叉树的存储表示与实现

    9.4 遍历二叉树

    9.5 遍历二叉树的应用

    9.6 线索二叉树

    9.7 树、森林与二叉树

    9.8 综合案例：哈夫曼树

    9.9 小结

    9.10 习题第10章 图

    10.1 图的定义与相关概念

    10.2 图的存储结构

    10.3 图的遍历

    10.4 图的连通性问题

    10.5 有向无环图

    10.6 最短路径

    10.7 图的应用举例

    10.8 小结

    10.9 习题

    第四篇 查找与排序

    第11章 查找

    11.1 基本概念

    11.2 静态查找

    11.3 动态查找

    11.4 B-树与B+树

    11.5 哈希表

    11.6 小结

    11.7 习题

    第12章 内排序

    12.1 基本概念12.2 插入排序

    12.3 交换排序

    12.4 选择排序

    12.5 归并排序

    12.6 基数排序

    12.7 小结

    12.8 习题

    第13章 外排序

    13.1 外存的存取特性

    13.2 磁盘排序

    13.3 磁带排序

    13.4 小结

    参考文献

    光盘内容前言

    《零基础学数据结构》自问世以来，已被许多高校选为数据结构

    教材，得到了众多读者的关心和问候，受到读者的喜欢和好评。广大

    读者非常期待第2版，同时对本书的修订提出了不少宝贵意见。有这么

    多热心读者关心本书，我感到非常欣慰，在此也对所有关注本书的朋

    友们说声谢谢!希望更多的朋友关注本书，以及提出更多的改进建

    议。

    经过修订后，本书案例更加丰富，语言表达更加简练、准确，替

    换了部分重复性的案例，保留了精华内容，修订了书中的错误和不足

    之处，保证所有程序能正确运行，视频讲解更加针对重点、难点进行

    分析。

    “数据结构”作为计算机专业的一门专业基础课程，对于初学者

    来说，许多专业术语较为抽象，不容易理解和掌握，本书采用通俗的

    语言进行讲解，针对每个知识点都给出例子和图表，便于读者理解和

    掌握。本书内容全面，涵盖数据结构的所有知识点，全书算法采用C语

    言实现，所有代码均在Visual C++6.0环境下调试通过，所有案例都是

    完整程序，能直接运行。本书不仅适合正在学习数据结构的学生作为自学教材，也适合作

    为计算机专业学生考研辅导用书和参加软考人员的辅导书。

    修订的内容

    1.更正了书中的错误

    本书第1版有些算法描述中存在一些不易察觉的错误，第2版重新

    对书中代码进行了全部调试，把错误的地方一一更正。根据读者提出

    的宝贵建议，对第1版中一些错误的表述也进行了修改。

    2.修订了书中的内容

    本书第1版有些概念描述不够准确，第2版对所有已发现的不恰当

    地方进行了修改，在不易理解的地方增加了图表，重新表述了许多概

    念和定义，使本书更易于理解，而且增加了近年考研题目，内容更加

    完善。

    3.补充替换书中的案例

    这次改版，删除了第1版的一些案例，并补充了一些较大型的案

    例，如迷宫问题、模拟停车场管理系统等，增加了近两年的考研算法试题，减少了一些重复性的案例，保留了一些具有代表性的案例，使

    本书更加实用。

    4.视频讲解突出重点、难点

    在本书配套的视频中，作者针对数据结构中的一些重点和难点部

    分进行详细分析，特别是对一些典型案例做了详细分析，通过学习本

    书并结合视频讲解，可使每一位读者都能真正理解并掌握数据结构中

    的每一个知识点。

    本书的第1～4章和第9章由陈锐编写，第7～8章由成建设编写，第

    5章由张立编写，第6章由李得强编写，其他章节由李铁塔、蔡洪涛、付海涛、段小涛、申文彬、郑苗苗编写。

    为什么要学数据结构

    如果你打算今后从事软件开发，或从事计算机科研、教学等工

    作，必须要学好数据结构这门课程。首先，因为数据结构作为计算机

    专业的专业基础课程，是计算机考研的必考科目之一，如果打算报考

    计算机专业的研究生，你必须学好它；其次，数据结构是计算机软

    考、计算机等级考试等相关考试的必考内容之一，要是想顺利通过这

    些考试，你也必须学好它；最后，数据结构还是你今后毕业，进入各软件公司、事业单位的必考内容之一，想要找到好工作，也必须学好

    它。

    即使你没有以上考虑，作为一名计算机从业人员，数据结构是其

    他后续计算机专业课程的基础，许多课程都会用到数据结构知识。有

    如此多的理由，你必须掌握好数据结构。

    如何学好数据结构

    对于初学者来说，数据结构这门课有许多抽象的东西，不是太容

    易掌握。万事开头难，只要你掌握了方法和技巧，学任何东西就会变

    得很容易，学习数据结构也是如此。要想学好数据结构，首先应该有

    信心，要有战胜困难的决心，特别一开始不要有畏惧心理，这一点很

    重要；其次就是要掌握好C语言，C语言是基础，因为本书中的算法都

    是用C语言描述的(其他大多数数据结构图书也采用C语言描述)，即

    使之前没有掌握好C语言也没有关系，只要有C语言基础就行，可以边

    学数据结构边巩固C语言知识。

    有了以上两点，你就离成功不远了，数据结构也没有那么可怕，其实就是概念抽象了点，本书已经进行了通俗的讲解，再多联系实际

    生活，学习数据结构就会变得很轻松。最后一点就是多上机，多思考，本书中所有算法都用C语言表述，并给出完整程序，你只需要把程序看懂，然后上机多调试，锻炼C语言

    的应用技巧，对数据结构中的一些算法思想就可以融会贯通，真正领

    会其中的内涵。

    如何使用本书

    本书全面讲解了数据结构的相关知识，案例非常丰富，第2版加入

    了作者对数据结构的理解，还修订了很多错误和不足之处。本书用通

    俗易懂的语言描述抽象的概念，配套视频针对重点和难点进行了讲

    解，方便大家理解与学习。

    本书可以作为学习数据结构的自学教材，也可以作为案头必备的

    参考书，值得珍藏。本书很适合初学数据结构的读者阅读，也可作为

    参加计算机考研学生的辅导书。

    在使用本书过程中，可以边看书，边听视频讲解，视频讲解主要

    针对本书中的难点和重点，每学完一部分内容，可以在电脑上调试本

    书配套的代码，认真领会算法的思想，并思考为什么要这样实现。

    相信在学完本书后，大家会在数据结构和算法方面有很大的收

    获。预祝大家在学习本书时有一个愉快的旅程。致谢

    我要感谢帮助本书问世的所有人，尤其是机械工业出版社的李华

    君编辑，他十分看重本书的应用价值，在他的努力下本书才得以顺利

    出版，对此，我深怀感激。

    还要感谢我的导师张蕾教授。她是对我职业生涯最有影响的人之

    一，她丰富的知识储备及敏锐的洞察力极大地影响了我的学习态度，促使我的学习能力和认识能力有了很大提高，也为本书的编写奠定了

    良好的知识与技术基础。

    耿国华老师在数据结构和算法领域有很高的造诣，耿教授在数据

    结构与算法领域给了我很大启发。

    还要感谢我的家人，在他们的默默付出与鼓励下，我才能顺利写

    完本书。

    最后还要感谢温县教育局电教馆全体同仁的帮助与鼓励，尤其要

    感谢张全仕馆长对我写作的关心与支持。

    由于作者水平有限，书中难免存在一些不足之处，恳请读者批评

    指正。读者可通过邮箱nwuchenrui@126.com与作者联系，也可通过QQ

    群(216732263)与作者交流。陈锐第一篇 基础知识

    第1章 数据结构概述

    数据结构是一门研究如何用计算机描述事物及其之间关系的学

    问，它是计算机学科的专业基础课程，是今后从事计算机软件开发的

    重要基础。它主要研究数据在计算机中的存储表示和对数据的处理方

    法。数据结构把数据划分为集合、线、树和图4种类型，后3种是数据

    结构研究的重点。本章旨在让读者对数据结构有个总体的把握，首先

    介绍了数据结构的有关概念，接着介绍了什么是抽象数据类型及抽象

    数据类型的描述方法，然后介绍了数据的逻辑结构与存储结构，最后

    介绍了算法的定义、算法的描述方法、算法设计的要求以及如何分析

    算法的效率高低。

    本章重点和难点：

    ·数据结构的基本概念

    ·什么是抽象数据类型

    ·如何计算算法的时间复杂度1.1 为什么要学习数据结构

    1.数据结构的发展变迁

    数据结构在计算机科学与技术专业中是一门综合性的专业基础

    课。在国外，数据结构作为一门独立的课程是从1968年才开始设立

    的，但在此之前其有关内容已散见于编译原理及操作系统之中。20世

    纪60年代中期，美国的一些大学开始开设相关课程，但当时的课程名

    称并不叫数据结构。

    1968年，美国的唐·欧·克努特教授开创了数据结构的最初体

    系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本

    较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪

    60年代末到70年代初出现了大型程序，软件也相对独立，结构化程序

    设计成为程序设计方法学的主要内容，人们越来越重视数据结构。

    从20世纪70年代中期到80年代，各种版本的数据结构著作相继出

    现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特

    殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方

    面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新

    的趋势，越来越被人们所重视。2.数据结构的地位

    在我国，数据结构已经不仅仅是计算机专业的核心课程，还是其

    他非计算机专业的主要选修课程之一。数据结构的研究不仅涉及计算

    机硬件的研究范围，而且与计算机软件的研究有着更密切的关系，无

    论是编译程序还是操作系统，都涉及数据元素在存储器中的分配问

    题。在研究信息检索时，也必须考虑如何组织数据，以便查找和存取

    数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬

    件和计算机软件三者之间的一门核心课程。

    开发所有计算机系统软件和应用软件都要用到各种类型的数据结

    构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算

    机程序设计语言是难以应付众多复杂问题的。要想有效地使用计算

    机、充分发挥计算机的性能，还必须学习和掌握好数据结构方面的有

    关知识。打好“数据结构”这门课程的扎实基础，对于学习计算机专

    业的其他课程，如操作系统、编译原理、数据库管理系统、软件工

    程、人工智能等都是十分有益的。

    在计算机发展的初期，人们使用计算机的目的主要是处理数值计

    算问题。当我们使用计算机来解决一个具体问题时，一般需要经过几

    个步骤，首先要从该具体问题中抽象出一个适当的数学模型；然后设

    计或选择一个解决此数学模型的算法；最后编出程序进行调试、测试，直至得到最终的解答。例如，求解桥梁结构中应力的数学模型的

    线性方程组，该方程组可以使用迭代算法来求解。

    由于当时所涉及的运算对象是简单的整型、实型或布尔类型数

    据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须

    重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数

    值计算问题显得越来越重要。据统计，当今处理非数值计算性问题占

    用了90%以上的机器时间。这类问题涉及的数据结构更为复杂，数据元

    素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类

    问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结

    构，才能有效地解决问题。

    学习数据结构的目的是为了了解计算机处理对象的特性，将实际

    问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与

    此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能

    训练来促进学生的综合应用能力和专业素质的提高。1.2 基本概念和术语

    本节主要介绍数据结构有关的一些基本概念和术语，以便读者在

    今后的学习过程中有统一的认识与理解。这些概念与术语将在以后的

    章节中频繁出现。

    1.数据

    数据(data)是描述客观事物的符号，能输入到计算机中并能被

    计算机程序处理的符号集合。它是计算机程序加工的“原料”。例

    如，一个文字处理程序(如Microsoft Word)的处理对象就是字符

    串，一个数值计算程序的处理对象就是整型和浮点型数据。因此，数

    据的含义非常广泛，如整型、浮点型等数值类型及字符、声音、图

    像、视频等非数值数据都属于数据范畴。

    2.数据元素

    数据元素(data element)是数据的基本单位，在计算机程序中

    通常作为一个整体考虑和处理。一个数据元素可由若干个数据项

    (data item)组成，数据项是数据不可分割的最小单位。例如，一个

    学校的教职工基本情况表包括编号、姓名、性别、籍贯、所在院系、出生年月及职称等数据项。这里的数据元素也称为记录。教职工基本

    情况如表1-1所示。

    表1-1 教职工基本情况

    3.数据对象

    数据对象(data object)是性质相同的数据元素的集合，是数据

    的一个子集。例如，正整数数据对象是集合N={1，2，3，…}，字母字

    符数据对象是集合C={‘A’，’B’，’C’，…}。

    4.数据结构

    数据结构(data structure)即数据的组织形式，它是数据元素

    之间存在的一种或多种特定关系的数据元素集合。在现实世界中，任

    何事物都是有内在联系的，而不是孤立存在的，同样在计算机中，数

    据元素不是孤立的、杂乱无序的，而是具有内在联系的数据集合。例

    如，表1-1的教职工基本情况表是一种表结构，学校的组织机构是一种

    层次结构，城市之间的交通路线属于图结构，如图1-1和图1-2所示。图1-1 学校组织机构图

    图1-2 城市之间交通路线图

    5.数据类型数据类型(data type)用来刻画一组性质相同的数据及其上的操

    作。数据类型是按照值的不同进行划分的。在高级语言中，每个变

    量、常量和表达式都有各自的取值范围，该类型就说明了变量或表达

    式的取值范围和所能进行的操作。例如，C语言中的字符类型规定了所

    占空间是8位，也就是它的取值范围，同时也定义了在其范围内可以进

    行赋值运算、比较运算等。

    在C语言中，按照取值的不同，数据类型还可以分为原子类型和结

    构类型两类。原子类型是不可以再分解的基本类型，包括整型、实

    型、字符型等。结构类型是由若干个类型组合而成，是可以再分解

    的。例如，整型数组是由若干整型数据组成的，结构体类型的值也是

    由若干个类型范围的数据构成，它们的类型都是相同的。

    在计算机处理的发展历史上，计算机已经不仅仅能够处理数值信

    息了，计算机所能处理的对象包括数值、字符、文字、声音、图像及

    视频等信息。任何信息只要经过数字化处理，能够让计算机识别，都

    能够进行处理。当然，这需要对要处理的信息进行抽象描述，让计算

    机理解。1.3 数据的逻辑结构与存储结构

    数据结构的主要任务就是通过分析数据对象的结构特征，包括逻

    辑结构及数据对象之间的关系，然后把逻辑结构表示成计算机可实现

    的物理结构，从而便于计算机处理。本节主要介绍数据的逻辑结构表

    示和存储结构的表示。

    1.3.1 逻辑结构

    数据的逻辑结构 (logical structure)是指在数据对象中数据

    元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4

    种结构类型。

    (1)集合 。结构中的数据元素除了同属于一个集合外，数据元

    素之间没有其他关系。这就像数学中的自然数集合，集合中的所有元

    素都属于该集合，除此之外，没有其他特性。例如，数学中的正整数

    集合{5，67，978，20，123，18}，集合中的数除了属于正整数外，元

    素之间没有其他关系。数据结构中的集合关系就类似于数学中的集

    合。集合表示如图1-3所示。

    (2)线性结构 。结构中的数据元素之间是一对一的关系。线性

    结构如图1-4所示。数据元素之间有一种先后的次序关系，a、b、c是一个线性表，其中，a是b的前驱，b是a的后继。

    (3)树形结构 。结构中的数据元素之间存在一种一对多的层次

    关系，树形结构如图1-5所示。这就像学校的组织结构图，学校下面是

    教学的院系、行政机构及一些研究所。

    (4)图结构 。结构中的数据元素是多对多的关系，图1-6就是一

    个图结构。城市之间的交通路线图就是多对多的关系，a、b、c、d、e、f、g是7个城市，城市a和城市b、e、f都存在一条直达路线，而城

    市b也和a、c、f存在一条直达路线。

    图1-3 集合结构

    图1-4 线性结构图1-5 树形结构

    图1-6 图结构

    1.3.2 存储结构

    存储结构 (storage structure)也称为物理结构 (physical

    structure)，指的是数据的逻辑结构在计算机中存储形式。数据的存

    储结构应能正确反映数据元素之间的逻辑关系。

    数据元素的存储结构形式通常有顺序存储结构和链式存储结构两

    种。顺序存储是把数据元素存放在一组地址连续的存储单元里，其数

    据元素间的逻辑关系和物理关系是一致的。采用顺序存储的字符串

    “abcdef”的存储结构如图1-7所示。链式存储是把数据元素存放在任

    意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表

    示数据元素之间的逻辑关系。字符串“abcdef”的链式存储结构如图

    1-8所示。图1-7 顺序存储结构图1-8 链式存储结构

    数据的逻辑结构和物理结构是密切相关的，今后在学习数据结构

    的过程中，读者将会发现，任何一个算法的设计取决于选定的数据逻

    辑结构，而算法的实现依赖于所采用的存储结构。

    如何描述存储结构呢？虽然存储结构涉及数据元素及其关系在存

    储器中的物理位置，但本书是建立在高级程序设计语言层次上的数据

    结构的操作，因此不能像上面那样直接以内存地址来描述存储结构，但可以借助高级程序设计语言中提供的数据类型来描述它，例如，可以用C语言中的一维数组类型来描述顺序存储结构用C语言中的自引用

    类型描述链式存储结构，其中用指针来表示元素之间的逻辑关系。1.4 抽象数据类型及其描述

    为了在计算机上实现某种操作，需要把处理的对象描述成计算机

    能识别的形式，即一定形式的数据类型，并定义其上的一组操作。这

    在数据结构这门课中称为抽象数据类型。

    1.4.1 什么是抽象数据类型

    抽象数据类型 (abstract data type，ADT)是描述具有某种逻

    辑关系的数学模型，并对在该数学模型上进行的一组操作。抽象数据

    类型描述的是一组逻辑上的特性，与在计算机内部表示无关。计算机

    中的整数数据类型是一个抽象数据类型，不同的处理器可能实现方法

    不同，但其逻辑特性相同，即加、减、乘、除等运算是一致的。在用

    户看来，各种计算机所提供的整数类型数学特性都是相同的，因此，“抽象”的意义在于数据类型的数学抽象特性，而不是它们的实现方

    法。

    抽象数据类型不仅包括在计算机中已经定义了的数据类型，例如

    整型、浮点型等，还包括用户自己定义的数据类型，例如结构体类

    型、类等。一个抽象数据类型定义了一个数据对象、数据对象中数据元素之

    间的关系及对数据元素的操作。抽象数据类型通常是指用来解决应用

    问题的数据模型，包括数据的定义和操作。

    抽象数据类型体现了程序设计中的问题分解、抽象和信息隐藏特

    性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理

    的问题，然后建立起一个计算机能处理的数据模型，并把每个功能模

    块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。

    这就类似人们日常生活中盖房子，把盖房子分成若干个小任务：地皮

    审批、图纸设计、施工、装修等，工程管理人员负责地皮的审批，地

    皮审批下来之后，工程技术人员根据用户需求设计图纸，建筑工人根

    据设计好的图纸进行施工(包括打地基、砌墙、安装门窗等)，盖好

    房子后请装修工人装修。

    盖房子的过程与抽象数据类型中的问题分解类似，工程管理人员

    不需要了解图纸如何设计，工程技术人员不需要了解打地基和砌墙的

    具体过程，装修工人不需要知道怎么画图纸和怎样盖房子，这就是抽

    象数据类型中的信息隐藏。

    1.4.2 抽象数据类型的描述

    对于初学者来说，抽象数据类型不太容易理解，用一大堆公式会

    让不少读者迷茫，因此，本书采用通俗的语言去讲解抽象数据类型。本书把抽象数据类型分为两个部分来描述，即数据对象集合和基本操

    作集合。其中，数据对象集合包括数据对象的定义及数据对象中元素

    之间关系的描述，基本操作集合是对数据对象的运算的描述。数据对

    象和数据关系的定义可采用数学符号和自然语言描述，基本操作的定

    义格式如下。

    基本操作名(参数表)：初始条件和操作结果描述。

    例如线性表的抽象数据类型，描述如下。

    1.数据对象集合

    线性表的数据对象集合为{a 1 ，a 2 ，…，a n }，每个元素的

    类型均为DataType。其中，除了第一个元素a 1 外，每一个元素有且

    只有一个直接前驱元素，除了最后一个元素a n 外，每一个元素有且

    只有一个直接后继元素。数据元素之间的关系是一对一的关系。

    2.基本操作集合

    线性表的基本操作如下所述。

    (1)InitList(L)：初始化操作，建立一个空的线性表L。这

    就像是在日常生活中，一所院校为了方便管理建立一个教职工基本情况表，准备登记教职工信息。

    (2)ListEmpty(L)：若线性表L为空，返回1，否则返回0。这

    就像是刚刚建立了教职工基本情况表，还没有登记教职工信息。

    (3)GetElem(L，i，e)：返回线性表L的第i个位置元素值给

    e。这就像在教职工基本情况表中，根据给定序号查找某个教师信息。

    (4)LocateElem(L，e)：在线性表L中查找与给定值e相等的元

    素，如果查找成功返回该元素在表中的序号表示成功，否则返回0表示

    失败。这就像在教职工基本情况表中，根据给定的姓名查找教师信

    息。

    (5)InsertList(L，i，e)：在线性表L中的第i个位置插入新

    元素e。这就类似于经过招聘考试，引进了一名教师，这个教师信息被

    登记到教职工基本情况表中。

    (6)DeleteList(L，i，e)：删除线性表L中的第i个位置元

    素，并用e返回其值。这就像某个教职工到了退休年龄或者被调入其他

    学校，需要将该教职工从教职工基本情况表中删除。

    (7)ListLength(L)：返回线性表L的元素个数。这就像查看教

    职工基本情况表中有多少个教职工。(8)ClearList(L)：将线性表L清空。这就像学校被撤销，不

    需要再保留教职工基本信息，将这些教职工信息全部清空。

    大多数教材用以下方式描述线性表的抽象数据类型。

    ADT List

    {

    数据对象：D={ai|ai

    ∈ElemSet

    ，i=1

    ，2

    ，…，n

    ，n

    ≥0}

    数据关系：R={
    ，ai>|ai-1

    ，ai

    ∈D

    ，i=2

    ，3

    ，…，n}

    基本操作如下。

    (1)InitList

    (L)

    初始条件：表L

    不存在。

    操作结果：建立一个空的线性表L。

    (2)ListEmpty

    (L)

    初始条件：表L

    存在。

    操作结果：若表L

    为空，返回1

    ，否则返回0。

    (3)GetElem

    (L

    ，i

    ，e)

    初始条件：表L

    存在，且i

    值合法，即1

    ≤i

    ≤ListLength

    (L)。

    操作结果：返回表L

    的第i

    个位置元素值给e。

    ((4)LocateElem

    (L

    ，e)

    初始条件：表L

    存在，且e

    为合法元素值。

    操作结果：在表L

    中查找与给定值e

    相等的元素。如果查找成功，则返回该元素在表中的序号；如果这样的元素不存在，则返回0。

    (5)InsertList

    (L

    ，i

    ，e)

    初始条件：表L

    存在，e

    为合法元素且1

    ≤i

    ≤ListLength

    (L)。

    操作结果：在表L

    中的第i

    个位置插入新元素e。

    (6)DeleteList

    (L

    ，i

    ，e)

    初始条件：表L

    存在且1

    ≤i

    ≤ListLength

    (L)。

    操作结果：删除表L

    中的第i

    个位置元素，并用e

    返回其值。

    (7)ListLength

    (L)

    初始条件：表L

    存在。

    操作结果：返回表L

    的元素个数。

    (8)ClearList

    (L)

    初始条件：表L

    存在。

    操作结果：将表L

    清空。

    }ADT List 以上是抽象数据类型的两种描述方式，显然前者会更容易被理解

    和接受。

    需要注意的是，在基本操作的描述过程中，参数传递有两种方

    式，一种是数值传递，另一种是引用传递。前者仅仅是将数值传递给

    形参，并不返回结果；后者其实是把实参的地址传递给形参，实参和

    形参其实是同一个变量，被调用函数通过修改该变量的值返回给调用

    函数，从而把结果带回。在描述算法时，在参数前加上表示引用传

    递；如果参数前没有，表示是数值传递。1.5 算法

    在数据类型建立起来之后，就要对这些数据类型进行操作，建立

    起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序

    运行效率的高低。如何建立一个比较好的运算集合就是算法要研究的

    问题。本节主要介绍算法的定义、算法的特性、算法的描述及算法与

    数据结构的关系。

    1.5.1 数据结构与算法的关系

    算法与数据结构关系密切。两者既有联系又有区别。

    数据结构与算法的联系可用一个公式描述，即程序=算法+数据结

    构。数据结构是算法实现的基础，算法总是要依赖于某种数据结构来

    实现的。算法的操作对象是数据结构。算法的设计和选择要同时结合

    数据结构，简单地说，数据结构的设计就是选择存储方式，如确定问

    题中的信息是用普通变量存储还是用数组存储或其他更加复杂的数据

    结构存储。算法设计的实质就是对实际问题要处理的数据选择一种恰

    当的存储结构，并在选定的存储结构上设计一个好的算法。

    数据结构是算法设计的基础。用一个形象的比喻来解释就是，开

    采煤矿过程中，煤矿以各种形式深埋于地下，矿体的结构就相当于计算机领域的数据结构，而煤就相当于一个个数据元素；开采煤矿然后

    运输、加工这些“操作”技术就相当于算法；显然，如何开采、如何

    运输必须考虑到煤矿的存储(物理)结构，只拥有开采技术而没有煤

    矿是没有任何意义的。算法设计必须要考虑到数据结构的构造，算法

    设计是不可能独立于数据结构存在的。另外，数据结构的设计和选择

    需要为算法服务。如果某种数据结构不利于算法实现它将没有太大的

    实际意义。知道某种数据结构的典型操作才能设计出好的算法。总

    之，算法的设计同时伴有数据结构的设计，两者都是为最终解决问题

    服务的。

    数据结构与算法的区别在于数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础

    上解决实际问题。算法是编程思想，数据结构则是这些思想的基础。

    1.5.2 什么是算法

    算法 (algorithm)是解决特定问题求解步骤的描述，在计算机

    中表现为有限的操作序列。操作序列包括了一组操作，每一个操作都

    完成特定的功能。例如求n个数中最大者的问题，其算法描述如下。

    (1)定义一个变量max和一个数组a[]，分别用来存放最大数和数

    组的元素，并假定第一个数最大，赋给max。max=a[0]；

    (2)依次把数组a中其余的n-1个数与max进行比较，遇到较大的

    数时，将其赋给max。

    for(i=1;i
    if(max
    max=a[i];

    最后，max中的数就是n个数中的最大者。

    1.5.3 算法的五大特性

    算法具有以下5个特性。

    (1)有穷性 。有穷性指的是算法在执行有限的步骤之后，自动

    结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。

    (2)确定性 。算法的每一步骤都具有确定的含义，不会出现二

    义性。算法在一定条件下只有一条执行路径，也就是相同的输入只能

    有一个唯一的输出结果。

    (3)可行性 。算法的每一步都必须是可行的，也就是说，每一

    步都能够通过执行有限次数完成。

    (4)输入 。算法具有零个或多个输入。(5)输出 。算法至少有一个或多个输出。输出的形式可以是打

    印输出也可以是返回一个或多个值。

    1.5.4 算法的描述

    算法的描述方式有多种，如自然语言、伪代码(或称为类语

    言)、程序流程图及程序设计语言(如C语言)等。其中，自然语言描

    述可以是汉语或英语等文字描述；伪代码形式类似于程序设计语言形

    式，但是不能直接运行；程序流程图的优点是直观，但是不易直接转

    化为可运行的程序；程序设计语言形式是完全采用像C、C++、Java等

    语言描述，可以直接在计算机上运行。

    例如判断正整数m是否为质数，算法可用以下几种方式描述。

    1.自然语言描述法

    利用自然语言描述“判断m是否为质数”的算法如下。

    ①输入正整数m，令i=2。

    ②如果 ，则令m对i求余，将余数送入中间变量r；否则

    输出“m是质数”，算法结束。③判断r是否为零。如果为零，输出“m不是质数”，算法结束；

    如果r不为零，则令i增加1，转到步骤②执行。

    因为上述算法采用自然语言描述不具有直观性和良好的可读性，采用程序流程图描述比较直观，可读性好，但是不能直接转化为计算

    机程序，移植性不好。

    2.程序流程图法

    判断m是否为质数的程序流程图如图1-9所示。我们采用类C语言描

    述和C语言描述如下：图1-9 判断m是否为质数的程序流程图

    3.类语言法类C语言描述如下。

    void IsPrime

    判断m

    是否为质数

    {

    scanf(m);

    输入正整数m

    for(i=2;i<=sqrt(m);i++)

    {

    r=m%i;

    求余数

    if(r==0)

    如果m

    能被整除

    {

    printf(m

    不是质数!);

    break;

    }

    }

    printf(m

    是质数!);

    }

    4.程序设计语言法

    C语言描述如下。

    void IsPrime

    判断m

    是否为质数

    {

    printf(

    请输入一个正整数：);

    scanf(%d,m);

    输入正整数m

    for(i=2;i<=sqrt(m);i++)

    {

    r=m%i;

    求余数

    if(r==0)

    如果m

    能被整除

    {

    printf(m

    不是质数!\n);

    break;

    }

    } printf(m

    是质数!\n);

    }

    可以看出，类语言的描述除了没有变量的定义，输入和输出的写

    法之外，与程序设计语言的描述的差别不大，类语言的可以直接转化

    为可以直接运行的计算机程序。

    为了方便读者学习和上机操作，本书所有算法均采用C程序设计语

    言描述，能直接上机运行。1.6 算法分析

    一个好的算法往往可以使程序运行的更快，衡量一个算法的好坏

    往往将算法效率和存储空间作为重要依据。算法的效率需要通过算法

    编制的程序在计算机上的运行时间来衡量，存储空间需求通过算法在

    执行过程中所占用的最大存储空间来衡量。本节主要介绍算法设计的

    要求、算法效率评价、算法的时间复杂度及算法的空间复杂度。

    1.6.1 算法设计的4个目标

    一个好的算法应该具备以下目标。

    1.算法的正确性

    算法的正确性 (correctness)是指算法至少应该包括对于输

    入、输出和加工处理无歧义性的描述，能正确反映问题的需求，且能

    够得到问题的正确答案。

    通常算法的正确性应包括以下4个层次。

    (1)算法对应的程序没有语法错误。

    (2)对于几组输入数据能得到满足规格要求的结果。(3)对于精心选择的典型的、苛刻的带有刁难性的几组输入数据

    能得到满足规格要求的结果。

    (4)对于一切合法的输入都能得到产生满足要求的结果。

    对于这4层算法正确性的含义，达到第4层意义上的正确是极为困

    难的，所有不同输入数据的数量大得惊人，逐一验证的方法是不现实

    的。一般情况下，我们把层次3作为衡量一个程序是否正确的标准。

    2.可读性

    算法主要是为了人们方便阅读和交流，其次才是计算机执行。可

    读性 (readability)好有助于人们对算法的理解，晦涩难懂的程序

    往往隐含错误不易被发现，难以调试和修改。

    3.健壮性

    当输入数据不合法时，算法也应该能做出反应或进行处理，而不

    会产生异常或莫名其妙的输出结果。例如，求一元二次方程根ax 2

    +bx+c=0的算法，需要考虑多种情况，先判断b 2 -4ac的正负，如果为

    正数，则该方程有两个不同的实根；如果为负，表明该方程无实根；

    如果为零，表明该方程只有一个实根；如果a=0，则该方程又变成了一元一次方程，此时若b=0，还要处理除数为零的情况。如果输入的a、b、c不是数值型，还要提示用户输入错误。

    4.高效率和低存储量

    效率指的是算法的执行时间。对于同一个问题如果有多个算法能

    够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需

    求指算法在执行过程中需要的最大存储空间。效率与低存储量需求都

    与问题的规模有关，求100个人的平均分与求1000个人的平均分所花的

    执行时间和运行空间显然有一定差别。设计算法时应尽量选择高效率

    和低存储量需求的算法。

    1.6.2 算法效率评价

    算法执行时间需通过依据该算法编制的程序在计算机上的运行时

    所耗费的时间来度量，而度量一个算法在计算机上的执行时间通常有

    如下两种方法。

    1.事后统计方法

    目前计算机内部大都有计时功能，有的甚至可精确到毫秒级，不

    同算法的程序可通过一组或若干组相同的测试程序和数据以分辨算法的优劣。但是，这种方法有两个缺陷，一是必须依据算法事先编制好

    程序，这通常需要花费大量的时间与精力；二是时间的长短依赖计算

    机硬件和软件等环境因素，有时会掩盖算法本身的优劣。因此，人们

    常常采用事前分析估算的方法评价算法的好坏。

    2.事前分析估算方法

    这主要在计算机程序编制前，对算法依据数学中的统计方法进行

    估算。这主要是因为算法的程序在计算机上的运行时间取决于以下因

    素。

    ·算法采用的策略、方法。

    ·编译产生的代码质量。

    ·问题的规模。

    ·书写的程序语言，对于同一个算法，语言级别越高，执行效率

    越低。

    ·机器执行指令的速度。

    在以上5个因素中，算法采用的不同的策略，或不同的编译系统，或不同的语言实现，或在不同的机器运行时，效率都不相同。抛开以

    上因素，算法效率则可以通过问题的规模来衡量。一个算法由控制结构(顺序、分支和循环结构)和基本语句(赋

    值语句、声明语句和输入输出语句)构成，则算法的运行时间取决于

    两者执行时间的总和，所有语句的执行次数可以作为语句的执行时间

    的度量。语句的重复执行次数称为语句频度。

    例如，斐波那契数列的算法和语句的频度如下。

    每一条语句的频度

    f0=0; 1

    f1=1; 1

    printf(%d,%d,f0,f1); 1

    for(i=2;i<=n;i++) n

    {

    fn=f0+f1; n-1

    printf(,%d,fn); n-1

    f0=f1; n-1

    f1=fn; n-1

    }

    每一条语句的右端是对应语句的频度 (frequency count)，即

    语句的执行次数。上面算法总的执行次数为T(n)=1+1+1+n+4(n-1)

    =5n-1。

    1.6.3 算法的时间复杂度

    在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的

    函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的

    时间复杂度，也就是算法 的时间量度 ，记作T(n)=O(f(n))。它表示随问题规模n的增大，算法的执行时间的增长率和f(n)的

    增长率相同，称作算法的渐进时间复杂度 (asymptotic time

    complexity)，简称为时间复杂度 。其中，f(n)是问题规模n的某

    个函数。

    一般情况下，随着n的增大，T(n)的增长较慢的算法为最优的算

    法。例如，在下列三段程序段中，给出原操作x=x+1的时间复杂度分

    析。

    (1)

    1；

    (2)

    for

    (i=1；i<=n；i++)

    x=x+1；

    (3)

    for

    (i=1；i<=n；i++)

    for

    (j=1；j<=n；j++))

    x=x+1；

    程序段(1)的时间复杂度为O(1)，称为常量阶；程序段(2)

    的时间复杂度为O(n)，称为线性阶；程序段(3)的时间复杂度为

    O(n 2 )，称为平方阶。此外算法的时间复杂度还有对数阶O(log 2

    n)、指数阶O(2 n )等。

    上面的斐波那契数列的时间复杂度T(n)=O(n)。

    常用的时间复杂度所耗费的时间从小到大依次是O(1)
    n)
    算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况

    下，具有指数级的时间的复杂度算法只有当n足够小时才是可使用的算

    法。具有常量阶、线性阶、对数阶、平方阶和立方阶的时间复杂度算

    法是常用的算法。一些常见函数的增长率如图1-10所示。图1-10 常见函数的增长率

    一般情况下，算法的时间复杂度只需要考虑关于问题规模n的增长

    率或阶数。例如以下程序段。

    for(i=2;i<=n;i++)

    for(j=2;j<=i-1;j++)

    {

    k++;

    a[i][j]=x;

    }

    语句k++的执行次数关于n的增长率为n 2 ，它是语句频度(n-1)

    (n-2)2中增长最快的项。在有些情况下，算法的基本操作的重复执行次数还依赖于输入的

    数据集。例如如下冒泡排序算法。

    void BubbleSort(int a[],int n)

    {

    int i,j,t;

    change=TRUE;

    for(i=1;i<=n-1change;i++)

    {

    change=FALSE;

    for(j=1;j<=n-i;j++)

    if(a[j]>a[j+1])

    {

    t=a[j];

    a[j]=a[j+1];

    a[j+1]=t;

    change=TRUE;

    }

    }

    }

    交换相邻两个整数为该算法中的基本操作。当数组a中的初始序列

    为从小到大有序排列时，基本操作的执行次数为0；当数组中初始序列

    从大到小排列时，基本操作的执行次数为n(n-1)2。对这类算法的

    分析，一种方法是计算所有情况的平均值，这种时间复杂的计算方法

    称为平均时间复杂度；另外一种方法是计算最坏情况下的时间复杂

    度，这种方法称为最坏时间复杂度。若数组a中初始输入数据可能出现

    n!种的排列情况的概率相等，则冒泡排序的平均时间复杂度为T(n)

    =O(n 2 )。

    然而，在很多情况下，各种输入数据集出现的概率难以确定，算

    法的平均复杂度也就难以确定。因此，另一种更可行也更为常用的办

    法是讨论算法在最坏情况下的时间复杂度，即分析最坏情况以估算算法执行时间的上界。例如，上面冒泡排序的最坏时间复杂度为数组a中

    初始序列为从大到小有序，则冒泡排序算法在最坏情况下的时间复杂

    度为T(n)=O(n 2 )。一般情况下，本书以后讨论的时间复杂度，在没有特殊说明情况下，都指的是最坏情况下的时间复杂度。

    1.6.4 算法的空间复杂度

    空间复杂度 (space complexity)作为算法所需存储空间的量

    度，记做S(n)=O(f(n))。其中，n为问题的规模，f(n)为语句

    关于n的所占存储空间的函数。一般情况下，一个程序在机器上执行

    时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需

    要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本

    身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即

    可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。1.7 学好数据结构的秘诀

    作为计算机专业的一名“老兵”，笔者个人学习、研究数据结构

    和算法已经近10年了，在学习的过程中，也遇到不少问题，为了让读

    者在学习数据结构的过程中少走弯路，下面分享一下笔者个人的一些

    经验，谈谈关于如何学好“数据结构”的一些粗浅认识。

    1.明确数据结构的重要性，树立学好数据结构的信心

    数据结构是计算机科学与技术专业的核心课程，不仅仅涉及计算

    机硬件的研究范围，并且与计算机软件的研究有着更为密切的关系，“数据结构”课程还是操作系统、数据库原理、编译原理、人工智

    能、算法设计与分析等课程的基础。数据结构是计算机专业硕士研究

    生入学考试的必考科目之一，还是计算机软件水平考试、等级考试的

    必考内容之一，数据结构在计算机专业中的重要性不言而喻。

    万事开头难，学习任何一样新东西，都是比较困难的，对于初学

    者而已，数据结构的确是一门不容易掌握的专业基础课，但你一定要

    树立学好数据结构的信心，主要困难无非有两个，一个是数据结构的

    概念比较抽象，不容易理解；另一个是没有熟练掌握一门程序设计语言。面对以上困难，只要我们见招拆招，其实也没有什么可怕的，不

    过选择一本好教材是十分有必要的。

    2.熟练掌握程序设计语言，变腐朽为神奇

    程序语言是学习数据结构和算法设计的基础，很显然，没有良好

    的程序设计语言能力，就不能很好地把算法用程序设计语言描述出

    来，程序设计语言和数据结构、算法的关系就像是画笔和画家的思想

    关系一样，程序设计语言就是这画笔，数据结构、算法就是画家的思

    想，即便画家的水平很高，如果不会使用画笔，再美的图画也无法给

    我们展现出来。

    可见，要想学好数据结构，必须至少熟练掌握一门程序设计语

    言，如C语言、C++语言等。

    3.结合生活实际，变抽象为具体

    数据结构是一项把实际问题抽象化和进行复杂程序设计的工程。

    它要求学生不仅具备C语言等高级程序设计语言的基础，而且还要学会

    掌握把复杂问题抽象成计算机能够解决的离散的数学模型的能力。在

    学习数据结构的过程中，要将各种结构与实际生活结合起来，把抽象

    的东西具体化，以便理解。例如学到队列时，很自然就会联想到火车站售票窗口前面排起的长长的队伍，这支长长的队伍其实就是队列的

    具体化，这样就会很容易理解关于队列的概念，如队头、队尾、出

    队、入队等。

    4.多思考，多上机实践

    数据结构既是一门理论性较强的学科，也是一门实践性很强的学

    科。特别是对于初学者而言，接触到的算法相对较少，编写算法还不

    够熟练，俗话说“熟能生巧，勤能补拙”，因此，只有多看有关算法

    和数据结构方面的图书，认真理解其中的算法思想，除了阅读算法之

    外，还要自己动手写算法，并在电脑上上机调试，这样才能知道编写

    的算法是否正确，存在哪些错误和缺陷，以避免今后再犯类似错误，长此以往，自己的算法和数据结构水平才能快速提高。

    有的表面上看是正确的程序，在电脑上运行后才发现隐藏的错

    误，特别是很细微的错误，只有多试几组数据，才知道程序到底是不

    是正确。因此，对于一个程序或算法，除了仔细阅读程序或算法判断

    是否存在逻辑错误外，还需要上机调试，在可能出错的地方设置断

    点，单步跟踪调试程序，观察各变量的变化情况，才能找到具体哪个

    地方出了问题。有时，可能仅仅是误敲了一个符号或变量，就可能产

    生错误，这种错误往往不容易发现，只有上机调试才能知道。因此，在学习数据结构与算法的时候一定要多上机实践。只要能做到以上几点，选择一本好的数据结构教材或参考书(最

    好算法完全用C语言实现，有完整代码)，加上读者的勤奋，学好数据

    结构自然不在话下。1.8 习题

    1.研究数据结构就是研究。

    A.数据的逻辑结构

    B.数据的存储结构

    C.数据的逻辑结构和存储结构

    D.数据的逻辑结构、存储结构及其基本操作

    2.算法分析的两个主要方面是。

    A.空间复杂度和时间复杂度

    B.正确性和简单性

    C.可读性和文档性

    D.数据复杂性和程序复杂性

    3.具有线性的数据结构是。

    A.图

    B.树C.广义表

    D.栈

    4.计算机中的算法指的是解决某一个问题的有限运算序列，它必

    须具备输入、输出、等5个特性。

    A.可执行性、可移植性和可扩充性

    B.可执行性、有穷性和确定性

    C.确定性、有穷性和稳定性

    D.易读性、稳定性和确定性

    5.下面程序段的时间复杂度是。

    for(i=0;i
    for(j=0;j
    a[i][j]=ij;

    A.O(m 2 )

    B.O(n 2 )

    C.O(mn)

    D.O(m+n)6.算法是。

    A.计算机程序

    B.解决问题的计算方法

    C.排序算法

    D.解决问题的有限运算序列

    7.某算法的语句执行频度为(3n+nlog 2 n+n 2 +8)，其时间复

    杂度表示。

    A.O(n)

    B.O(nlog 2 n)

    C.O(n 2 )

    D.O(log 2 n)

    8.下面程序段的时间复杂度为。

    i=1;

    while(i<=n)

    i=i3;

    A.O(n)B.O(3n)

    C.O(log 3 n)

    D.O(n 3 )

    9.数据结构是一门研究非数值计算的程序设计问题中计算机的数

    据元素以及它们之间的和运算等的学科。

    A.结构

    B.关系

    C.运算

    D.算法

    10.下面程序段的时间复杂度是。

    i=s=0;

    while(s
    i++;s+=i;

    }

    A.O(n)

    B.O(n 2 )

    C.O(log 2 n)D.O(n 3 )

    11.通常从正确性、易读性、健壮性、高效性等4个方面评价算法

    的质量，以下解释错误的是。

    A.正确性算法应能正确地实现预定的功能

    B.易读性算法应易于阅读和理解，以便调试、修改和扩充

    C.健壮性当环境发生变化时，算法能适当地做出反应或进行处

    理，不会产生不需要的运行结果

    D.高效性即达到所需要的时间性能第2章 C语言基础

    C语言作为数据结构的算法描述语言，广泛应用于系统软件和应用

    软件的开发。在真正开始学习数据结构知识之前，笔者先带领读者复

    习C语言中的一些重点和难点，为数据结构的学习扫清障碍。本章主要

    针对C语言的重点和难点部分进行了细致讲解，主要内容包括C语言开

    发环境、函数与递归、指针、参数传递、动态内存分配及结构体、联

    合体。

    本章重点和难点：

    ·递归函数的实现和递归如何转化为非递归

    ·指针数组、数组指针、函数指针及理解与使用

    ·理解传地址调用中变量的变化情况

    ·链表的操作2.1 C语言开发环境

    C语言常见的开发环境有多种，如LCC、Turbo C 2.0、Visual

    C++、Borland C++，本节主要介绍使用最为广泛的Turbo C 2.0和

    Visual C++6.0。

    2.1.1 Turbo C 2.0开发环境

    1989年，美国Borland公司推出了Turbo C 2.0(Turbo C简称为

    TC)，它是集编辑、编译、链接和运行于一体的C程序集成开发环境。

    Turbo C 2.0界面简单，上手容易，使用方便，通过一个简单的主界面

    可以很容易编辑、编译和链接程序，正所谓“麻雀虽小，五脏俱

    全”，它是初学者广泛使用的开发工具。

    1.进入Turbo C 2.0环境

    在Windows系统中，运行Turbo C 2.0有两种方式，一是直接双击

    Turbo C 2.0文件夹下的文件TC.EXE运行；二是切换到DOS命令行下通

    过命令行进入。下面重点介绍命令行方式如何进入Turbo C 2.0开发环

    境，具体步骤如下。①假如Turbo C 2.0编译程序安装在D:\TC目录下，那么需要单击

    【开始】|【运行】命令，打开【运行】对话框，在文本框中输入

    “command”或者“cmd”，如图2-1所示。

    ②单击【确定】按钮，进入DOS运行环境，如图2-2所示。

    ③输入“d:”后按【Enter】键，切换到盘符“D:\”目录。接着

    输入“cd tc”命令后按【Enter】键，进入“D:\tc”目录，如图2-3

    所示。

    ④输入“tc”后按【Enter】键，进入Turbo C 2.0集成开发环境

    主界面，如图2-4所示。

    图2-1 “运行”对话框图2-2 进入DOS运行环境

    图2-3 DOS命令行操作示意图图2-4 Turbo C 2.0集成开发环境主界面

    从图2-4可以看到，Turbo C 2.0集成开发环境的主菜单包括

    【File】、【Edit】、【Run】、【Compile】、【Project】、【Options】、【Debug】和【Breakwatch】8个菜单项。这8个菜单项

    分别代表的是【文件】、【编辑】、【运行】、【编译】、【工

    程】、【选项】、【调试】和【中断查看】。

    2.设置Turbo C 2.0的运行环境

    在Turbo C 2.0的运行环境中，不能使用鼠标，只能使用键盘。通

    过按键盘上的【F10】键先激活菜单，然后通过按四个方向键【↑】、【↓】、【←】、【→】对菜单和菜单项进行选择，被选中的菜单项

    以黑底白字显示。

    在使用Turbo C 2.0之前，需要对该运行环境进行一些相关的设

    置。在C语言程序中，经常会调用一些系统函数，而这些函数存在于

    Turbo C 2.0的系统文件中，因此，只有设置好了系统文件的路径，才

    能正确运行C语言程序，否则就会出现编译错误。

    在使用Turbo C 2.0之前，首先需要修改Turbo C 2.0的包含文件

    目录和库文件目录为当前文件所在的目录，其操作步骤如下。①按【F10】键激活【Options】菜单，并按【Enter】键打开下拉

    菜单，然后按【↓】方向键选中【Directories】命令。

    ②按【Enter】键，进入下一级菜单，然后选中【Include

    directories】命令，按【Enter】键打开【Include directories】对

    话框，将默认的路径“C:\TURBOC2\INCLUDE”修改为

    “D:\TC\INCLUDE”。如图2-5所示。

    ③按【Enter】键返回上一级菜单，按【↓】方向键，选中

    【Library directories】命令，按【Enter】键打开【Library

    directories】对话框，将默认的路径“C:\TURBOC2\LIB”修改为

    “D:\TC\LIB”，并按【Enter】键。

    ④为了在下次使用Turbo C 2.0时不再进行以上修改，需要保存上

    面的环境设置。这需要去掉Turbo C 2.0配置文件“TCCONFIG.TC”的

    只读属性，否则无法保存以上设置。执行【Options】|【Save

    options】命令，并按【Enter】键，打开【Config File】对话框，然

    后按【Enter】键弹出【Verify】提示对话框，直接输入“Y”即可完

    成修改。图2-5 设置“包含头文件”的路径

    图2-6 设置库文件路径

    3.使用Turbo C 2.0编写C语言程序

    按【F10】键激活菜单，并选中【Edit】菜单后按【Enter】键，输入以下代码。

    void main

    {

    printf(hello world!\n);

    } 按【F10】激活菜单，执行【Compile】|【Compile to OBJ】命

    令，对程序进行编译，然后执行【Compile】|【Link EXE file】命

    令，链接程序，如果程序没有错误，就会生成.EXE文件。

    这时，我们就可以执行【Run】|【Run】命令或者按快捷键

    【Ctrl+F9】运行程序，最后通过执行【Run】|【Use Screen】命令或

    者按快捷键【Alt+F5】查看运行结果，如图2-7所示。

    这时，如果按【Esc】键，就会返回Turbo C 2.0集成开发环境。

    如果程序中有错误，在编译或链接时就会出现错误提示信息，如

    图2-8是一个链接错误的提示信息。按任意键，会以不同颜色将光标定

    位到错误行，用户可以根据系统提示的错误原因修改错误，并重新编

    译、链接运行程序。

    图2-7 程序运行结果图2-8 链接错误的提示信息

    其他常见操作，如执行【File】|【Load】命令和【File】|

    【Pick】命令，用于加载存在磁盘中的文件；执行【File】|

    【Save】、【File】|【Save as】和【File】|【Write to】命令，用

    于将程序保存在磁盘上；执行【File】|【Quit】命令或按快捷键

    【Alt+X】，可以退出Turbo C 2.0集成开发环境。

    2.1.2 Visual C++6.0开发环境

    Visual C++6.0是强大的CC++软件开发工具，使用非常广泛，已

    经成为程序员首选的开发工具。利用它不仅可以开发控制台应用程

    序，还可以开发Windows SDK、MFC等应用程序。因为本书主要讲解利

    用C语言描述算法，所以仅介绍如何使用Visual C++6.0开发控制台程

    序。

    用Visual C++6.0编写C语言程序需要如下两个步骤，一是创建一

    个新的Viusal C++6.0控制台项目；二是在该项目中创建C程序文件，并编辑C语言程序。1.新建Visual C++6.0控制台项目

    ①执行【文件】|【新建】命令，弹出【新建】对话框，单击【工

    程】标签，在项目文件中选择【Win32 Console Application】命令，在“工程名称”文本框中输入项目名称“Test”，单击【位置】按

    钮，选择保存路径为“D:\C程序\Test”，如图2-9所示。

    ②单击【确定】按钮，打开【Win32 Console Application】对话

    框，即新建控制台项目的第一步。这一步有4个选项，选择【一个空工

    程】选项，就是要建立一个空项目，如图2-10所示。

    图2-9 新建一个控制台项目图2-10 控制台应用程序设置

    ③单击【完成】按钮，打开【新建工程信息】对话框，即新建立

    的控制台项目信息：已经建立了一个空项目，且项目中没有文件。该

    项目路径为“D:\C程序\Test”，如图2-11所示。

    ④单击【确定】按钮，进入控制台的项目环境中，如图2-12所

    示。图2-11 控制台应用程序提示信息图2-12 控制台项目开发环境

    这样，就建立了一个名字为Test的项目文件，下面就需要在该新

    建的控制台项目中建立一个C程序文件，即建立一个扩展名为“.c”的

    文件。

    2.在控制台项目中新建一个C程序文件

    ①单击【FileView】标签，再单击“Test”前的【+】按钮将其展

    开，然后右击“Source Files”选项，在弹出的快捷菜单中选择【添

    加文件到目录】命令，准备在项目中添加一个C程序文件，如图2-13所

    示。

    ②单击【添加文件到目录】命令，打开【插入文件到工程】对话

    框，并输入文件名“test.c”，如图2-14所示。单击【确定】按钮，弹出一个提示信息对话框，提示指定的test.c文件不存在，是否要建

    立一个文件，如图2-15所示。图2-13 在控制台项目中添加C程序文件

    图2-14 在控制台项目中添加一个“test.c”文件对话框

    ③单击【是】按钮，就为项目建立了一个C程序文件，并命名为

    “test.c”。这时就可以编写C语言程序了。

    ④在编辑区编写一个简单的C程序，如图2-16所示。其实，在Visual C++6.0环境中编辑C语言程序、编译、链接及运

    行程序都非常简单。编辑好程序后，只需要单击一个命令按钮就可以

    查看到运行结果了。

    下面，单击工具栏 中的图标可编译程序，单击图标

    可链接程序，单击图标 运行程序，其运行结果如图2-17所示。

    图2-15 添加一个“test.c”文件提示信息对话框

    图2-16 “test.c”源程序图2-17 “Test.c”程序运行结果

    从图2-16中可以看到，Visual C++ 6.0开发环境中包括【文

    件】、【编辑】、【查看】、【插入】、【工程】、【组建】、【工

    具】、【窗口】和【帮助】9个主菜单。其中，【文件】菜单下面主要

    包括【新建】、【打开】、【保存】和【退出】等命令，通过【新

    建】命令，可以创建新的项目文件和C程序文件；【打开】命令可以打

    开一个已经存在的文件，【保存】命令可以将程序文件保存；【退

    出】命令可以用来退出Visual C++ 6.0程序窗口。

    【组建】菜单下面主要包括【编译】、【组建】、【全部重

    建】、【开始调试】和【执行】等命令。其中，【编译】命令用来编

    译项目文件；【链接】命令用来将所有用到的程序文件链接到一起并

    生成扩展名为.exe的文件；【全部重建】命令可以将项目中的所有文

    件进行编译；【开始调试】命令包括断点调试和单步调试；【执行】

    命令用来运行可执行文件。2.2 递归与非递归

    在学习C语言的过程中递归是C语言的重点和难点。在数据结构与

    算法实践过程中，经常会遇到利用递归实现算法的情况。递归是一种

    分而治之、将复杂问题转换为简单问题的求解方法。使用递归可以使

    编写的程序简洁、结构清晰，程序的正确性很容易证明，不需要了解

    递归调用的具体细节。

    本节主要介绍函数的递归调用、如何使用递归巧妙解决看上去比

    较复杂的问题。

    2.2.1 函数的递归调用

    简单来说，函数的递归调用就是自己调用自己 ，即一个函数在调

    用其他函数的过程中，又出现了对自身的调用，这种函数称为递归函

    数。函数的递归调用可分为直接递归调用和间接递归调用。其中，在

    函数中直接调用自己称为函数的直接递归调用 ，如图2-18所示；如果

    函数f1调用了函数f2，函数f2又调用了f1，这种调用方式称为间接递

    归调用 ，如图2-19所示。

    函数的递归调用就是自己调用自己，可以直接调用自己也可以间

    接调用自己。图2-18 直接递归调用过程

    图2-19 间接递归调用过程

    在用递归解决实际问题时，递归函数只知道最基本问题的解。在

    递归函数中，遇到基本问题时仅仅返回一个值，在解决较为复杂的问

    题时，通过将复杂的问题化解为比原有问题更简单、规模更小的问

    题，最后把复杂问题变成一个基本问题，而基本问题的答案是已知

    的，基本问题解决后，比基本问题大一点的问题也得到解决，直到原

    有问题得到解决。

    例如，利用递归求n的阶乘n!。n的阶乘递归定义为n!=n(n-

    1)!，当n=5时，则有

    5!=54!

    4!=43!

    3!=32 !

    2!=21!

    1!=10!

    0!=1

    递归计算5!的过程如图2-20所示。因为5!＝5(5-1)!，因

    此，如果能求出(5-1)!，也就能求出5!；又因为(5-1)!＝(5-

    1)(5-2)!；因此，如果能求出(5-2)!，则也就能求出(5-

    1)!；……最后一直递归到1!＝10!，因此，如果能求出0!，也

    就能求出1!；0!值是1，按上述分析过程逆向推回去，最后便可求得

    5!。

    这样就把求解问题5!分解为求5这个基本问题与求4!这个比较复

    杂的问题，接着继续把求解4!分解为求4这个基本问题与求3!比较复

    杂的问题，直到把原问题变成求解0!=1这个最基本的已知问题为止。

    根据上述分析可知，求解可分成两个阶段，第一阶段是由未知逐

    步推得已知的过程，称为“回推”；第二阶段是与回推过程相反的过

    程，即由已知逐步推得最后结果的过程，称为“递推”。其中，左半

    部分是回推过程，回推过程在计算出0!=1时停止调用；右半部分是递

    推过程，直到计算出5!=120为止。

    2.2.2 递归应用举例下面以具体的例子讲解递归的调用。

    【例2-1】 利用递归求n!。

    【分析】 前面已经分析了递归实现n!的整个过程(见图2-

    20)，只需要做到以下两点就可完成求n!：

    (1)当n=0(递归调用结束，即递归的出口)时，返回1。

    (2)当n≠0时，需要把复杂问题分解成较为简单的问题，直到分

    解成最简单的问题0!=1为止。

    递归求n!的算法实现如下。

    include

    long factorial(int n);

    void main

    {

    int num;

    for(num=0;num<10;num++)

    printf(%d!=%ld\n,num,factorial(num));

    }

    long factorial(int n)

    递归求n!函数实现

    {

    if(n==0)

    当n=0

    时，递归调用出口

    return 1; 0!=1

    是最基本问题的解

    else

    否则

    return nfactorial(n-1);

    递归调用将问题分解成较为简单的问题

    }

    程序运行结果如图2-21所示。图2-20 求5!的间接递归调用过程

    图2-21 递归求n!的运行结果

    【例2-2】 要求利用递归实现求n个数中的最大者。

    【分析】 假设元素序列存放在数组a中，数组a中n个元素的最大

    者可以通过将a[n-1]与前n-1个元素最大者比较之后得到。当n=1时，有findmax(a，n)=a[0]；当n>1时，有findmax(a，n)=(a[n-

    1]>findmax(a，n-1)?a[n-1]:findmax(n-1)。

    也就是说，数组a中只有一个元素时，最大者是a[0]；超过一个元

    素时，则要比较最后一个元素a[n-1]和前n-1个元素中的最大者，其中

    较大的一个即所求。而前n-1个元素的最大者需要继续调用findmax函

    数。

    求n个数中的最大者的递归算法实现如下。

    include

    define N 200

    int findmax(int a[],int n);

    void main

    {

    int a[N],n,i;

    printf(

    请输入n

    的值:);

    scanf(%d,n);

    printf(

    请依次输入%d

    个数：\n,n);

    for(i=0;i
    scanf(%d,a[i]);

    printf(

    在这%d

    个数中，最大的元素是:%d\n,n,findmax(a,n));

    }

    int findmax(int a[],int n)

    {

    int m;

    if(n<=1)

    return a[0];

    else

    {

    m=findmax(a,n-1);

    return a[n-1]>=m?a[n-1]:m;

    }

    }

    程序的运行结果如图2-22所示。【例2-3】 利用递归函数输出正整数和等于n的所有不增的正整数

    和式。例如，当n=5时，不增的和式如下。

    5=5

    5=4+1

    5=3+2

    5=3+1+1

    5=2+2+1

    5=2+1+1+1

    5=1+1+1+1+1

    【分析】 引入数组a，用来存放分解出来的和数，其中，a[k]存

    放第k步分解出来的和数。递归函数应设置3个参数，第1个参数是数组

    名a，用来将数组中的元素传递给被调用函数；第2个参数i表示本次递

    归调用要分解的数；第3个参数k是本次递归调用将要分解出的第k个和

    数。递归函数的原型如下。

    void rd(int a[],int i,int k)

    对将要分解的数i，可分解出来的数j共有i种可能选择，它们是

    i、i-1、…、2、1。但为了保证分解出来的和数依次构成不增的正整

    数数列，要求从i分解出来的和数j不能超过a[k-1]，即上次分解出来

    的和数。

    特别地，为保证对第一步(k=1)分解也成立，程序可在a[0]预置

    n，即第一个和数最大为n。在分解过程中，当分解出来的数j==i时，说明已完成一个和式分解，应将和式输出；当分解出来的数j
    明还有i-j需要进行第k+1次分解。和为n的所有不增正整数和式分解算法实现如下。

    include

    define N 100

    void rd(int a[],int i,int k);

    void main

    {

    int n,a[N];

    printf(

    请输入一个正整数n(1

    ≤n

    ≤20):);

    scanf(%d,n);

    a[0]=n;

    printf(

    不增的和式分解结果:\n);

    rd(a,n,1);

    }

    void rd(int a[],int i,int k)

    {

    int j,p;

    for(j=i;j>=1;j--)

    {

    if(j<=a[k-1])

    {

    a[k]=j;

    if(j==i)

    {

    printf(%d=%d,a[0],a[1]);

    for(p=2;p<=k;p++)

    printf(+%d,a[p]);

    printf(\n);

    }

    else

    rd(a,i-j,k+1);

    }

    }

    }

    程序运行结果如图2-23所示。

    图2-22 递归实现求n个数的最大者程序运行结果图2-23 和式分解

    2.2.3 迭代与递归

    迭代与递归是程序设计中最常用的两种结构。任何能使用递归解

    决的问题都能使用迭代的方法解决。迭代和递归的区别是，迭代使用

    的是循环结构，递归使用的是选择结构。使用递归能够使程序的结构

    更清晰，设计出的程序更简洁、程序更容易让人理解。

    但是，递归也有许多不利之处，大量的递归调用会耗费大量的时

    间和内存。每次递归调用都会建立函数的一个备份，会占用大量的内

    存空间。迭代则不需要反复调用函数和占用额外的内存。通过分析递

    归求n的阶乘n!的计算过程，我们可以把它转化为非递归实现，其非

    递归实现如下。

    int NonRecFact(int n)

    非递归求前n

    的阶乘

    {

    int i,s=1;

    for(i=1;i<=n;i++)

    利用迭代求n

    的阶乘

    s=i; return s;

    }

    对于大整数问题，考虑到n值非常大的情况，运算结果超出一般整

    数的位数，可以用一维数组存储长整数，数组中的每个元素只存储长

    整数的一位数字。如有m位长整数N用数组a[]存储，N=a[m]10 m-1

    +a[m-1]10 m-2 +…+a[2]10 1 +a[1]10 0 ，并用a[0]存储长整数N

    的位数m，即a[0]=m。按上述约定，数组的每个元素存储k的阶乘k!的

    每一位数字，并从低位到高位依次存储于数组的第2个元素、第3个元

    素……例如，6!=720在数组中的存储形式如图2-24所示。

    其中，第一个元素3表示长整数是一个3位数，接着是低位到高位

    的0、2、7，表示长整数720。

    图2-24 k!在数组中的存储情况

    在计算阶乘k!时，可以采用对已求得的阶乘(k-1)!连续累加

    k-1次(即得到k(k-1)!)后得到。例如，已知5!=120，计算

    6!，可对原来的120再累加5次120(即得到65)得到720。具体程序

    实现如下。

    include

    include

    define N 100

    void fact(int a[],int k)

    {

    int b,m,i,j,r,carry;

    m=a[0]; b=(int)malloc(sizeof(int)(m+1));

    for(i=1;i<=m;i++)

    b[i]=a[i];

    for(j=1;j
    {

    for(carry=0,i=1;i<=m;i++)

    {

    r=(i<=a[0]?a[i]+b[i]:a[i])+carry;

    a[i]=r%10;

    carry=r10;

    }

    if(carry)

    a[++m]=carry;

    }

    free(b);

    a[0]=m;

    }

    void write(int a,int k)

    {

    int i;

    printf(%4d!=,k);

    for(i=a[0];i>0;i--)

    printf(%d,a[i]);

    printf(\n);

    }

    void main

    {

    int a[N],n,k;

    printf(

    请输入正整数n

    的值:);

    scanf(%d,n);

    a[0]=1;a[1]=1;

    write(a,1);

    for(k=2;k<=n;k++)

    {

    fact(a,k);

    write(a,k);

    }

    }

    对于较为简单的递归问题，可以利用简单的迭代将其转化为非递

    归。而对于较为复杂的递归问题，需要通过利用数据结构中的栈来消

    除递归。2.3 指针

    指针是C语言中的一个重要概念，也是最不容易掌握的内容。指针常常用在函数的参数传

    递和动态内存分配中。指针与数组相结合，使引用数组成分的形式更加多样化，访问数组元素

    的手段更加灵活；指针与结构体相结合，利用系统提供的动态存储手段，能构造出各种复杂的

    动态数据结构；利用指针形参，使函数能实现传递地址形参和函数形参的要求。在“数据结

    构”课程中，指针的使用非常频繁，因此，要想真正掌握数据结构，就需要灵活、正确地使用

    指针。本节主要介绍指针变量的概念、指针变量的引用、指针与数组、函数指针与指针函数。

    2.3.1 什么是指针

    指针是一种变量，也称指针变量，它的值不是整数、浮点数和字符，而是内存地址。指针

    的值就是变量的地址，而变量又拥有一个具体值。因此，可以理解为变量名直接引用了一个

    值，指针间接地引用了一个值。

    在理解指针之前，先来了解下地址的概念。图2-25展示了变量在内存中的存储情况。假设

    a、b、c、d、bPtr分别是5个变量，其中，a、b、c、d是整型变量，bPtr是指针变量。整型变

    量在内存中占用4个字节，变量a的存放地址是2000、2001、2002和2003四个内存单元，变量b

    存放在2004～2007内存单元中，变量bPtr存放在4600～4603四个内存单元中。整型变量a、b、c、d的内容分别是25、12、78、5，而指针变量bPtr的内容是一个地址，为2004开始的内存地

    址，即bPtr存放的是变量b的地址，换句话说，就是bPtr指向变量b的存储位置，可以用一个箭

    头表示从地址是4600的位置指向变量地址为2004的位置。

    一个存放变量地址的类型称为该变量的“指针”。如果有一个变量用来存放另一个变量的

    地址，则称这个变量为指针变量。在图2-26中，qPtr用来存放变量q的地址，qPtr就是一个指

    针变量。

    在C语言中，所有变量在使用前都需要声明。例如，声明一个指针变量的语句如下。

    int qPtr,q; q是整型变量，表示要存放一个整数类型的值；qPtr是一个整型指针变量，表示要存放一

    个变量的地址，而这个变量是整数类型。qPtr叫做一个指向整型的指针。

    说明 在声明指针变量时，“”只是一个指针类型标识符，指针变量的声明也可以写成

    intqPtr。

    指针变量可以在声明时赋值，也可以在声明后赋值。例如，在声明时为指针变量赋值的语

    句如下。

    int q=12；

    int qPtr=q;

    或在声明后为指针变量赋值，语句如下。

    int q=12,qPtr;

    qPtr=q;

    这两种赋值方法都是把变量q的地址赋值给指针变量qPtr。qPtr=q叫做指向变量q，其

    中，是取地址运算符，表示返回变量q的地址。指针变量qPtr与变量q的关系如图2-26所示。

    图2-25 指针变量在内存中的表示

    图2-26 q直接引用一个值和qPtr间接引用一个变量q直接引用和间接引用可以用日常生活中的两个抽屉来形象说明。有两个抽屉A和B，抽屉A

    有一把钥匙，抽屉B也有一把钥匙。为了方便，可以把两把钥匙都带在身上，需要取抽屉A中的

    东西时直接用钥匙A打开抽屉；也可以为了安全，把钥匙A放到抽屉B中，把抽屉B的钥匙带在身

    上，需要取抽屉A中的东西时，先打开抽屉B，再取出抽屉A的钥匙，然后打开抽屉A，取出需要

    的东西。前一种方法就相当于通过变量直接引用，后一种方法相当于通过指针间接引用。其

    中，抽屉B的钥匙相当于指针变量，抽屉A的钥匙相当于一般的变量。

    2.3.2 指针变量的间接引用

    与普通变量一样，指针变量也可以对数据进行操作。指针变量主要通过取地址运算符和

    指针运算符来存取数据。例如，a指的是变量a的地址，ptr表示变量ptr所指向的内存单元

    存放的内容。下面通过具体例子说明和运算符及指针变量的使用。

    【例2-4】 利用变量和指针变量存取数据。

    【分析】 主要考查如何利用和运算符来存取变量中的数据，取地址运算符和指针运算

    符是互逆的操作，应灵活掌握两个运算符的使用技巧。程序代码如下。

    include

    void main

    {

    int q=12;

    int qPtr;

    声明指针变量qPtr

    qPtr=q;

    指针变量qPtr

    指向变量q

    打印变量q

    的地址和qPtr

    的内容

    printf(q

    的地址是：%p\nqPtr

    中的内容是：%p\n,q,qPtr);

    打印q

    的值和qPtr

    指向变量的内容

    printf(q

    的值是：%d\nqPtr

    的值是：%d\n,q,qPtr);

    运算符''

    和''

    是互逆的

    printf(qPtr=%p,qPtr=%p\n

    因此有qPtr=qPtr\n,qPtr,qPtr);

    }

    程序运行结果如图2-27所示。图2-27 利用变量与指针变量进行存取操作的运行结果

    和作为单目运算符，结合性是从右到左，优先级别相同，因此对于表达式qPtr来说，先进行运算，后进行运算。因为qPtr是指向变量q的，所以qPtr的值为q，qPtr就是对q取

    地址，即q，q的地址。qPtr是先进行取地址运算即qPtr，即qPtr的地址，然后进行运

    算，那么qPtr就是qPtr本身，即q的地址。因此，qPtr和qPtr是等价的。

    注意 指针变量只能用来存放地址，不能将一个整型值赋给一个指针变量。而且指针变

    量的类型应和所指向的变量的类型一致，例如整型指针只能指向整型变量，不能指向浮点型变

    量。指针变量是一种数据类型，表明该变量用来存放变量的地址；变量指针是变量的地址。

    2.3.3 指针与数组

    指针可以与变量结合，也可以与数组结合使用。指针数组和数组指针是两个截然不同的概

    念，指针数组是一种数组，该数组存放的是一组变量的地址。数组指针是一个指针，表示该指

    针是指向数组的指针。

    1.指向数组元素的指针

    指针可以指向变量，也可以指向数组及数组中的元素。

    例如定义一个整型数组和一个指针变量，语句如下。

    int a[5]={10,20,30,40,50};

    int aPtr;

    这里的a是一个数组，它包含了5个整型数据。变量名a就是数组a的首地址，它与a[0]等

    价。如果令aPtr=a[0]或者aPtr=a，则aPtr也指向了数组a的首地址。如图2-28所示。也可以在定义指针变量时直接赋值，如以下语句是等价的。

    int aPtr=a[0];

    int aPtr;

    aPtr =a[0];

    与整型、浮点型数据一样，指针也可以进行算术运算，但含义却不同。当一个指针加

    1(或减)1并不是指针值增加(或减少)1，而是使指针指向的位置向后(或向前)移动了一

    个位置，即加上(或减去)该整数与指针指向对象的大小的乘积。例如对于aPtr+=3，如果一

    个整数占用4个字节，则相加后aPtr=2000+43=2012(这里假设指针的初值是2000)。同样指

    针也可以进行自增(++)运算和自减(--)运算。

    也可以用一个指针变量减去另一个指针变量。例如，指向数组元素的指针aPtr的地址是

    2008，另一个指向数组元素的指针bPtr的地址是2000，则a=aPtr-bPtr的运算结果就是把从

    aPtr到bPtr之间的元素个数赋给a，元素个数为(2008-2000)4=2(假设整数占用4个字

    节)。

    我们也可以通过指针来引用数组元素。例如以下语句。

    (aPtr+2);

    如果aPtr是指向a[0]，即数组a的首地址，则aPtr+2就是数组a[2]的地址，(aPtr+2)就

    是30。

    注意 指向数组的指针可以进行自增或自减运算，但是数组名则不能进行自增或自减运

    算，这是因为数组名是一个常量指针，它是一个常量，常量值是不能改变的。

    【例2-5】 用指针引用数组元素并打印输出。

    【分析】 主要考查指针与数组结合进行的运算，有指针对数组的引用及指针的加、减运

    算。指针及数组对元素操作的实现如下。

    include

    void main

    {

    int a[5]={10,20,30,40,50};

    int aPtr,i;

    指针变量声明

    aPtr=a[0];

    指针变量指向变量q for(i=0;i<5;i++)

    通过数组下标引用元素的方式输出数组元素

    printf(a[%d]=%d\n,i,a[i]);

    for(i=0;i<5;i++)

    通过数组名引用元素的方式输出数组元素

    printf((a+%d)=%d\n,i,(a+i));

    for(i=0;i<5;i++)

    通过指针变量下标引用元素的方式输出数组元素

    printf(aPtr[%d]=%d\n,i,aPtr[i]);

    for(aPtr=a,i=0;aPtr
    通过指针变量偏移引用元素的方式输出数组元素

    printf((aPtr+%d)=%d\n,i,aPtr);

    }

    程序中共有4个for循环，其中第一个for循环是利用数组的下标访问数组的元素，第二个

    for循环是利用使用数组名访问数组的元素，在C语言中，地址也可以像一般的变量一样进行

    加、减运算，但是指针的加1和减1表示的是一个元素单元。第三个for循环是利用指针访问数

    组中的元素，第四个for循环则是先将指针偏移，然后访问该指针所指向的内容。

    上述4种访问数组元素的方法表明，在C语言中指针的运用非常灵活。

    程序运行结果如图2-29所示。

    图2-28 数组的指针与数组在内存中的关系图2-29 指针引用数组元素的运行结果

    2.指针数组

    指针数组 其实也是一个数组，只是数组中的元素是指针类型的数据。换句话说，指针数

    组中的每一个元素都是一个指针变量。

    定义指针数组的方式如下。

    int p[4];

    由于[]运算符优先级比高，p优先与[]结合，形成p[]数组形式，然后与结合，表示该数

    组是指针类型的，每个数组元素是一个指向整型的变量。从字面上理解，指针数组首先是一个

    数组，这个数组存放的是指针类型的变量。

    指针数组常常用于存储一些长度不等的字符串数据，有的读者可能会问，为什么不存放在

    二维数组中？这是因为字符串长度不等，若将这些字符串存放在二维数组中，就需要定义一个

    能容纳最长字符串的二维数组，这样就会出现一部分存储空间不能得到有效利用。

    例如字符串“C Programming Language”、“Assembly Language”、“Data

    Structure”和“Natural Language”在二维数组中的存储情况，如图2-30所示。图2-30 字符串在二维数组中的存储情况

    不难看出，利用二维数组保存多个字符串时，为了保证能存储所有的字符串，必须按最长

    的字符串长度来定义二维数组的列数。为了节省存储单元，可以采用指针数组保存字符串，定

    义如下。

    char s[4]={C Programming Language,Assembly Language,Java Language,Natural Language};

    在指针数组中存储字符串的情况如图2-31所示。

    图2-31 字符串在指针数组中的存储情况

    这样在字符串比较多且长度不一时，就可以大大地节省内存空间。

    【例2-6】 用指针数组保存字符串并将字符串打印输出。

    【分析】 主要考查指针的应用及对指针数组概念的理解，其实s[4]就是一个特殊的数

    组，s[0]、s[1]、s[2]、s[3]分别存放指向4个字符串指针，即数组保存的是各个字符串的首

    地址。代码如下。

    include

    void main

    {

    定义指针数组

    char s[4]={C Programming Language,Assembly Language, Data Structure ,Natural Language};

    int n=4;

    指针数组元素的个数

    int i;

    char aPtr;

    第1

    种方法输出：通过数组名输出字符串

    printf(

    第1

    种方法输出：通过指针数组的数组名输出字符串:\n); for(i=0;i
    printf(

    第%d

    个字符串：%s\n,i+1,s[i]);

    第2

    种方法输出：通过指向数组的指针输出字符串

    printf(

    第2

    种方法输出：通过指向数组的指针输出字符串:\n);

    for(aPtr=s[0],i=0;i
    {

    printf(

    第%d

    个字符串：%s\n,i+1,aPtr);

    i++;

    }

    }

    程序运行结果如图2-32所示。

    【例2-7】 利用指针数组实现对一组变量的值按照从小到大排序，排序时交换指向变量的

    指针值。

    【分析】 主要考查指针数组的概念及用法。让指针数组的各成分分别指向各变量，通过

    指针数组引用变量的值并交换之，使存放在指针数组中各分量指向的变量值从小到大顺序排

    列。实现代码如下。

    include

    void bubble(int a[],int n);

    void main

    {

    int a,b,c,d,e,f,i;

    int vp[]={a,b,c,d,e,f};

    printf(

    请输入a,b,c,d,e,f

    的值：);

    scanf(%d%d%d%d%d%d,a,b,c,d,e,f);

    bubble(vp,sizeof(vp)sizeof(vp[0]));

    for(i=0;i
    printf(%4d,vp[i]);

    printf(\n);

    }

    void bubble(int a[],int n)

    {

    int i,j,flag,t;

    for(i=0;i
    {

    flag=0;

    for(j=0;j
    if(a[j]>a[j+1])

    {

    t=a[j];

    a[j]=a[j+1];

    a[j+1]=t;

    flag=1;

    }

    if(flag==0)

    return;

    }

    }

    程序运行结果如图2-33所示。图2-32 字符数组输出结果

    图2-33 程序运行结果

    3.数组指针

    数组指针 是指向数组的一个指针。如下定义。

    int (p)[4];

    其中，p是指向一个拥有4个元素的数组指针，数组中每个元素都为整型。与前面刚刚介绍

    过的指针数组做比较，这里定义的数组指针多了一对括号，p两边的括号不可以省略。这里定

    义的p仅仅是一个指针，不过这个指针有点特殊，这个p指向的是包含4个元素的一维数组。数

    组指针p与它指向的数组之间的关系可以用图2-34来表示。

    如果有如下语句。

    int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};

    p=a;

    数组指针p与数组a中元素之间的关系如图2-35所示。其中，(p)[0]、(p)[1]、(p)[2]、(p)[3]分别保存的是元素值为1、2、3、4的地址。p、p+1和p+2分别指向二维

    数组的第一行、第二行和第三行，p+1表示将指针p移动到下一行。图2-34数组指针p的表示

    图2-35 数组指针p与二维数组的对应关系

    (p+1)+2表示数组a第1行第2列的元素的地址，即a[1][2]，((p+1)+2)表示a[1]

    [2]的值即7，其中1表示行，2表示列。下面编程输出以上数组指针的值和数组的内容。

    【例2-8】 在屏幕上打印图2-35中数组指针p及数组a中的元素。

    【分析】 主要考查利用数组指针引用数组中的元素的方法。数组指针p与数组a中元素的

    对应关系如图2-35所示。通过利用数组指针p引用数组a中的元素并输出p的值，以验证对指针

    引用的正确性，加深对数组指针的理解。实现代码如下。

    include

    void main

    {

    int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};

    int (p)[4];

    声明数组指针变量p

    int row,col;

    p=a;

    指针p

    指向数组元素为4

    的数组

    打印输出数组指针p

    指向的数组的值

    for(row=0;row<3;row++)

    {

    for(col=0;col<4;col++)

    printf(a[%d,%d]=%-4d,row,col,((p+row)+col));

    printf(\n);

    }

    通过改变指针p

    修改数组a

    的行地址，改变col

    的值修改数组a

    的列地址

    for(p=a,row=0;p
    {

    for(col=0;col<4;col++)

    printf((p[%d])[%d]=%p,row,col,((p)+col));

    printf(\n);

    }

    }

    程序运行结果如图2-36所示。图2-36 打印输出数组指针和数组元素

    注意 区别数组指针和指针数组。数组指针首先是一个指针，并且它是一个指向数组的

    指针。指针数组首先是一个数组，并且它是保存指针变量的数组。

    2.3.4 指针函数与函数指针

    与指针数组、数组指针一样，指针函数与函数指针也是一对孪生兄弟，也是常常容易混淆

    的概念。顾名思义，指针函数是一种函数，它表示函数的返回值是指针类型；函数指针是指针

    的一种，它表示该指针指向一个函数。

    1.指针函数

    指针函数 是指函数的返回值是指针类型的函数。在C语言中，一个函数的返回值可以是整

    型、实型和字符型，也可以是指针类型。例如，以下是一个指针函数的定义。

    float func(int a,int b);

    其中，func是函数名，前面的“”表明返回值的类型是指针类型，因为前面的类型标识

    符是float，所以返回的指针是指向浮点型的。该函数有两个参数，参数类型都是整型。下面

    我们还是通过一个具体实例来介绍指针函数的用法。

    【例2-9】 假设若干个学生的成绩在二维数组中存放，要求输入学生编号，利用指针函数

    实现其成绩的输出。

    【分析】 主要考查指针函数的使用。学生成绩存放在二维数组中，每一行存放一个学生

    的成绩，通过输入学生编号，返回该学生存放成绩的地址，然后利用指针输出每一门的学生成绩。程序实现如下。

    include

    int FindAddress(int (ptr)[4],int n);

    声明查找成绩地址函数

    void Display(int a[][4],int n,int p);

    声明输出成绩函数

    void main

    {

    int row,n=4;

    int p;

    int score[3][4]={{83,78,79,88},{71,88,92,63},{99,92,87,80}};

    printf(

    请输入学生编号(1

    或2

    或3).

    输入0

    退出程序.\n);

    scanf(%d,row);

    输入要输出学生成绩的编号

    while(row)

    {

    if(row==1||row==2||row==3)

    {

    printf(

    第%d

    个学生的成绩4

    门课的成绩是：\n,row);

    p=FindAddress(score,row-1);

    调用指针函数

    Display(score,n,p);

    调用输出成绩函数

    printf(

    请输入学生编号(1

    或2

    或3).

    输入0

    退出程序.\n);

    scanf(%d,row);

    }

    else

    {

    printf(

    输入不合法，请重新输入(1

    或2

    或3)

    ，输入0

    退出程序.\n);

    scanf(%d,row);

    }

    }

    }

    int FindAddress(int (ptrScore)[4],int n)

    查找某条学生成绩记录地址函数。通过传递的行地址找到要查找学生成绩的地址，并返回行地址

    {

    int ptr;

    ptr=(ptrScore+n);

    修改行地址，即找到学生的第一门课成绩的地址

    return ptr;

    }

    void Display(int a[][4],int n,int p)

    输出学生成绩的实现函数。利用传递过来的指针输出每门课的成绩

    {

    int col;

    for(col=0;col
    printf(%4d,(p+col));

    输出查找学生的每门课成绩

    printf(\n);

    }

    程序运行结果如图2-37所示。图2-37 通过指针函数返回指针并输出成绩的运行结果

    主函数通过语句p=FindAddress(score，row-1)；调用指针函数

    FindAddress(int(ptrScore)[4]，int n)，并把二维数组的行地址传递给形式参数

    ptrScore，在FindAddress(int(ptrScore)[4]，int n)中，执行语句

    ptr=(ptrScore+n)，返回行指针ptr，然后调用Display(score，n，p)输出成绩。在

    Display(int a[][4]，int n，intp)中，通过p+col改变列地址，即找到该学生成绩的每门

    课的位置，依次输出每门课的成绩。

    2.函数指针

    指针可以指向变量、数组，也可以指向函数，指向函数的指针就是函数指针。与数组名类

    似，函数名就是程序在内存中的起始地址。指向函数的指针可以把地址传递给函数，也可以从

    函数返回给指向函数的指针。

    【例2-10】 通过一个函数求两个数的乘积，并通过函数指针调用该函数。

    【分析】 主要考查函数指针的调用方法。程序实现代码如下。

    include

    包含输入输出

    int Mult(int a,int b);

    声明两个数乘积的函数

    void main

    {

    int a,b;

    int (func)(int,int);

    声明一个函数指针

    printf(

    请输入两个数:);

    scanf(%d,%d,a,b);

    第1

    种调用函数的方法：函数名调用求两个数乘积函数

    printf(

    第第1

    种调用函数的方法：函数名调用求两个数乘积的函数:\n);

    printf(%d%d=%d\n,a,b,Mult(a,b));

    通过函数名调用

    第2

    种调用函数的方法：函数指针调用求两个数乘积的函数

    func=Mult;

    函数指针指向求乘积函数

    printf(

    第2

    种调用函数的方法：函数指针调用求两个数乘积函数:\n);

    printf(%d%d=%d\n,a,b,(func)(a,b));

    通过函数指针调用函数

    }

    int Mult(int x,int y)

    实现求两个数乘积函数

    {

    return xy;

    }

    程序运行结果如图2-38所示。

    语句int(func)(int，int)；声明一个指向函数的指针变量，并且所指向的函数返回

    值为整型，它有两个整型参数。

    在声明函数中，由于运算符的优先级比运算符高，所以不可以省略。

    语句func=Mult；表示函数指针func指向函数Mult，func和Mult均指向函数Mult的起始地

    址，程序在编译阶段会被翻译成一行行指令并被装入到内存区域，如图2-39所示。

    图2-38 函数指针调用求两个数乘积函数的运行结果

    图2-39 函数指针在内存中的表示其中，主函数中的语句(func)(a，b)；是执行调用求两个数乘积函数的，因为函数

    本身就是一个地址，也可以写成func(a，b)的形式。

    函数指针还可以作为参数传递给其他函数。

    【例2-11】 利用函数指针作为函数参数，实现选择排序算法的升序排列和降序排列。

    【分析】 主要考查函数指针作为函数参数的使用。程序实现代码如下。

    include

    包含输入输出函数

    define N 10

    数组元素个数

    int Ascending(int a,int b);

    是否进行升序排列

    int Descending(int a,int b);

    是否进行降序排列

    void swap(int ,int );

    交换数据

    void SelectSort(int a[],int n,int (compare)(int,int));

    选择排序，函数指针作为参数调用

    void Display(int a[],int n);

    输出数组元素

    void main

    {

    int a[N]={22,55,12,7,19,65,81,3,30,52};

    int flag;

    while(1)

    {

    printf(1:

    从小到大排序.\n2:

    从大到小排序.\n0:

    结束!\n);

    printf(

    请输入：);

    scanf(%d,flag);

    switch(flag)

    {

    case 1:

    printf(

    排序前的数据为:);

    Display(a,N);

    SelectSort(a,N,Ascending);

    从小到大排序，将函数作为参数传递

    printf(

    从小到大排列后的元素序列为:);

    Display(a,N);

    break;

    case 2:

    printf(

    排序前的数据为:);

    Display(a,N);

    SelectSort(a,N,Descending);

    从大到小排序，将函数作为参数传递

    printf(

    从大到小排列后的元素序列为:);

    Display(a,N);

    break;

    case 0:

    printf(

    程序结束!\n);

    return;

    break;

    default:

    printf(

    输入数据不合法，请重新输入.\n);

    break;

    }

    }

    }

    选择排序，将函数作为参数传递，判断是从小到大还是从大到小排序

    void SelectSort(int a[],int n,int(compare)(int,int))

    {

    int i,j,k; for(i=0;i
    {

    j=i;

    for(k=i+1;k
    if((compare)(a[k],a[j]))

    j=k;

    swap(a[i],a[j]);

    }

    }

    交换数组的元素

    void swap(int a,int b)

    {

    int t;

    t=a;

    a=b;

    b=t;

    }

    判断相邻数据大小，如果前者大，升序排列需要交换

    int Ascending(int a,int b)

    {

    if(a
    return 1;

    else

    return 0;

    }

    判断相邻数据大小，如果前者大，降序排列需要交换

    int Descending(int a,int b)

    {

    if(a>b)

    return 1;

    else

    return 0;

    }

    输出数组元素

    void Display(int a[],int n)

    {

    int i;

    for(i=0;i
    printf(%4d,a[i]);

    printf(\n);

    }

    程序运行结果如图2-40所示。

    图2-40 函数指针作为函数参数传递的排序运行结果

    其中，函数SelectSort(a，N，Ascending)中的参数Asscending是一个函数名，传递给

    函数定义void SelectSort(int a[]，int n，int(compare)(int，int))中的函数指针

    compare，这样指针就指向了Asscending。从而可以在执行语句(compare)(a[j]，a[j+1])时调用函数Ascending(int a，int b)判断是否需要交换数组中两个相邻的元素，然后调用swap(a[j]，a[j+1])进行交换。

    3.函数指针数组

    假设有3个函数f1、f2和f3，可以把这3个函数作为数组元素存放在一个数组中，需要定义

    一个指向函数的指针数组指向这三个函数，代码如下。

    void (f[3])(int)={f1,f2,f3};

    f是包含3个指向函数指针元素的数组，f[0]、f[1]和f[2]分别指向函数f1、f2和f3。通过

    函数指针f调用函数的形式如下。

    f[n](m); n

    和m

    都是整数

    【例2-12】 声明一个指向函数的指针数组，并通过指针调用函数。

    【分析】 主要考查指向函数的指针数组的使用。程序实现如下。

    include

    void f1(int n);

    函数f1

    声明

    void f2(int n);

    函数f2

    声明

    void f3(int n);

    函数f3

    声明

    void main

    {

    void (f[3])={f1,f2,f3};

    声明指向函数的指针数组

    int flag;

    printf(

    调用函数请输入1

    、2

    或者3

    ，结束程序请输入0。\n);

    scanf(%d,flag);

    while(flag)

    {

    if(flag==1||flag==2||flag==3)

    {

    f[flag-1](flag);

    通过函数指针调用数组中的函数

    printf(

    请输入1

    、2

    或者3

    ，输入0

    结束程序.\n);

    scanf(%d,flag);

    }

    else {

    printf(

    请输入一个合法的数(1~3),输入0

    结束程序.\n);

    scanf(%d,flag);

    }

    }

    printf(

    程序结束.\n);

    }

    void f1(int n)

    函数f1

    的定义

    {

    printf(

    函数f%d:

    调用第%d

    个函数!\n,n,n);

    }

    void f2(int n)

    函数f2

    的定义

    {

    printf(

    函数f%d:

    调用第%d

    个函数!\n,n,n);

    }

    void f3(int n)

    函数f3

    的定义

    {

    printf(

    函数f%d:

    调用第%d

    个函数!\n,n,n);

    }

    程序的运行结果如图2-41所示。

    图2-41 指针调用保存在数组中的函数的运行结果

    注意 函数指针不能执行像f+1、f++、f--等运算。2.4 参数传递

    在程序设计过程中，参数传递是经常会遇到的情况。在C语言中，函数的参数传递的方式通常有两种，一种是传值的方式；另一种是传

    地址的方式。本节主要介绍传值调用和传地址调用。

    2.4.1 传值调用

    在函数调用时，一般情况下，调用函数和被调用函数之间会有参

    数传递。调用函数后面括号里面的参数是实际参数 ，被调用函数中的

    参数是形式参数 。传值调用是建立参数的一个副本并把值传递给形式

    参数，在被调用函数中修改形式参数的值，并不会影响到调用函数实

    际参数的值。

    【例2-13】 编写一个函数，求两个整数的最大公约数。

    【分析】 通过传值调用的方式，把实际参数的值传递给形式参

    数，其实形式参数是实际参数的一个副本(拷贝)。其程序实现如

    下。

    include

    包含输入输出函数

    int GCD(int m,int n);

    求两个整数的最大公约数的函数声明

    void main

    {

    int a,b,v;

    printf(

    请输入两个整数请输入两个整数:);

    scanf(%d,%d,a,b);

    v=GCD(a,b);

    调用求两个数中的较大者的函数

    printf(%d

    和%d

    的最大公约数为:%d\n,a,b,v);

    }

    int GCD(int m,int n)

    求两个整数的最大公约数，并返回公约数

    {

    int r;

    r=m;

    do

    {

    m=n;

    n=r;

    r=m%n;

    }while(r);

    return n;

    }

    程序的输出结果如图2-42所示。

    假设输入两个数15和25，在主函数中，将15和25分别赋值给实际

    参数a和b，通过语句s=GCD(a，b)调用实现函数GCD(int x，int

    y)也就是所谓的被调用函数，将15和25分别传递给被调用函数的形式

    参数m和n。然后求m和n的最大公约数，通过语句return n；将最大公

    约数5返回给主函数，即被调用函数，因此输出结果为5。

    上述函数参数传递属于参数的单向传递，即a和b可以把值分别传

    递给m和n，而不可以把m和n传递给a和b。在传值调用中，实际参数和

    形式参数分别占用不同的内存单元，形式参数是实际参数的一个副

    本，实际参数和形式参数的值的改变都不会相互受到影响，如图2-43

    所示。这就像有一张身份证原件，它的复印件就是个副本，复印件的丢失不会影响到身份证原件的存在，身份证原件的丢失也不会影响到

    复印件的存在。

    图2-42 求两个整数的最大公约数运行结果

    图2-43 参数传递过程

    图2-44 形式参数改变后的情况

    在调用函数时，形式参数被分配存储单元，并把15和25传递给形

    式参数，在函数调用结束，形式参数被分配的存储单元被释放，形式参数不复存在，而主函数中的实际参数仍然存在，并且其值不会受到

    影响。在被调用函数中，如果改变形式参数的值，假设把m和n的值分

    别改变为20和35，a和b的值不会改变，如图2-44所示。

    2.4.2 传地址调用

    C语言通过指针(地址)实现传地址调用。在函数调用过程中，如

    果需要在被调用函数中修改参数值，则需要把实际参数的地址传递给

    形式参数，通过修改该地址的内容改变形式参数的值，以达到修改调

    用函数中实际参数的目的。

    【例2-14】 编写一个求两个整数较大者和较小者的函数，要求用

    传地址方式实现。

    【分析】 通过传地址调用的方式，把两个实际参数传递给形式参

    数。在被调用函数中，先比较两个形式参数值的大小，如果前者小于

    后者，则交换两个参数值，其中，前者为大，后者为小。传地址调用

    时，在调用函数和被调用函数中，对参数的操作其实都是在对同一块

    内存操作，实际参数和形式参数共用同一块内存。其程序实现如下。

    include

    包含输入输出函数

    void Swap(int x,int y);

    函数声明

    void main

    {

    int a,b;

    printf(

    请输入两个整数：\n);

    scanf(%d,%d,a,b); if(a
    Swap(a,b);

    两个数中如果前者小，则交换两个值，使其较大的保存在a

    中较小保存在b

    中

    printf(

    在两个整数%d

    和%d

    中，较大者为:%d,较小者为:%d\n,a,b,a,b);

    }

    void Swap(int x,int y)

    交换两个数，较大的保存在x

    中，较小的保存在y

    中

    {

    int z;

    z=x;

    x=y;

    y=z;

    }

    程序的运行结果如图2-45所示。

    图2-45 传地址方式求两个整数的较大者和较小者的程序运行结果

    在主函数中，如果a
    其中，实际参数是变量的地址，就是把地址传递给被调用函数

    Swap(intx，inty)中的形式参数x和y，x和y是指针变量，即指针x

    和y指向变量a和b。这样，交换x和y的值就是交换a和b的值。函数调

    用时，实际参数和形式参数的变化情况如图2-46所示。如果要修改多个参数的值并返回给调用函数，该怎么呢？这就需

    要将数组名作为参数传递给被调用函数。数组名作为参数传递时，传

    递的是整个数组。数组名是数组的首地址，如果把数组名作为实际参

    数，在函数调用时，会把数组的首地址传递给形式参数。这样形式参

    数就可以根据数组的首地址访问整个数组并对其操作，这是因为整个

    数组元素的地址是连续的。

    下面是一个数组名作为参数传递的例子。

    图2-46 实际参数和形式参数的变化情况【例2-15】 编写函数，要求将数组中的n个元素的值分别减去

    20。

    【分析】 数组名作为参数传递给被调用函数，实际上是把数组的

    起始地址传递给形式参数。因为数组在内存中存储的连续性，可以利

    用数组下标和指针访问数组中的每一个元素，这样在被调用函数中就

    可以对整个数组进行操作，无须将每一个数据元素作为参数传递给被

    调用函数。将数组名作为参数传递，调用函数和被调用函数都是对占

    同一块内存单元的数组进行操作。其程序实现如下。

    include

    包含输入输出函数

    define N 10

    void SubArray1(int x,int n);

    数组名作为参数的函数原型

    void SubArray2(int aPtr,int n);

    指针作为参数的函数原型

    void main

    {

    int a[N]={51,52,53,54,55,56,57,58,59,60};

    int i;

    printf(

    原来数组中的元素为:\n);

    for(i=0;i
    printf(%4d,a[i]);

    printf(\n);

    printf(

    数组中的元素第一次减去20

    之后为:\n);

    SubArray1(a,N);

    调用SubArray1

    ：数组名作为参数的函数

    for(i=0;i
    printf(%4d,a[i]);

    printf(\n);

    printf(

    数组中的元素第二次减去20

    之后为:\n);

    SubArray2(a,N);

    调用SubArray2

    ：指针作为参数的函数

    for(i=0;i
    printf(%4d,a[i]);

    printf(\n);

    }

    void SubArray1(int b[],int n)

    数组名作为参数，将数组中的元素减去20 {

    int i;

    for(i=0;i
    b[i]=b[i]-20;

    }

    void SubArray2(int aPtr,int n)

    指针作为参数，将数组中的元素减去20

    {

    int i;

    for(i=0;i
    (aPtr+i)=(aPtr+i)-20;

    }

    程序运行结果如图2-47所示。

    该函数以两种方式实现了函数调用，即数组名作为形式参数和指

    针作为形式参数。在许多情况下，数组和指针效果是一样的。

    在没有调用函数SubArray1(int b[]，int n)之前，数组a在内

    存中的情况如图2-48所示。数组元素被保存在一个联系的存储单元

    中，数组名a指向数组的第一个元素。在调用函数SubArray1(int

    b[]，int n)后，参数传递给数组名b，b也指向数组a的第一个元素，然后对所有元素减去20，如图2-49所示。调用函数

    SubArray2(intaPtr，int n)后，参数传递给指针变量aPtr，aPtr

    也指向了数组a，并再一次把数组元素减去20，如图2-50所示。

    图2-47 数组中的元素减去20后的程序运行结果图2-48 未调用函数前

    图2-49 第一次数组元素被减去20后

    图2-50 第二次数组元素被减去20后

    注意 在传值调用中，参数传递是单向传递，只能由实际参数传

    递给形式参数，而不能把形式参数反向传递给实际参数。而在传地址

    调用中，对形式参数的操作，即是对实际参数的操作，它们拥有同一

    块内存单元，属于双向传递。2.5 结构体与联合体

    结构体和联合体(也称共用体)是自定义的数据类型，用于构造非数值数据类

    型，在处理实际问题中应用非常广泛。数据结构中的链表、队列、树、图等结构都

    需要用到结构体。本节主要介绍结构体、联合体及其应用。

    2.5.1 结构体的定义

    一个教职工基本情况表包括编号、姓名、性别、职称、学历和联系电话等信

    息，每个数据信息的类型并不相同，使用前面学过的数据类型不能将这些信息有效

    组织起来。每一个教职工都包含编号、姓名、性别、职称、学历和联系电话等数据

    项，这些数据项放在一起构成的信息称为一个记录。例如，一个教师基本情况表如

    表2-1所示。

    表2-1 教师基本情况表

    要用C语言描述表中的某一条记录，需要定义一种特殊的类型，这种类型就是结

    构体类型。它的定义如下。

    struct teacher

    结构体类型

    {

    int no;

    编号

    char name[20];

    姓名

    char sex[4];

    性别

    char headship[8];

    职称

    char degree[6];

    学历

    long int phone;

    联系电话联系电话

    };

    其中，struct teacher就是新的数据类型──结构体类型，no、name、sex、headship、degree和phone为结构体类型的成员，表示记录中的数据项。这样，结构

    体类型struct teacher就可以完整地表示一个教师信息了。

    定义结构体类型的一般格式如下。

    struct

    结构体名

    {

    成员列表;

    };

    struct与结构体名合在一起构成结构体类型，结构体名与变量名的命名规则一

    样。前面的student就是结构体名。使用一对花括号将成员列表括起来，在右花括号

    外使用一个分号作为定义结构体类型的结束。前面的no、name、sex等都是结构体类

    型的成员，每个成员需要说明其类型，就像定义变量一样。

    注意 在定义结构体类型时，struct不可以省略。struct和结构体名一起构成

    结构体类型，例如，前面的struct teacher是结构体类型，而teacher只是结构体

    名。不要遗漏结构体外的分号，这是非常容易出错的地方。

    像上面介绍的struct teacher类型是无法用C语言中的整型、浮点型、字符型等

    基本数据类型描述的，只能用其他数据类型构造出新的数据类型。例如，一个学生

    记录可能包括学号、姓名、性别、年龄及成绩等数据项，学生的记录可以用以下的

    结构体类型描述。

    struct student

    {

    char no;

    int name;

    char sex;

    int age;

    float score;

    }; 其中，struct是关键字，表示是一个结构体类型，大括号里面是结构体的成

    员；struct student是一个类型名，如果要定义一个结构体变量，例如如下语句。

    struct student stu1;

    stu1就是类型为结构体struct student类型的变量。如果给结构体变量stu1的

    成员分别赋值，语句如下。

    stu1.no=13001;

    stu1.age=20;

    stu1.name=Zhu Tong;

    stu1.sex='m';

    stu1.score=89.0;

    则stu1的结构如图2-51所示。

    图2-51 stu1的结构

    结构体的变量定义也可以和定义结构体类型同时定义。例如如下语句。

    struct student

    {

    char no;

    int name;

    char sex;

    int age;

    float score;

    }stu1;

    同样，也可以定义结构体数组类型。结构体变量的定义与初始化可以分开进

    行，也可以在结构体数组的定义的时候初始化，例如如下语句。

    struct student

    {

    char no;

    char name;

    char sex;

    int age;

    float score; }stu[2]={{13001,Zhu Tong,'m',22,90},{13002,Guo Jing,'f',21,82}};

    数组中各个元素在内存中的情况如图2-52所示。

    图2-52 结构体数组stu在内存中的结构

    2.5.2 指向结构体的指针

    指针可以指向整型、浮点型、字符等基本类型变量，同样也可以指向结构体变

    量。指向结构体变量的指针的值是结构体变量的起始地址。指针可以指向结构体，也可以指向结构体数组。指向结构体的指针和指向变量和指向数组的指针的用法类

    似。

    【例2-16】 利用指向结构体数组的指针输出学生基本信息。

    【说明】 指向结构体的指针与指向数组的指针一样，结构体中的成员变量地址

    是连续的，将指针指向结构体数组，就可直接访问结构体中的所有成员。程序实现如下。

    include

    包含输入输出函数

    define N 10

    结构体类型及变量定义、初始化

    struct student

    {

    char no;

    char name;

    char sex;

    int age;

    float score;

    }stu[3]={{13001,Zhu Tong,'m',22,90.0},{13002,Li Hua,'f',21,82.0},{13003,Yang Yang,'m',22,95.0}};

    void main

    {

    struct student p;

    printf(

    学生基本情况表:\n);

    printf(

    学号

    姓名

    性别

    年龄

    成绩\n);

    for(p=stu;p
    通过指向结构体的指针输出学生信息

    printf(%-8s%12s%8c%8d%8.1f\n,p->no,p->name,p->sex,p->age,p->score);

    }

    程序运行结果如图2-53所示。

    首先定义了一个指向结构体的指针变量p，在循环体中，指针指向结构体数组

    p=stu，即指针指向了结构体变量的起始地址。通过p->no、p->name等访问各个成

    员。如果p+1，表示数组中第2个元素stu[1]的起始地址。p+2表示数组中的第3个元

    素地址，如图2-54所示。

    图2-53 通过结构体指针输出学生信息图2-54 指向结构体数组的指针在内存的情况

    2.5.3 用typedef定义数据类型

    通常情况下，在定义结构体类型时，使用关键字typedef为新的数据类型起一个

    好记的名字。typedef是C语言中的关键字，它的主要作用是为类型重新命名，一般

    形式如下。

    typedef

    类型名1

    类型名2

    其中，类型名1是已经存在的类型，如int、float、char、long等；也可以是结

    构体类型，如struct student。类型名2是你重新起的名字，命名规则与变量名的命

    名规则类似，必须是一个合法的标识符。1.使用typedef为基本数据类型重新命名

    例如如下语句。

    typedef int COUNT;

    将int

    型重新命名为COUNT

    typedef float SCORE;

    将float

    型重新命名为SCORE

    经过以上重新定义变量，COUNT就代表了int，SCORE就表示了float。这样，以

    上语句与如下语句等价。

    int a,b,c;

    定义int

    型变量a

    、b

    、c

    COUNT a,b,c;

    定义COUNT

    型变量a

    、b

    、c

    2.使用typedef为数组类型重新命名

    例如如下代码是将NUM定义数组类型。

    typedef int NUM[20]; NUM

    被定义为新的数组类型

    代码表示NUM被定义为数组类型，该数组的长度为20，类型为int。可以使用NUM

    定义int型数组，代码如下。

    NUM a;

    使用NUM

    定义int

    型数组

    a表示长度为20的int型数组，它与如下代码等价。int a[20];

    使用int

    定义数组

    3.使用typedef为指针类型重新命名

    使用typedef为指针类型变量重新命名与重新命名数组类型的方法是类似的。例

    如如下语句。

    typedef float POINTER; POINT

    被定义为指针类型

    POINTER表示指向float类型的指针类型。如果要定义一个float类型的指针变量

    p，代码如下。

    POINTER p;

    使用POINTER

    定义指针变量

    p被定义为指向float类型的指针变量。同样，也可以使用typedef重新为指向函

    数的指针类型命名，例如定义一个函数指针类型，代码如下。

    typedef int (PTR)(int,int); PTR

    被定义为函数指针类型

    PTR被定义为函数指针类型，PTR是指向返回值为int且有两个int型参数的函数

    指针。如下语句使用PTR定义变量。

    PTR pm;

    使用PTR

    定义一个函数指针变量pm

    pm被定义为一个函数指针变量。

    4.使用typedef为用户自定义数据类型重新命名用户自己定义的数据类型主要包括结构体、联合体、枚举类型，最为常用的是

    为结构体类型重新命名，联合体和枚举类型的命名方法与结构体的重新命名方法类

    似。例如，将一个结构体命名为DATE，代码如下。

    typedef struct

    为结构体类型重新命名

    {

    int year;

    int month;

    int day;

    }DATE;

    从类型名DATE可以很容易看出，DATE是表示日期的类型。上面的类型重新定义

    是在定义结构体类型的同时为结构体命名；也可以先定义结构体类型，然后重新为

    结构体命名，代码如下。

    struct date

    定义结构体类型

    {

    int year;

    int month;

    int day;

    };

    typedef date DATE;

    为结构体类型重新命名

    以上两段代码是等价的。注意，date和DATE是两个不同的名字，C语言是区分大

    小写的。接下来，就可以使用DATE定义变量了，代码如下。

    DATE d;

    定义变量d

    上面的变量定义与如下变量定义等价。

    struct date d;

    2.5.4 联合体与结构体一样，联合体也是一种派生的数据类型。但是与结构体不同的是，联

    合体的成员共享同一个存储空间。

    1.定义联合体类型及变量

    定义联合体的方式与定义结构体的方式类似，定义联合体的一般形式如下。

    union

    共用体名

    {

    成员列表;

    }

    变量列表;

    其中，union是C语言的关键字，用来定义联合体类型。例如，一个联合体的类

    型定义如下。

    union data

    定义联合体类型和变量abc

    {

    int a;

    float b;

    char c;

    double d;

    }abc;

    以上代码是将联合体类型与变量同时定义，当然也可以先定义联合体类型，然

    后定义变量，例如如下语句。

    union data

    定义联合体类型union abc

    {

    int a;

    float b;

    char c;

    double d;

    };

    union data abc;

    定义联合体类型的变量abc

    当然也可以省略联合体名data，代码如下。

    union

    省略了联合体名data

    { int a;

    float b;

    char c;

    double d;

    };

    union data abc;

    定义联合体类型的变量abc

    以上3段代码是等价的。

    从联合体的类型定义可以看出，联合体与结构体的定义非常相似。但是联合体

    与结构体在存储方式上却是不同的。联合体中的成员在同一时刻只有一个有效，联

    合体中的成员占用同一块内存单元。上面定义的变量abc在内存中的情况如图2-55所

    示。

    图2-55 变量abc在内存中的情况

    其中，变量abc中包含4个成员，它以占用内存单元最长的成员作为变量的长

    度。因此，abc占用8个字节，而不是4+4+1+8=17个字节。

    2.引用联合体成员变量

    引用联合体成员变量的方式与引用结构体成员变量的方式相同。例如，前面定

    义了联合体变量abc，引用变量中的成员的代码如下。abc.a

    引用 ......