数据结构之——链表

写博文前跑跑题：发现还是码博文好啊！今天午休前躺在床上朗读余秋雨的《行者无疆》，读到写歌德和席勒的友情，歌德在认识席勒之前，简直是曲高和寡，身边的朋友富贵却见识短浅，没有在艺术和文学的阳春白雪上有所共鸣，所以歌德宁愿独孤写作也不愿扎堆毫无共同言语的身边人，直到遇到席勒……所以有时我宁愿写写自己专业的东西也不愿再和那些有的没得的人聊天了，说实话这个习惯也很久了，不是主动攀上兴致聊点饶有趣味的东西，一般应付式的答复终以有其他事耽搁暂停，这样其实也未尝不好，一切不以维持友谊而开头的对话都应该适可而止，正是奋斗年华，人人都很忙。

链表：之前在前一个博客speaknowcpp.blog.com写的是单向链表，这里为了总结写个双向链表以示不同和提升。另：我的博客都开在国外服务器，不是专门技术博园，没有弄代码高亮得插件，可能无法复制，所以从这次的博客开始提供源代码百度云下载链接。Hope You Like It.

链表是线性数据结构，可以有单向，也有双向。

•   Node（节点）

节点成为Node,是两线段相连接的一个交集点。相邻的节点互称前驱（Predecessor）或后继（Successor）。链表最基础的两个节点：首节点（Header），末节点（Trailer）。

•   ListNode模板类（一般声明节点的模板都作为.h的一个单独文件来调用）listNode.h

解释：（1）.节点所在的位置和之前向量命名一样，统称为“秩” 用一个typedef 让Rank表示int

（2）.模板中包括 数据域 ,前驱节点，后继节点

（3）.针对header和trailer的构造函数 后面的构造器则是对数据，前驱，后继的初始化，                      这也在一方面表示构造函数是初始化变量的作用

（4）.前驱后继的操作接口

• Creat The List（创建链表）

**图示：

解释：（1）.本文件在源代码是list_initialize.h的源文件

（2）.给header和trailer动态分配内存

（3）.如图 header->pred = NULL ； trailer->succ = NULL；

• 查找算法 (traverse in searching ranks)

图示:

在节点p（可能是trailer）前驱中，找到等于e的最后者，找到则返回节点p,找不到则返回NULL，已示越界，查找失败

**实现方法：

**

解释：1.函数形参三个（1）.查找的元素  （2）总查找的节点个数 （2）节点p的位置

          2.从右向左 n–  逐个对比 p的前驱的数据域与e是否相等

• 插入算法（insert）

图示：初始1.

将新的节点插入，步骤1：将新节点类似“镶嵌”进去，先连接前驱和后继至header和trailer

然后，因为是双向链表，将头的后继连上new 将尾的前驱连上new

代码实现：

解释：1.这里提供了四个接口，刚好是上面所描述的四个步骤，接口在源代码里面都有。

• 删除节点

如果把插入看成是一个短片的顺时间放帧，那删除节点就是插入节点的逆序放帧。

实现：

解释:

1.找到元素

2.将目标节点的后继当作其指向的前驱的后继    将目标节点的前驱当作其指向的后继的前驱       （讲的有点复杂，思考一下吧）

具体代码连接：链接：http://pan.baidu.com/s/1kTrfIXD  密码：cw48