C语言实现静态链表
/*-----------------------------------------------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------------------------------------------*//* 静态链表的核心思想是利用int类型的变量来代替指针存储下一个数据元素的位置。所以，如果要定义指针，就用int代替，如果要使用p->next，就用space.cur代替，如果要使用p->data，就用space.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;//SLinkList为整个静态链表，预先申请好的用来重新分配的内存空间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.cur为头指针；0表示空指针Status InitList_SL(int& S){if (!space.cur){InitSpace_SL(space);}S = Malloc_SL(space);space.cur = 0;return OK;}Status InitSpace_SL(SLinkList& space){for (int i = 0; i < MAXSIZE - 1; i++){space.cur = i + 1;}space.cur = 0;return OK;}//返回能malloc的L的位置，即下标int Malloc_SL(SLinkList& space){int i = space.cur;if (space.cur){space.cur = space.cur;}return i;}void Free_SL(SLinkList& space, int i){space.cur = space.cur;space.cur = i;}Status DestroyList_SL(int& S){int p = S;while(S != 0){S = space.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.data);space.cur = space.cur;space.cur = p;}}Status ClearList_SL(int& S){int p = S;while(p != 0){p = space.cur;Free_SL(space, p);}return OK;}bool ListEmpty_SL(int S){return space.cur == 0;}int ListLength_SL(int S){int i = 0;int p = S;while(space.cur != 0){i++;p = space.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.cur;j++;}e = space.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.data, e) && p){p = space.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.cur;j++;}int a = Malloc_SL(space);space.data = e;space.cur = space.cur;space.cur = a;return OK;}Status ListDelete_SL(int& S, int i, ElemType& e){int p = S;int j = 0;while(space.cur && j < i - 1){p = space.cur;++j;}if (!space.cur || j > i -1){return ERROR;}int q = space.cur;space.cur = space.cur;e = space.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.cur;pb = space.cur;pc = Sa;while (pa && pb){if (space.data <= space.data){space.cur = pa;pc = pa;pa = space.cur;}else{space.cur = pb;pc = pb;pb = space.cur;}}space.cur = pa ? pa : pb;}Status ListTraverse(int S, Status(*visit)(ElemType)){int p = S;while(space.cur != 0){(*visit)(space.cur].data);p = space.cur;}return OK;}#endif
页:
[1]