一个能够自动扩容的顺序表 ArrList (GCC编译)。
1 #include2 #include 3 #include 4 5 #define TRUE 1 6 #define FALSE 0 7 8 typedef struct 9 { 10 int x; 11 int y; 12 }Point2D; // Point2D 结构 13 14 typedef struct 15 { 16 Point2D *pt; //线性表的数据项 17 int length; //线性表当前长度 18 int size; //线性表总容量 19 }ArrList; // ArrList 结构 20 21 22 //声明线性表所具有的方法 23 ArrList *CreateArrList( int nLength ); //创建长为 nArrLength 的线性表 24 void DestroyArrList( ArrList *pArrList ); //销毁线性表 pArrList 25 void ClearArrList( ArrList *pArrList ); //置空线性表 pArrList 26 int IsEmptyArrList( ArrList *pArrList ); //检测线性表是否为空 27 int GetArrListLength( ArrList *pArrList ); //获取线性表长度 28 int GetArrListSize( ArrList *pArrList ); //获取线性表总容量 29 int GetArrListElement( ArrList *pArrList, int n, Point2D *pt ); //获取线性表中第n个元素 30 int FindElement( ArrList *pArrList, int nPos, Point2D *pt ); //从 nPos 起查找 pt 第一次出现的位置 31 int GetPriorElement( ArrList *pArrList, Point2D *pt, Point2D *prior_pt ); //获取 pt 的前驱节点到 prior_pt 32 int GetNextElement( ArrList *pArrList, Point2D *pt, Point2D *next_pt ); //获取 pt 的后继节点到 next_pt 33 int AppendToArrList( ArrList *pArrList, Point2D *pt ); //将 pt 添加到线性表末尾处 34 int InsertToArrList( ArrList *pArrList, int nPos, Point2D *pt ); //将 pt 插入到 nPos 处 35 int DeleteFromArrList( ArrList *pArrList, int nPos ); //删除线性表上位置为 nPos 的元素 36 void ForEachArrList( ArrList *pArrList, void (*func)(Point2D *pt) ); //对线性表中每个元素执行 func 函数 37 int ArrListCpy( ArrList *pArrListDest, ArrList *pArrListSrc ); //将线性表 pArrListSrc 复制到 pArrListDest 38 int ArrListCat( ArrList *pArrListDest, ArrList *pArrListSrc ); //将线性表 pArrListSrc 连接到 pArrListDest 的末尾 39 40 41 //线性表方法实现 42 /** 43 * @brief 创建长度为 nLength 的线性表 ArrList 44 * 45 * @param nLength 所要构建的线性表长度 46 * 47 * @return 指向所创建的线性表的指针 48 */ 49 ArrList *CreateArrList( int nLength ) 50 { 51 ArrList *pl = (ArrList *)malloc( sizeof(ArrList) ); 52 53 pl->pt = (Point2D *)calloc( nLength, sizeof(Point2D) ); 54 pl->length = 0; 55 pl->size = nLength; 56 57 return pl; 58 } 59 60 /** 61 * @brief 销毁一条线性表 62 * 63 * @param pArrList 指向待销毁线性表的指针 64 * 65 * @return void 66 */ 67 void DestroyArrList( ArrList *pArrList ) 68 { 69 free( pArrList->pt ); ///先释放线性表pt 70 free( pArrList ); ///销毁线性表pArrList 71 } 72 73 /** 74 * @brief 置空一条线性表 75 * 76 * @param pArrList 指向待置空线性表的指针 77 * 78 * @return void 79 */ 80 void ClearArrList( ArrList *pArrList ) 81 { 82 pArrList->length = 0; 83 } 84 85 /** 86 * @brief 检测线性表是否为空 87 * 88 * @param pArrList 指向待检测线性表的指针 89 * 90 * @return 为空则返回 TRUE, 否则返回 FALSE 91 */ 92 int IsEmptyArrList( ArrList *pArrList ) 93 { 94 return pArrList->length == 0 ? TRUE : FALSE; 95 } 96 97 /** 98 * @brief 获取线性表长度 99 *100 * @param pArrList 指向待获取长度的线性表的指针101 *102 * @return 返回获取到的线性表长度103 */104 int GetArrListLength( ArrList *pArrList )105 {106 return pArrList->length;107 }108 109 /**110 * @brief 获取线性表总容量111 *112 * @param pArrList 指向待获取容量的线性表的指针113 *114 * @return 返回获取到的线性表的总容量115 */116 int GetArrListSize( ArrList *pArrList )117 {118 return pArrList->size;119 }120 121 /**122 * @brief 获取线性表中第 n 个元素123 *124 * @param pArrList 指向待获取其中的元素的线性表的指针125 * @param n 要获取的第 n 个元素126 * @param pt 用于存放获取到的元素的值的 Point2D 类型指针127 *128 * @return 获取成功返回 TRUE, 否则返回 FALSE129 *130 * @note 元素n, n 从 0 起131 */132 int GetArrListElement( ArrList *pArrList, int n, Point2D *pt )133 {134 if( n < 0 || n > pArrList->length-1 )135 return FALSE;136 137 pt->x = pArrList->pt[n].x;138 pt->y = pArrList->pt[n].y;139 140 return TRUE;141 }142 143 /**144 * @brief 从 nPos 处查找元素 pt 第一次出现的位置145 *146 * @param pArrList 指向待查找其中的元素的线性表的指针147 * @param nPos 查找起始位置148 * @param pt 指向待查找元素的指针149 *150 * @return 若找到, 返回元素 pt 在线性表中的位置(下标), 否则返回 -1151 *152 * @note 位置从 0 计起153 */154 int FindElement( ArrList *pArrList, int nPos, Point2D *pt )155 {156 int n = nPos;157 for( n; n < pArrList->length; ++n )158 {159 if( (pArrList->pt[n].x == pt->x) && (pArrList->pt[n].y == pt->y) )160 return n;161 }162 163 return -1;164 }165 166 /**167 * @brief 获取线性表中 pt 元素的前驱节点到 prior_pt168 *169 * @param pArrList 指向待获取其中的元素的线性表的指针170 * @param pt 指向目标节点的指针171 * @param prior_pt 存放查找到的目标节点的前驱节点172 *173 * @return 若获取到前驱节点, 返回目标节点的前驱节点在线性表中的位置(下标), 否则返回 -1174 *175 * @note 位置从 0 计起176 */177 int GetPriorElement( ArrList *pArrList, Point2D *pt, Point2D *prior_pt )178 {179 int n = 0;180 for( n = 0; n < pArrList->length; ++n )181 {182 if( (pArrList->pt[n].x == pt->x) && (pArrList->pt[n].y == pt->y) )183 {184 if( n <= 0 ) ///目标节点是头节点, 无前驱节点185 return -1;186 else ///存在并找到前驱节点187 {188 prior_pt->x = pArrList->pt[n-1].x;189 prior_pt->y = pArrList->pt[n-1].y;190 191 return n-1;192 }193 }194 }195 196 return -1;197 }198 199 /**200 * @brief 获取线性表中 pt 元素的后继节点到 next_pt201 *202 * @param pArrList 指向待获取其中的元素的线性表的指针203 * @param pt 指向目标节点的指针204 * @param next_pt 存放查找到的目标节点的后继节点205 *206 * @return 若获取到后继节点, 返回目标节点的后继节点在线性表中的位置(下标), 否则返回 -1207 *208 * @note 位置从 0 计起209 */210 int GetNextElement( ArrList *pArrList, Point2D *pt, Point2D *next_pt )211 {212 int n = 0;213 for( n = 0; n < pArrList->length; ++n )214 {215 if( (pArrList->pt[n].x == pt->x) && (pArrList->pt[n].y == pt->y) )216 {217 if( n >= pArrList->length-1 ) ///目标节点是尾节点, 无后继节点218 return -1;219 else ///存在并找到后继节点220 {221 next_pt->x = pArrList->pt[n+1].x;222 next_pt->y = pArrList->pt[n+1].y;223 224 return n+1;225 }226 }227 }228 229 return -1;230 }231 232 /**233 * @brief 添加一个元素至线性表末尾234 *235 * @param pArrList 指向待添加元素的线性表的指针236 * @param pt 指向待添加的元素的指针237 *238 * @return 成功添加则返回当前线性表长度, 否则返回 -1239 */240 int AppendToArrList( ArrList *pArrList, Point2D *pt )241 {242 if( pArrList->size - pArrList->length < 1 ) ///检测是否需要扩容243 {244 Point2D *p = (Point2D *)calloc(pArrList->length * 2, sizeof(Point2D));245 memcpy( p, pArrList->pt, pArrList->length*sizeof(Point2D) );246 pArrList->size = pArrList->length * 2;247 free( pArrList->pt );248 pArrList->pt = p;249 }250 251 pArrList->pt[pArrList->length].x = pt->x;252 pArrList->pt[pArrList->length].y = pt->y;253 254 return ++pArrList->length;255 }256 257 /**258 * @brief 插入一个元素 pt 到线性表 nPos 处259 *260 * @param pArrList 指向待插入元素的线性表指针261 * @param nPos 插入的位置(下标)262 * @param pt 指向待插入的元素的指针263 *264 * @return 插入成功则返回当前线性表长度, 否则返回 -1265 *266 * @note 插入位置 nPos 从 0 计起267 */268 int InsertToArrList( ArrList *pArrList, int nPos, Point2D *pt )269 {270 if( (nPos < 0) || (nPos > pArrList->length-1) )271 return -1;272 273 if( pArrList->size - pArrList->length < 1 ) ///检测是否需要扩容274 {275 Point2D *p = (Point2D *)calloc(pArrList->length*2, sizeof(Point2D));276 memcpy( p, pArrList->pt, pArrList->length * sizeof(Point2D) );277 pArrList->size = pArrList->length * 2;278 free( pArrList->pt );279 pArrList->pt = p;280 }281 282 int nMax = pArrList->length; ///获取线性表插入1元素后的长度283 for( nMax; nMax > nPos; --nMax )284 {285 pArrList->pt[nMax].x = pArrList->pt[nMax-1].x;286 pArrList->pt[nMax].y = pArrList->pt[nMax-1].y;287 }288 pArrList->pt[nPos].x = pt->x;289 pArrList->pt[nPos].y = pt->y;290 291 return ++pArrList->length;292 }293 294 /**295 * @brief 从线性表上删除一个元素296 *297 * @param pArrList 指向待处理线性表的指针298 * @param nPos 需要删除的元素位置(下标)299 *300 * @return 成功删除返回删除后线性表长度, 否则返回 -1301 *302 * @note 删除位置 nPos 从 0 计起303 */304 int DeleteFromArrList( ArrList *pArrList, int nPos )305 {306 if( (nPos < 0) || (nPos > pArrList->length - 1) )307 return -1;308 309 if( nPos == pArrList->length - 1 )310 return --pArrList->length;311 312 for( nPos; nPos < pArrList->length; ++nPos )313 {314 pArrList->pt[nPos].x = pArrList->pt[nPos+1].x;315 pArrList->pt[nPos].y = pArrList->pt[nPos+1].y;316 }317 318 return --pArrList->length;319 }320 321 /**322 * @brief 对线性表中的元素依次执行传入的函数323 *324 * @param pArrList 指向待处理的线性表的指针325 * @param func 传入的函数指针326 *327 * @return void328 *329 * @note 传入的函数的参数为线性表元素类型的指针330 */331 void ForEachArrList( ArrList *pArrList, void (*func)(Point2D *pt) )332 {333 int i = 0;334 for( i = 0; i < pArrList->length; ++i )335 {336 func( &pArrList->pt[i] );337 }338 }339 340 /**341 * @brief 将线性表 pArrListSrc 复制到目标线性表 pArrListDest342 *343 * @param pArrListDest 目标线性表344 * @param pArrListSrc 源线性表345 *346 * @return 成功则返回复制后的目标线性表的长度, 否则返回 -1347 */348 int ArrListCpy( ArrList *pArrListDest, ArrList *pArrListSrc )349 {350 if( pArrListDest->size - pArrListSrc->length < 0 ) ///目标线性表是否需要扩容351 {352 free(pArrListDest->pt);353 Point2D *p = (Point2D *)calloc(pArrListSrc->length, sizeof(Point2D));354 pArrListDest->pt = p;355 pArrListDest->size = pArrListSrc->length;356 }357 358 memcpy( pArrListDest->pt, pArrListSrc->pt, pArrListSrc->length * sizeof(Point2D) );359 pArrListDest->length = pArrListSrc->length;360 361 return pArrListDest->length;362 }363 364 /**365 * @brief 将线性表 pArrListSrc 连接到目标线性表 pArrListDest366 *367 * @param pArrListDest 目标线性表368 * @param pArrListSrc 源线性表369 *370 * @return 成功则返回连接后的目标线性表的长度, 否则返回 -1371 */372 int ArrListCat( ArrList *pArrListDest, ArrList *pArrListSrc )373 {374 if( pArrListDest->size - pArrListDest->length < pArrListSrc->length ) ///目标线性表是否需要扩容375 {376 Point2D *p = (Point2D *)calloc(pArrListDest->length + pArrListSrc->length, sizeof(Point2D));377 memcpy( p, pArrListDest->pt, pArrListDest->length * sizeof(Point2D) );378 free(pArrListDest->pt);379 pArrListDest->pt = p;380 pArrListDest->size = pArrListDest->length + pArrListSrc->length;381 }382 383 int pos = 0;384 for(pos; pos < pArrListSrc->length; ++pos )385 {386 pArrListDest->pt[pArrListDest->length + pos].x = pArrListSrc->pt[pos].x;387 pArrListDest->pt[pArrListDest->length + pos].y = pArrListSrc->pt[pos].y;388 }389 390 pArrListDest->length += pArrListSrc->length;391 392 return pArrListDest->length;393 }394 395 //测试线性表 ArrList396 397 //回调函数398 void display( Point2D *pt )399 {400 printf( "(%d,%d) ", pt->x, pt->y );401 }402 403 int main()404 {405 Point2D pt1, pt2;406 ArrList *plstA = CreateArrList( 10 ); //创建一个长度为 10 的线性表 plstA407 408 ///409 printf("测试添加元素..\n");410 int i = 0;411 for( i; i < 10; ++i )412 {413 pt1.x = i; pt1.y = i;414 AppendToArrList( plstA, &pt1 ); //测试添加415 }416 ForEachArrList( plstA, display ); //对每个元素执行 display417 printf( "\nplstA len = %d, size = %d\n", GetArrListLength(plstA), GetArrListSize(plstA) );418 419 ///420 printf("\n测试被动扩容添加..\n");421 for( i = 10; i < 35; ++i )422 {423 pt1.x = i; pt1.y = i;424 AppendToArrList( plstA, &pt1 ); //测试被动扩容425 }426 ForEachArrList( plstA, display );427 printf( "\nplstA len = %d, size = %d\n", GetArrListLength(plstA), GetArrListSize(plstA) );428 429 ///430 printf("\n测试插入到头部、尾部..\n");431 pt1.x = 100; pt1.y = 100;432 InsertToArrList( plstA, 0, &pt1 ); //测试插入到首部433 InsertToArrList( plstA, GetArrListLength(plstA)-1, &pt1 ); //测试插入到尾部434 ForEachArrList( plstA, display );435 printf( "\nplstA len = %d, size = %d\n", GetArrListLength(plstA), GetArrListSize(plstA) );436 437 ///438 printf("\n测试获取节点元素..\n");439 GetArrListElement( plstA, 5, &pt2 ); //获取节点位置为5的元素440 printf("节点坐标为5的元素pt2: (%d,%d)\n", pt2.x, pt2.y);441 442 ///443 printf("\n测试获取某元素的前驱节点..\n");444 Point2D pri_pt, next_pt;445 GetPriorElement( plstA, &pt2, &pri_pt ); //获取 pt2 的前驱节点446 printf("pt2的前驱节点: (%d, %d)\n", pri_pt.x, pri_pt.y);447 GetNextElement( plstA, &pt2, &next_pt ); //获取 pt2 的后继节点448 printf("pt2的后继节点: (%d, %d)\n", next_pt.x, next_pt.y);449 450 ///451 printf("\n测试查找元素..\n");452 printf("元素 next_pt 在线性表中第一次出现的位置: %d\n", FindElement(plstA, 0, &next_pt)); //从 0 起查找元素 next_pt453 454 ///455 printf("\n测试删除某元素..\n");456 printf("删除位置为0的元素: ");457 DeleteFromArrList( plstA, 0 ); //删除节点位置为0的元素458 ForEachArrList( plstA, display );459 printf( "\nplstA len = %d, size = %d\n", GetArrListLength(plstA), GetArrListSize(plstA) );460 461 ///462 printf("\n测试复制线性表..\n");463 printf("创建线性表 plstB : ");464 ArrList *plstB = CreateArrList( 50 );465 for( i = 50; i < 60; ++i )466 {467 pt2.x = i; pt2.y = i;468 AppendToArrList( plstB, &pt2 );469 }470 ForEachArrList( plstB, display );471 printf( "\nplstB len = %d, size = %d\n", GetArrListLength(plstB), GetArrListSize(plstB) );472 printf("将 plstB 复制到 plstA: \n");473 ArrListCpy( plstA, plstB ); //将线性表 plstB 复制到 plstA474 ForEachArrList( plstA, display );475 printf( "plstA len = %d, size = %d\n", GetArrListLength(plstA), GetArrListSize(plstA) );476 477 ///478 printf("\n测试连接线性表..\n");479 printf("将 plstB 连接到 plstA: ");480 ArrListCat( plstA, plstB ); //将线性表 plstB 连接到 plstA481 ForEachArrList( plstA, display );482 printf( "\nplstA len = %d, size = %d\n", GetArrListLength(plstA), GetArrListSize(plstA) );483 484 ///485 printf("\n测试清空线性表..\n");486 ClearArrList( plstA ); //清空线性表 plstA487 ForEachArrList( plstA, display );488 printf( "plstA len = %d, size = %d\n", GetArrListLength(plstA), GetArrListSize(plstA) );489 printf( "IsEmpty = %d\n", IsEmptyArrList(plstA) );490 491 ///492 printf("\n销毁线性表..\n");493 DestroyArrList( plstA ); //销毁线性表, 释放资源494 DestroyArrList( plstB );495 496 return 0;497 }
若存在 bug 或程序缺陷, 请留言反馈, 谢谢。