1 #include "stdio.h" 2 #include "stdlib.h" 3 4 typedef int ElemType; //线性表存储基本类型 5 typedef int Status; //基本操作函数类型 6 #define LIST_INT_SIZE 50 //线性表初始化存储空间分配量 7 #define LISTINCREMENT 10 //线性表存储空间分配量增值 8 #define OK 1 9 #define ERROR 0 10 11 typedef struct 12 { 13 ElemType *elem; //存储空间基址 14 int length; //当前长度 15 int listsize; //当前分配的存储容量（以sizeof（ElemType）为单位） 16 }SqList; 17 18 //构建一个空的线性表 19 Status InitList(SqList &L) 20 { 21 L.elem = (ElemType *)malloc(LIST_INT_SIZE * sizeof(ElemType)); 22 if(!L.elem) //如果初始化失败返回ERROR 23 return ERROR; 24 L.length = 0; //空表长度为0 25 L.listsize = LIST_INT_SIZE; //初始存储容量 26 return OK; 27 }//InitLise 28 29 //销毁线性表L 30 Status DestroyList(SqList &L) 31 { 32 free(L.elem); //收回空间 33 L.elem = NULL; //基址指向NULL 34 L.length = 0; //长度变0 35 L.listsize = 0; //清除存储容量 36 return OK; 37 }//DestroyList 38 39 //重置线性表L为空表 40 bool ClearList(SqList &L) 41 { 42 L.length = 0; 43 return OK; 44 }//ClearList 45 46 //查看线性表是否为空表 47 Status ListEmpty(SqList L) 48 { 49 if(L.length == 0) 50 return OK; 51 else 52 return ERROR; 53 }//ListEmpty 54 55 //查看线性表的元素个数 56 int ListLength(SqList L) 57 { 58 return L.length; //返回长度 59 }//ListLength 60 61 //用e返回第i个数据元素的值 62 Status GetElem(SqList L, int i, ElemType &e) 63 { 64 if(i < 1 || i > L.length) //判断i值是否合法 65 return ERROR; 66 e = L.elem[i-1]; //赋值第i个元素值 67 return OK; 68 }//GetElem 69 70 //返回L中第一个与e满足关系compare()的数据元素 71 //若这样的数据元素不存在则返回0 72 int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType,ElemType)) 73 { 74 ElemType *p = L.elem; 75 int i = 1; 76 while(i <= L.length && !compare(*p++,e)) 77 ++i; 78 if(i <= L.length) 79 return i; 80 else 81 return -1; 82 }//LocateElem 83 84 //若cur_e是L的数据元素，且不是第一个，则用pre_e返回他的前驱 85 //否则操作是啊比，pre_e无定义 86 Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e) 87 { 88 int i = 2; 89 ElemType *p = L.elem+1; 90 while(i <= L.length && *p != cur_e) 91 { 92 p++; 93 i++; 94 } 95 if(i > L.length) 96 return ERROR; 97 else 98 { 99 pre_e = *--p;100 return OK;101 }102 }//PriorElem103 104 //若cur_e是L的数据元素，且不是最后一个，则用next_e返回他的后驱105 //否则操作是啊比，next_e无定义106 Status NextList(SqList L, ElemType cur_e, ElemType &next_e)107 {108 int i = 1;109 ElemType *p = L.elem;110 while(i <= L.length && *p != cur_e)111 {112 ++p;113 ++i;114 }115 if(i == L.length)116 return ERROR;117 else118 {119 next_e = *++p;120 return OK;121 }122 }//NextList123 124 //插入元素125 Status ListInsert(SqList &L, int i, ElemType e)126 {127 if(i < 1 || i > L.length+1) //判断i值是否合法128 return ERROR; 129 SqList newbase; //用于存储新加元素的位置空间130 if(L.length >= L.listsize) //当前存储分配已满，增加分配131 {132 newbase.elem = (ElemType *)realloc(L.elem,133 (L.listsize + LISTINCREMENT) * sizeof(ElemType));134 if(!newbase.elem) //存储分配失败135 return ERROR; 136 L.elem = newbase.elem; //新基址137 L.listsize += LISTINCREMENT; //增加存储容量138 }139 ElemType *q = &(L.elem[i-1]); //q指向插入位置140 for (ElemType *p = &(L.elem[L.length-1]); p >= q; --p) //p指向表尾141 *(p+1) = *p; //插入位置及之后的元素右移142 *q = e; //插入元素143 ++L.length; //表长加一144 return OK;145 }//ListInsert146 147 //删除第几个元素并返回值148 Status ListDelete(SqList &L, int i, ElemType &e)149 {150 if((i < 1) || (i > L.length)) //判断i值是否合法151 return ERROR; //i值不合法返回失败152 ElemType *p = &(L.elem[i-1]); //p指向被删除元素的位置153 e = *p; //返回被删除元素的值154 ElemType *q = L.elem + L.length - 1; //q指向最后一个元素的位置155 for (++p; p <= q; ++p) //被删除元素之后的元素左移156 *(p-1) = *p;157 --L.length; //当前表长减一158 return OK;159 }//ListDelete160 161 //依次对L的每一个数据元素调用Visit()函数162 Status ListTraverse(SqList L, void(*Visit)(ElemType*))163 {164 ElemType *p = L.elem;165 int i;166 for(i = 1; i <= L.length; i++)167 Visit(p++);168 printf("\n");169 return OK;170 }//ListTraverse171 172 //ListTraverse()调用函数Visit()173 //Visit函数在这里做输出链表功能174 void Visit(ElemType *c)175 {176 printf("%d",*c); //%d随data类型而变177 }178 179 //查找元素180 int ListLocate(SqList L, ElemType e)181 {182 int i = 1;183 while(i <= L.length)184 {185 if (L.elem[i-1] == e)186 break;187 i++;188 }189 if(i <= L.length) //找到指定元素则返回位置否则返回-1190 return i;191 else192 return -1;193 }//ListLocate 线性表的顺序表达的13个基本函数。
参考《数据结构（C语言版）》严蔚敏编著