本程序在linux下编译通过
SqList.h
1 #include2 #include 3 #include 4 5 //定义数据类型为int型 6 typedef int ElemType; 7 8 //定义数据类型的打印函数 9 typedef void (*Visit)(ElemType*); 10 11 //定义数据类型的比较函数 12 typedef int (*Compare)(ElemType*, ElemType*); 13 14 typedef struct List{ 15 ElemType *list; //存储空间基址 16 int size; //当前长度 17 int maxSize; //当前分配的存储容量 18 }SqList; 19 typedef SqList* PSqList; 20 typedef const SqList CSqList; 21 typedef const SqList* PCSqList; 22 23 /**************************************** 24 Purpose : 初始化线性表 25 Input : pList -- 线性表指针 26 ms -- 线性表最大容量 27 Return : 0 --OK 28 -1 --FAIL 29 *****************************************/ 30 int InitList(PSqList pList, int ms); 31 32 /**************************************** 33 Purpose : 清除线性表L中的所有元素，释放存储空间 34 使之成为一个空表 35 Input : pList -- 线性表指针 36 Return : None 37 *****************************************/ 38 void ClearList(PSqList pList); 39 40 /**************************************** 41 Purpose : 返回线性表数据长度 42 Input : pList -- 线性表指针 43 Return : 线性表长度 44 *****************************************/ 45 int ListLength(PSqList pList); 46 47 48 /**************************************** 49 Purpose : 判断线性表是否为空 50 Input : pList -- 线性表指针 51 Return : 1 -- 为空 52 0 -- 不为空 53 *****************************************/ 54 int ListEmpty(PSqList pList); 55 56 57 /**************************************** 58 Purpose : 返回线性表中第nPos个元素的值 59 Input : pList -- 线性表指针 60 nPos -- 元素的位置 [1,ListLength(L)] 61 e -- 要返回的元素 62 Return : 0 --OK 63 -1 --FAIL 64 *****************************************/ 65 int GetElem(PSqList pList, int nPos, ElemType* e); 66 67 68 /**************************************** 69 Purpose : 遍历输出线性表中每个元素 70 Input : pList -- 线性表指针 71 visit -- 遍历函数指针 72 Return : 0 --OK 73 -1 --FAIL 74 *****************************************/ 75 int TraverseList(PSqList pList, Visit visit); 76 77 78 /**************************************** 79 Purpose : 向线性表中第nPos个位置插入元素data 80 Input : pList -- 线性表指针 81 nPos -- 元素的位置 [1, ListLength[L]+1] 82 data -- 要插入的元素 83 Return : 0 --OK 84 -1 --FAIL 85 *****************************************/ 86 int InsertList(PSqList pList, int nPos, ElemType* data); 87 88 89 /**************************************** 90 Purpose : 从线性表中第nPos个位置删除元素并赋值给data 91 Input : pList -- 线性表指针 92 nPos -- 元素的位置 [1, ListLength[L]] 93 data -- 要赋值的元素 94 Return : 0 --OK 95 -1 --FAIL 96 *****************************************/ 97 int DeleteList(PSqList pList, int nPos, ElemType* data); 98 99 100 /****************************************101 Purpose : 更新第nPos个位置元素102 Input : pList -- 线性表指针103 nPos -- 元素的位置 [1, ListLength[L]]104 data -- 要更新的元素105 Return : 0 --OK106 -1 --FAIL107 *****************************************/108 int UpdateList(PSqList pList, int nPos, ElemType* val);109 110 111 112 /****************************************113 Purpose : 对线性表进行排序114 Input : pList -- 线性表指针115 compare -- 比较函数116 Return : 0 --OK117 -1 --FAIL118 *****************************************/119 int OrderList(PSqList pList, Compare compare);
SqList.c
1 /********************************************************************* 2 *: 3 *: Author: dspeeding 4 *: Copyright (c) 2013, dspeeding 5 *: 6 *: Created at: 2013.08.05 7 *: Last modified: 2013.08.05 8 *: 9 *: Introduction: 线性表实现 10 *： 11 *: 注：ElemType类型 不能进行深拷贝，请留意 12 *: 如使用 TraverseList 函数 则需要自己实现Visit函数 13 *: 如使用 OrderList 函数 则需要自己实现Compare函数 14 *: 该OrderList函数 使用简单冒泡排序算法实现 15 *: 16 *:*********************************************************************/ 17 18 #include "SqList.h" 19 20 21 22 /**************************************** 23 Purpose : 扩展线性表 24 Input : pList -- 线性表指针 25 Return : 0 --OK 26 -1 --FAIL 27 *****************************************/ 28 int againMalloc(PSqList pList) 29 { 30 //扩展空间为原来的2倍，原内容被自动拷贝到p所指向的存储空间 31 ElemType *p = realloc(pList->list, 2*pList->maxSize*sizeof(ElemType)); 32 if(!p) 33 { 34 //分配空间失败 35 return -1; 36 } 37 38 pList->list = p; 39 pList->maxSize = 2*pList->maxSize; 40 return 0; 41 } 42 43 /**************************************** 44 Purpose : 初始化线性表 45 Input : pList -- 线性表指针 46 ms -- 线性表最大容量 47 Return : 0 --OK 48 -1 --FAIL 49 *****************************************/ 50 int InitList(PSqList pList, int ms) 51 { 52 if(ms <= 0) 53 { 54 //ms无效 55 return -1; 56 } 57 pList->maxSize = ms; 58 pList->size = 0; 59 pList->list = malloc(ms*sizeof(ElemType)); 60 if(!pList->list) 61 { 62 //分配空间失败 63 return -1; 64 } 65 return 0; 66 } 67 68 69 /**************************************** 70 Purpose : 清除线性表L中的所有元素，释放存储空间 71 使之成为一个空表 72 Input : pList -- 线性表指针 73 Return : None 74 *****************************************/ 75 void ClearList(PSqList pList) 76 { 77 if(pList != NULL) 78 { 79 if(pList->list != NULL) 80 { 81 free(pList->list); 82 pList->list = NULL; 83 pList->size = 0; 84 pList->maxSize = 0; 85 } 86 } 87 } 88 89 90 /**************************************** 91 Purpose : 返回线性表数据长度 92 Input : pList -- 线性表指针 93 Return : 线性表长度 94 *****************************************/ 95 int ListLength(PSqList pList) 96 { 97 return pList->size; 98 } 99 100 101 /****************************************102 Purpose : 判断线性表是否为空103 Input : pList -- 线性表指针104 Return : 1 -- 为空105 0 -- 不为空106 *****************************************/107 int ListEmpty(PSqList pList)108 {109 if(pList->size == 0)110 {111 return 1;112 }113 else114 {115 return 0;116 }117 }118 119 /****************************************120 Purpose : 返回线性表中第nPos个元素的值121 Input : pList -- 线性表指针122 nPos -- 元素的位置 [1,ListLength(L)]123 e -- 要返回的元素124 Return : 0 --OK125 -1 --FAIL126 *****************************************/127 int GetElem(PSqList pList, int nPos, ElemType* e)128 {129 if(pList== NULL || pList->list == NULL)130 {131 return -1;132 }133 if(nPos < 1|| nPos > pList->size)134 {135 //越界136 return -1;137 }138 if(pList->list == NULL)139 {140 return -1;141 }142 143 memcpy(e, &pList->list[nPos-1], sizeof(ElemType));144 return 0;145 }146 147 /****************************************148 Purpose : 遍历输出线性表中每个元素149 Input : pList -- 线性表指针150 visit -- 遍历函数指针151 Return : 0 --OK152 -1 --FAIL153 *****************************************/154 int TraverseList(PSqList pList, Visit visit)155 {156 int i;157 if(visit == NULL || pList==NULL || pList->list==NULL)158 {159 return -1;160 }161 for(i=0;i size;i++)162 {163 visit(&pList->list[i]);164 }165 return 0;166 }167 168 169 /****************************************170 Purpose : 向线性表中第nPos个位置插入元素data171 Input : pList -- 线性表指针172 nPos -- 元素的位置 [1, ListLength[L]+1]173 data -- 要插入的元素174 Return : 0 --OK175 -1 --FAIL176 *****************************************/177 int InsertList(PSqList pList, int nPos, ElemType* data)178 {179 int i;180 if(pList== NULL || pList->list == NULL)181 {182 return -1;183 }184 185 if(nPos < 1 || nPos > pList->size + 1)186 {187 return -1;188 }189 if(pList->size == pList->maxSize)190 {191 //重新分配更大空间192 if(againMalloc(pList))193 {194 return -1;195 }196 }197 198 for(i=pList->size - 1;i>=nPos - 1;i--)199 {200 memcpy(&pList->list[i+1], &pList->list[i], sizeof(ElemType));201 }202 memcpy(&pList->list[nPos-1], data, sizeof(ElemType));203 pList->size++;204 return 0;205 }206 207 /****************************************208 Purpose : 从线性表中第nPos个位置删除元素并赋值给data209 Input : pList -- 线性表指针210 nPos -- 元素的位置 [1, ListLength[L]]211 data -- 要赋值的元素212 Return : 0 --OK213 -1 --FAIL214 *****************************************/215 int DeleteList(PSqList pList, int nPos, ElemType* data)216 {217 int i;218 if(pList->size == 0 || pList== NULL || pList->list == NULL)219 {220 return -1;221 }222 if(nPos < 1 ||nPos > pList->size)223 {224 return -1;225 }226 memcpy(data, &pList->list[nPos-1], sizeof(ElemType));227 for(i=nPos;i size;i++)228 {229 memcpy(&pList->list[i-1], &pList->list[i], sizeof(ElemType));230 }231 pList->size--;232 return 0;233 }234 235 /****************************************236 Purpose : 更新第nPos个位置元素237 Input : pList -- 线性表指针238 nPos -- 元素的位置 [1, ListLength[L]]239 data -- 要更新的元素240 Return : 0 --OK241 -1 --FAIL242 *****************************************/243 int UpdateList(PSqList pList, int nPos, ElemType* val)244 {245 if(nPos < 1 || nPos > pList->size)246 {247 return -1;248 }249 if(pList== NULL || pList->list == NULL || val == NULL)250 {251 return -1;252 }253 memcpy(&pList->list[nPos-1], val, sizeof(ElemType));254 return 0;255 }256 257 /****************************************258 Purpose : 对线性表进行排序259 Input : pList -- 线性表指针260 compare -- 比较函数261 Return : 0 --OK262 -1 --FAIL263 *****************************************/264 int OrderList(PSqList pList, Compare compare)265 {266 int i,j;267 ElemType tmp;268 if(compare == NULL || pList == NULL || pList->list ==NULL)269 {270 return -1;271 }272 for(i=0;i size;i++)273 {274 for(j=i+1;j size;j++)275 {276 if(compare(&pList->list[i], &pList->list[j]) > 0)277 {278 memcpy(&tmp, &pList->list[i],sizeof(ElemType));279 memcpy(&pList->list[i], &pList->list[j], sizeof(ElemType));280 memcpy(&pList->list[j],&tmp, sizeof(ElemType));281 }282 }283 }284 return 0;285 }
testmain.c
1 #include2 #include "SqList.h" 3 4 5 6 void visit(ElemType *val) 7 { 8 printf("%d\n", *val); 9 }10 11 12 int compare(ElemType* e1, ElemType* e2)13 {14 return *e1 - *e2;15 }16 17 18 int main(int argc, char* argv[])19 {20 SqList L;21 int i,index;22 int nRet;23 24 25 nRet = InitList(&L, 5);26 for(i=0;i<5;i++)27 {28 InsertList(&L,i+1,&i);29 }30 31 i= -1;32 nRet = InsertList(&L, ListLength(&L), &i);33 if(nRet)34 {35 printf("插入线性表数据失败\n");36 }37 i=100;38 nRet = InsertList(&L, 2, &i);39 if(nRet)40 {41 printf("插入线性表数据失败\n");42 }43 44 TraverseList(&L, (Visit)visit);45 46 printf("排序线性表\n");47 OrderList(&L, compare);48 TraverseList(&L, (Visit)visit);49 50 51 52 nRet = DeleteList(&L, 2, &i);53 if(nRet)54 {55 printf("删除线性表数据失败\n");56 }57 printf("删除线性表数据为[%d]\n", i);58 TraverseList(&L, (Visit)visit);59 60 printf("更新线性表数据\n", i);61 i=555;62 nRet = UpdateList(&L, 2, &i);63 if(nRet)64 {65 printf("更新线性表数据失败\n");66 }67 68 TraverseList(&L, (Visit)visit);69 70 ClearList(&L);71 72 return 0;73 }
makefile
makefile为通用文件，后边除非特殊情况，否则都以本文件为编译文件
CC=gccSRC_DIR=./TARGET = testmainvpath %.c $(SRC_DIR)SRC_FILES:=$(wildcard $(SRC_DIR)*.c)SRC_FILES:=$(notdir $(SRC_FILES))OBJ_FILES:=$(patsubst %.c,%.o,$(SRC_FILES))FLAG_DEBUG=-g -Wall$(TARGET):$(OBJ_FILES) $(CC) -o $@ $(FLAG_DEBUG) $(OBJ_FILES) $(OBJ_FILES):%.o:%.c $(CC) -c $(FLAG_DEBUG) $? -o $@clean: -rm -rf *.o -rm -rf $(TARGET)