C语言兑现线性链表（1）

C语言实现线性链表（1）

/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*/#ifndef LINKED_LIST_H#define 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 LNode{ElemType data;struct LNode * next;}LNode, *LinkList;Status compare(ElemType x, ElemType y){return x == y;}Status visit(ElemType x){printf("%c", x);return OK;}Status InitList_L(LinkList& L);Status DestroyList_L(LinkList& L);void CreateList_L(LinkList& L, int n);Status ClearList_L(LinkList& L);bool ListEmpty_L(LinkList L);int ListLength_L(LinkList L);//1 <= i <= ListLength(L)Status GetElem_L(LinkList L, int i, ElemType& e);int LocateElem_L(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));Status PriorElem_L(LinkList L, ElemType cur_e, ElemType& pre_e);Status NextElem_L(LinkList L, ElemType cur_e, ElemType& next_e);Status ListInsert_L(LinkList& L, int i, ElemType e);Status ListDelete_L(LinkList& L, int i, ElemType& e);void MergeList_L(LinkList La, LinkList Lb, LinkList& Lc);void union_L(LinkList& La, LinkList& Lb);Status ListTraverse(LinkList L, Status(*visit)(ElemType));Status InitList_L(LinkList& L){//创建头结点//为L指向的对象分配sizeof(LNode)大小的空间L = (LinkList)malloc(sizeof(LNode));L->next = NULL;return OK;}Status DestroyList_L(LinkList& L){if (ListEmpty_L(L)){return ERROR;}LinkList temp = L;while (L == NULL){L = L->next;free(temp);}free(L);return OK;}void CreateList_L(LinkList& L, int n){// L = (LinkList)malloc(sizeof(LNode));// L->next = NULL;LinkList p;for (int i = n; i > 0; --i){p = (LinkList)malloc(sizeof(LNode));scanf_s("%c", &p->data);p->next = L->next;L->next = p;}}bool ListEmpty_L(LinkList L){return L->next == NULL;}int ListLength_L(LinkList L){int i = 0;LinkList p = L;while(p->next != NULL){i++;p = p->next;}return i;}Status GetElem_L(LinkList L, int i, ElemType& e){LinkList p = L;for (int a = 1; a <= i; a++){p = p->next;}e = p->data;return OK;}int LocateElem_L(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)){if (L == NULL){return ERROR;}int i = 0;LinkList p = L;while(p != NULL){i++;p = p->next;if ((*compare)(p->data, e)){return i;}}return 0;}Status PriorElem_L(LinkList L, ElemType cur_e, ElemType& pre_e){int i = LocateElem_L(L, cur_e, compare);if (L == NULL && i == 1){return ERROR;}GetElem_L(L, i - 1, pre_e);return OK;}Status NextElem_L(LinkList L, ElemType cur_e, ElemType& next_e){int i = LocateElem_L(L, cur_e, compare);if (L == NULL && i == ListLength_L(L)){return ERROR;}GetElem_L(L, i + 1, next_e);return OK;}Status ListInsert_L(LinkList& L, int i, ElemType e){//寻找第i个结点，并令p指向其前趋LinkList p = L;int j = 0;while (p && j < i - 1){p = p->next;++j;}if (!p || j > i - 1){return ERROR;}LinkList s = (LinkList)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return OK;}Status ListDelete_L(LinkList& L, int i, ElemType& e){//寻找第i个结点，并令p指向其前趋LinkList p = L;int j = 0;while (p->next && j < i - 1){p = p->next;++j;}if (!(p->next) || j > i - 1){return ERROR;}LinkList q = p->next;p->next = q->next;e = q->data;free(q);return OK;}//为Lc重新分配所有结点空间void MergeList_L(LinkList La, LinkList Lb, LinkList& Lc){int i = 1, j = 1, k = 0;int La_Len = ListLength_L(La);int Lb_Len = ListLength_L(Lb);ElemType ai, bj;while((i <= La_Len) && (j <= Lb_Len)){GetElem_L(La, i, ai);GetElem_L(Lb, j, bj);if (ai <= bj){if (!ListInsert_L(Lc, ++k, ai)){printf("Insert Error!");}++i;}else{if (!ListInsert_L(Lc, ++k, bj)){printf("Insert Error!");}++j;}}while(i <= La_Len){GetElem_L(La, i++, ai);ListInsert_L(Lc, ++k, ai);}while (j <= Lb_Len){GetElem_L(Lb, j++, bj);ListInsert_L(Lc, ++k, bj);}}//新建Lc，将La和Lb插入到Lc中，遍历完一个链表后直接将剩下的一个链表链接到Lc后面//由于是链表，所以插入的过程只是在修改指针的值，并没有重新分配空间，所以会改变原来链表的结构(pc->next = pa ? pa : pb)void union_L(LinkList& La, LinkList& Lb){LinkList pa, pb, pc;pa = La->next;pb = Lb->next;pc = La;while(pa && pb){if (pa->data <= pb->data){pc->next = pa;pc = pa;pa = pa->next;}else{pc->next = pb;pc = pb;pb = pb->next;}}//if 1 : pa; if 0 : pbpc->next = pa ? pa : pb;}//按值传递，头指针L不会变//L是指向头结点的指针，并没有使用到头结点的数据域，使用了头结点的指针域Status ListTraverse(LinkList L, Status(*visit)(ElemType)){LinkList p = L;if (ListEmpty_L(L)){return ERROR;}while(p->next != NULL){(*visit)(p->next->data);p = p->next;}return OK;}#endif