（1）数据结构——线性表（数组）实现（1）数据结构——线性表（数

本程序在linux下编译通过
SqList.h

1 #include 2 #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{ 15ElemType *list; //存储空间基址 16int size; //当前长度 17int maxSize; //当前分配的存储容量 18 }SqList; 19 typedef SqList* PSqList; 20 typedef const SqList CSqList; 21 typedef const SqList* PCSqList; 22 23 /**************************************** 24Purpose :初始化线性表 25Input:pList-- 线性表指针 26ms-- 线性表最大容量 27Return:0--OK 28-1--FAIL 29 *****************************************/ 30 int InitList(PSqList pList, int ms); 31 32 /**************************************** 33Purpose :清除线性表L中的所有元素，释放存储空间 34使之成为一个空表 35Input:pList-- 线性表指针 36Return:None 37 *****************************************/ 38 void ClearList(PSqList pList); 39 40 /**************************************** 41Purpose :返回线性表数据长度 42Input:pList-- 线性表指针 43Return:线性表长度 44 *****************************************/ 45 int ListLength(PSqList pList); 46 47 48 /**************************************** 49Purpose :判断线性表是否为空 50Input:pList-- 线性表指针 51Return:1 -- 为空 520 -- 不为空 53 *****************************************/ 54 int ListEmpty(PSqList pList); 55 56 57 /**************************************** 58Purpose :返回线性表中第nPos个元素的值 59Input:pList-- 线性表指针 60nPos-- 元素的位置 [1,ListLength(L)] 61e-- 要返回的元素 62Return:0--OK 63-1--FAIL 64 *****************************************/ 65 int GetElem(PSqList pList, int nPos, ElemType* e); 66 67 68 /**************************************** 69Purpose :遍历输出线性表中每个元素 70Input:pList-- 线性表指针 71visit-- 遍历函数指针 72Return:0--OK 73-1--FAIL 74 *****************************************/ 75 int TraverseList(PSqList pList, Visit visit); 76 77 78 /**************************************** 79Purpose :向线性表中第nPos个位置插入元素data 80Input:pList-- 线性表指针 81nPos-- 元素的位置 [1, ListLength[L]+1] 82data-- 要插入的元素 83Return:0--OK 84-1--FAIL 85 *****************************************/ 86 int InsertList(PSqList pList, int nPos, ElemType* data); 87 88 89 /**************************************** 90Purpose :从线性表中第nPos个位置删除元素并赋值给data 91Input:pList-- 线性表指针 92nPos-- 元素的位置[1, ListLength[L]] 93data-- 要赋值的元素 94Return:0--OK 95-1--FAIL 96 *****************************************/ 97 int DeleteList(PSqList pList, int nPos, ElemType* data); 98 99 100 /**************************************** 101Purpose :更新第nPos个位置元素 102Input:pList-- 线性表指针 103nPos-- 元素的位置[1, ListLength[L]] 104data-- 要更新的元素 105Return:0--OK 106-1--FAIL 107 *****************************************/ 108 int UpdateList(PSqList pList, int nPos, ElemType* val); 109 110 111 112 /**************************************** 113Purpose :对线性表进行排序 114Input:pList-- 线性表指针 115compare-- 比较函数 116Return:0--OK 117-1--FAIL 118 *****************************************/ 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 /**************************************** 23Purpose :扩展线性表 24Input:pList-- 线性表指针 25Return:0--OK 26-1--FAIL 27 *****************************************/ 28 intagainMalloc(PSqList pList) 29 { 30//扩展空间为原来的2倍，原内容被自动拷贝到p所指向的存储空间 31ElemType *p = realloc(pList->list, 2*pList->maxSize*sizeof(ElemType)); 32if(!p) 33{ 34//分配空间失败 35return -1; 36} 37 38pList->list = p; 39pList->maxSize = 2*pList->maxSize; 40return 0; 41 } 42 43 /**************************************** 44Purpose :初始化线性表 45Input:pList-- 线性表指针 46ms-- 线性表最大容量 47Return:0--OK 48-1--FAIL 49 *****************************************/ 50 int InitList(PSqList pList, int ms) 51 { 52if(ms <= 0) 53{ 54//ms无效 55return -1; 56} 57pList->maxSize = ms; 58pList->size = 0; 59pList->list = malloc(ms*sizeof(ElemType)); 60if(!pList->list) 61{ 62//分配空间失败 63return -1; 64} 65return 0; 66 } 67 68 69 /**************************************** 70Purpose :清除线性表L中的所有元素，释放存储空间 71使之成为一个空表 72Input:pList-- 线性表指针 73Return:None 74 *****************************************/ 75 void ClearList(PSqList pList) 76 { 77if(pList != NULL) 78{ 79if(pList->list != NULL) 80{ 81free(pList->list); 82pList->list = NULL; 83pList->size = 0; 84pList->maxSize = 0; 85} 86} 87 } 88 89 90 /**************************************** 91Purpose :返回线性表数据长度 92Input:pList-- 线性表指针 93Return:线性表长度 94 *****************************************/ 95 int ListLength(PSqList pList) 96 { 97return pList->size; 98 } 99 100 101 /**************************************** 102Purpose :判断线性表是否为空 103Input:pList-- 线性表指针 104Return:1 -- 为空 1050 -- 不为空 106 *****************************************/ 107 int ListEmpty(PSqList pList) 108 { 109if(pList->size == 0) 110{ 111return 1; 112} 113else 114{ 115return 0; 116} 117 } 118 119 /**************************************** 120Purpose :返回线性表中第nPos个元素的值 121Input:pList-- 线性表指针 122nPos-- 元素的位置 [1,ListLength(L)] 123e-- 要返回的元素 124Return:0--OK 125-1--FAIL 126 *****************************************/ 127 int GetElem(PSqList pList, int nPos, ElemType* e) 128 { 129if(pList== NULL || pList->list == NULL) 130{ 131return -1; 132} 133if(nPos < 1|| nPos > pList->size) 134{ 135//越界 136return -1; 137} 138if(pList->list == NULL) 139{ 140return -1; 141} 142 143memcpy(e, &pList->list[nPos-1], sizeof(ElemType)); 144return 0; 145 } 146 147 /**************************************** 148Purpose :遍历输出线性表中每个元素 149Input:pList-- 线性表指针 150visit-- 遍历函数指针 151Return:0--OK 152-1--FAIL 153 *****************************************/ 154 int TraverseList(PSqList pList, Visit visit) 155 { 156int i; 157if(visit == NULL || pList==NULL || pList->list==NULL) 158{ 159return -1; 160} 161for(i=0; isize; i++) 162{ 163visit(&pList->list[i]); 164} 165return 0; 166 } 167 168 169 /**************************************** 170Purpose :向线性表中第nPos个位置插入元素data 171Input:pList-- 线性表指针 172nPos-- 元素的位置 [1, ListLength[L]+1] 173data-- 要插入的元素 174Return:0--OK 175-1--FAIL 176 *****************************************/ 177 int InsertList(PSqList pList, int nPos, ElemType* data) 178 { 179int i; 180if(pList== NULL || pList->list == NULL) 181{ 182return -1; 183} 184 185if(nPos < 1 || nPos > pList->size + 1) 186{ 187return -1; 188} 189if(pList->size == pList->maxSize) 190{ 191//重新分配更大空间 192if(againMalloc(pList)) 193{ 194return -1; 195} 196} 197 198for(i=pList->size - 1; i>=nPos - 1; i--) 199{ 200memcpy(&pList->list[i+1], &pList->list[i], sizeof(ElemType)); 201} 202memcpy(&pList->list[nPos-1], data, sizeof(ElemType)); 203pList->size++; 204return 0; 205 } 206 207 /**************************************** 208Purpose :从线性表中第nPos个位置删除元素并赋值给data 209Input:pList-- 线性表指针 210nPos-- 元素的位置[1, ListLength[L]] 211data-- 要赋值的元素 212Return:0--OK 213-1--FAIL 214 *****************************************/ 215 int DeleteList(PSqList pList, int nPos, ElemType* data) 216 { 217int i; 218if(pList->size == 0 || pList== NULL || pList->list == NULL) 219{ 220return -1; 221} 222if(nPos < 1 ||nPos > pList->size) 223{ 224return -1; 225} 226memcpy(data, &pList->list[nPos-1], sizeof(ElemType)); 227for(i=nPos; isize; i++) 228{ 229memcpy(&pList->list[i-1], &pList->list[i], sizeof(ElemType)); 230} 231pList->size--; 232return0; 233 } 234 235 /**************************************** 236Purpose :更新第nPos个位置元素 237Input:pList-- 线性表指针 238nPos-- 元素的位置[1, ListLength[L]] 239data-- 要更新的元素 240Return:0--OK 241-1--FAIL 242 *****************************************/ 243 int UpdateList(PSqList pList, int nPos, ElemType* val) 244 { 245if(nPos < 1 || nPos > pList->size) 246{ 247return -1; 248} 249if(pList== NULL || pList->list == NULL || val == NULL) 250{ 251return -1; 252} 253memcpy(&pList->list[nPos-1], val, sizeof(ElemType)); 254return 0; 255 } 256 257 /**************************************** 258Purpose :对线性表进行排序 259Input:pList-- 线性表指针 260compare-- 比较函数 261Return:0--OK 262-1--FAIL 263 *****************************************/ 264 int OrderList(PSqList pList, Compare compare) 265 { 266int i,j; 267ElemType tmp; 268if(compare == NULL || pList == NULL || pList->list ==NULL) 269{ 270return -1; 271} 272for(i=0; i【（1）数据结构——线性表（数组）实现】size; i++) 273{ 274for(j=i+1; jsize; j++) 275{ 276if(compare(&pList->list[i], &pList->list[j]) > 0) 277{ 278memcpy(&tmp, &pList->list[i],sizeof(ElemType)); 279memcpy(&pList->list[i], &pList->list[j], sizeof(ElemType)); 280memcpy(&pList->list[j],&tmp, sizeof(ElemType)); 281} 282} 283} 284return 0; 285 }

　testmain.c

1 #include 2 #include "SqList.h" 3 4 5 6 void visit(ElemType *val) 7 { 8printf("%d\n", *val); 9 } 10 11 12 int compare(ElemType* e1, ElemType* e2) 13 { 14return *e1 - *e2; 15 } 16 17 18 int main(int argc, char* argv[]) 19 { 20SqList L; 21int i,index; 22int nRet; 23 24 25nRet = InitList(&L, 5); 26for(i=0; i<5; i++) 27{ 28InsertList(&L,i+1,&i); 29} 30 31i= -1; 32nRet = InsertList(&L, ListLength(&L), &i); 33if(nRet) 34{ 35printf("插入线性表数据失败\n"); 36} 37i=100; 38nRet = InsertList(&L, 2, &i); 39if(nRet) 40{ 41printf("插入线性表数据失败\n"); 42} 43 44TraverseList(&L, (Visit)visit); 45 46printf("排序线性表\n"); 47OrderList(&L, compare); 48TraverseList(&L, (Visit)visit); 49 50 51 52nRet = DeleteList(&L, 2, &i); 53if(nRet) 54{ 55printf("删除线性表数据失败\n"); 56} 57printf("删除线性表数据为[%d]\n", i); 58TraverseList(&L, (Visit)visit); 59 60printf("更新线性表数据\n", i); 61i=555; 62nRet = UpdateList(&L, 2, &i); 63if(nRet) 64{ 65printf("更新线性表数据失败\n"); 66} 67 68TraverseList(&L, (Visit)visit); 69 70ClearList(&L); 71 72return 0; 73 }

　makefile
makefile为通用文件，后边除非特殊情况，否则都以本文件为编译文件

CC=gcc SRC_DIR=./TARGET = testmain vpath %.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)

转载于:https://www.cnblogs.com/dspeeding/p/3240579.html