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

阳光穿透心脏的1/2处 2022-08-27 05:58 155阅读 0赞

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

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

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

![Center][]

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

![Center 1][]

看到顺序存储结构的图示，我们可能会马上联想到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

![SouthEast][]

#     #

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

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

[Center]: /images/20220824/23703bb66ccb4d98b15d3edbc70081af.png
[Center 1]: /images/20220824/50821ab17c574d7f82bc90aee98f27f0.png
[SouthEast]: /images/20220824/ca7345d060c149b581d4ada89d75dbc1.png