在我们的数据结构探索中,我们已经探讨时间复杂度、空间复杂度。大家可以移步到我的上篇文章:
今天,我们将深入研究另一个重要的主题——顺序表
全部的源代码大家可以去我github主页进行浏览:Nerosts/just-a-try: 学习c语言的过程、真 (github.com)
在介绍顺序表前,先来了解一下线性表的概念,后面一段时间讲到的数据结构也都属于线性表。
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、字符串…
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为:
#define N 7
typedef int SLDataTypt;
struct SeqList
{
int a[N];//数组长度固定
int size;//有效数据的个数
//因为数组长度固定,也不需要capacity来表示容积
};
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;//the number of valid data
int capacity;//the size of volumetric space
}SL;
void SLInit(SL* ps); //初始化
void SLDestroy(SL* ps);//销毁
void SLPrint(SL* ps);//打印
void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插
void SLPopFront(SL* ps);//头删
void SLPopBack(SL* ps);//尾删
// 顺序表查找
int SLFind(SL* ps, SLDataType x);//返回下标索引
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);
void SLInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->a);//pa->a 是realloc动态开辟的
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)//size means the number of valid data
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void CheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* new = realloc(ps->a,sizeof(SLDataType) * newcapacity);
if (new == NULL)
{
perror("realloc");
return -1;
}
ps->a = new;
ps->capacity = newcapacity;
}
}
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
CheckCapacity(ps);//检查此时容积是否存满
ps->a[ps->size] = x;
ps->size++;
}
SLPushBack函数用于向单链表尾部添加元素。
CheckCapacity函数用于检查单链表的容量是否已满,如果已满则进行扩容操作
这两个函数结合起来可以实现向单链表尾部添加元素并在需要时自动扩容的功能
void SLPushFront(SL* ps, SLDataType x) //将所有元素向后迁移一个,把第一个位置空出来
{
assert(ps);
CheckCapacity(ps);
memmove(ps->a + 1, ps->a, sizeof(SLDataType) * ps->size);
ps->a[0] = x;
ps->size++;
}
函数的作用是将所有元素向后移动一个位置,从而空出第一个位置,然后在第一个位置插入新的元素x
void SLPopFront(SL* ps)//整体向前偏移
{
assert(ps);
assert(ps->size > 0);//保证有元素来删
memmove(ps->a, ps->a+1, sizeof(SLDataType) * ps->size);
ps->size--;
}
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size > 0);
ps->size--;
}
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (x == ps->a[i])
{
return i;
}
}
return -1;
}
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
CheckCapacity(ps);
memmove(ps->a + pos + 1, ps->a + pos, sizeof(SLDataType) * (ps->size - pos));
ps->a[pos] = x;
ps->size++;
}
void SeqListErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int start = pos;
while (start < ps->size)
{
ps->a[start] = ps->a[start + 1];
start++;
}
ps->size--;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void test1()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
printf("尾插三个:");
SLPrint(&s);
SLPushFront(&s, 0);
SLPushFront(&s, 0);
printf("头插2个:");
SLPrint(&s);
SLPopFront(&s);
SLPopFront(&s);
printf("头删2个:");
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
printf("尾删2个:");
SLPrint(&s);
SLDestroy(&s);
}
int main()
{
test1();
return 0;
}
结果如下:
可见功能都正常运行
这次顺序表的内容就先到这里啦!感谢大家支持