資料結構-雙向循環連結清單(無頭結點)相關操作

#include <stdio.h>
#include <stdlib.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0

//雙向循環連結清單結構體定義（無頭結點）
typedef int ElemType;
typedef struct DulNode {
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;
}DulNode,*DulLinkList;


DulLinkList InitList_Dul(DulLinkList L);//初始化一個雙向循環連結清單
DulLinkList CreateElemP_Dul(DulLinkList L);//建立一個雙向循環連結清單
void PrintList_Dul(DulLinkList L);//輸出該雙向循環連結清單
int GetElemP1_Dul(DulLinkList L,int i,ElemType *e);//取得雙向循環連結清單上第i個位置上的元素的值
DulLinkList ListInsert_Dul(DulLinkList L,int i,ElemType e);//向該雙向循環連結清單的第i個位置之前插入元素。
int ListLength_Dul(DulLinkList L);//傳回雙向循環連結清單的長度
DulLinkList GetElemP2_Dul(DulLinkList L,int i);//傳回雙向循環連結清單上第i個位置上的指針
DulLinkList ListDelete_Dul(DulLinkList L,int i,ElemType *e);//删除雙向循環連結清單上第i個位置的元素，并傳回該元素的值
int GetLocate_Dul(DulLinkList L,ElemType e);//傳回雙向循環連結清單上元素e的位序

//初始化一個雙向循環連結清單
DulLinkList InitList_Dul(DulLinkList L) {
    L = (DulLinkList)malloc(sizeof(DulNode));
    if(L != NULL) {
        L->next = L->prior = L;
    } else {
        exit(OVERFLOW);
    }
    return L;

}

//建立一個雙向循環連結清單
DulLinkList CreateElemP_Dul(DulLinkList L) {
    int n,i;
    DulLinkList p,s;
    s = L;
    printf("請輸入雙向循環連結清單的元素個數：");
    scanf("%d",&n);
    printf("請輸入雙向循環連結清單中元素的值：");
    for(i=0; i<n; i++) {
        p = (DulLinkList)malloc(sizeof(DulNode));
        scanf("%d",&p->data);
        p->prior = s->prior;
        s->prior->next = p;
        p->next = s;
        s->prior = p;
    }
    return L;
}

//輸出該雙向循環連結清單
void PrintList_Dul(DulLinkList L) {
    int i;
    DulLinkList p;
    p = L;
    printf("該循環連結清單中的元素為：");
    while(p->next != L) {
        p = p->next;
        printf("%d ",p->data);
    }
    printf("\n");
}

//傳回雙向循環連結清單的長度
int ListLength_Dul(DulLinkList L) {
    DulLinkList p;
    int i;
    p = L->next;
    i = 0;
    while((p!=L) && (p!=NULL)) {
        ++i;
        p = p->next;
    }
    return i;
}

//取得雙向循環連結清單上第i個位置上的元素的值
int GetElemP1_Dul(DulLinkList L,int i,ElemType *e) {
    DulLinkList p;
    int j;
    p = L;
    j = 0;
    while(p->next && j<i) {
        ++j;
        p = p->next;
    }
    if(!p || j>i) return ERROR;
    *e = p->data;
    return OK;
}

//傳回雙向循環連結清單上第i個位置上的指針
DulLinkList GetElemP2_Dul(DulLinkList L,int i) {
    DulLinkList p;
    int j;
    p = L;
    j = 0;
    while(p->next && j<i) {
        ++j;
        p = p->next;
    }
    if(!p || j>i) return ERROR;
    return p;
}

//向該雙向循環連結清單的第i個位置之前插入元素e
DulLinkList ListInsert_Dul(DulLinkList L,int i,ElemType e) {
    DulLinkList p,s;
    int m;
    if(!(p=GetElemP2_Dul(L,i))) {
        return ERROR;
    }

    if(!(s = (DulLinkList)malloc(sizeof(DulNode)))) {
        return ERROR;
    }
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return L;
}

//删除雙向循環連結清單上第i個位置的元素，并傳回該元素的值
DulLinkList ListDelete_Dul(DulLinkList L,int i,ElemType *e) {
    DulLinkList p;
    if(!(p=GetElemP2_Dul(L,i))) {
        return ERROR;
    }
    *e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    return L;
}

//傳回雙向循環連結清單上元素e的位序
int GetLocate_Dul(DulLinkList L,ElemType e) {
    DulLinkList p;
    int j;
    p = L->next;
    j = 0;
    while((p != L) && (p->data!=e)) {
        j++;
    }
    return j;
}

//主函數
int main()
{
    DulLinkList dul;
    int len,loc;
    ElemType e;
    dul = InitList_Dul(dul);
    dul = CreateElemP_Dul(dul);
    len = ListLength_Dul(dul);
    printf("該雙向連結清單的長度為：%d\n",len);
    PrintList_Dul(dul);
    GetElemP1_Dul(dul,3,&e);//3為元素所在的位序
    printf("第i個位置的元素為：%d\n",e);
    printf("向連結清單中插入一個元素後：");
    dul = ListInsert_Dul(dul,1,0);//1為插入元素的位置
    PrintList_Dul(dul);
    printf("從連結清單删除一個元素後：");
    dul = ListDelete_Dul(dul,2,&e);//2為删除元素的位序
    PrintList_Dul(dul);
    printf("删除的元素是：%d\n",e);
    loc = GetLocate_Dul(dul,0);//0為元素的值
    printf("該雙向循環連結清單元素i的位序為:%d\n",loc);
    return 0;
}