初阶数据结构
第一章 时间复杂度和空间复杂度
第二章 动态顺序表的实现
前言
本系列的内容是以C语言为基础,讲解并实现初阶的数据结构,而高阶的数据结构在后续的章节中会用C++来实现。那么本系列则起着承上启下的关键作用,即帮助大家熟悉C语言,也帮助大家入门数据结构。
一、什么是数据结构?
计算机最强大的地方就是处理数据的能力非常强。那么如何高效地处理数据就成了关键问题。而我们要做的就是将数据之间搭建起一定的联系,使得众多数据共同构成一个整体。那么我们就是需要根据不同的数据、不同的需求去构建不同的数据间的联系,也就是我们所说的数据结构。
二、什么是顺序表?
其实在我们C语言章节中所学的数组的概念,数组中的每一个元素都对应一个下标,而这些下标就会让这些数据“排好队”,即让彼此之间按顺序存储,这就是这些数据之间的联系。但是我们发现,我们的数组大小是无法动态改变的。但我们这里所说的顺序表则是一个能够动态改变内存的数组。
三、动态顺序表的构建
struct SeqList
{
int *a;//元素所对类型的指针
int size;//当前顺序表中的数据个数
int capacity;//顺序表所能存储的最大元素个数
};
上面就是一个简单动态顺序表的定义,size和capacity是很好理解的,那么这个指针是干什么的呢?
我们所创建的顺序表是可以动态存储的,那么在堆区开辟内存后会返回对应的地址,此时我们需要创建一个指针来记录这块内存的地址,并通过这个指针对内存进行操作。而这个指针的类型取决于内存存储的数据的类型,即顺序表中的元素类型。假如我们存储的是整型数据,那么这个指针就应该是整型数据。
但是这个顺序表的定义局限性很大,我们将其限制在了int类型。那么如何修改才能使其的存储范围更广呢?
typedef int ElementType;//定义元素类型
typedef struct SeqList
{
ElementType* a;//记录堆区开辟的内存空间
int size;//元素的实际个数
int capacity;//元素的最大容量
} SeqList; //定义动态顺序表的结构体,并重命名
此时,当我们需要存储不同的数据类型的时候,只需要将typedef后面改成我们想要的类型即可,不需要把代码中的处处元素类型都改掉,大大提高了代码的适用范围。
四、接口函数的实现
1、初始化
void SeqListInit(SeqList *SL)
{
SL->a = NULL;
SL->size = SL->capacity = 0;
}
我们将指针设置为空指针,将元素个数和顺序表容量设置为0。
2、容量的检查和开辟
无论是元素的插入还是删除,都要涉及到顺序表容量和元素个数的问题,所以优先实现容量检查和开辟的函数是非常有必要的。
//检查容量,扩容
void SeqListCheckCapacity(SeqList *SL)
{
assert(SL!=NULL);
if (SL->size == SL->capacity)
{
int NewCapacity = SL->capacity == 0 ? 4 : 2 * SL->capacity;
ElementType*temp=(ElementType*)realloc(SL->a,(NewCapacity)*sizeof(ElementType));
if (temp == NULL)
{
perror("SeqListCheckCapacity():\n");
}
SL->a = temp;
SL->capacity = NewCapacity;
}
else
{
return;
}
}
如果这个顺序表是刚刚创建的,那么其容量是0,此时我们就给它开辟4个元素大小的空间,如果容量不是0,当容量已经满的时候,我们就直接将容量翻倍。并且重新开辟一段空间。很多人会想,我们第一次使用顺序表开辟空间的时候,不应该使用malloc或者calloc函数吗?为什么要用realloc函数,其实我们可以在官网的介绍中找到答案,当我们在realloc函数中传入的是一个空指针的时候,此时的realloc函数就相当于一个malloc函数。因此,我们就可以只用realloc函数。
我们开辟完内存之后不能直接用LS->a,来接收。因为如果realloc函数开辟失败,函数就会返回一个空指针,这个空指针传递给我们的LS->a的时候,不仅使我们的空间没有得到增加,反而还失去了原来的空间,风险较大。所以我们创建要给临时的指针来判断一下,这个指针是否为空,倘若不为空再用LS->a来接收。
3、销毁
//销毁
void SeqListDestroy(SeqList* SL)
{
free(SL->a);
SL->a = NULL;
SL->size = SL->capacity = 0;
}
销毁函数就非常好写了,这里就不作解释了。
4、尾插
//尾插
void SeqListPushBack(SeqList *SL, ElementType data)
{
assert(SL!=NULL);
SeqListCheckCapacity(SL);
SL->a[SL->size] = data;
SL->size++;
}
再插入之前,我们先判断一下容量是否已满,如果满了则立即扩容。当容量足够时,我们在顺序表的尾部插入一个数据,并且让元素个数加一。
5、尾删
尾删其实很简单,我们只需要将size–,这样做的目的就是在顺序表打印的时候,不让其访问最后一个元素,那么此时从表面上来看就完成了数据的删除。
但是这里有一个问题,size的最小值是0,倘若我们的顺序表本身就是空的,那么是不需要进行size–的,假设我们进行了size–的功能,那么我们利用size表示下标,访问顺序表内容的时候,就会出现严重的数组向前越界访问的问题。因此,我们在实现尾删的过程中需要进行条件的判断。
void SeqListPopBack(SeqList *SL)
{
assert(SL != NULL);
assert(SL->size != 0);
SL->a[SL->size - 1] = 0;
SL->size--;
}
6、头插
首先我们需要检查一下容量,其次我们需要将现存的数据整体向后挪动一个单位,这样做的目的是把第一个位置让出来,以便我们插入新的数据。最后把元素个数size++。
void SeqListPushFront(SeqList *SL, ElementType data)
{
assert(SL!=NULL);
SeqListCheckCapacity(SL);
for (int i = SL->size-1; i >=0; i--)
{
SL->a[i + 1] = SL->a[i];
}
SL->a[0] = data;
SL->size++;
}
7、头删
头删和尾删的大体逻辑是相同的,我们首先需要检查一下size是否为0。接下来的操作我们只需要让后面的数据覆盖前面的数据,最终就完成了头删的效果。
void SeqListPopFront(SeqList *SL, ElementType data)
{
assert(SL!=NULL);
assert(SL->size!=0);
for (int i = 0; i < SL->size-1; i++)
{
SL->a[i] = SL->a[i + 1];
}
SL->a[SL->size - 1] = 0;
SL->size--;
}
8、随机插入
什么是随机插入呢?即我们可以在顺序表的指定位置去插入数据。我们假设插入位置的下标是pos,那么我们只需要将pos位置到最后的所有数据整体向后移动,然后把pos的位置空出来,再在pos的位置插入一个新的元素,最后size++。
//中间插入
void SeqListInsert(SeqList* SL, int pos, ElementType data)
{
assert(SL!=NULL);
SeqListCheckCapacity(SL);
for (int i = SL->size-1; i >=pos; i--)
{
SL->a[i + 1] = SL->a[i];
}
SL->a[pos] = data;
SL->size++;
}
上面的代码严谨吗?
我们直到顺序表的一大特性就是连续性,元素与元素之间必须是连续存储的,所以当我们在与末尾元素间隔一段距离的地方插入一个元素,这样就会导致整个顺序表是不连续的,中间出现了空白部分。虽然在逻辑上出现了错误,但是由于我们的容量一般情况下大于元素个数,所以系统不会报错。此时就需要我们多加思考,调试,才能发现类似的逻辑错误。为了修改这个错误,我们只需要断言一下即可:
assert(pos >= 0&&pos<=SL->size);
那么最终的版本就是:
void SeqListInsert(SeqList* SL, int pos, ElementType data)
{
assert(SL!=NULL);
assert(pos >= 0&&pos<=SL->size);
SeqListCheckCapacity(SL);
for (int i = SL->size-1; i >=pos; i--)
{
SL->a[i + 1] = SL->a[i];
}
SL->a[pos] = data;
SL->size++;
}
==注意挪动的方向,小心造成数据的覆盖!!==
9、随机删除
涉及到删除,我们首先需要断言一下size是否为0。然后将pos后面的数据整体向前移动,覆盖原来pos位置所对的数据,最终size–。即完成了指定位置删除功能。同时,我们还需要注意到顺序表的连续性,因此我们就能写下下图所示的代码:
void SeqListErase(SeqList* SL, int pos)
{
assert(SL != NULL);
assert(pos >= 0 && pos <= SL->size-1);
SeqListCheckCapacity(SL);
for (int i = pos; i < SL->size - 1; i++)
{
SL->a[i] = SL->a[i + 1];
}
SL->a[SL->size - 1] = 0;
SL->size--;
}
10、查找
这个功能就非常简单了,遍历一遍顺序表即可。找到了则返回所查找元素的下标,找不到则返回-1。
int SeqListFind(SeqList* SL, ElementType data)
{
assert(SL!=NULL);
for (int i = 0; i < SL->size; i++)
{
if (SL->a[i] == data)
{
return i;
}
}
return -1;
}
11、打印
这个也是非常简单的,同样也是遍历一下顺序表即可。
void SeqListPrint(SeqList *SL)
{
assert(SL!=NULL);
for (int i = 0; i < SL->size; i++)
{
printf("%d ", SL->a[i]);
}
printf("\n");
}
五、顺序表的优缺点
1、优点:
顺序表最大的优势就是在于各个元素在物理结构上是紧密连接的,因此我们可以通过下表的计算推算出中间某个元素的位置,找这个元素的算法的时间复杂度仅仅是O(1)
。这是非常关键的一个优点,比如在二分查找、快速排序等等需要随机访问功能的算法中,采用顺序表的结构去存储数据是非常有优势的。
2、缺点:
- 空间不够的时候,系统会对其进行扩容,而扩容是有一定消耗的。
- 进行顺序表的头部或者中间位置插入和删除时,需要挪动大量的数据,导致该过程的时间复杂度比较高。
- 由于动态顺序表存在扩容的功能,一般都会扩容为原来的二倍,因此大概率存在一定的空间浪费。