C语言实现双向循环链表
/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*//*实现双向循环链表*/#ifndef DOUBLE_LINKED_LIST_H#define DOUBLE_LINKED_LIST_H#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0;#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef char ElemType; //定义处理数据元素的类型为intypedef struct DuLNode {ElemType data;struct DuLNode* prior;struct DuLNode* next;}*DuLinkList;Status compare(ElemType x, ElemType y){return x == y;}Status visit(ElemType x){printf("%c", x);return OK;}Status InitList_DL(DuLinkList& L);Status DestroyList_DL(DuLinkList& L);void CreateList_DL(DuLinkList& L, int n);Status ClearList_DL(DuLinkList& L);bool ListEmpty_DL(DuLinkList L);int ListLength_DL(DuLinkList L);Status GetElem_DL(DuLinkList L, int i, ElemType& e);int LocateElem_DL(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType));Status PriorElem_DL(DuLinkList L, ElemType cur_e, ElemType& pre_e);Status NextElem_DL(DuLinkList L, ElemType cur_e, ElemType& next_e);Status ListInsert_DL(DuLinkList& L, int i, ElemType e);Status ListDelete_DL(DuLinkList& L, int i, ElemType& e);void MergeList_DL(DuLinkList DLa, DuLinkList DLb, DuLinkList& DLc);void union_DL(DuLinkList& DLa, DuLinkList& DLb);Status ListTraverse_DL(DuLinkList L, Status(*visit)(ElemType));Status InitList_DL(DuLinkList& L){L = (DuLinkList)malloc(sizeof(DuLNode));L->prior = L;L->next = L;return OK;}Status DestroyList_DL(DuLinkList& L){ClearList_DL(L);free(L);return OK;}void CreateList_DL(DuLinkList& L, int n){DuLinkList p;for (int i = 1; i <= n; i++){p = (DuLinkList)malloc(sizeof(DuLinkList));scanf_s("%c", &p->data);ListInsert_DL(L, i, p->data);}}Status ClearList_DL(DuLinkList& L){ElemType e;for (int i = 1; i <= ListLength_DL(L); i++){ListDelete_DL(L, 1, e);}return OK;}bool ListEmpty_DL(DuLinkList L){return L->prior == L && L->next == L;}int ListLength_DL(DuLinkList L){int i = 0;DuLinkList p = L->next;while(p != L){i++;p = p->next;}return i;}Status GetElem_DL(DuLinkList L, int i, ElemType& e){DuLinkList p = L;for (int a = 1; a <= i; a++){p = p->next;}e = p->data;return OK;}int LocateElem_DL(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)){int i = 0;DuLinkList p = L->next;while(p != L){i++;p = p->next;if ((*compare)(p->data, e)){return i;}}return 0;}Status PriorElem_DL(DuLinkList L, ElemType cur_e, ElemType& pre_e){DuLinkList p = L->next;while(p != L && !(*compare)(p->data, cur_e)){p = p->next;}pre_e = p->prior->data;return OK;}Status NextElem_DL(DuLinkList L, ElemType cur_e, ElemType& next_e){DuLinkList p = L->next;while(p != L && !(*compare)(p->data, cur_e)){p = p->next;}next_e = p->next->data;return OK;}Status ListInsert_DL(DuLinkList& L, int i, ElemType e){DuLinkList p = L->next;int j = 0;while (p != L && j < i - 2){p = p->next;++j;}DuLinkList s = (DuLinkList)malloc(sizeof(DuLNode));s->data = e; s->next = p->next; p->next->prior = s;s->prior = p;p->next = s;return OK;}Status ListDelete_DL(DuLinkList& L, int i, ElemType& e){//寻找到要删除的结点DuLinkList p = L->next;int j = 0;while (p != L && j < i - 2){p = p->next;++j;}e = p->data;p->prior->next = p->next;p->next->prior = p->prior;return OK;}void MergeList_DL(DuLinkList DLa, DuLinkList DLb, DuLinkList& DLc){int i = 1, j = 1, k = 0;int DLa_Len = ListLength_DL(DLa);int DLb_Len = ListLength_DL(DLb);ElemType ai, bj;while((i <= DLa_Len) && (j <= DLb_Len)){GetElem_DL(DLa, i, ai);GetElem_DL(DLb, j, bj);if (ai <= bj){if (!ListInsert_DL(DLc, ++k, ai)){printf("Insert Error!");}++i;}else{if (!ListInsert_DL(DLc, ++k, bj)){printf("Insert Error!");}++j;}}while(i <= DLa_Len){GetElem_DL(DLa, i++, ai);ListInsert_DL(DLc, ++k, ai);}while (j <= DLb_Len){GetElem_DL(DLb, j++, bj);ListInsert_DL(DLc, ++k, bj);}}//双向循环链表union后会改变两个链表，所以不能再对DLb进行操作//链接两个链表，要删除DLb的头指针void union_DL(DuLinkList& DLa, DuLinkList& DLb){DLb->prior->next = DLa;DLa->prior->next = DLb->next;DuLinkList temp = DLa->prior;DLa->prior = DLb->prior;DLb->next->prior = temp;free(DLb);}Status ListTraverse_DL(DuLinkList L, Status(*visit)(ElemType)){DuLinkList p = L->next;if (ListEmpty_DL(L)){return ERROR;}while(p != L){(*visit)(p->data);p = p->next;}return OK;}#endif
