C语言实现循环链表

/*-----------------------------------------Copyright (c) 2010-2011 Zidane CLiUsage of this program is free for non-commercial use.-----------------------------------------*//* 在循环链表中设立为指针而不设置头指针.L->next即为头结点.*/#ifndef CIRCULAR_LINKED_LIST_H#define CIRCULAR_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; //定义处理数据元素的类型为inttypedef struct CLNode{ElemType data;struct CLNode * next;}CLNode, *CLinkList;Status compare(ElemType x, ElemType y){return x == y;}Status visit(ElemType x){printf("%c", x);return OK;}Status InitList_CL(CLinkList& L);Status DestroyList_CL(CLinkList& L);void CreateList_CL(CLinkList& L, int n);Status ClearList_CL(CLinkList& L);bool ListEmpty_CL(CLinkList L);int ListLength_CL(CLinkList L);//1 <= i <= CListCLength(L)Status GetElem_CL(CLinkList L, int i, ElemType& e);int LocateElem_CL(CLinkList L, ElemType e, Status(*compare)(ElemType, ElemType));Status PriorElem_CL(CLinkList L, ElemType cur_e, ElemType& pre_e);Status NextElem_CL(CLinkList L, ElemType cur_e, ElemType& next_e);Status ListInsert_CL(CLinkList& L, int i, ElemType e);Status ListDelete_CL(CLinkList& L, int i, ElemType& e);void MergeList_CL(CLinkList CLa, CLinkList CLb, CLinkList& CLc);void union_CL(CLinkList& CLa, CLinkList& CLb);Status ListTraverse_CL(CLinkList L, Status(*visit)(ElemType));Status InitList_CL(CLinkList& L){L = (CLinkList)malloc(sizeof(CLNode));L->next = L;return OK;}Status DestroyList_CL(CLinkList& L){ClearList_CL(L);free(L);return OK;}void CreateList_CL(CLinkList& L, int n){CLinkList p;for (int i = 1; i <= n; i++){p = (CLinkList)malloc(sizeof(CLNode));scanf_s("%c", &p->data);ListInsert_CL(L, i, p->data);}}Status ClearList_CL(CLinkList& L){ElemType e;while(ListLength_CL(L)){ListDelete_CL(L, 1, e);}return OK;}bool ListEmpty_CL(CLinkList L){return L->next == L;}int ListLength_CL(CLinkList L){int i = 0;CLinkList p = L->next;while(p != L){i++;p = p->next;}return i;}Status GetElem_CL(CLinkList L, int i, ElemType& e){CLinkList p = L->next;for (int a = 1; a <= i; a++){p = p->next;}e = p->data;return OK;}int LocateElem_CL(CLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)){int i = 0;CLinkList p = L->next;while(p != L){i++;p = p->next;if ((*compare)(p->data, e)){return i;}}return 0;}Status PriorElem_CL(CLinkList L, ElemType cur_e, ElemType& pre_e){int i = LocateElem_CL(L, cur_e, compare);if (L == L->next && i == 1){return ERROR;}GetElem_CL(L, i - 1, pre_e);return OK;}Status NextElem_CL(CLinkList L, ElemType cur_e, ElemType& next_e){int i = LocateElem_CL(L, cur_e, compare);if (L == L->next && i == ListLength_CL(L)){return ERROR;}GetElem_CL(L, i + 1, next_e);return OK;}Status ListInsert_CL(CLinkList& L, int i, ElemType e){CLinkList p = L->next;int j = 0;while (p != L && j < i - 1){p = p->next;++j;}if (p == L && j > i - 1){return ERROR;}CLinkList s = (CLinkList)malloc(sizeof(CLNode));s->data = e;s->next = L->next;p->next = s;L = s;return OK;}Status ListDelete_CL(CLinkList& L, int i, ElemType& e){CLinkList p = L->next;int j = 0;while (p != L && j < i - 1){p = p->next;++j;}if (p == L || j > i - 1){return ERROR;}CLinkList q = p->next;p->next = q->next;if (q == L){L = p;}e = q->data;free(q);return OK;}void MergeList_CL(CLinkList CLa, CLinkList CLb, CLinkList& CLc){int i = 1, j = 1, k = 0;int CLa_Len = ListLength_CL(CLa);int CLb_Len = ListLength_CL(CLb);ElemType ai, bj;while((i <= CLa_Len) && (j <= CLb_Len)){GetElem_CL(CLa, i, ai);GetElem_CL(CLb, j, bj);if (ai <= bj){if (!ListInsert_CL(CLc, ++k, ai)){printf("Insert Error!");}++i;}else{if (!ListInsert_CL(CLc, ++k, bj)){printf("Insert Error!");}++j;}}while(i <= CLa_Len){GetElem_CL(CLa, i++, ai);ListInsert_CL(CLc, ++k, ai);}while (j <= CLb_Len){GetElem_CL(CLb, j++, bj);ListInsert_CL(CLc, ++k, bj);}}void union_CL(CLinkList& CLa, CLinkList& CLb){CLinkList temp = CLb->next;CLb->next = CLa->next;//使用temp->next为了跳过CLb的头结点CLa->next = temp->next;CLa = CLb;}Status ListTraverse_CL(CLinkList L, Status(*visit)(ElemType)){CLinkList p = L->next;if (ListEmpty_CL(L)){return ERROR;}while(p != L){(*visit)(p->next->data);p = p->next;}return OK;}#endif