2-5 线性表的链式表示和实现

顺序表回顾

特点：以物理位置相邻表示逻辑关系

优点：任何一元素都可以随机存取

缺点：进行插入和删除操作时，需要移动大量元素，存储空间不灵活

链式存储结构：

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

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

1. 用一组物理位置任意的存储单元来存放线性表的元素
2. 这组存储单位既可以是连续的，也可以是不连续的，甚至是零散的分布在内存中的任意位置上
3. 链表中元素的逻辑次序不一定相同

各结点由两个域组成

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

术语

1. 结点：数据元素的存储映像。由数据域和指针域两部分组成