磁县邯郸网站建设,给网站做rss,国外专名做路演的网站,dw网页制作教程div视频教程全文目录引言顺序表定义静态顺序表动态顺序表动态顺序表的接口实现顺序表的初始化与销毁顺序表尾插/尾删顺序表头插/头删顺序表在pos位置插入/删除顺序表的打印顺序表中的查找总结引言
在生产中#xff0c;为了方便管理数据#xff0c;我们经常会需要将一些数据连续的存储起…
全文目录引言顺序表定义静态顺序表动态顺序表动态顺序表的接口实现顺序表的初始化与销毁顺序表尾插/尾删顺序表头插/头删顺序表在pos位置插入/删除顺序表的打印顺序表中的查找总结引言
在生产中为了方便管理数据我们经常会需要将一些数据连续的存储起来。例如手机的通讯录中需要存储联系人的信息图书管理系统中需要存储图书的信息等。
想到存储一系列相同类型的数据我们就不免想到数组。数组可以实现将一些相同类型的数据存储到一块连续的空间中。其实我们在这篇文章中要介绍的顺序表中的数据就是以数组的形式存储的。
顺序表定义
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
为了方便管理数据我们通常会将存储数据的数组与目前数据的状态顺序表中已经存储元素的个数等放在一个结构体变量中。
静态顺序表
静态顺序表就是使用定长的数组存储数据的顺序表。
我们需要将存储数据的数组与当前已存储的数据的个数放在一个结构体变量中以方便对数据进行管理
typedef int SLDateType;typedef struct SeqList
{SLDateType arr[10];size_t size;
}SeqList;但是这样存储数据是有很明显的缺陷的就是空间的大小一旦确定下来就不能改变了当数据存储满之后也不能实现扩容。
所以我们可以使用动态顺序表来实现
动态顺序表
动态顺序表就是使用动态开辟的数组存储数据的顺序表
我们需要将存储数据的动态空间的地址、当前已经存储的数据的个数与顺序表的容量大小放在一个结构体变量中方便对数据进行管理
typedef int SLDateType;typedef struct SeqList
{SLDateType* arr;size_t size;size_t capacity;
}SeqList;SLDateType* arr指向的空间是动态开辟的当需要扩容时只需要使用realloc函数进行扩容即可。
动态顺序表的接口实现
在有了顺序表的相关概念后我们就可以尝试实现一下顺序表 静态顺序表的实现其实是较为简单的这里就只介绍动态顺序表的实现
首先我们需要将上述的SeqList类型的结构体定义出来。但此时它的成员为一个SLDateType*型的指针、任意值的size变量与capacity变量。并没有任何意义所以我们需要对这个结构体中的成员进行初始化
顺序表的初始化与销毁
初始化函数void SeqListInit(SeqList* ps);
对于初始化函数只有一个参数就是我们创建的结构体的结构体指针。在这个函数中我们需要实现动态开辟一块空间用来存放数据并且将size与capacity的值初始化为0
void SeqListInit(SeqList* ps)
{assert(ps);ps-arr (SLDateType*)calloc(INIT, sizeof(SLDateType));if (ps-arr NULL){perror(calloc);return;}ps-capacity INIT;ps-size 0;
}我们的空间是动态开辟的在使用结束后自然需要free释放
内存释放函数void SeqListDestroy(SeqList* ps)
void SeqListDestroy(SeqList* ps)
{assert(ps);free(ps-arr);ps-arr NULL;ps-capacity 0;ps-size 0;
}有了存储数据的空间我们就需要实现对这些数据的操作无非增、删、查、改。 我们将逐一实现这些操作
顺序表尾插/尾删
顺序表的尾插就是在顺序表的末尾插入一个值。 我们直接在顺序表中下标为size结构体中的成员的位置插入一个数据即可。
但是这样的想法是有漏洞的当size等于capacity时即顺序表已经存满的时候。我们如果还将数据存在下标为size的位置就会出现数组越界的问题。所以插入数据前我们需要判断是否需要扩容如果需要则使用realloc扩容后再插入数据 别忘了插入后size
void SeqListPushBack(SeqList* ps, SLDateType x)
{assert(ps);if (ps-capacity ps-size){SLDateType* ptr (SLDateType*)realloc(ps-arr, 2 * ps-capacity * sizeof(SLDateType));if (ptr NULL){perror(realloc);return;}ps-arr ptr;ps-capacity * 2;}*(ps-arr ps-size) x;
}顺序表的尾删就是删除顺序表中的最后一个数据
当然当顺序表中的数据数size为0时就不执行此函数。这里我们可以直接使用assert来判断 别忘了删除后size–
void SeqListPopBack(SeqList* ps)
{assert(ps);assert(ps-size 0);*(ps-arr --(ps-size)) 0;
}顺序表头插/头删
顺序表的头插就是在顺序表的前面插入一个数据。
此时我们显然是不能直接用数据覆盖第一个数据的。而是需要将顺序表中的数据整体向后移动一个元素的位置然后再将第一个元素的位置覆盖。 当然头插也需要判断顺序表是否已满 别忘了插入后size
void SeqListPushFront(SeqList* ps, SLDateType x)
{assert(ps);if (ps-capacity ps-size){SLDateType* ptr (SLDateType*)realloc(ps-arr, 2 * ps-capacity * sizeof(SLDateType));if (ptr NULL){perror(realloc);return;}ps-arr ptr;ps-capacity * 2;}for(size_t i ps-size; i 0; i--){*(ps-arr i) *(ps-arr i - 1);}*ps-arr x;ps-size;
}顺序表的头删就是将顺序表中最前面的元素删除。 首先判断size是否为0。然后我们可以直接用后面的元素覆盖前面一个的元素这样可以直接实现删除第一个元素 别忘了删除后size–
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps-size 0);for (size_t i 1; i ps-size; i){*(ps-arr i - 1) *(ps-arr i);}ps-size--;
}顺序表在pos位置插入/删除
实现了头插头删、尾插尾删后我们再进一步思考能不能实现在顺序表的任意位置插入或删除任意位置的元素
在pos位置插入数据时 同样需要判断是否已满。我们需要将从pos开始的元素向后移动然后再将元素插入到pos位置即可 别忘了插入后size
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);if (ps-capacity ps-size){SLDateType* ptr (SLDateType*)realloc(ps-arr, 2 * ps-capacity * sizeof(SLDateType));if (ptr NULL){perror(realloc);return;}ps-arr ptr;ps-capacity * 2;}for (int i ps-size; i pos; i--){*(ps-arr i) *(ps-arr i - 1);}ps-size;*(ps-arr pos) x;
}删除pos位置的元素时首先判断size是否为0。然后只需要将从pos后的元素统一向前覆盖即可实现pos位置数据的删除 别忘了删除后size–
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(ps-size 0);for (size_t i pos; i ps-size - 1; i){*(ps-arr i) *(ps-arr i 1);}*(ps-arr --(ps-size)) 0;
}顺序表的打印
打印顺序表中元素时直接便利顺序表打印即可
void SeqListPrint(SeqList* ps)
{assert(ps);for (size_t i 0; i ps-size; i){printf(%d , *(ps-arr i));}
}顺序表中的查找
查找顺序表中数据时只需要将顺序表中度元素遍历逐个与输入元素比较即可。查找到后返回下标否则返回0
int SeqListFind(SeqList* ps, SLDateType x)
{assert(ps);for (size_t i 0; i ps-size; i){if (*(ps-arr i) x){return i 1;}}return -1;
}总结
到此关于顺序表的所有内容就介绍完了。不难发现这些数据存储的形式可以抽象化为线性顺序表其实就是线性表的一种。
线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表有顺序表、链表、栈、队列、字符串等。
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。在下一篇文章我们将要介绍的链表也是线性表的一种。
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出
如果本文对你有帮助希望一键三连哦
希望与大家共同进步哦
