数据结构教程第八课线性表的链式表示与实现
文章作者 100test 发表时间 2007:03:10 18:29:48
来源 100Test.Com百考试题网
本课主题: 线性表的链式表示与实现
教学目的: 掌握线性链表、单链表、静态链表的概念、表示及实现方法
教学重点: 线性链表之单链表的表示及实现方法。
教学难点: 线性链表的概念。
授课内容:
一、复习顺序表的定义。
二、线性链表的概念:
以链式结构存储的线性表称之为线性链表。
特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系,对表的每个数据元素除存储本身的信息之外,还需存储一个指示其直接衙继的信息。这两部分信息组成数据元素的存储映象,称为结点。
2000:1000 |
2000:1010 |
2000:1020 |
2000:1030 |
2000:1040 |
2000:1050 |
2000:1060 |
... |
2000:4000 | |
头指针2000:1006 |
2000:1030 |
a3 |
2000:1040 |
a6 |
NULL |
a1 |
2000:1060 |
a4 |
2000:1050 |
a5 |
2000:1020 |
a2 |
2000:1010 |
数据域 |
指针域 |
|
| |
|
例:下图是若干抽屉,每个抽屉中放一个数据元素和一个指向后继元素的指针,一号抽屉中放线性表的第一个元素,它的下一个即第二个元素的位置标为5,即放在第5个抽屉中,而第三个放在2号抽屉中。第三个元素即为最后一个,它的下一个元素的指针标为空,用0表示。
![](http://www.bc-cn.net/Article/UploadFDL01/200411/20041112070816592.jpg)
用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的
![](http://www.bc-cn.net/Article/UploadFDL01/200411/20041112070818121.jpg)