锐客网

  1. 首页 > it技术 > >

线性表之顺序存储结构（C语言动态数组实现）

【线性表之顺序存储结构（C语言动态数组实现）】线性表的定义：N个数据元素的有限序列
线性表从存储结构上分为：顺序存储结构（数组）和 链式存储结构（链表）
顺序存储结构：是用一段连续的内存空间存储表中的数据 L=(a1,a2,a3....an)
线性表之顺序存储结构（C语言动态数组实现）
文章图片

链式存储结构：是用一段一段连续的内存空间存储表中每一行的数据，段与段之间通过一个引用（指针）相互连接来，形成一个链式的存储结构
线性表之顺序存储结构（C语言动态数组实现）
文章图片

看到顺序存储结构的图示，我们可能会马上联想到C语言的数组。是的，数组就是一种典型的顺序存储数据结构。下面我通过一个实例，来实现对顺序存储结构中的数据增、删、改、查的操作。
首先定一个描述线性表数据的顺序存储结构：

// 默认增长因子 #define DEFAULT_CAPACITY 10typedef unsigned int * PU32; typedef unsigned int U32; /************************************************************************/ /* 线性表数据结构，存储数组元素、数组大小、数组增长因子，下面简称为动态数组*/ /************************************************************************/ typedef struct _tag_ArrayList { PU32 container; // 存储数组元素的容器 int length; // 数组长度 int capacity; // 数组增长因子 } TArrayList;

container：是一个无符号32位的指针数组，用于存储线性表中的所有元素，后面的增、删、改查都是操作这个操作中指针元素
length：记录数组中的元数数量，表示这个线性表中存储了多少个数据元素
capacity：因为要实现数组动态扩容的功能，这个值代表数组满后，每次扩容的大小，默认为10

线性表初始化
ArrayList * ArrayList_CreateDefault() { return ArrayList_Create(DEFAULT_CAPACITY); }ArrayList * ArrayList_Create(int capacity) { if (capacity < 0) { printf("fun ArrayList_Create error, Illegal capacity: %d", capacity); return NULL; } TArrayList *list = (TArrayList *)malloc(sizeof(TArrayList)); if (list == NULL) { printf("out of memory, create ArrayList fail!"); return NULL; } list->capacity = capacity; list->length = 0; list->container = (PU32)malloc(sizeof(PU32)* DEFAULT_CAPACITY); if (list->container == NULL) { printf("out of memory, create Array container fail!"); return NULL; } memset(list->container, 0, sizeof(PU32)* DEFAULT_CAPACITY); return list; }

ArrayList_CreateDefault：初始化默认10个元素大小的线性表存储空间
ArrayList_Create：根据capacity大小初始化
其中ArrayList是通过typedef void定义的一个类型，因为想屏蔽内部实现线性表的数据存储结构，使用者无须关注里面的实现细节，只需保存这个线性表句柄的引用，当每次操作线性表时，都将这个句柄作为形参传给相应的函数即可。

往线性表中指定位置添加元素
int ArrayList_AddItem(ArrayList *list, ArrayItem *item, int pos) { int ret = 0; TArrayList *arrayList = NULL; if (list == NULL || item == NULL) { ret = -1; printf("fun ArrayList_AddItem error:%d of the list is NULL or item is NULL\n", ret); return ret; } arrayList = (TArrayList *)list; // 容错处理，如果当前存储了3个元素，要在第5个位置插入一个元素，将插入位置改成第4个位置 // |0|1|2|3| | | if (pos > arrayList->length) { pos = arrayList->length; } // 扩容 PU32 newContainer = NULL; if (arrayList->length > 0 && arrayList->length % arrayList->capacity == 0) { newContainer = (PU32)malloc(sizeof(PU32)* (arrayList->length + arrayList->capacity)); if (newContainer == NULL) { ret = -2; printf("out of memory, add item fail!"); return ret; } memset(newContainer, 0, arrayList->length * sizeof(PU32)); // 将旧的数据拷贝到新的容器中 memcpy(newContainer, arrayList->container, arrayList->length * sizeof(PU32)); // 释放旧容器的内存 free(arrayList->container); // 指向新容器的地址 arrayList->container = newContainer; } // 将元素插入到数组pos位置 for (int i = arrayList->length; i > pos; i--) { arrayList->container[i] = arrayList->container[i - 1]; } arrayList->container[pos] = (U32)item; arrayList->length++; return ret; }

1、添加前，首先判断再添加一个元素后，数组是否会满，如果会满就先扩容
arrayList->length > 0 && arrayList->length % arrayList->capacity == 0
2、将元素插入到数组中指定的位置。如果当前数组中有5个元素，新元素要插入到数组的第3个位置，所以第3个位置和后面的元素都要往后移
for (int i = arrayList->length; i > pos; i--)
{
arrayList->container[i] = arrayList->container[i - 1];
}
arrayList->container[pos] = (U32)item;
arrayList->length++; // 长度+1

线性表之顺序存储结构（C语言动态数组实现）
文章图片



删除线性表中指定位置的元素（与添加相反）
ArrayItem * ArrayList_RemoveItem(ArrayList *list, int pos) { TArrayList *arrayList = NULL; ArrayItem *arrayItem = NULL; arrayList = checkRange(list, pos); if (arrayList == NULL) { return NULL; } // 缓存删除的元素 arrayItem = (ArrayItem *)arrayList->container[pos]; // 从数组中移徐指定索引的元素 for (int i = pos; i < arrayList->length; i++) { arrayList->container[i] = arrayList->container[i + 1]; } arrayList->length--; // 长度减1 return arrayItem; // 返回被删除的元素 }

删除前首先保存要删除的元素，删除成功返回将该元素返回
还有其它操作（在表尾添加元素、获取、遍历、清除、销毁等），这里不一一讲解了，源代码中有详细的注释，下面给出完整的源代码与测试用例：

// //ArrayList.h //线性表存储--动态数组 // //Created by 杨信 on 14-5-15. //Copyright (c) 2014年 yangxin. All rights reserved. //#ifndef __ArrayList_H__ #define __ArrayList_H__#ifdef _cplusplus extern "C" { #endif typedef void ArrayList; // 线性表句柄 typedef void ArrayItem; // 线性表的条目 /* 遍历数组的回调函数 @item : 当前元素 @pos: 当前元素的索引 */ typedef void(*_Each_Function)(ArrayItem *item, int pos); /* 创建一个默认capacity大小的动态数组 capacity默认为10 @return 动态数组句柄 */ ArrayList * ArrayList_CreateDefault(); /* 创建一个初始化容量为capacity大小的动态数组 @capacity : 数组大小增长因子，如果数组已满，则自动增长capacity大小 @return 动态数组句柄 */ ArrayList * ArrayList_Create(int capacity); /* 在指定位置添加(插入)一个元素 @list : 动态数组句柄 @item : 新添加的数组元素 @pos: 插入位置（索引从0开始） @return 插入成功返回0，失败返回非0值 */ int ArrayList_AddItem(ArrayList *list, ArrayItem *item, int pos); /* 在数组某尾添加一个元素 @list : 动态数组句柄 @item : 新添加的数组元素 @return 插入成功返回0，失败返回非0值 */ int ArrayList_AddItemBack(ArrayList *list, ArrayItem *item); /* 删除一个数组元素 @list : 动态数组句柄 @pos: 插入位置（索引从0开始） @return 删除成功返回被删除的元素，失败返回NULL */ ArrayItem * ArrayList_RemoveItem(ArrayList *list, int pos); /* 清空数组所有元素 @list : 动态数组句柄 @return 成功返回0，失败返回非0值 */ int ArrayList_Clear(ArrayList *list); /* 修改数组元素 @list : 动态数组句柄 @item : 新元素 @pos: 修改元素的索引 @return 修改成功返回0，失败返回非0值 */ int ArrayList_SetItem(ArrayList *list, ArrayItem *item, int pos); /* 获取数组指定位置的元素 @list : 动态数组句柄 @pos: 元素索引 @return 返回数组指定位置的元素，如果pos大于等于数组长度或小于0，则返回NULL */ ArrayItem * ArrayList_GetItem(ArrayList *list, int pos); /* 遍历数组 @list : 动态数组句柄 @_fun_callback ： 遍历数组中每个元素时的回调函数 函数原型：void(*_Each_Function)(ArrayItem *item, int pos); 示例：void ArrayEachCallback(ArrayItem *item, int pos) { ... } */ void ArrayList_For_Each(ArrayList *list, _Each_Function _fun_callback); /* 遍历数组指定范围内的元素 @list : 动态数组句柄 @begin : 元素开始位置 @end : 元素结束位置 @_fun_callback : 遍历数组中每个元素时的回调函数 函数原型：void(*_Each_Function)(ArrayItem *item, int pos); 示例：void ArrayEachCallback(ArrayItem *item, int pos) { ... } */ void ArrayList_For_Each_Range(ArrayList *list, int begin, int end, _Each_Function _fun_callback); /* 获取动态数组的长度（存储的元素数量） @list : 动态数组句柄 @return 数组长度 */ int ArrayList_GetLength(ArrayList * list); /* 获取动态数组的增长因子 @list : 动态数组句柄 @return 数组增长因子 */ int ArrayList_GetCapacity(ArrayList * list); /* 销毁动态数组（释放内存） @list ： 动态数组句柄 @return 销毁成功返回0，失败返回非0值 */ int ArrayList_Destory(ArrayList **list); #ifdef _cplusplus } #endif #endif// //ArrayList.c //线性表存储--动态数组 // //Created by 杨信 on 14-5-15. //Copyright (c) 2014年 yangxin. All rights reserved. //#include #include #include #include "ArrayList.h"// 默认增长因子 #define DEFAULT_CAPACITY 10typedef unsigned int * PU32; typedef unsigned int U32; /************************************************************************/ /* 线性表数据结构，存储数组元素、数组大小、数组增长因子，下面简称为动态数组*/ /************************************************************************/ typedef struct _tag_ArrayList { PU32 container; // 存储数组元素的容器 int length; // 数组长度 int capacity; // 数组增长因子 } TArrayList; // 检查索引范围 static TArrayList * checkRange(ArrayList *list, int pos); ArrayList * ArrayList_CreateDefault() { return ArrayList_Create(DEFAULT_CAPACITY); }ArrayList * ArrayList_Create(int capacity) { if (capacity < 0) { printf("fun ArrayList_Create error, Illegal capacity: %d", capacity); return NULL; } TArrayList *list = (TArrayList *)malloc(sizeof(TArrayList)); if (list == NULL) { printf("out of memory, create ArrayList fail!"); return NULL; } list->capacity = capacity; list->length = 0; list->container = (PU32)malloc(sizeof(PU32)* DEFAULT_CAPACITY); if (list->container == NULL) { printf("out of memory, create Array container fail!"); return NULL; } memset(list->container, 0, sizeof(PU32)* DEFAULT_CAPACITY); return list; }int ArrayList_AddItem(ArrayList *list, ArrayItem *item, int pos) { int ret = 0; TArrayList *arrayList = NULL; if (list == NULL || item == NULL) { ret = -1; printf("fun ArrayList_AddItem error:%d of the list is NULL or item is NULL\n", ret); return ret; } arrayList = (TArrayList *)list; // 容错处理，如果当前存储了3个元素，要在第5个位置插入一个元素，将插入位置改成第4个位置 // |0|1|2|3| | | if (pos > arrayList->length) { pos = arrayList->length; } // 扩容 PU32 newContainer = NULL; if (arrayList->length > 0 && arrayList->length % arrayList->capacity == 0) { newContainer = (PU32)malloc(sizeof(PU32)* (arrayList->length + arrayList->capacity)); if (newContainer == NULL) { ret = -2; printf("out of memory, add item fail!"); return ret; } memset(newContainer, 0, arrayList->length * sizeof(PU32)); // 将旧的数据拷贝到新的容器中 memcpy(newContainer, arrayList->container, arrayList->length * sizeof(PU32)); // 释放旧容器的内存 free(arrayList->container); // 指向新容器的地址 arrayList->container = newContainer; } // 将元素插入到数组pos位置 for (int i = arrayList->length; i > pos; i--) { arrayList->container[i] = arrayList->container[i - 1]; } arrayList->container[pos] = (U32)item; arrayList->length++; // 长度+1 return ret; }int ArrayList_AddItemBack(ArrayList *list, ArrayItem *item) { int ret = 0; TArrayList *arrayList = NULL; if (list == NULL || item == NULL) { ret = -1; printf("fun ArrayList_AddItemBack error:%d, of the list or item is NULL.\n"); return ret; } arrayList = (TArrayList *)list; return ArrayList_AddItem(list, item, arrayList->length); }ArrayItem * ArrayList_RemoveItem(ArrayList *list, int pos) { TArrayList *arrayList = NULL; ArrayItem *arrayItem = NULL; arrayList = checkRange(list, pos); if (arrayList == NULL) { return NULL; } // 缓存删除的元素 arrayItem = (ArrayItem *)arrayList->container[pos]; // 从数组中移徐指定索引的元素 for (int i = pos; i < arrayList->length; i++) { arrayList->container[i] = arrayList->container[i + 1]; } arrayList->length--; // 长度减1 return arrayItem; // 返回被删除的元素 }int ArrayList_Clear(ArrayList *list) { int ret = 0; TArrayList *arrayList = NULL; if (list == NULL) { ret = -1; printf("fun ArrayList_Clear error:%d, of the list is NULL.\n"); return ret; } arrayList = (TArrayList *)list; while (arrayList->length) { arrayList->container[--arrayList->length] = 0; } return 0; }int ArrayList_SetItem(ArrayList *list, ArrayItem *item, int pos) { int ret = 0; TArrayList *arrayList = NULL; arrayList = checkRange(list, pos); if (arrayList == NULL || item == NULL) { ret = -1; printf("fun ArrayList_SetItem error:%d, of the list or item is NULL.\n",ret); return ret; } arrayList->container[pos] = (U32)item; return 0; }ArrayItem * ArrayList_GetItem(ArrayList *list, int pos) { TArrayList *arrayList = NULL; arrayList = checkRange(list, pos); if (arrayList == NULL) { return NULL; } return (ArrayItem *)arrayList->container[pos]; }void ArrayList_For_Each(ArrayList *list, _Each_Function _fun_callback) { TArrayList *arrayList = NULL; if (list == NULL || _fun_callback == NULL) { printf("fun ArrayList_For_Each error, list or _fun_callback is NULL.\n"); return; } arrayList = (TArrayList *)list; for (int i = 0; i < arrayList->length; i++) { _fun_callback((ArrayItem *)arrayList->container[i], i); } }; void ArrayList_For_Each_Range(ArrayList *list, int begin, int end, _Each_Function _fun_callback) { TArrayList *arrayList = NULL; if (list == NULL || _fun_callback == NULL) { printf("fun ArrayList_For_Each_Range error, list or _fun_callback is NULL.\n"); return; } arrayList = (TArrayList *)list; if ((begin < 0 || begin > end) || (end >= arrayList->length || end < begin)) { printf("fun ArrayList_For_Each_Range error, pos out range:%d-%d", begin, end); return; } for (int i = begin; i < end; i++) { _fun_callback((ArrayItem *)arrayList->container[i], i); } }; int ArrayList_GetLength(ArrayList * list) { TArrayList *arrayList = NULL; if (list == NULL) { printf("fun ArrayList_GetLength error, list is NULL.\n"); return -1; } arrayList = (TArrayList *)list; return arrayList->length; }int ArrayList_GetCapacity(ArrayList * list) { TArrayList *arrayList = NULL; if (list == NULL) { printf("fun ArrayList_GetCapacity error, list is NULL.\n"); return -1; } arrayList = (TArrayList *)list; return arrayList->capacity; }int ArrayList_Destory(ArrayList **list) { int ret = 0; if (list == NULL) { ret = -1; printf("fun ArrayList_Destory error:%d from (list == NULL)\n", ret); return ret; } TArrayList *arrayList = (TArrayList *)*list; if (arrayList->container != NULL) { free(arrayList->container); arrayList->container = NULL; } free(arrayList); *list = NULL; return ret; }static TArrayList * checkRange(ArrayList *list, int pos) { TArrayList *arrayList = NULL; if (list == NULL) { printf("fun checkRange error, of the list is NULL.\n"); return NULL; } arrayList = (TArrayList *)list; if (pos < 0 || pos >= arrayList->length) { printf("fun checkRange error, of the pos:%d out range.\n", pos); return NULL; } return arrayList; }//-------------------------测试用例--------------------------------// #include #include #include "ArrayList.h"typedef struct Person { int age; char name[20]; }Person; void EachArrayCallback(ArrayItem *item, int pos) { Person *p = (Person *)item; printf("%d-->age=%d\n",pos,p->age); }void main1() { int ret = -65535; ArrayList *list = NULL; list = ArrayList_Create(2); Person p1, p2, p3, p4, p5,p6,p7,p8; p1.age = 10; p2.age = 20; p3.age = 30; p4.age = 40; p5.age = 50; p6.age = 60; p7.age = 70; p8.age = 80; //ArrayList_AddItem(list, 100, 7); ArrayList_AddItem(list, &p1, 0); ArrayList_AddItem(list, &p2, 0); ArrayList_AddItem(list, &p3, 0); ArrayList_AddItem(list, &p4, 0); ArrayList_AddItem(list, &p5, 0); ArrayList_AddItem(list, &p6, 0); ArrayList_AddItemBack(list, &p7); ArrayList_AddItemBack(list, &p8); printf("数组长度：%d\n", ArrayList_GetLength(list)); ArrayItem *item = ArrayList_RemoveItem(list, 2); printf("删除索引2位置的元素：%d\n",((Person *)item)->age); for (int i = 0; i < ArrayList_GetLength(list); i++) { Person *p = (Person *)ArrayList_GetItem(list, i); printf("age=%d\n", p->age); } Person pp = {100,"zhangsan"}; ArrayList_SetItem(list, &pp, 1); // 修改索引位置为1的元素 Person *p = (Person *)ArrayList_GetItem(list,1); if (p != NULL) { printf("age=%d\n",p->age); } printf("\n---------------------foreach回调函数遍历数组------------------\n"); ArrayList_For_Each(list, EachArrayCallback); // 遍历指定范围内的元素 printf("\n---------------foreach遍历指定范围内的数组元素------------------\n"); ArrayList_For_Each_Range(list, 2, 5, EachArrayCallback); // 清徐数组所有元素 ret = ArrayList_Clear(list); printf("arraylist length: %d\n", ArrayList_GetLength(list)); ret = ArrayList_Destory(&list); system("pause"); }void fun(ArrayItem *item, int pos) { printf("%d--%d\n",pos,(unsigned int)item); }void main() { ArrayList *list = NULL; list = ArrayList_Create(5); ArrayList_AddItem(list, (ArrayItem *)10, 0); ArrayList_AddItem(list, (ArrayItem *)20, 0); ArrayList_AddItem(list, (ArrayItem *)30, 0); ArrayList_AddItem(list, (ArrayItem *)40, 0); ArrayList_AddItem(list, (ArrayItem *)50, 0); ArrayList_AddItemBack(list, (ArrayItem *)60); printf("delete-->%d\n",(unsigned int)ArrayList_RemoveItem(list, 0)); ArrayList_For_Each(list, fun); ArrayList_Destory(&list); system("pause"); }

转载于:https://www.cnblogs.com/xyang0917/p/4172502.html

    推荐阅读


    上一篇：Java学习笔记18---final关键字修饰变量、方法及类

    下一篇：JavaScript+CSS实现经典的树形导航栏