线性表(五)--双向链表以及静态链表 (C语言实现)

有了单向循环链表,我们路确定某一个结点的前趋,但是我们发现这需要遍历整个链表,如果希望从表中快速确定某一个结点的前趋,另一个解决方法就是在单链表的每个结点里再增加一个指向其前趋的指针域 prior。这样形成的链表中就有两条方向不同的链,就是双向链表


与单向链表不同,双向链表有两个指针域。所以定义如下:

typedef struct DNode 
{     
   ElemType data; 
   struct DNode *prior,*next; 
}DNode,* DoubleList; 

事实上,双向链表也是由头指针唯一确定的,因为增加头结点能使双链表的某些运算变得方便。在双向链表中,那些只涉及后继指针的算法,如求表长度、取元素、元素定位等,与单链表中相应的算法相同,但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化,因此与单链表中的算法不同。

先来看看插入操作。

在双向链表第 i 个结点之前插入一个的新的结点
int DlinkIns(DoubleList L,int i,ElemType e) 
{ 
     DNode  *s,*p; 
     … /*先检查待插入的位置i是否合法(实现方法同单链表的前插操作)*/ 
     … /*若位置i合法,则找到第i个结点并让指针p指向它*/ 
     s=(DNode*)malloc(sizeof(DNode)); 
      if (s) 
      { 
         s->data=e;       
         s->prior=p->prior;      ① 
         p->prior->next=s;      ② 
         s->next=p;           ③ 
         p->prior=s;           ④ 
         return TRUE; 
      }  
      else return FALSE; 
} 

对于删除,实际上和单链表没有区别。
同样的双向链表也存在循环链表,和单链表区别不大,就不再累述了。
其实对于链表来说,只要能在脑海中有示例图,理解了之后就可以很轻松的写出来。

之前介绍的链表,其实都是动态的。那么什么是静态链表呢。静态链表其实是数组模拟实现的链表。
静态链表的基本特征:
1.存储池:定义一个较大的结构数组作为备用结点空间
2.游标机制:每个结点应含有两个域:data域和next(或cursor)域

#define  Maxsize  链表可能达到的最大长度 typedef  struct 
{
    ElemType data;  
    int cursor; 
}Component, StaticList[Maxsize]; 

对于静态链表的理解可能看了这幅图会好很多。

那么到这里线性表就结束了,没有六七八九。。。