C语言兑现静态链表

C语言实现静态链表

/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*//* 静态链表的核心思想是利用int类型的变量来代替指针存储下一个数据元素的位置。所以，如果要定义指针，就用int代替，如果要使用p->next，就用space[p].cur代替，如果要使用p->data，就用space[p].data代替。 不过静态链表无法摆脱顺序表的弊端，需要在程序最开始分配空间。*/#ifndef STATIC_SLIST_H#define STATIC_SLIST_H#include <stdlib.h>#include <stdio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0;#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;#define MAXSIZE 1000typedef char ElemType; //定义处理数据元素的类型为inttypedef struct {ElemType data;int cur; //游标cur代替指针指示结点在数组中的相对位置；0表示空指针；cur从1开始}component, SLinkList[MAXSIZE];//SLinkList[MAXSIZE]为整个静态链表，预先申请好的用来重新分配的内存空间Status compare(ElemType x, ElemType y){return x == y;}Status visit(ElemType x){printf("%c", x);return OK;}Status InitList_SL(int& S);Status InitSpace_SL(SLinkList& space);Status DestroyList_SL(int& S);void CreateList_SL(int& S, int n);Status ClearList_SL(int& S);bool ListEmpty_SL(int S);int ListLength_SL(int S);//1 <= i <= ListLength(L)int Malloc_SL(SLinkList& space);void Free_SL(SLinkList& space, int i);Status GetElem_SL(int S, int i, ElemType& e);int LocateElem_SL(int S, ElemType e, Status(*compare)(ElemType, ElemType));Status PriorElem_SL(int S, ElemType cur_e, ElemType& pre_e);Status NextElem_SL(int S, ElemType cur_e, ElemType& next_e);Status ListInsert_SL(int& S, int i, ElemType e);Status ListDelete_SL(int& S, int i, ElemType& e);void MergeList_SL(int Sa, int Sb, int& Sc);void union_SL(int& Sa, int& Sb);Status ListTraverse(int S, Status(*visit)(ElemType));SLinkList space;//静态链表为数组，需要提前分配空间//而提前分配好的数组需要用cur链接起来//L[0].cur为头指针；0表示空指针Status InitList_SL(int& S){if (!space[0].cur){InitSpace_SL(space);}S = Malloc_SL(space);space[S].cur = 0;return OK;}Status InitSpace_SL(SLinkList& space){for (int i = 0; i < MAXSIZE - 1; i++){space[i].cur = i + 1;}space[MAXSIZE - 1].cur = 0;return OK;}//返回能malloc的L的位置，即下标int Malloc_SL(SLinkList& space){int i = space[0].cur;if (space[0].cur){space[0].cur = space[i].cur;}return i;}void Free_SL(SLinkList& space, int i){space[i].cur = space[0].cur;space[0].cur = i;}Status DestroyList_SL(int& S){int p = S;while(S != 0){S = space[S].cur;Free_SL(space, p);}Free_SL(space, S);return OK;}void CreateList_SL(int& S, int n){int p ;for (int i = n; i > 0; --i){p = Malloc_SL(space);scanf_s("%c", &space[p].data);space[p].cur = space[S].cur;space[S].cur = p;}}Status ClearList_SL(int& S){int p = S;while(p != 0){p = space[p].cur;Free_SL(space, p);}return OK;}bool ListEmpty_SL(int S){return space[S].cur == 0;}int ListLength_SL(int S){int i = 0;int p = S;while(space[p].cur != 0){i++;p = space[p].cur;}return i;} //获得cur为i的dataStatus GetElem_SL(int S, int i, ElemType& e){int p = S;int j = 0;while(j < i){p = space[p].cur;j++;}e = space[p].data;return OK;} //返回cur cur为0 <= cur <= MAXSIZE - 1int LocateElem_SL(int S, ElemType e, Status(*compare)(ElemType, ElemType)){int p = S;int j = 0;while(!(*compare)(space[p].data, e) && p){p = space[p].cur;j++;}return j;}Status PriorElem_SL(int S, ElemType cur_e, ElemType& pre_e){int i = LocateElem_SL(S, cur_e, compare);GetElem_SL(S, i - 1, pre_e);return OK;}Status NextElem_SL(int S, ElemType cur_e, ElemType& next_e){int i = LocateElem_SL(S, cur_e, compare);GetElem_SL(S, i + 1, next_e);return OK;} //1 <= i <= MAXSIZE - 1//插入到下标为i，即cur为i+1的位置Status ListInsert_SL(int& S, int i, ElemType e){//找到下标为i的前一结点int p = S;int j = 0;while(p && j < i - 1){p = space[p].cur;j++;}int a = Malloc_SL(space);space[a].data = e;space[a].cur = space[p].cur;space[p].cur = a;return OK;}Status ListDelete_SL(int& S, int i, ElemType& e){int p = S;int j = 0;while(space[p].cur && j < i - 1){p = space[p].cur;++j;}if (!space[p].cur || j > i -1){return ERROR;}int q = space[p].cur;space[p].cur = space[q].cur;e = space[q].data;Free_SL(space, q);return OK;}void MergeList_SL(int Sa, int Sb, int& Sc){int i = 1, j = 1, k = 0;int Sa_Len = ListLength_SL(Sa);int Sb_Len = ListLength_SL(Sb);ElemType ai, bj;while ((i <= Sa_Len) && (j <= Sb_Len)){GetElem_SL(Sa, i, ai);GetElem_SL(Sb, j, bj);if (ai <= bj){if (!ListInsert_SL(Sc, ++k, ai)){printf("Insert Error!");}++i;}else{if (!ListInsert_SL(Sc, ++k, bj)){printf("Insert Error!");}++j;}}while(i <= Sa_Len){GetElem_SL(Sa, i++, ai);ListInsert_SL(Sc, ++k, ai);}while(j <= Sb_Len){GetElem_SL(Sb, j++, bj);ListInsert_SL(Sc, ++k, bj);}}void union_SL(int& Sa, int& Sb){int pa, pb, pc;pa = space[Sa].cur;pb = space[Sb].cur;pc = Sa;while (pa && pb){if (space[pa].data <= space[pb].data){space[pc].cur = pa;pc = pa;pa = space[pa].cur;}else{space[pc].cur = pb;pc = pb;pb = space[pb].cur;}}space[pc].cur = pa ? pa : pb;}Status ListTraverse(int S, Status(*visit)(ElemType)){int p = S;while(space[p].cur != 0){(*visit)(space[space[p].cur].data);p = space[p].cur;}return OK;}#endif