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

yangxin0917

``````// 默认增长因子
#define DEFAULT_CAPACITY 10

typedef 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大小初始化

## 往线性表中指定位置添加元素

``````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

## 删除线性表中指定位置的元素（与添加相反）

``````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.
//

#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.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ArrayList.h"

// 默认增长因子
#define DEFAULT_CAPACITY 10

typedef 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 <stdio.h>
#include <stdlib.h>
#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;

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);

printf("delete-->%d\n",(unsigned int)ArrayList_RemoveItem(list, 0));

ArrayList_For_Each(list, fun);

ArrayList_Destory(&list);

system("pause");
}``````

### yangxin0917

2014/05/04
98
0

2018/01/06
0
0
《数据结构》笔记三：线性表之顺序存储结构

06/28
0
0

cjun1990
2015/09/24
86
0

Mr.Right-w
07/15
0
0

Less导入选项

Less 提供了CSS @import CSS规则的几个扩展，以提供更多的灵活性来处理外部文件。 语法： @import (keyword) "filename"; 以下是导入指令的相关详情： reference，使用较少的文件但不输出。 ...

4分钟前
2
0
Docker下实现MySQL主从(读、写分离)同步配置

docker下实现两个(或多个)mysql容器的主、从数据库同步配置，首先要明白docker容器的相互通信关系，默认是使用的bridge模式： 也就是说，通过docker run命令创建docker容器是每个容器都有自己...

14分钟前
7
0

33分钟前
15
0

56分钟前
22
0

30
0