数据结构与算法-02-线性表

第二章 线性表

线性表的链式表示和实现

结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上并不一定相邻

线性表的链式表示又称为非顺序映像或链式映像

1. 存储特点

   • 线性表中数据元素（结点）在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

   • 访问只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

     这种存取元素的方式被称为顺序存取法。顺序表是随机存取，链表是顺序存取。

   例1：

   线性表：（赵、钱、孙、李、周、吴、郑、王）

   • 顺序表

     存储地址	存储状态
     0031	赵
     0033	钱
     0035	孙
     0037	李
     0039	周
     0041	吴
     0043	郑
     0045	王

   • 链表

     存储地址	结点
     	数据域	指针域
     0001	李	0043
     0007	钱	0013
     0013	孙	0001
     0019	王	NULL
     0025	吴	0037
     0031（头指针H）	赵	0007
     0037	郑	0019
     0043	周	0025

     单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名。

   例2：

   26个英文小写字母表的链式存储结构

   • 逻辑结构：（a，b，......，z）
   • 链式存储结构：

   

   各结点由两个域组成：

   • 数据域：存储元素数值数据
   • 指针域：存储直接后继结点的存储位置

2. 与链式存储有关的术语

   • 结点：数据元素的存储映像。由数据域和指针域两部分组成
   • 链表：n个结点由指针链组成一个链表，它是线性表的链式存储映像，成为线性表的链式存储结构

   

3. 单链表、双链表、循环链表

   • 结点只有一个指针域的链表，称为单链表或者线性链表

     

   • 结点有两个指针域的链表，称为双链表

     

   • 首位相接的链表成为循环链表

     

   • 头指针、头结点和首元结点

     

     • 头指针：是指向链表中第一个结点的指针。
     • 首元结点：是指链表中存储第一个数据元素的结点。
     • 头结点：是在链表的首元结点之前附设的一个结点。

4. 讨论

   • 讨论1：如何表示空表？

     • 无头结点时，头指针为空时表示空表

       

     • 有头结点时，当头结点的指针域为空时表示空表

       

   • 讨论2：在链表中设置头结点有什么好处？

     • 便于首元结点的处理

       首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无须进行特殊处理

     • 便于空表和非空表的统一处理

       无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了

   • 讨论3：头结点的数据域内装的是什么？

     头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。