C++程序设计之链表

1、线性表（Linear List）是由n个数据元素（节点）a1，a2，……，an组成的有限序列。

如： 排队中的乘客，词典中的词语，网络游戏的登录玩家等

2、线性表的特点：

1、有序性

       第一个元素无直接前驱（前续元素），其他每个元素有且仅有惟一一个直接前驱，最后一个元素无直接后继（后续元素），其他每个元素有且仅有惟一一个直接后继。

2、抽象性

       数据元素可以是任意类型。

3、同质性

       数据元素具有相同的类型。

3、线性表有两种存储形式：

顺序表和链表

4、顺序表（Sequential List）是把线性表的节点按逻辑次序存放在一组地址连续的单元里。

       它的特点是用物理位置上的邻接关系来表示节点间的逻辑关系，这一特点使用户可以随机存取表中的任意1个节点，但它也使得插入和删除操作会移动大量的节点。

5、链表

       线性表的链式存储结构是用一组任意的存储单元（可以是连续的，也可以是不连续的）来存储线性表的各个数据元素。

       每个元素除了需要储藏自身信息外，还需要存储一个指示其后继元素的信息（即直接后继的存储位置），这两部分信息组成了一个数据元素的存储结构，称为一个节点（node）。

6、链表每个节点包括两个域：数据域和指针域。数据域存储数据元素本身的信息，指针域是后续节点的指针，最后一个节点的指针域为空指针。

       第一个节点称为首节点，它的地址存储在链表首节点指针中，链表中的每一个节点都是同一种结构类型。

7、链表的基本操作主要有4种：

建立链表

插入节点

删除节点

查找节点

8、一个链表的节点结构可以如下定义：

1、建立链表：

       链表首节点指针是访问一个链表的通道，通过它，可以找到链表中的各个节点。链表中没有节点时，首节点指针为空。当创建了第一个节点后，它就指向第一个节点。

2、例如：

3、节点查找：

可以根据输入的条件，从首节点开始比较，直到尾节点。

4、例如：

5、删除节点：

       删除前，首先要把这个节点从链表中移出，让剩余的节点组成链表，然后删除这个节点。

6、插入节点：

       在一个链表的指定位置插入节点，要求链表本身必须是已按某种规律排好序的。

7、插入节点有4种情况。

1、原表是空表

       使head指向被插节点即可。

8、被插节点值最小

       应插入在第一节点之前。这种情况下使head指向被插节点，被插节点的指针域指向原来的第一节点则可。

9、中间位置插入

       使插入位置的前一节点的指针域指向被插节点，使被插节点的指针域指向插入位置的后一节点。

10、链表末尾加入

       使原表末节点指针域指向被插节点，被插节点指针域置为NULL。