线性表顺序储存

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

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

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

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