閱讀331 返回首頁    go 阿裏雲 go 技術社區[雲棲]

線性表之順序存儲結構（C語言動態數組實現）

線性表的定義：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");
}

最後更新：2017-04-03 12:56:41

  上一篇：go Docker網絡詳解
  下一篇：go Xcode在調試時查看到變量都是nil的問題