C语言实现顺序表

/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*/#include <stdio.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 int BOOL;#define LIST_INIT_SIZE 100//初始化空间大小#define LISTINCREMENT 10  //当空间不足时，为顺序表增加一个大小为LISTINCREMENT个数据元素的空间typedef int ElemType; //定义处理数据元素的类型为int//数据typedef struct{ElemType* elem;  //存储空间基址int length;      //当前长度int listsize;    //当前分配的存储容量(以sizeof(ElemType)为单位)}Sqlist;Status compare(ElemType x, ElemType y){return x == y;}//初始化一个空的顺序表Status InitList_Sq(Sqlist *L){//从基址L.elem开始分配LIST_INIT_SIZE * sizeof(ElemType)大小的空间L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));if (!L->elem){exit(OVERFLOW);}L->length = 0;L->listsize = LIST_INIT_SIZE;return OK;}//销毁一个顺序表Status DestroyList_Sq(Sqlist *L){if (!L->elem){return ERROR;}free(L->elem);return OK;}//将顺序表重置为空Status ClearList_Sq(Sqlist *L){if (!L->elem){return ERROR;}L->length = 0;L->listsize = LIST_INIT_SIZE;return OK;}//判断顺序表是否为空；如果为空，返回TRUE；如果不为空，返回FALSEBOOL ListEmpty_Sq(Sqlist L){if (L.length == 0)return TRUE;return FALSE;}//返回顺序表长度int ListLength_Sq(Sqlist L){if (!L.elem){return ERROR;}return L.length;}//获得顺序表第i个元素的值，并存储在e中Status GetElem_Sq(Sqlist L, int i, ElemType* e){if ((!L.elem) || i < 1 || i > ListLength_Sq(L)){return ERROR;}*e = L.elem[i - 1];return OK;}//获得顺序表中第一次出现指定数据元素e的位置i，1 <= i <= ListLength(L)，如果存在，返回位置i；如果不存在，返回0//compare只是一个函数，不清楚为什么要加入到参数表，更不明白下面调用compare函数为什么要用间接引用操作符int LocateElem_Sq(Sqlist L, ElemType e, Status(*compare)(ElemType, ElemType)){//i为位置的值，赋初值为1int i = 1;//给p赋顺序表的基址，通过p++来遍历顺序表ElemType* p = L.elem;//这里的compare是在Status(*compare)(ElemType, ElemType)定义的while (i <= L.length && !(*compare)(*p++, e)){++i;}if (i <= L.length)return i;elsereturn 0;}//获得顺序表中指定元素cur_e的前一个数据元素，并存储在pre_e中Status PriorElem_Sq(Sqlist L, ElemType cur_e, ElemType* pre_e){int pos = LocateElem_Sq(L, cur_e, compare);if (L.elem &&  pos <= 1){return ERROR;}GetElem_Sq(L, pos - 1, pre_e);return OK;}//获得顺序表中指定元素cur_e的后一个数据元素，并存储在next_e中Status NextElem_Sq(Sqlist L, ElemType cur_e, ElemType* next_e){int pos = LocateElem_Sq(L, cur_e, compare);if (L.elem &&  pos == L.length){return ERROR;}GetElem_Sq(L, pos + 1, next_e);return OK;}//在顺序表L中位置i(1 <= i <= ListLength(L) + 1)插入数据元素e，要求为非递增序列Status ListInsert_Sq(Sqlist* L, int i, ElemType e){if (i < 1 || i > L->length + 1){return ERROR;}//当前存储空间已满，增加分配if (L->length >= L->listsize){ElemType* newbase = (ElemType*)realloc(L->elem, (L->listsize  + LISTINCREMENT) * sizeof(ElemType));if (!newbase){exit(OVERFLOW);}L->elem = newbase;L->listsize += LISTINCREMENT;}ElemType *p, *q;//给q赋位置i处数据元素的地址，q为顺序表末尾数据元素地址q = &(L->elem[i - 1]);//为了方便，从最后一个数据元素开始移动for (p = &(L->elem[L->length - 1]); p >= q; --p){*(p + 1) = *p;}*q = e;++L->length;return OK;}//2.11Status ListInsert_Auto_Sq(Sqlist* L, ElemType e){//选出合适的位置int i, j;for (i = 1; i <= L->length; i++){if (L->elem[i - 1] > e)break;}//移动元素for (j = ++(L->length); j >= i + 1; j--){L->elem[j - 1] = L->elem[j - 2];}//赋值L->elem[i - 1] = e;return OK;}//在顺序表L中位置i(1 <= i <= ListLength(L) + 1)删除数据元素，并将删除的值存在e中Status ListDelete_Sq(Sqlist* L, int i, ElemType* e){if ((i < 1) || (i > L->length)){return ERROR;}ElemType *p, *q;//给q赋位置i处数据元素的地址，q为顺序表末尾数据元素地址p = &(L->elem[i - 1]);*e = *p;q = L->elem + L->length - 1;//为了方便，从删除位置i处开始移动for (++p; p <= q; ++p){*(p - 1) = *p;}--L->length;return OK;}//归并两个顺序表，并将结果存储在Lc中，要求La和Lb非递减排列//时间复杂度为O(ListLength(La) + ListLength(b))void MergeList_Sq(Sqlist La, Sqlist Lb, Sqlist* Lc){ElemType *pa, *pb, *pc, *pa_last, *pb_last;//pa和pb赋La.elem和Lb.elem的基址pa = La.elem;pb = Lb.elem;//初始化LcLc->listsize = Lc->length = La.length + Lb.length;//pc赋Lc.elem的基址pc = Lc->elem = (ElemType*)malloc(Lc->listsize * sizeof(ElemType));if (!Lc->elem){exit(OVERFLOW);}//pa_last和pb_last指向La.elem和Lb.elem的最后的数据元素pa_last = La.elem + La.length - 1;pb_last = Lb.elem + Lb.length - 1;//给pc赋值，遍历完其中一个表后会退出循环while(pa <= pa_last && pb <= pb_last){if (*pa <= *pb){*pc++ = *pa++;}else{*pc++ = *pb++;}}//将剩下的一个未被遍历完的顺序表加入到pc中while(pa <= pa_last)*pc++ = *pa++;while(pb <= pb_last)*pc++ = *pb++;}//合并两个表，将所有在顺序表Lb中但不在La中的数据元素插入到La中//时间复杂度为O(ListLength(La) * ListLength(b))void union_Sq(Sqlist* La, Sqlist* Lb){int La_len = ListLength_Sq(*La);int Lb_len = ListLength_Sq(*Lb);ElemType e;int i;for (i = 1; i <= Lb_len; i++){GetElem_Sq(*Lb, i, &e);if (!LocateElem_Sq(*La, e, compare)){ListInsert_Sq(La, ++La_len, e);}}}Status visit(ElemType x){printf("%d", x);return OK;}//遍历整个顺序表Status ListTraverse(Sqlist L, Status(*visit)(ElemType)){if (!L.elem){return ERROR;}int i;ElemType e = 1;for (i = 1; i <= ListLength_Sq(L); i++){if (!visit(L.elem[i - 1])){return ERROR;}}printf("\n");return OK;}//2.12 比较两个顺序表int CompareList(Sqlist a, Sqlist b){//找出最大共同前缀int i;for (i = 0; i < a.length && i < b.length; i++){if (a.elem[i] != b.elem[i])break;}//求A’和B‘//i为A‘和B’的首元元素//判断AB关系//A' == B;  A'和B‘为空表if (i == a.length && i == b.length)return 0;//A' < B'  A’为空表，B‘不为空表else if (a.length == i && b.length)return -1;//A' < B'  A‘和B’都不为空，A‘首元素小于B’首元素else if (a.elem[i] < b.elem[i])return -1;//A' > B'elsereturn 1;}int main(){Sqlist *a = (Sqlist*)malloc(sizeof(Sqlist));Sqlist *b = (Sqlist*)malloc(sizeof(Sqlist));InitList_Sq(a);InitList_Sq(b);int i;ElemType e = 1;for (i = 1; i <= 5; i++){ListInsert_Sq(a, i, e);e += 2;}e = 1;for (i = 1; i <= 5; i++){ListInsert_Sq(b, i, e);e += 1;}//ListInsert_Auto_Sq(a, 8);printf("%d\n", CompareList(*b, *a));//ListTraverse(*a, visit);DestroyList_Sq(a);DestroyList_Sq(b);free(a);free(b);return 0;}

?

?