数据结构实验中指针相关问题

摘要：《数据结构》是实践性很强的计算机专业核心课程，一般以C语言作为程序设计语言，但指针往往成为学生编程中的难点。结合《数据结构》课程的需要，从指针的本质出发，讨论了指针基本概念、指针和数组及指向函数的指针几个问题，目的是帮助学生在《数据结构》课程的学习中更好地理解和应用指针。

关键词：指针；C语言；实验；数据结构

中图分类号：G642 文献标志码：A 文章编号：1674-9324（2014）04-0110-03

一、引言

《数据结构》作为实践性很强的计算机专业的基础课，教学中必然离不开实践。针对《数据结构》的课程设计实践不仅可以帮助学生巩固和加深对课程内容的理解，更重要的是可以进一步锻炼程序设计的技能[1]。C语言是数据结构实验中重要的程序设计语言，指针是C语言中一个非常重要的概念。在C语言中，指针的应用非常灵活，对于程序设计初学者来说比较难掌握，更谈不上灵活合理的应用。《数据结构》中（注：文中的讨论围绕严蔚敏老师的《数据结构》C语言版教材[2]），为了实现数据的存储结构，指针在线性表、树和图的存储中都有重要的应用，可以说，数据结构的实验绕不开指针的应用，如果学生掌握不好指针，是无法进行数据结构实验学习的。

教学中注意到，学生的主要问题是对指针的本质缺乏清晰的理解，知其然不知其所以然，导致在应用时只会依葫芦画瓢，不会灵活应用。针对学生理解和应用中的难点问题，剖析了指针的本质，以此为基础，讨论了指针的使用、指针和数组及指向函数的指针几个问题，希望能够加深学生对指针的理解，并在数据结构的实验中灵活应用。

二、指针

1.变量和数据类型。变量和数据类型是C语言中的基本概念，是否能理解它们的本质，对后续指针概念的理解非常重要。但是，由于它们是最基本的东西，教师和学生都认为很好理解，不是很重视。因此，学生对它们的理解往往流于表面，产生模糊的认识，如：变量是会变化的量；对变量名和变量的关系，变量和数据类型的关系等认识不清。

对变量的理解应该强调变量最本质的意义：内存中的一块存储空间，即所谓变量就是一块存储空间，如图1所示。

围绕对变量本质的理解应该强调几点：①一块空间（变量）具有两个特征，一是这块空间在内存中的起始地址（计算机内部16进制地址表示不便，本文中用3位10进制数示意），表示这块空间的开始，二是从起始地址开始的空间大小，这两个特征一起确定了一个变量；②作为内存的一块存储空间，自然可以存储不同的值，会变化；③变量的声明是提出分配存储空间的要求，没有分配空间，当然不能存值，不能使用；④为了在程序中方便使用变量，变量可以取一个名字，即变量名。

变量都有数据类型，从存储空间分配的角度看，数据类型的本质是对分配空间大小的约定。要给一个变量分配存储空间，涉及两个东西：分在那，分多大。分在那由当前内存情况确定，而分多大则由变量所属的数据类型确定，如int型就分4个字节大小。

2.指针的概念。指针是C语言中的派生数据类型，如int *p，声明了一个由整型派生的指针变量p，如图2所示。学生在为什么要用指针、指针变量和原类型之间是什么关系等问题上往往产生混淆，不能够清晰理解。

对指针概念的理解应该强调几点：①指针变量也是变量，声明了指针变量后同样需要给该变量分配一块存储空间，只是该空间存储的内容有点特殊，是一个地址。②获取数据存储空间的基本方式有两种，一是在程序的数据说明部分进行声明，这样，程序执行时存储空间已经预先分配，并建立了变量名和存储空间之间的映射，可称为静态分配。二是在程序执行的过程中，通过申请（如malloc函数）获得存储空间，可称为动态分配，这样的空间无法给予变量名，存取这样空间的唯一办法只能通过该空间的地址，即指向该地址的指针来存取。如图2中圈1所示，malloc函数申请了一块大小为4个字节的空间，空间起始地址是300，为了在后续程序中使用这块存储空间，该地址赋值给指向整型的指针p，p中存储的内容变为300。③应该强调，作为派生类型，指针变量也是有数据类型的，其数据类型是指针变量所指向的存储空间大小的约定。如图2中定义的p是一个指向整型的指针，强调这一点有助于学生对指针应用的理解。例如，表达式中，出现在指针变量前的*称为指针运算符，如赋值语句*p=21，其意义是给p中地址所指向的存储空间赋值，图2中，p中存有地址300，确定了被赋值空间的起始地址，而p的类型-整型，确定了这块空间的大小，即*p确定了一块从300开始，长度为4的存储空间。变量的本质是一块存储空间，那么反过来说，一块确定的存储空间就是一个变量，*p确定了一块存储空间，它等价于变量，给*p赋值等价于给整型变量赋值。

三、指针的应用

1.指针和数组。C语言中，数组名代表数组的起始地址，是一个常数，可以看做一个指针。《数据结构》中，线性表的顺序映像存储结构是通过动态申请的数组实现的，设线性表为a1，a2，…，an（n=20），数据元素类型为整型，其存储结构的定义如下所示：

#define L_SIZE 20

typedef struct{

int *elem；

int length；？摇？摇？摇 /*已存数据的个数*/

int listsize； ？摇 ？摇 /*数组容量的大小*/

}Sqlist；

上述代码主要定义了结构体数据类型Sqlist，该结构体类型中包含3个域：elem，length和listsize，其中elem是一个整型的指针变量，用来指向申请存储空间的起始地址。类型定义后可以声明该类型的变量，如Sqlist L；线性表的存储空间（数组）需要申请，如图3所示。

malloc函数申请了一块大小为80个字节的存储空间，该空间的起始地址假设为100，函数返回后，地址100被赋值给整型的指针变量L.elem，即指针变量L.elem中存有地址100。

学生对静态数组的使用相对熟练些，但往往不习惯动态申请数组的使用，下面以线性表的遍历为例来说明一下其使用方式。动态申请数组中遍历的实现有两种常用方式：一是把指针当做数组名来使用。数组名是地址，可以看做指针，反之，指针同样能够看做是数组名。遍历的代码可以写为：

for（i=0；i

这里要注意理解中括号[ ]的意义，中括号本质上是运算符，它的意义是执行操作L.elem+i（这里要关注指针的类型，即不同类型的指针加i，计算结果是不同的），找到存储ai+1这个整型数据的4个字节空间的起始地址，随后根据指针的类型（确定大小），存取这4个字节的存储空间。

二是通过指针来进行遍历。遍历的代码可以写为：

for（p=L.elem；p

整型指针p首先被赋值L.elem，图3中是100，这时p指向数组中第0号单元的起始地址，通过指针运算符*p存取从100开始的4个字节空间，即数组中第0号单元。随后，通过p的自加运算，指针p后移4个字节（p是整型指针），依次对数组中所有元素进行遍历。从结果上来看，代码（1）和代码（2）是完全等价的。

2.链表。线性表的非顺序映像存储结构是链表实现的。定义链表结点（结构体），动态申请结点存储空间，线性表每个数据元素存储在一个结点中，通过指针描述数据元数之间的关系，其结点的定义如下所示：

typedef struct LNode{

？摇int data；

？摇struct LNode *next；

} LNode，*LinkList；

上述代码主要定义了结构体数据类型LNode 和指向结构体的指针类型LinkList，该结构体类型中包含2个域：存储数据元素的域data和指针域next，next用来指向本结点数据元数在逻辑结构中的后继，链表如图4所示。

仍以线性表的遍历为例来说明其使用方式，利用指针p来进行遍历，代码可以写为：

p=head->next；

while （p） {

对数据元素p->data进行处理；？摇？摇？摇（3）

p=p->next；}

p被赋值p=head->next，指向首元结点，随后通过循环中p=p->next语句，p依次指向后继结点，直到链表结束。这里要注意对->操作符的理解，当指针p指向一个结构体存储空间时，如果需要存取结构体中的某个域，可以使用“p->域名”的方式，如p->data就是存取该结构体中的data域；另有一种等价的方式“*p.域名”，如*p.data，*p确定一块结构体空间（结构体变量），用“.”操作符存取结构体变量的某个域。

3.指向函数的指针。函数载人内存时，必定占有一块存储空间，可以定义指向函数的指针，通过指针来调用函数，例如：

int （*p）（ ）；？摇？摇？摇/* 定义了一个函数指针，其所指函数的返回值为整型*/

p=fun；？摇？摇？摇？摇？摇？摇？摇/*设int fun（int， int）；*/

（*p）（a，b）？圳fun（a，b）

首先定义了一个指向函数的指针p，随后p被赋值函数名，即让p指向函数fun，p指向fun后，可以通过指向函数的指针调用函数，其效果和通过函数名调用是等价的。应该注意到，这样用法毫无价值，能通过函数名调用，何必还要间接用指针调用。因此，指向函数的指针一般用作函数的形式参数，例如：

Status Sub（int e）；

Status Add（int e）；？摇？摇？摇/*返回值为Status的两个函数*/

void Preorder（BiTree T，status（*visit）（int e））{ ？摇/*遍历二叉树的函数*/

……….

（*visit）（a）；？摇？摇/*通过指向函数的指针调用函数*/

………

}

Preorder（T，Sub）；

Preorder（T，Add）；

假设有数据元素为整型的二叉树T，Preorder是实现二叉树的先序遍历的函数。上述代码中，首先给出了两个函数返回值为Status的函数原型，设Sub是对整数进行减处理的函数，Add是进行加处理的函数。那么，Preorder（T，Sub）调用时，函数名Sub作为实参传递给形参visit（指向函数的指针），则在遍历过程中（*visit）（a）所调用的函数是Sub；同理，Preorder（T，Add）调用时，（*visit）（a）所调用的函数是Add。这里应该强调，为什么要这么做？从上例中看，对二叉树的遍历过程是一样的，通过两次调用中visit所指的函数不同，对二叉树T中数据元素的处理不同，一次是减，一次是加。指向函数的指针带来的好处是，如果对数据元素的处理有新的变化，如增加乘的处理，仅需要编写乘的函数Mul，随后调用Preorder（T，Mul）就可实现对二叉树中数据元素的乘处理，不需要改变Preorder函数。这样的程序结构非常有利于提高程序的可维护性。

四、小结

作为实践性很强的计算机专业核心课程，《数据结构》课程的实验环节非常重要，指针的灵活应用是课程实验中的难点。学生对指针了理解往往流于表面，只会模仿性应用，不能深入理解和灵活应用。文中，我们结合实际的教学经验，总结了指针中的几个学生不容易掌握的问题，并分析讨论了教学中的要点。通过多年的教学实践，对学生《数据结构》课程的学习和提高编程能力是有帮助的。

参考文献：

[1]陈越，何钦铭，冯雁.“数据结构”综合性课程设计教学探索与实践[J].计算机教育，2008，（8）：54-55.

[2]严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2009.

基金项目：清华携手Google助力西部教育项目-2012年精品课程建设项目“数据结构”；2013年云南省教学改革研究项目“面向对象软件开发系列课程教学改革探索”；云南大学“中青年骨干教师培养计划”项目（编号：XT412004）。

作者简介：孔兵，男，博士，副教授，研究方向为智能数据处理；陈红梅，博士，女，讲师，研究方向为数据挖掘；袁国武，男，博士，讲师，研究方向为图形图像处理。