前言
线性表是n个具有相同属性的有限数列,常见的线性表有:=顺序表,链表,栈,队列,字符串…
线性表在逻辑上是线性结构,也就是说连成一条直线,但是在物理结构上不一定连续,线性表在物理上存储是,通常以数组和链式结构的形式进行存储。
本章,我们将通过顺序表的实现来研究顺序表
一、"SeqList.h"部分
一个大的工程,永远不可能只有一个源文件,所以我们要善于将一个工程分成几个部分来完结,该头文件则是包含了库函数的引用头文件及函数的定义,包括了几个顺序表的功能,这里我们将其一一列出
需要注意的部分博主已经注释
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;//指向动态开辟数组
int size;//存储有效数据个数
int capacity;//空间大小
}SeqList;
// 对数据的管理:增删查改
void SeqListInit(SeqList* ps);//初始化
void SeqListDestroy(SeqList* ps);//消除
void SLCheckCapacity(SeqList* ps);//扩容空间
void SeqListPrint(SeqList* ps);//打印
void SeqListPushBack(SeqList* ps, SLDateType x);//尾插
void SeqListPopBack(SeqList* ps);//尾删
void SeqListPushFront(SeqList* ps, SLDateType x);//头插
void SeqListPopFront(SeqList* ps);//头删
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除low位置的值
void SeqListErase(SeqList* ps, int low);
下面我们就要围绕着头文件进行程序的编写
二、"SeqList.c"部分
1.初始化
既然是动态规划内存,那便少不了malloc,relloc之类动态内存函数的使用,这里,我们使用malloc进行动态开辟数组空间
代码如下:
void SeqListInit(SeqList* ps)
{
ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
if (ps->a == NULL)
{
perror("malloc failed");
exit(-1);
}
ps->size = 0;
ps->capacity = 4;
}
初始化比较简单,这里我们就讲到这
2.销毁
我们开辟空间后,不在使用时,要及时销毁,对于释放内存空间,且与malloc经常一起出没的,那便是free函数,释放内存后,别忘了讲指针置空
void SeqListDestroy(SeqList* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
3.扩容及打印
有时候我们在添加数时可能会发生空间满了的情况,所以这时候我们就要扩容,但扩容用哪个动态内存函数好呢,答案肯定是realloc,因为它能更灵活的对内存大小进行调整
注:realloc开辟的内存空间千万不能用free释放,因为realloc自己带有释放功能,盲目使用可能会造成意想不到的后果
void SLCheckCapacity(SeqList* ps)//扩容
{
//满了就要去扩容
if (ps->size == ps->capacity)
{
SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDateType));
if (tmp == NULL)
{
perror("realloc failed");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;
}
}
打印就比较简单了,基本上写代码就能用,这里我们之间上代码
void SeqListPrint(SeqList* ps)//打印
{
for (int i = 0; i < ps->size; i++)
printf("%d ", ps->a[i]);
printf("\n");
}
4.尾插及尾删
尾插,顾名思义就是在数组结尾处插入一个数字,这里我们的有效数字个数size就得加1,并防止ps->size>=ps->capacity即可
void SeqListPushBack(SeqList* ps, SLDateType x)//尾插
{
SLCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
尾删也就是讲最后一位数字删去,这里我们要防止出现数组没数据的情况即(ps->size=0).
这里我们可以采用断言函数来控制size的范围
void SeqListPopBack(SeqList* ps)//尾删
{
//暴力删除
assert(ps->size > 0);
ps->size--;
5.头插及头删
这两个也类似与上面的尾插和尾删,同样得注意ps->size=ps->capacity及ps->size=0的情况,这里与数组的首尾增添相似,这里就不细讲了,直接上代码
void SeqListPushFront(SeqList* ps, SLDateType x)//头插
{
SLCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopFront(SeqList* ps)//头删
{
assert(ps->size > 0);
for (int i = 0; i < ps->size; i++)
ps->a[i] = ps->a[i + 1];
ps->size--;
}
6.顺序表查找
顺序表的查找原理与数组查找大致一致,读者可以根据数组查找来复刻出顺序表查找的方式,上代码
int SeqListFind(SeqList* ps, SLDateType x)//顺序表查找
{
for (int i = 0; i < ps->size; i++)
{
if (x == ps->a[i])
{
return 1;
}
}
return 0;
}
7.顺序表在pos位插入x
这里插入问题首先还是要考虑ps->size=ps->capacity的情况,如何插入一个数字与数组同样是大相径庭,故这里就不细讲
void SeqListInsert(SeqList* ps, int pos, SLDateType x)// 顺序表在pos位置插入x
{
SLCheckCapacity(ps);
assert(pos>=0&&pos<=ps->size);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
SeqListPrint(ps);
}
8.顺序表删除low位置的数
提到删除,第一时间想到会不会出现ps->size=0的情况,然后同样利用数组知识,写出代码
void SeqListErase(SeqList* ps, int low)// 顺序表删除low位置的值
{
assert(low>=0&&low<ps->size);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (i != low - 1)
printf("%d ", ps->a[i]);
}
}
顺序表的核心部分到此结束了,下面我们来进行模拟实现
三、"text.c"部分
这里我们对照函数部分写出对应的实现方法,来确定函数是否有误,这里我们直接放代码
#include "SeqList.h"
void TestSeqList1()//尾插尾删
{
SeqList sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPopBack(&sl);
SeqListPrint(&sl);
SeqListDestroy(&sl);
}
void TestSeqlist2()//头插头删
{
SeqList sl;
SeqListInit(&sl);
SeqListPushFront(&sl, 1);
SeqListPushFront(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPopFront(&sl);
SeqListPrint(&sl);
SeqListDestroy(&sl);
}
void TestSeqlist3()//查找数
{
SeqList sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPrint(&sl);
int ret = SeqListFind(&sl, 2);
if (ret == 1)
{
printf("找到了,下标为:%d\n", ret);
}
else
printf("该数字不在该顺序表里\n");
//SeqListPrint(&sl);
SeqListDestroy(&sl);
}
void TestSeqlist4()//顺序表在pos位置插入x,在low删除数字
{
SeqList sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
printf("插入前:\n");
SeqListPrint(&sl);
printf("插入后:\n");
SeqListInsert(&sl, 3, 5);
printf("删除low位置数字后:\n");
SeqListErase(&sl, 2);
SeqListDestroy(&sl);
}
int main()
{
printf("尾插尾删用例\n");
TestSeqList1();
printf("头插头删用例\n");
TestSeqlist2();
printf("顺序表查找数据用例\n");
TestSeqlist3();
printf("顺序表在pos位置插入x,删除low位置的数用例\n");
TestSeqlist4();
return 0;
}
博主使用的用例结果如下图所示:
文章来源:https://www.toymoban.com/news/detail-621394.html
结语
关于顺序表的内容即实现到这里就结束了,希望可以帮到各位文章来源地址https://www.toymoban.com/news/detail-621394.html
到了这里,关于数据结构-顺序表各项功能的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!