C++程序设计之链表

本人学习C++的过程经验及总结，本文内容：链表的概念与使用

工具/原料

VS2015

链表的概念

1、线性表（Linear List）是由n个数据元素（节点）a1，a2，……，an组成的有限序列。如： 排队中的乘客，词典中的词语，网络游戏的登录玩家等

2、线性表的特点：1、有序性 第一个元素无直接前驱（前续元素），其他每个元素有且仅有惟一一个直接前驱，最后一个元素无直接后继（后续元素），其他每个元素有且仅有惟一一个直接后继。2、抽象性 数据元素可以是任意类型。3、同质性 数据元素具有相同的类型。

3、线性表有两种存储形式：顺序表和链表

4、顺序表（Sequent坡纠课柩ial List）是把线性表的节点按逻辑次序存放在一组地址连续的单元里。 它的特点是用物理醐蛑臀谁位置上的邻接关系来表示节点间的逻辑关系，这一特点使用户可以随机存取表中的任意1个节点，但它也使得插入和删除操作会移动大量的节点。

7、链表的基本操作主要有4种：建立链表插入节点删除节点查找节点

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

2、例如：

4、例如：

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

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

10、链表末尾加入 使原表末节点指针域指向被插节点，被插节点指针域置为NULL。