循环链表之双循环链表（C语言版）-创新互联

Status Insert_Yes_Tail(List *head,ElemType x)

{

SeqNode s = BuyNode(x);

if(FALSE == IsEmpty(s))

{

printf("out of memory\n");

return FALSE;

}

s->next = head->phead;

s->prev = head->ptail;

s->prev->next = s;

s->next->prev = s;

head->ptail = s;

head->length++;

return TRUE;

}

//不带头结点的双循环链表的尾插，插入成功返回TRUE,失败返回FALSE

Status Insert_No_Tail(List *head,ElemType x)

{

SeqNode s = BuyNode(x);

if(FALSE == IsEmpty(s))

{

printf("out of memory\n ");

return FALSE;

}

if(0 == head->length)    //处理空链表的情况

{

head->phead = s;

head->ptail = s;

s->next = s;

s->prev = s;

}

s->next = head->phead;

s->prev = head->ptail;

s->next->prev = s;

s->prev->next = s;

head->ptail = s;

head->length++;

return TRUE;

}

双循环链表的按值插（这里是按照从小到大的顺序）

    双循环链表按值插入（这里是从小到大的顺序），无论是带头结点还是不带头结点，当是空表的时候，直接插入链表，不需用查找插入位置。

    其他情况调用Find函数查找要插入的位置，Find函数的返回值是要插入的地址的后一个元素的地址。由于双循环链表可以同过当前元素找到前一个结点所以Find返回来的地址就可以完成插入操作。当是空表的时候，与头插或者尾插的空表示意图一样，读者返回到前边看，这里不给出示意图，这里只给出有元素的按值插入示意图：

    不带头结点的按值插入，有一点需要注意，当只有一个结点的时候再次插入第二个结点的时候需要修改phead和ptail的指向，由于只有一个结点，不管是第二个要插入的值比第一个大还是小，由于是循环链表，Find函数返回的都是第一个结点，这样就需要在插如函数中，进行单独处理。

    由于带头结点，所以不会出现不带头结点那种需要单独处理的特殊情况，但是带头节点与不带头结点都有共同的特殊情况，那就是空表时的情况。

具体代码实现：

//带头结点的按值插入，插入成功返回TRUE,失败返回FALSE。

Status Insert_Yse_Value(List *head,ElemType value)

{

SeqNode s =  BuyNode(value);

SeqNode p = NULL;

if(FALSE == IsEmpty(s))

{

printf("out of memory\n");

return FALSE;

}

if(0 == head->length)         //处理空表的情况

{

s->next = head->phead;

s->prev = head->phead;

head->phead->next = s;

head->ptail = s;

head->phead->prev = s;

head->length++;

return TRUE;

}

p = Find(*head,head->phead->next,value);       //Find函数，之前定义的，返回要插入的位置的地址。

 //这里我提一下这个判断条件，给Find函数传过去的地址，是首元结点的地址，所以当Find()函数返回的地址为head->phead时，说明该元素需要插入到表尾，所以就需要修改ptial的指向。

if(head->phead == p)

{

head->ptail = s;

}

s->next = p;

s->prev = p->prev;

s->prev->next = s;

s->next->prev = s;

head->length++;

return TRUE;

}

//不带头结点的按值插入，插入成功返回TRUE,失败返回FALSE。

Status Insert_No_Value(List *head,ElemType value)

{

SeqNode s = BuyNode(value);

SeqNode p = NULL;

if(FALSE == IsEmpty(s))

{

printf("out of memory\n");

return FALSE;

}

if(0 == head->length)          //处理空表的情况

{

head->phead = s;

head->ptail = s;

s->next = s;

s->prev = s;

head->length++;

return TRUE;

}

p = Find(*head,head->phead,value);   //Find函数，之前定义的，返回要插入的位置的地址。

s->next = p;

s->prev = p->prev;

p->prev = s;

s->prev->next = s;

//重点说一下这一部分，由于没有头结点，所以当Find()函数head->phead时，有可能是往头插，也有可能是往尾插，所以就需要进行判断，当Find()函数的返回值等于头指针时，如果将要插入的值大于首元结点的值，那么就是说，要插入的值是往最后插，即就是需要把ptail修改指向新结点。否则修改phead。

if(head->phead == p)

{

if( s->data > head->ptail->data)

{

head->ptail = s;

}

else

{

head->phead = s;

}

}

head->length++;

return TRUE;

}

循环双链表的头删

    不论是带头结点的链表还是不带头结点当链表为空时直接返回FALSE;对于带头结点和不带头结点的双循环链表，都需要注意一个结点的情况，对于带头结点的双循环链表，由于phead始终是指向头结点的，所以，不需用修改头指针的指向，以及最后一个节点的next域除了当删除到最后一个结点时，其他的都不用修改phead、ptail、ptail->next、phead->prev。然而对于不带头结点就需要每次维护循环链表的完整性，修改这些值。我们继续看图：