1. 引子:线性表
了解到学习数据结构与算法的重要性后,又学习了评判程序效率高低算法好坏的标准,时间空间复杂度。接下来,进行一些简单数据结构的初步学习。所有数据结构中存在着可以划分为一大类的简单结构,线性表,即在逻辑上都呈现线性关系的数据结构(物理结构上不一定是线性),诸如,顺序表,链表,栈,队列等。今天,进行其中顺序表的学习。
2. 简单数据结构:顺序表
2.1 顺序表简介与功能模块分析
简介:
顺序表为在物理地址上连续的一种简单线性结构,其存储的数据元素一个连着一个。一般使用数组来进行其的实现,根据其存储空间是否可以动态增长又进一步分为,静态(定长数组)与动态(使用动态内存管理函数实现malloc)的顺序表。
功能模块分析:
数据存储方式:
- 定长数组/malloc动态开辟空间
- 存储数据信息的记录变量,帮助数据的管理
以上两部分构成的结构体。数组管理方式:
- 增(头插,尾插,随机插入):push_front,push_back,insert
- 删(头删,尾删,随机删除):pop_front,pop_back,erase
- 改(指定数据的修改):modify
- 查(指定数据的查询):find
2.2 顺序表的实现
2.2.1 顺序表:存储数据结构的构建
静态顺序表:
//替换更改表中元素类型
typedef int STDatatype;
//定义能够存储的数据个数
#define N 100
//静态
typedef struct SeqList
{
STDatatype data[N];
int capacity;
int size;
}SeqList;
动态顺序表:
typedef struct SeqList
{
STDatatype* data;
int capacity;
int size;
}SeqList;
2.2.2 顺序表:初始化与空间清理(动态)
初始化:
void SLInit(SeqList* s)
{
//不为NULL
assert(s);
//初始空间开辟4个数据大小
s->data = (STDatatype*)malloc(4 * sizeof(STDatatype));
if (s->data == NULL)
{
perror("malloc fail");
exit(-1);
}
s->capacity = 4;
s->size = 0;
}
空间清理:
void SLDestroy(SeqList* s)
{
assert(s);
free(s->data);
s->capacity = 0;
s->size = 0;
}
2.2.3 顺序表:插入与删除数据
扩容函数:
void CheckCapacity(SeqList* s)
{
assert(s);
if (s->capacity == s->size)
{
//使用临时变量去接收新地址(可能会扩容失败返回NULL),增加程序的健壮性
STDatatype* tmp = (STDatatype*)realloc(s->data, s->capacity * 2 * sizeof(STDatatype));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
s->data = tmp;
s->capacity *= 2;
}
}
尾插,尾删
尾插过程演示:
尾删过程演示:
//尾插
void SLPush_Back(SeqList* s, STDatatype val)
{
assert(s);
CheckCapacity(s);
s->data[s->size] = val;
s->size++;
}
//尾删
void SLPop_Back(SeqList* s)
{
assert(s);
assert(s->size > 0);
s->size--;
}
头插,头删
头插过程演示:
头删过程演示:
//头插
void SLPush_Front(SeqList* s, STDatatype val)
{
assert(s);
CheckCapacity(s);
int i = s->size;
while (i > 0)
{
s->data[i] = s->data[i - 1];
i--;
}
s->data[i] = val;
s->size++;
}
//头删
void SLPop_Front(SeqList* s)
{
assert(s);
//暴力检查
assert(s->size > 0);
//警告
/*if (s->size == 0)
{
printf("表内已无元素,删除失败\n");
return;
}*/
int i = 0;
while (i < s->size - 1)
{
s->data[i] = s->data[i + 1];
i++;
}
s->size--;
}
随机插入与随机删除
随机插入:
随机插入演示过程:
注:当随机插入的下标pos为0 或者 size - 1就相当于头插与尾插,可以直接复用到头插,尾插部分。头删,尾删相同
//在pos位置插入元素
//pos为下标
void SLInsert(SeqList* s, int pos, STDatatype val)
{
assert(s);
assert(pos >= 0);
assert(pos < s->size);
CheckCapacity(s);
int i = s->size;
while (i > pos)
{
s->data[i] = s->data[i - 1];
i--;
}
s->data[pos] = val;
s->size++;
}
随机删除:
随机删除演示过程:
void SLErase(SeqList* s, int pos)
{
assert(s);
assert(s->size > 0);
assert(pos >= 0);
assert(pos < s->size);
int i = pos;
while (i < s->size - 1)
{
s->data[i] = s->data[i + 1];
i++;
}
s->size--;
}
2.2.4 查找数据与修改
<1> 查找数据(查找顺序表中是否有指定数据,并返回下标):文章来源:https://www.toymoban.com/news/detail-807669.html
//找到返回下标,未找到返回-1
int SLFind(SeqList* s, STDatatype val)
{
assert(s);
int i = 0;
for (i = 0; i < s->size; i++)
{
if (s->data[i] == val)
{
return i;
}
}
return -1;
}
<2> 修改指定下标的数据(不要直接访问数据,函数可以帮助检查数据合法)文章来源地址https://www.toymoban.com/news/detail-807669.html
//高内聚,低耦合f
void SLModify(SeqList* s, int pos, STDatatype val)
{
assert(s);
assert(pos > 0);
assert(pos < s->size);
s->data[pos] = val;
}
到了这里,关于初阶数据结构:顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!