上一篇博文中主要总结线性表中的链式存储结构实现，，比如单向链表、循环链表，还通过对比链表和顺序表的多项式的存储表示，说明链表的优点。可以参看上篇博文
下面先对没有介绍的链表中的双链表进行介绍，并通过稀疏矩阵的三元组的链式结构来深入理解较为复杂的链表存储结构。最后对三次博文所讲述的内容进行梳理，以帮助在实际应用中选择最合适的存储结构：顺序表和链表，来组织实现自己的算法和功能。
双向链表
下面用示意图对比一下几种链表的表示：
单向链表表头
单向链表的结构如下：
循环链表的结构如下：
在循环单链表中，从任意一个结点出发，沿着向后链能够访问到表中的所有元素；对循环链表的操作与普通单链表基本相同，只是判表空和判断表尾元素的条件有所不同
判断表尾：p->next == head判断表空：head->next == head
双向链表
指在前驱和后继方向都能遍历的线性链表，每个结点结构如下图所示：
双向链表结构如下：
双向链表的优点是：实现双向查找（单链表不容易做到），缺点是：空间开销大。
双向链表通常采用带表头结点的循环链表形式，结构如下：
双向链表结点CDNode的抽象数据类型：
typedef struct CDNode{DataType m_dData;CDNode *m_pNext, *m_pPrev;}
CDNode的基本操作如下：
void SetDNode(DNode *front);DNode *GetPrev(DNode *ptr);DNode *GetNext(DNode *ptr);void InsertPrev(DNode *pNode);void InsertNext(DNode *pNode);Void DeleteDNode(DNode *ptr);
双向链表CDList的实现：
typedef CDList{CDNode *m_pHead;int Size;}
CDList的基本操作：
Void SetDLList();//构造Void FreeDLList();//析构int DLListSize ();int DLListIsEmpty();//int DLListLocate();DataType DLListGetData();void DLListInsert();void DLListDelete();
针对几个比较抽象的操作进行图例说明：
********************************************************************************************
注：在链表的操作中要注意修改指针的顺序
********************************************************************************************
有序表有序表的插入
在有顺序表L中插入新的结点，使得L仍然有序
void OrderInsert( SqList L, ElemType x ) { //L非递减有序的顺序表，插入新元素x，使L仍然有序 i=L.length-1; //i指向表尾元素 while(i>=0 && x<L.elem[i]) { L.elem[i+1]=L.elem[i]; //大于x的元素右移i–; } //while L.elem[i+1]=x; L.length++;} //OrderInser
void OrderInsert( LinkList *L, ElemType e ) {
p=L;
while(p->next!=NULL &&p->next->data<e)
s=(LNode*)malloc(sizeof(LNode));
s->next=p->next; s->data=e;
p->next=s;
} //OrderInsert O(n)
有序表的合并
使得合并后的表仍然有序：
void MergeList( LinkList *La, LinkList *Lb ) {
pa=La->next; pb=Lb->next;
while(pa&& pb)
if(pa->data<=pb>data)
{
pc->next=pa; pc=pa; pa=pa->next;
}
else {
pc->next=pb; pc=pb; pb=pb->next;
}
pc->next = pa? pa : pb;
delete Lb;
}
链表应用：稀疏矩阵
稀疏矩阵:只有少数非 0 矩阵元素顺序结构:
三元组顺序表: (i,j,data)Typedef struct{Int I,j;DataType item;}Triple;
Typedef struct{Triple data[MaxSize+1];Int mu,nu,tu;}TSMatrix;
走马观花之外，这才是深入体验，探索自我的最佳时间，
