C++引用在《数据结构》算法中的应用研究与实践(已经接受).pdfVIP

C++引用在《数据结构》算法中的应用研究与实践

摘要严蔚敏编写的教材《数据结构（C语言版）》是数据结构的经典教材，

其中用到了C++的引用参数，但一般高校在其前期的C语言课程中都

没有讲过，一般数据结构教师也不会讲这部分内容，所以学生就感觉

要把该教材上的算法转变成程序非常困难。为此本文对引用的基本知

识进行了介绍，并以线性表的存储表示为例，探讨了引用在数据结构

中的顺序存储表示和链式存储表示中的应用，从中可见教材中的算法

几乎是零修改就可以直接使用。

关键词引用严蔚敏教材数据结构无缝衔接

严蔚敏教材《数据结构（C语言版）》是数据结构的经典教材，被很多高校采用，其中

采用类C语言来描述算法，除采用了C语言的一个核心子集来描述算法外，另外重要一点

就是采用了引用调用的参数传递方式。该书的C语言核心子集都容易理解，学生用C语言

实现也很简单，但引用参数这部分内容在C语言中没有讲过，一般数据结构教师也不讲，

并且涉及到C++，所以学生就感觉教材上的引用参数很难理解，要把教材上的算法改写成程

序的跨度和难度都非常大。

为此，本文对引用的概念、引用参数的使用进行了简单介绍，并以线性表的存储表示为

例，给出了两个在严蔚敏《数据结构（C语言版）》教材中经常要用到的数组和链表操作的

实现，学生通过对本文内容的理解和练习，可以实现C语言与数据结构的自由过渡和无缝

衔接，帮助学生理解数据结构教材中的算法，提高将算法转换成程序的能力。在编程环境上，

采用了TurboCC++3.0英文版集成环境，它包含了TurboC的功能，识别标准C，又能进

行C++编程，只要将源文件存为扩展名为.cpp的文件，就可以用标准C编程，同时又能使

用C++的引用。

一、引用的基本概念

引用是C++引入的新语言特性，是C++常用的一个重要内容之一，正确、灵活地使用

引用，可以使程序简洁、高效。引用就是某一变量（目标）的一个别名，对引用的操作与对

变量直接操作完全一样，都是操作同一个变量单元。

引用的声明方法：类型标识符引用名=目标变量名；

//例1，源文件名为：yin1.cpp

#includestdio.h

main()

{inta;intra=a;//定义引用ra,它是变量a的引用，即别名

用变量a输入

分别用变量a和引用输出

用变量a的引用输入

}

例1程序运行后，可以看到操作变量a的引用ra和操作变量a本身的效果是一样的。

说明：

（1）在此不是求地址运算，而是起标识作用。

1

（2）类型标识符是指目标变量的类型。

（3）声明引用时，必须同时对其进行初始化。

（4）引用声明完毕后，相当于目标变量名有两个名称，即该目标原名称和引用名，且

不能再把该引用名作为其他变量名的别名。

ra=1;等价于a=1;

（5）声明一个引用，不是新定义了一个变量，它只表示该引用名是目标变量名的一个

别名，它本身不是一种数据类型，因此引用本身不占存储单元，系统也不给引用分配存储单

元。故：对引用求地址，就是对目标变量求地址。ra与a相等。

（6）不能建立数组的引用。因为数组是一个由若干个元素所组成的集合，所以无法建

立一个数组的别名。

二、引用作为函数的参数

引用的一个重要作用就是作为函数的参数。以前的C语言中函数参数传递是值传递，

如果有大块数据需要传递的时候，采用的方案往往是指针，因为这样可以避免为整块数据建

立副本并全部压栈，可以提高程序的效率。但是现在（C++中）又增加了一种同样有效率的

选择（在某些特殊情况下又是必须的选择），就是引用。

//例2，源文件名为：yin2.cpp，包含swap和main两个函数

voidswap(intp1,intp2)//