文档章节

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

yangxin0917
 yangxin0917
发布于 2014/12/18 19:33
字数 3094
阅读 50
收藏 0

线性表的定义: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");
}

本文转载自:http://blog.csdn.net/xyang81/article/details/25914859

yangxin0917
粉丝 3
博文 76
码字总数 31277
作品 0
昌平
高级程序员
私信 提问
线性表Linear List-线性表的顺序表示和实现

线性表Linear List 线性表:线性表(Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列 其中: 数据元素的个数n定义为表的长度 = "list".length() ("...

秋风醉了
2014/05/04
98
0
数据结构与算法-C语言篇5-线性表之顺序存储结构

数据结构与算法-目录 1、线性表的定义:有零个或多个数据元素组成的有序数列。 线性表是一种常用的数据结构。在实际应用中,线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。...

香沙小熊
2018/01/06
0
0
《数据结构》笔记三:线性表之顺序存储结构

前言: 关于源码的几个说明: 编码工具:Xcode 语言:C语言 参考书:《大话数据结构》 为了方便不熟悉的小伙伴们,文中关于代码的部分给出了详细的步骤,只要按照步骤,都可以实现。 另:小编...

小曼blog
06/28
0
0
数据结构/算法——线性表*

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,...

cjun1990
2015/09/24
86
0
数据结构之_动态数组 顺序表的实现

数据结构之_动态数组 顺序表的实现 1.基本概念 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。 线性表 (a1,a2,……,an)的顺序存储示意图如下: 2.线...

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容器是每个容器都有自己...

源哥L
14分钟前
7
0
一起来学Java8(三)——方法引用

在一起来学Java8(一)——函数式编程中有一个简单的函数式编程的例子: import java.util.function.Consumer;class Person { public static void sayHello(String name) { S...

猿敲月下码
33分钟前
15
0
读书笔记:深入理解ES6(十一)

第十一章 Promise与异步编程   Promise可以实现其他语言中类似Future和Deferred一样的功能,是另一种异步编程的选择,它既可以像事件和回调函数一样指定稍后执行的代码,也可以明确指示代码...

张森ZS
56分钟前
22
0
面试官,Java8 JVM内存结构变了,永久代到元空间

在文章《JVM之内存结构详解》中我们描述了Java7以前的JVM内存结构,但在Java8和以后版本中JVM的内存结构慢慢发生了变化。作为面试官如果你还不知道,那么面试过程中是不是有些露怯?作为面试...

程序新视界
今天
30
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部