循环单链表

/***********************************************
    循环单链表的实现
    by Rowandjj
    date 2014.4.1

***********************************************/
#include<IOSTREAM>
using namespace std;

#define OVERFLOW -1

typedef int ElemType;
typedef struct _NODE_
{
    ElemType e;
    struct _NODE_ *next;
}Node,*pNode,*LinkList_C;
/*操作声明*/
void InitList(LinkList_C &L);
void DestroyList(LinkList_C &L);
int ListEmpty(LinkList_C L);
int ListLength(LinkList_C L);
void PrintList(LinkList_C L);
int GetElem(LinkList_C L,int n,ElemType &e);
int LocateElem(LinkList_C L,ElemType e);
int ListInsert(LinkList_C &L,int n,ElemType e);
int ListDelete(LinkList_C &L,int n,ElemType &e);

void CreateList(LinkList_C &L,int n);
/*****************************************************/
/*具体实现细节*/
void InitList(LinkList_C &L)
{
    L = (pNode)malloc(sizeof(Node));
    if(!L)
    {
        exit(OVERFLOW);
    }
    L->next = L;
}
void CreateList(LinkList_C &L,int n)
{
    ElemType e;
    if(n <= 0)
    {
        return;
    }
    for(int i = 0; i < n; i++)
    {
        pNode p = (pNode)malloc(sizeof(Node));
        if(!p)
        {
            exit(OVERFLOW);
        }
        cin>>e;
        p->e = e;
        p->next = L->next;
        L->next = p;
    }
}
int ListDelete(LinkList_C &L,int n,ElemType &e)
{
    pNode p = L,q;
    int i = 0;

    if(p->next == L || n <= 0)
    {
        return 0;
    }
    if(n == 1)
    {
        q = p->next;
        e = q->e;
        p->next = q->next;
        free(q);
    
        return 1;
    }
    p = p->next;
    while(p!=L && i<n-2)
    {
        i++;
        p = p->next;
    }
    if(p == L)
    {    
        return 0;
    }
    if(p->next == L)//注意这里加了一个判断，否则当要删除的位置为链表长度时+1时会报错
    {
        return 0;
    }
    q = p->next;
    p->next = q->next;
    e = q->e;
    free(q);

    return 1;
}
int ListInsert(LinkList_C &L,int n,ElemType e)
{
    pNode p = L,q;
    int i = 0;
    if(n<= 0)
    {
        return 0;
    }
    if(p->next == L || n == 1)
    {
        q = (pNode)malloc(sizeof(Node));
        if(!q)
        {
            exit(OVERFLOW);
        }
        q->e = e;
        q->next = p->next;
        p->next = q;
        
        return 1;
    }
    else
    {
        p = p->next;
        while(p != L && i < n-2)
        {
            p = p->next;
            i++;
        }
        if(p == L)
        {
            return 0;
        }
        q = (pNode)malloc(sizeof(Node));
        if(!q)
        {
            exit(OVERFLOW);
        }    
        q->next = p->next;
        p->next = q;
        q->e = e;
    
        return 1;
    }
}
int LocateElem(LinkList_C L,ElemType e)
{
    pNode p = L->next;
    int i = 1;
    if(p == L)
    {
        return -1;
    }
    while(p!=L && p->e != e)
    {
        p = p->next;
        i++;
    }
    if(p == L)
    {
        return -1;
    }
    return i;
}
int GetElem(LinkList_C L,int n,ElemType &e)
{
    //  1<=n<=list_size
    pNode p = L->next;
    int i = 0;
    if(p == L)
    {
        return 0;
    }
    if(n == 1)
    {
        e = p->e;
        return 1;
    }
    while(p!=L && i < n-1)
    {
        i++;
        p = p->next;
    }
    if(p == L)
    {
        return 0;
    }
    e = p->e;
    return 1;
}
void PrintList(LinkList_C L)
{
    pNode p = L->next;
    while(p!=L)
    {
        cout<<p->e<<" ";
        p = p->next;
    }
    cout<<endl;
}
int ListLength(LinkList_C L)
{
    pNode p = L->next;
    int i = 0;
    if(p == L)
    {
        return 0;
    }
    while(p!=L)
    {
        i++;
        p = p->next;
    }
    return i;
}
int ListEmpty(LinkList_C L)
{
    return L->next == L;
}
void DestroyList(LinkList_C &L)
{
    pNode p,q = L->next;
    while(q != L)
    {
        p = q->next;
        free(q);
        q = p;
    }
    free(L);
    L = NULL;
}