双向循环链表简单实现

DLoopLinkList.h

//
// DLoopLinkList.h
//  双向循环链表 2013/03
//

#ifndef DLOOP_LINK_LIST_H
#define DLOOP_LINK_LIST_H

typedef int ElemType;
typedef struct DLoopLinkList
{
    struct DLoopLinkList *prior;
    ElemType data;
    struct DLoopLinkList *next;
}DLoopLinkList, *PtrDLoopLinkList;

void InitDLoopLinkList(PtrDLoopLinkList);
void DestoryDLoopLinkList(PtrDLoopLinkList);
void InsertDLoopLinkList(PtrDLoopLinkList, int, ElemType);
void ShowDLoopLinkList(PtrDLoopLinkList);
void Append(PtrDLoopLinkList, ElemType);
void Delete(PtrDLoopLinkList, int, ElemType *);

#endif

 DLoopLinkList.c

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include "DLoopLinkList.h"

void InitDLoopLinkList(PtrDLoopLinkList ptrDLL)
{
    ptrDLL->prior = ptrDLL;
    ptrDLL->next = ptrDLL;
}

typedef PtrDLoopLinkList PDLLL;
void DestoryDLoopLinkList(PtrDLoopLinkList ptrDll)
{
    PDLLL pite;      // 用于遍历的指针
    PDLLL temp;      // 用于存放要删除的节点的临时指针

    pite = ptrDll->next;        // 指向首元节点

    while(pite != ptrDll)
    {
        temp = pite;
        pite = pite->next;
        free(temp);
    }

    ptrDll->prior = NULL;
}

//
// index表示插入到index之前
//
void InsertDLoopLinkList(PDLLL ptrDll, int index, ElemType data)
{
    // 构建新节点 
    PDLLL newNode = NULL;
    PDLLL pIte = NULL;          // 用来循环的指针
    PDLLL pHead = ptrDll;       // 头指针
    int i = -1;                 
    
    newNode = (PDLLL)malloc(sizeof(DLoopLinkList));
    newNode->data = data;

    pIte = pHead;         // 初始化指向首元节点
    // 遍历找到第i-1个节点
    while(i < index - 1)
    {
        pIte = pIte->next; 
        ++i;
    }
    //printf("i = %d, data = %d", i, pIte->data);

    if(i == index - 1)
    {
        //printf("call insert\n");
        newNode->prior = pIte;
        pIte->next->prior = newNode;
        newNode->next = pIte->next;
        pIte->next = newNode;
    }
}

void ShowDLoopLinkList(PDLLL dllList)
{
     PDLLL pIte;

     pIte = dllList->next;
     //printf("pIte = %p\n", pIte);
     while(pIte != dllList)
     {
        printf("%-4d",pIte->data); 
        pIte = pIte->next;
     }

     printf("\n");
}

void Append(PtrDLoopLinkList pdl, ElemType data)
{
    // 创建一个节点
    PDLLL newNode = (PDLLL)malloc(sizeof(DLoopLinkList));
    newNode->data = data;

    newNode->next = pdl->prior->next;
    pdl->prior->next = newNode;
    newNode->prior = pdl->prior;
    pdl->prior = newNode;
}

void Delete(PtrDLoopLinkList pdl, int index, ElemType * pData)
{
    int i = 0;
    PDLLL pIte = pdl->next;

    while(i < index && pIte != pdl)
    {
        pIte = pIte->next;
        ++i;         
    }

    if(i == index && pIte != pdl)
    {
        *pData = pIte->data;
        pIte->prior->next = pIte->next;
        pIte->next->prior = pIte->prior;
        free(pIte);
    }
}

 main.c

#include <stdio.h>
#include "DLoopLinkList.h"

#define Insert InsertDLoopLinkList

int main(int argc, char* argv[])
{
    DLoopLinkList dl;
    int i = 0;
    ElemType e;

    InitDLoopLinkList(&dl);
    for(; i < 100; ++i)
    {
        Append(&dl, i);
    }
    
    Insert(&dl, 100, 100);
    Insert(&dl, 0, 100);
    Insert(&dl, 1, 101);
    Delete(&dl, 0, &e);
    printf("The element which be deleted:%d\n", e);
    Delete(&dl, 101, &e);
    printf("The element which be deleted:%d\n", e);
    ShowDLoopLinkList(&dl);
    printf("<<ShowDLoopLinkList>> ends.\n");
    DestoryDLoopLinkList(&dl);
}