线性表,是一个或多个数据元素的集合,数据之间是连续的一段内存。线性表的特性如下。
- 数据元素之间是有顺序的
- 数据元素个数是有限的
- 数据元素的类型必须相同
以下代码中包含了线性表的增删改查的实现,并且实现了数据结构和算法的分离,使任何数据类型,都可以通过我们编写的线性表类来储存。中间发生的变化在代码后面一幅图中做了充分的表示。
#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; }
以上为实现的代码,光看代码一定很乱,你根本不知道我们是怎么将数据结构和算法分离开来的,这里我特意画了一幅图,大家可以借鉴一下:
One Reply to “线性表顺序储存”