链式存储结构在《数据结构》中的教法

摘要：链式存储结的特色--指针以其灵活性而不易被学生掌握，针对诸如指针变量赋值运算的难点，提出新的教法与同仁共勉。

关键词： 链式存储结 指针变量 赋值运算

Teaching Methods of Linked Structure in "Date structure"

Kan Nan

（Department of Information Engineering, WuHan Vocational College of Information Transmission Technology, Nan Kan, 430074 , China）

Abstract：Pointer is a difficulty for students to grasp in linked structure; there is one question about it. For example assignmentoperation about pointer variable,,Based on this, author discusses new teaching methods.

Keyword: linked structure; pointer variable; assignment operation

《数据结构》主要研究信息的逻辑结构及其基本操作在计算机中的表现和现实，是计算机专业的核心课程。链式存储作为该课程讨论的重要的储结结构之一，是学生应掌握程序设计技巧的基础。

从进几年《数据结构》课程的教学过程反映出，当讨论链式存储结构时学生出现理解上的“瓶颈”现象。问题集中体现在：指针变量与指针赋值运算。下面就这一问题谈谈教法与感受，希望与同仁共勉。

首先我们引入两个概念 “菜篮子”和“菜”而且要分清它们。 说到赋值语句，我们先来回顾一下赋值运算的实质。尽管不同语句的赋值语句有不同的语法结构，但大都数语句所定义的语意大体相同。下面以C语言为例说明：

某程序段中语句x=y；x和y是变量名，无论他们是数据类型，每一名字有两个“身份”：一方面该变量名代表一定的存储单元，另一方面代表该存储单元里的内容，以该单元的内容为值。赋值语句x=y的意义是：“把y的值送入x所代表的存储单元”，也就是说，赋值语句中赋值号“=”左右两边的变量名扮演着两种不同的角色。为了区别一个变量名的两种“身份”我们把一个名字所代表的那个存储单元称为该名的左值，通俗地说是“菜篮子”用来装菜的；把一个名字所代表的的单元内容（值）称为该名的右值，对应的就是“菜”。当变量名出现在等号左边就是“菜篮子”出现在等号右边就是“菜”，赋值运算就是把“菜”往“菜篮子”里放（注意这儿的“菜篮子”的特殊性：最后一次方的“菜”就覆盖“菜篮子”里以前放的“菜”，且“菜篮子”里只能放一个“菜”）。

对变量名的双重性有了以上的深刻认识在来讨论指针变量的赋值运算学生就恍然大悟了。

例1： 有定义如下的双向链接表

struct dnode {elemtp data;

struct dnode *prior, *next;}*p,*r;如图1所示，在双向链接表中的结点之前插入一个结点r使线性表（a1…ai，ai+1…an）变成（a1…ai,b,ai+1…an）。操作语句如下；

{1}r->prior=p->prior;

{2}r->next=p;

{3}p->prior->next=r

{4}p->prior=r;

以上4条语句的语义分别是：

{1}把数据元素ai所在的结点地址（在p的prior域中放着的地址值，此时表现为变量p->prior所代表的内容，以后简称右值，也就是我们所说的“菜”）放到结点r 的prior域中(此时r->prior应以其所代表的存储单元的身份出现，即左值，也就是“菜篮子”)这就是把变量p->prior所代表的存储单元的地址值赋值给变量r->prior所代表的存储单元，即把“菜”放进“菜篮子”，线1所代表的链建成了。注意千万不能把该语句中理解为其左值，我们是不可能把“菜篮子”放进“菜篮子”的

{2}把数据元素ai+1所在结点的地址（是变量p代表的内容，即p的右值）放到结点r 的next域（是变量r->next代表的存储单元，即左值）。变量p的值作为“菜”放进了变量r->next这个“菜篮子”，线2所代表的链建成了。

{3}把入数据元素b所在的结点的地址（该地址作为值在r所代表的存储单元中放着，即r右值）放到数据元素ai所在的结点next域中，而数据元素ai所在的结点就是p->prior（因为数据元素ai所在的结点地址在p->prior中放着，此时取其右值），那么数据元素ai所在的结点next域中就是p->prior->next这个“菜篮子”，此时语句实现使b变成ai的后续，经赋值后原链5自然断掉。

{4}把入数据元素b所在的结点的中的地址，放到数据元素ai+1的地址，放到数据元素ai+1所在结点prior域中，变量r的值再次为“菜”放入了变量p->prior“菜篮子”，就使b称为ai+1的前驱，经赋值后原链自然断掉。

以上4条语句{1},{2}的次序可以调换，{3},{4}的次序不可以调换，而且{1},{3}语句必须在{4}之前，只要学生对赋值语句能有以上的深刻理解，其原因就不言而喻了。再复杂的链式存储结构及其操作一般都涉及改变链的状态，其无非就是通过赋值语句来改变链，在操作中分清变量“菜篮子”和“菜”的双重角色，对学生掌握链式存储结构起着重要的作用。

参考文献：

[1]Horowitz ES. Fundamentals of Data Structures. Pitmen Publishing Limited, 1976

[2]陈火旺。编译原理 北京：国防工业出版社，1984