论文部分内容阅读
【摘要】实现数据的逻辑结构到计算机存储器的映像有多种不同的方式，顺序存储结构和链式存储结构是两种最主要的存储方式。但是数据存储结构对学生来说是一个很抽象的概念。根据多年讲授C语言的实践和体会，并结合C语言课程的特征，通过使用类比教学法，深度剖析了顺序存储结构和链式存储结构，使学生全面的理解和掌握数据存储结构的概念。
【关键词】类比法 C语言教学 数据存储 链表 数组
【 基金项目】防灾科技学院重点教研项目2012A04；防灾科技学院第一批精品建设课程。
【中图分类号】TP313 【文献标识码】A 【文章编号】2095-3089（2013）06-0136-02
形象类比法属于讲授教学方法的一种，即借助于两类不同本质事物之间的相似性，通过比较，形象地将一种已经熟悉或掌握的特殊对象推移到另一种新的特殊对象上去的推理手段，也是教学中创设真实生动情景的有效工具之一[1]。
在自然界中，数据元素之间的逻辑结构关系存在两种不同的表示方法：顺序映象和非顺序映象，并由此得到在计算机中两种不同的物理存储结构表示：顺序存储结构和链式存储结构。顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。
数据的物理存储结构对初学者来说非常抽象，文章提出了形象类比法将抽象概念形象化，帮助学生很好的掌握数据在计算机中的物理存储概念。
一、顺序存储和链式存储的创建
如何来理解顺序存储结构和链式存储结构，分别以一维数组和单链表为例，用一个形象的例子来说明空间是如何来分配的。
假如现在一个有20个人的班级的全体同学出去旅游几天，首先解决的就是住宿问题，内存就像一个很大的宾馆，这20个人有两种入住的的方法。
1.1建立数组
第一种，假设目前是旅游淡季，20个同学在宾馆里要了连续的20个房间，然后按学号的顺序入住在这20间房间里，用C程序语言描述为：
int a[20]；// 内存连续的分配20个int大小的空间
1.2建立单链表
第二种，假设目前是旅游旺季，没有连续的20个房间，还要保证在知道第一个学生的房间号的情况下，能找到所有其他学生的房间号，那么如何分配呢？首先给1号学生分配一个房间，把1号学生的房间号告诉班主任；然后给2号学生分配一个房间，把2号学生的房间号告诉1号学生；再给3号学生分配一个房间，把3号学生的房间号告诉2号学生……最后当所有学生的都入住进去之后，单链表就形成了。建立一个含有20个元素的单链表，用C程序语言描述为：
typedef struct Node
{ int data；
struct Node *next；
}List；
List *Create（）
{ int a，i=1；
List *head，*p，*q；
p=（List *）malloc（sizeof（struct Node））；//为第一个学生分配一个房间
scanf（“%d”，&p->data）；
head=p；
while（i<20）
{ q=（List *）malloc（sizeof（struct Node））；//为后面的每一个学生分配一个房间
scanf（“%d”，&q->data）；
q->next=NULL；
p->next=q；
p=q；
i++；
}
return head；
}
整个链表建立完成之后，返回单链表的首地址，也就是班级负责人记录下1号学生的房间号。
二、数据的查找
2.1在一维数组中查找数据
如何在顺序表中查找某一个元素呢？现在我们已经知道第一个学生的房间号，根据数组数据存放的特点，即20个学生之间是连续的入住在宾馆里，那么我们可以通过学号计算出任何一个学生的房间号。Loc表示某个元素的地址，那么：Loc（a[i]）=Loc（a[0]）+i；时间复杂度为O（1），所以数组是随机存取结构，可以随机存取数组中的任意一个元素。
2.2在单链表中查找数据
如何在单链表中查找某一个元素呢？例如：如何查找4号学生的房间号？我们知道4号学生的房间号3号学生知道，而3号学生的房间号2号学生知道……所有我们要在单链表中查找某个学生的房间号必须从1号学生开始，1号学生知道2号学生的房间号，2号学生知道3号学生的房间号……。查找的时间复杂度为O（n）。用C程序语言表示如下：
List *Search（List *head，int i）//head 存放1号学生的房间号，i待查找的学生的学号
{ List *p；
p=head；
while（i！=p->data） p-p->next；
return p； //返回i号学生的房间号
}
三、数据的插入和删除
3.1在一维数组中插入和删除数据
如何在顺序表中删除某一个元素呢？假设现在在旅游期间的第二天学号为5号的学生因为有事情提前返校，如何删除该数据，使得其他数据在内存中物理位置仍然是连续的，即剩余的其他同学在宾馆中的房间是紧密相连的，应该如何操作呢？那就要求从6号学生开始，后面的学生陆续搬家。6号学生搬到5号学生的房间，7号学生搬到8号学生的房间……直到20号学生搬到19号学生的房间。此算法的平均时间复杂度为O（n），用C程序语言表示为： void delete（int a[]，int n）//在数组a中删除下标为n的元素
{ int i；
for（i=n；i<20；i++） a[i]=a[i+1]；
}
如何在顺序表中插入一个元素呢？假设5号学生处理完学校的事情了，第四天又来回到宾馆，为了让他们仍然是按照学号有序的方式入住在连续相邻的宾馆里，该如何操作呢？这就要求从最后一名学生一直到6号学生陆续搬家，给5号学生腾出房间，即：19号学生搬回到原先的第20个房间，给18号学生腾出房间，18号学生搬到19号学生给腾出来的房间，17号学生搬到18学生腾出来的房间……直到5号房间空闲，5号学生住进去。此算法的时间复杂度为O（n），用C程序语言表示为：
void insert（int a[]，int n，int m）//在数组a的下标为n的位置插入一个元素m
{ int i；
for（i=19；i>n；i--） a[i]=a[i+1]；
a[n]=m；
}
3.2在单链表中插入和删除数据
如何在单链表中删除一个元素呢？现在仍然假设5号学生在旅游的第二天因为有事情提前返校，如何删除数据使得单链表中的元素仍然是线性关系呢？显然5号学生离开，只需要把他所知道的6号学生的房间号告诉4号学生就可以了。此算法的时间复杂度为O（1），用C程序语言来表示为：
void detele（List *head，int n）//在单链表中删除一个元素
{ List *p；
p=search（head，n）；//search函数返回值为待删除节点的前驱节点
if（P->next！=NULL）
{ p->next=p->p->next；
free（p->next）；
}
}
如何在单链表中插入一个元素呢？现在仍假设5号学生处理完学校的事情后第四天返回宾馆，为了保证数据之间仍然是按学号的顺序组成的一个链，该如何操作呢？首先给5号学生在宾馆里分配一个空房间，5号学生住进去；然后找到5号学生应该插入的位置，在4号之后，6号之前，修改指针，即把6号学生的房间号告诉5号学生，然后把5号学生的房间号告诉4号学生，他们之间又形成了一条新的链。此算法的时间复杂度为O（1），用C程序语言表示如下：
void insert（List *head，int n）
{ List *s，*p；
p=search（head，n）；//search函数返回值为待删除节点的前驱节点
s=（List *）malloc（sizeof（stuct node））
s->data=n；
s->next=p->next->next；
p->next=s；
}
四、数组与链表的优缺点比较
通过形象的类比法，很容易看出数组和链表的差别及各自的优缺点。
数组在内存开辟连续的一片区域，而链表可以连续，也可以不连续；数组中的数据在内存中是按顺序存储的，要访问数组中的元素可以按照下标索引来访问，速度比较快；但是对数组进行插入和删除算法，平均需要移动一半的元素，所以对数组进行插入和删除操作效率很低。
链表是随机存储的，链表的插入，删除操作效率很高，只需要修改指针。但是要访问链表中的某个元素的话，需从头指针顺着链表扫描才能取得，所以链表的随机访问的效率比数组低。
参考文献：
[1] 徐学福.论类比教学模式[J].广西师范大学学报（哲学社会科学版），1998，34（2）：27～32
[2]谭浩强.C程序多设计.第3版.清华大学出版社，2005
[3]严蔚敏.数据结构.第2版.清华大学出版社，2001
[4]韩莹，丰继林，单维锋.C语言实训教程.第1版.清华大学出版社，2013.1
【关键词】类比法 C语言教学 数据存储 链表 数组
【 基金项目】防灾科技学院重点教研项目2012A04；防灾科技学院第一批精品建设课程。
【中图分类号】TP313 【文献标识码】A 【文章编号】2095-3089（2013）06-0136-02
形象类比法属于讲授教学方法的一种，即借助于两类不同本质事物之间的相似性，通过比较，形象地将一种已经熟悉或掌握的特殊对象推移到另一种新的特殊对象上去的推理手段，也是教学中创设真实生动情景的有效工具之一[1]。
在自然界中，数据元素之间的逻辑结构关系存在两种不同的表示方法：顺序映象和非顺序映象，并由此得到在计算机中两种不同的物理存储结构表示：顺序存储结构和链式存储结构。顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。
数据的物理存储结构对初学者来说非常抽象，文章提出了形象类比法将抽象概念形象化，帮助学生很好的掌握数据在计算机中的物理存储概念。
一、顺序存储和链式存储的创建
如何来理解顺序存储结构和链式存储结构，分别以一维数组和单链表为例，用一个形象的例子来说明空间是如何来分配的。
假如现在一个有20个人的班级的全体同学出去旅游几天，首先解决的就是住宿问题，内存就像一个很大的宾馆，这20个人有两种入住的的方法。
1.1建立数组
第一种，假设目前是旅游淡季，20个同学在宾馆里要了连续的20个房间，然后按学号的顺序入住在这20间房间里，用C程序语言描述为：
int a[20]；// 内存连续的分配20个int大小的空间
1.2建立单链表
第二种，假设目前是旅游旺季，没有连续的20个房间，还要保证在知道第一个学生的房间号的情况下，能找到所有其他学生的房间号，那么如何分配呢？首先给1号学生分配一个房间，把1号学生的房间号告诉班主任；然后给2号学生分配一个房间，把2号学生的房间号告诉1号学生；再给3号学生分配一个房间，把3号学生的房间号告诉2号学生……最后当所有学生的都入住进去之后，单链表就形成了。建立一个含有20个元素的单链表，用C程序语言描述为：
typedef struct Node
{ int data；
struct Node *next；
}List；
List *Create（）
{ int a，i=1；
List *head，*p，*q；
p=（List *）malloc（sizeof（struct Node））；//为第一个学生分配一个房间
scanf（“%d”，&p->data）；
head=p；
while（i<20）
{ q=（List *）malloc（sizeof（struct Node））；//为后面的每一个学生分配一个房间
scanf（“%d”，&q->data）；
q->next=NULL；
p->next=q；
p=q；
i++；
}
return head；
}
整个链表建立完成之后，返回单链表的首地址，也就是班级负责人记录下1号学生的房间号。
二、数据的查找
2.1在一维数组中查找数据
如何在顺序表中查找某一个元素呢？现在我们已经知道第一个学生的房间号，根据数组数据存放的特点，即20个学生之间是连续的入住在宾馆里，那么我们可以通过学号计算出任何一个学生的房间号。Loc表示某个元素的地址，那么：Loc（a[i]）=Loc（a[0]）+i；时间复杂度为O（1），所以数组是随机存取结构，可以随机存取数组中的任意一个元素。
2.2在单链表中查找数据
如何在单链表中查找某一个元素呢？例如：如何查找4号学生的房间号？我们知道4号学生的房间号3号学生知道，而3号学生的房间号2号学生知道……所有我们要在单链表中查找某个学生的房间号必须从1号学生开始，1号学生知道2号学生的房间号，2号学生知道3号学生的房间号……。查找的时间复杂度为O（n）。用C程序语言表示如下：
List *Search（List *head，int i）//head 存放1号学生的房间号，i待查找的学生的学号
{ List *p；
p=head；
while（i！=p->data） p-p->next；
return p； //返回i号学生的房间号
}
三、数据的插入和删除
3.1在一维数组中插入和删除数据
如何在顺序表中删除某一个元素呢？假设现在在旅游期间的第二天学号为5号的学生因为有事情提前返校，如何删除该数据，使得其他数据在内存中物理位置仍然是连续的，即剩余的其他同学在宾馆中的房间是紧密相连的，应该如何操作呢？那就要求从6号学生开始，后面的学生陆续搬家。6号学生搬到5号学生的房间，7号学生搬到8号学生的房间……直到20号学生搬到19号学生的房间。此算法的平均时间复杂度为O（n），用C程序语言表示为： void delete（int a[]，int n）//在数组a中删除下标为n的元素
{ int i；
for（i=n；i<20；i++） a[i]=a[i+1]；
}
如何在顺序表中插入一个元素呢？假设5号学生处理完学校的事情了，第四天又来回到宾馆，为了让他们仍然是按照学号有序的方式入住在连续相邻的宾馆里，该如何操作呢？这就要求从最后一名学生一直到6号学生陆续搬家，给5号学生腾出房间，即：19号学生搬回到原先的第20个房间，给18号学生腾出房间，18号学生搬到19号学生给腾出来的房间，17号学生搬到18学生腾出来的房间……直到5号房间空闲，5号学生住进去。此算法的时间复杂度为O（n），用C程序语言表示为：
void insert（int a[]，int n，int m）//在数组a的下标为n的位置插入一个元素m
{ int i；
for（i=19；i>n；i--） a[i]=a[i+1]；
a[n]=m；
}
3.2在单链表中插入和删除数据
如何在单链表中删除一个元素呢？现在仍然假设5号学生在旅游的第二天因为有事情提前返校，如何删除数据使得单链表中的元素仍然是线性关系呢？显然5号学生离开，只需要把他所知道的6号学生的房间号告诉4号学生就可以了。此算法的时间复杂度为O（1），用C程序语言来表示为：
void detele（List *head，int n）//在单链表中删除一个元素
{ List *p；
p=search（head，n）；//search函数返回值为待删除节点的前驱节点
if（P->next！=NULL）
{ p->next=p->p->next；
free（p->next）；
}
}
如何在单链表中插入一个元素呢？现在仍假设5号学生处理完学校的事情后第四天返回宾馆，为了保证数据之间仍然是按学号的顺序组成的一个链，该如何操作呢？首先给5号学生在宾馆里分配一个空房间，5号学生住进去；然后找到5号学生应该插入的位置，在4号之后，6号之前，修改指针，即把6号学生的房间号告诉5号学生，然后把5号学生的房间号告诉4号学生，他们之间又形成了一条新的链。此算法的时间复杂度为O（1），用C程序语言表示如下：
void insert（List *head，int n）
{ List *s，*p；
p=search（head，n）；//search函数返回值为待删除节点的前驱节点
s=（List *）malloc（sizeof（stuct node））
s->data=n；
s->next=p->next->next；
p->next=s；
}
四、数组与链表的优缺点比较
通过形象的类比法，很容易看出数组和链表的差别及各自的优缺点。
数组在内存开辟连续的一片区域，而链表可以连续，也可以不连续；数组中的数据在内存中是按顺序存储的，要访问数组中的元素可以按照下标索引来访问，速度比较快；但是对数组进行插入和删除算法，平均需要移动一半的元素，所以对数组进行插入和删除操作效率很低。
链表是随机存储的，链表的插入，删除操作效率很高，只需要修改指针。但是要访问链表中的某个元素的话，需从头指针顺着链表扫描才能取得，所以链表的随机访问的效率比数组低。
参考文献：
[1] 徐学福.论类比教学模式[J].广西师范大学学报（哲学社会科学版），1998，34（2）：27～32
[2]谭浩强.C程序多设计.第3版.清华大学出版社，2005
[3]严蔚敏.数据结构.第2版.清华大学出版社，2001
[4]韩莹，丰继林，单维锋.C语言实训教程.第1版.清华大学出版社，2013.1