线性表的顺序存储（业务结点和算法逻辑分离）

参考了传智扫地僧讲义

直接上代码，具体插入和删除的分析，在上篇文章

线性表的顺序存储传统写法

seqlist_02.h

#ifndef __MY_SEQLIST_H__ #define __MY_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); //链表 在某一个位置 插入元素 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos); //获取某一个位置的链表结点 SeqListNode* SeqList_Get(SeqList* list, int pos); //删除某一个位置的结点 SeqListNode* SeqList_Delete(SeqList* list, int pos); #endif //__MY_SEQLIST_H__

seqlist_02.cpp

#include<iostream> #include"seqlist_02.h" using namespace std; //定义内部的句柄结构体 typedef struct tag_Myseqlist { int capacity; int length; int **array;//二维数组，相当于一维指针数组 /*这种写法，相当于管理结点的地址，就是结点的地址是一个连续空间，而结点本身是应用层 传递过来，可能不是连续的，所以这中写法与线性表的顺序存储，中结点在连续内存空间 存储稍稍有点不同，但是为了业务结点和线性表的顺序存储的算法实现分离，在c语言里只能 这样传递指针*/ }Myseqlist; SeqList* SeqList_Create(int capacity) { Myseqlist *tmp = (Myseqlist *)malloc(sizeof(Myseqlist)); if (tmp == NULL) { printf("SeqList_Create malloc(capacity*sizeof(Myseqlist)) error\n"); return NULL; } memset(tmp, 0, sizeof(Myseqlist)); tmp->array = (int **)malloc(sizeof(void *)*capacity); if (tmp->array == NULL) { printf("SeqList_Create malloc(sizeof(void *)*capacity) error\n"); return NULL; } memset(tmp->array, 0, capacity); tmp->length = 0; tmp->capacity = capacity; return tmp; } void SeqList_Destroy(SeqList* list) { if (list == NULL) { printf("err:func SeqList_Destroy list == NULL\n"); return ; } Myseqlist * tmp = (Myseqlist *)list; if (tmp->array != NULL) free(tmp->array); free(tmp); return; } void SeqList_Clear(SeqList* list) { if (list == NULL) { printf("err:func SeqList_Destroy list == NULL\n"); return; } Myseqlist * tmp = (Myseqlist *)list; if (tmp->array != NULL) { memset(tmp->array, 0, tmp->capacity); } tmp->capacity = 0; tmp->length = 0; } int SeqList_Length(SeqList* list) { if (list == NULL) { printf("err:func SeqList_Destroy list == NULL\n"); return -1; } Myseqlist * tmp = (Myseqlist *)list; return tmp->length; } //链表 容量 int SeqList_Capacity(SeqList* list) { if (list == NULL) { printf("err:func SeqList_Destroy list == NULL\n"); return -1; } Myseqlist * tmp = (Myseqlist *)list; return tmp->capacity; } //链表 在某一个位置 插入元素 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos) { if (list == NULL || node==NULL)//指针数据不对 { printf("err:func SeqList_Insert (list == NULL || node==NULL)\n"); return -1; } Myseqlist * tmp = (Myseqlist *)list; if (pos<0 || pos>tmp->length)//插入的位置不合理，小于最小位置，大于最后一个位置的后面位置 { printf("err:func SeqList_Insert (pos<0 || pos>tmp->length)\n"); return -2; } if (tmp->length >= tmp->capacity) { printf("err:func SeqList_Insert tmp->length >= tmp->capacity\n"); return -3; } //检查通过开始干活 if (pos <= tmp->length - 1)//不是在表尾插入需要移动元素 { for (int i = tmp->length; i > pos; i--) { tmp->array[i] = tmp->array[i-1]; } } tmp->array[pos] =(int *)node; tmp->length++; return 0; } SeqListNode* SeqList_Get(SeqList* list, int pos) { if (list == NULL) { printf("err:func SeqList_Destroy list == NULL\n"); return NULL; } Myseqlist * tmp = (Myseqlist *)list; return tmp->array[pos]; } SeqListNode* SeqList_Delete(SeqList* list, int pos) { if (list == NULL)//指针数据不对 { printf("err:func SeqList_Insert (list == NULL || node==NULL)\n"); return NULL; } Myseqlist * tmp = (Myseqlist *)list; if (pos<0 || pos>tmp->length-1)//删除位置不合理 { printf("err:func SeqList_Insert (pos<0 || pos>tmp->length)\n"); return NULL; } if (tmp->length == 0)//没有元素进行删除 { printf("err:func SeqList_Insert tmp->length ==0\n"); return NULL; } //把数据缓存下来 SeqListNode*ret =tmp->array[pos]; //检查完毕，开始干活 for (int i = pos + 1; i < tmp->length; i++) { tmp->array[i - 1] = tmp->array[i]; } tmp->length--; return ret; }

测试框架代码如下所示：

#include"seqlist_02.h" #include<iostream> //自己定义业务结点 typedef struct tag_Student { char name[30]; int age; }Student; int main(int argc, char*argv[]) { Student s1; Student s2; Student s3; s1.age = 11; s2.age = 12; s3.age = 13; SeqList *handle = SeqList_Create(20); SeqList_Insert(handle, (SeqListNode*)&s1,0);//头插法 SeqList_Insert(handle, (SeqListNode*)&s2,0);//头插法 SeqList_Insert(handle, (SeqListNode*)&s3, SeqList_Length(handle));//尾插法 //遍历元素 for (int i = 0; i < SeqList_Length(handle); i++) { Student* tmp = (Student*)SeqList_Get(handle, i); printf("第[%d]个元素的值是[%d]\n", i, tmp->age); } //删除元素 Student* tmp = (Student*)SeqList_Delete(handle, 0); printf("被删除元素的值是[%d]\n",tmp->age); //再次遍历元素 for (int i = 0; i < SeqList_Length(handle); i++) { Student* tmp = (Student*)SeqList_Get(handle, i); printf("第[%d]个元素的值是[%d]\n", i, tmp->age); } SeqList_Clear(handle); SeqList_Destroy(handle); return 0; }

输出结果如图：