线性表顺序储存

线性表，是一个或多个数据元素的集合，数据之间是连续的一段内存。线性表的特性如下。

1. 数据元素之间是有顺序的
2. 数据元素个数是有限的
3. 数据元素的类型必须相同

以下代码中包含了线性表的增删改查的实现，并且实现了数据结构和算法的分离，使任何数据类型，都可以通过我们编写的线性表类来储存。中间发生的变化在代码后面一幅图中做了充分的表示。

#ifndef _SEQLIST_H
#define _SEQLIST_H

typedef void SeqList;		// 表的类型
typedef void SeqListNode;	// 表中每个数据的类型

//创建线性表
SeqList* SeqList_Create(int capacity);
//销毁线性表
void SeqList_Destroy(SeqList* list);
//清空线性表
void SeqList_Clear(SeqList* list);
//获取线性表的长度
int SeqList_Length(SeqList* list);
//获取线性表的容量
int SeqList_Capacity(SeqList* list);
//获取线性表中某个位置的元素
SeqListNode* SeqList_Get(SeqList* list, int pos);
//将元素插入线性表
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);
//将元素从线性表中删除
SeqListNode* SeqList_Delete(SeqList* list, int pos);

#endif	//_SEQLIST_H

#include "SeqList.h"
#include <iostream>

#if 0
typedef void SeqList;		// 表的类型
typedef void SeqListNode;	// 表中每个数据的类型
#endif

typedef struct _tag_Seqlist
{
	// 容量大小
	int capacity;	
	// 实际有的数据个数
	int length;				
	// 用以储存未知类型指针数据的动态数组，使用时需动态分配
	unsigned int *array;	
}TSeqList;

SeqList* SeqList_Create(int capacity)
{
	// 给顺序表分配空间
	TSeqList* list = (TSeqList*)malloc(sizeof(TSeqList));
	if (NULL == list) return NULL;

	// 给表中的 array 成员分配空间，用以储存数据
	list->array = (unsigned int*)malloc(sizeof(unsigned int) * capacity);
	if (NULL == list->array)
	{
		free(list);
		return NULL;
	}

	// 初始化顺序表中各个成员的数据
	list->capacity = capacity;
	list->length = 0;
	memset(list->array, 0, sizeof(unsigned int) * capacity);

	// 返回链表并转换为外部可识别的格式
	return (SeqList*)list;
}

void SeqList_Destroy(SeqList* list)
{
	// 判断 list 是否有效
	if (NULL == list) return;

	// 将外部数据类型转换为内部可以识别的 TSeqList 类型
	TSeqList *tlist = (TSeqList*)list;
	// 判断 TSeqList 成员 array 是否有效
	if (NULL != tlist->array)
	{
		// 如果有效则释放
		free(tlist->array);
	}
	// 释放整个顺序表的内存
	free(tlist);
}

void SeqList_Clear(SeqList* list)
{
	// 判断 list 是否有效
	if (NULL == list) return;

	// 将外部数据类型转换为内部可以识别的 TSeqList 类型
	TSeqList *tlist = (TSeqList*)list;
	// 将数据成员中的 length 置为 0，代表清空，后面来的数据会覆盖原有数据
	tlist->length = 0;
}

int SeqList_Length(SeqList* list)
{
	if (NULL == list) return -1;

	TSeqList *tlist = (TSeqList*)list;
	// 返回有效个数
	return tlist->length;
}

int SeqList_Capacity(SeqList* list)
{
	if (NULL == list) return -1;

	TSeqList *tlist = (TSeqList*)list;
	// 返回表长度
	return tlist->capacity;
}

SeqListNode* SeqList_Get(SeqList* list, int pos)
{
	if (NULL == list) return NULL;

	TSeqList *tlist = (TSeqList*)list;
	// 获取单个成员的数据转换成外部可识别的类型并返回
	SeqListNode* pNote = (SeqListNode*)tlist->array[pos];
	return pNote;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
	if (NULL == list) return -1;

	TSeqList *tlist = (TSeqList*)list;
	// 判断是否满了
	if (tlist->capacity == tlist->length) return 0;

	// 整体向后移动
	for (int i = tlist->length; i > pos; i--)
	{
		tlist->array[i] = tlist->array[i - 1];
	}

	// 插入数据
	tlist->array[pos] = (unsigned int)node;
	// 有效个数+1
	tlist->length++;

	return 0;
}

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
	if (NULL == list) return NULL;

	TSeqList *tlist = (TSeqList*)list;
	if (0 == tlist->length) return NULL;

	// 记录被删除之前的位置
	SeqListNode* pNodeTmp = (SeqListNode*)tlist->array[pos];

	// 整体向前移，覆盖要删除的数据
	for (int i = pos + 1; i < tlist->length; i++)
	{
		tlist->array[i - 1] = tlist->array[i];
	}

	// 有效个数-1
	tlist->length--;
	return pNodeTmp;
}

#include <stdio.h>
#include "SeqList.h"

// 外部要储存的数据的类型结构
typedef struct _tag_Teacher
{
	int age;
	char name[36];
}Teacher;

int main()
{
	SeqList* list = SeqList_Create(25);

	// 定义一个自己需要储存的数据列表
	Teacher tea[10];

	// 初始化自己的数据
	for (int i = 0; i < 10; i++)
	{
		tea[i].age = i + 20;
		sprintf_s(tea[i].name, "teacher idx [teacher_%d]", i);

		// 插入数据，要把我们自己的数据类型转成线性表中数据的类型
		// 其实这里只是传递一个起始地址而已，我们无需关心内部如何储存
		SeqList_Insert(list, (SeqListNode*)&tea[i], i);
	}

	for (int i = 0; i < SeqList_Length(list); i++)
	{
		// 利用SeqList_Get函数获取线性表内部的数据
		// 但返回回来的数据是线性表的类型，我们无法解释
		// 所以要强制转换成我们能解释的数据类型，就是结构体 Teacher 类型
		Teacher* tmp = (Teacher*)SeqList_Get(list, i);
		printf("%d --- %s\n", tmp->age, tmp->name);
	}

	while (SeqList_Length(list))
	{
		Teacher* tmp = (Teacher*)SeqList_Delete(list, 0);
		printf("delete -> %d --- %s\n", tmp->age, tmp->name);
	}

	SeqList_Destroy(list);
	return 0;
}

以上为实现的代码，光看代码一定很乱，你根本不知道我们是怎么将数据结构和算法分离开来的，这里我特意画了一幅图，大家可以借鉴一下：