数据结构-双向循环链表-题解(C语言代码)

typedef struct _Node
{
    int data;
    struct _Node* prev;
    struct _Node* next;
    char zero[4];//内存对齐 
}NODE,*PNODE;
PNODE Head = NULL;
PNODE Last = NULL;
//双向循环链表
void insert(int index, int value);//在index处插入value值 
void delByInd(int index);//根据index删除链表中的值 
void printList();//打印链表中的值 
int contain(int value);//value值是否包含在链表中 
int contain(int value)
{
    PNODE tmp = Head;
    if(tmp == NULL)
        return 0;    //不包含 
    while(1)
    {
        if(tmp->data == value)//判断当前节点的值是否等于value
        {
            return 1;    //包含 
        }else    //不等于，就判断下一个节点是否等于头结点（Head) 
        {
            if(tmp->next != Head)
            {
                tmp = tmp->next; //不等于，tmp指针指向下一个节点 
            }else    //等于头结点，退出，表示没找到。 
            {
                return 0;//不包含 
            }
        }
    }
}
void insert(int index, int value)
{
    if(Head == NULL)
    {
        Head = (NODE*)malloc(sizeof(NODE));
    //    Last = Head;//尾部指向头部 
        //初始化Head结构 
        Head->data = value;
        Head->prev = Head;
        Head->next = Head;
        Last = Head;
        return;
    }
    if(contain(value))//表示当前链表已经有此值。 
        return;
    PNODE temp = Head;
    NODE* nd = (NODE*)malloc(sizeof(NODE));
    nd->data = value;
    nd->prev = Head;
    nd->next = Head;
    if(index == 1)//作为头结点插入
    {
        //将头尾节点的指针更新 
        nd->prev = Last;
        Last->next = nd;
        //将nd节点作为头结点 
        nd->next = temp;
        temp->prev = nd; 
        Head = nd;
        Last = Head->prev;
    }else
    {
        int i = 1;
        //遍历到指定位置
        while(i != index && temp->next != Head)//当前节点的下一个节点不等于头结点 
        {
            temp = temp->next;
            i++;    
        }
        if(i == index && temp == Last)//指定位置是尾节点
        {// 思路是将尾节点的上一个节点更新为插入节点
            temp->prev->next = nd;//尾节点的上一个节点重新指向插入节点
            nd->next = temp;
            temp->prev = nd;
        }else if(i != index && temp == Last)//没有指定的位置，也就是超过了尾节点
        {//将插入节点作为尾节点进行处理
            temp->next = nd;
            nd->prev = temp;
            nd->next = Head;
            //更新尾指针
            Last = nd;
            //更新头指针
            Head->prev = Last;        
        }else     //在中间节点插入
        {// 思路是更新前后指针
            nd->prev = temp->prev;
            temp->prev->next = nd;
            nd->next = temp;
            temp->prev = nd;    
        }
    }
}
void delByInd(int index)
{
    PNODE temp = Head;
    PNODE tmp2 = NULL;
    if(temp == NULL)
        return;
    if(index == 1)//删除头结点 
    {
        if(temp->next != Head)//表示有一个以上的节点 
        {
            if(temp->next == Last)//只有两个节点 
            {//更新头尾指针
                Head = temp->next;
                Last = Head;
                Head->prev = Last;
                Head->next = Last;
                free(temp);
                temp = NULL;
            }else    //多个节点 
            {//更新头尾指针，尾指针的prev重新指向新的Head，
            //将下一个节点作为头指针
                Head = temp->next;
                Head->prev = Last;
                Last->next = Head;
                free(temp);
                temp = NULL;
            }
        }else //只有一个节点 
        {//释放内存，更新头尾指针为空
            Last = NULL;
            free(Head);
            Head = NULL;
        } 
    }else    //在其他位置上删除
    {
        int i;
        for(i = 1; i != index && temp->next != Head; ++i)//当前节点的下一个节点不等于头结点 
        {
            temp = temp->next;
        }
        if(i == index)// 找到指定位置
        {
            if(temp == Last)//删除节点是尾节点 
            {
                Last = temp->prev;//当前节点的上一个节点作为尾节点 
                Head->prev =  Last;
                Last->next = Head;
                free(temp);
                temp = NULL;
            }else //删除中间节点 
            {
                temp->prev->next = temp->next;
                temp->next->prev = temp->prev;
                free(temp);
                temp = NULL;
            }
        }
    }
}
void printList()
{
    PNODE temp = Head;
    if(temp != NULL)
    {
        printf("%d",temp->data);
    }else
    {
        return;
     } 
    while(temp->next != Head)//当前节点的下一个节点不等于头结点 
    {
        temp = temp->next;
        printf(" %d",temp->data);
    }
    printf("\n");
}