线性表的定义：N个数据元素的有限序列

线性表从存储结构上分为：顺序存储结构（数组）和 链式存储结构（链表）

顺序存储结构：是用一段连续的内存空间存储表中的数据 L=(a1,a2,a3....an)

链式存储结构：是用一段一段连续的内存空间存储表中每一行的数据，段与段之间通过一个引用（指针）相互连接来，形成一个链式的存储结构

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

首先定一个描述线性表数据的顺序存储结构：

// 默认增长因子

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

其中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

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

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

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

}