&＃x1f307;个人主页&＃xff1a;平凡的小苏
&＃x1f4da;学习格言&＃xff1a;别人可以拷贝我的模式&＃xff0c;但不能拷贝我不断往前的激情
&＃x1f6f8;C语言专栏&＃xff1a;https://blog.csdn.net/vhhhbb/category_12174730.html
&＃x1f680;数据结构专栏&＃xff1a;https://blog.csdn.net/vhhhbb/category_12211053.html
家人们更新不易&＃xff0c;你们的&＃x1f44d;点赞&＃x1f44d;和⭐关注⭐真的对我真重要&＃xff0c;各位路过的友友麻烦多多点赞关注&＃xff0c;欢迎你们的私信提问&＃xff0c;感谢你们的转发&＃xff01;
关注我&＃xff0c;关注我&＃xff0c;关注我&＃xff0c;你们将会看到更多的优质内容&＃xff01;&＃xff01;
目录
1、顺序表概念
2、函数接口的实现
2.1、顺序表的初始化
2.2、顺序表的插入操作
2.3、顺序表的删除操作
2.4、顺序表的插入和删除的时间复杂度
2.5、线性表的顺序存储结构的优缺点
2.6、顺序表的查找
2.7、顺序表的销毁
3、顺序表源码
SList.c
SList.h
Test.c
1、顺序表概念
线性表的顺序存储结构&＃xff0c;指的是用一段地址连续的存储单元依次存储线性表的数据元素
- 线性表的存储结构&＃xff0c;说白了&＃xff0c;就是在内存中找块地儿&＃xff0c;通过占位的形式&＃xff0c;把一块内存空间给占了&＃xff0c;然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据都相同&＃xff0c;所以可以用C语言&＃xff08;其他语言也相同&＃xff09;的一维数组来实现顺序存储结构&＃xff0c;即把第一个数据元素存到数组下标为0的位置中&＃xff0c;接着把线性表相邻的元素存储在数组中相邻的位置。
2、函数接口的实现
来看线性表顺序存储的结构代码。
#include
#include
#include
#define InitCapa 4;//初始容量
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a; //动态分配数组&＃xff0c;存储数据元素
int size;//数组元素个数
int capacity;//数组容量的大小
}SeqList;
2.1、顺序表的初始化
void SeqListInit(SeqList* ps)
{
assert(ps);
ps->a &＃61; (SLDateType*)malloc(sizeof(SLDateType) * 4);
ps->size &＃61; 0;
ps->capacity &＃61; InitCapa;
}
注&＃xff1a;顺序表的初始化首先要动态分配容量为4的数组。数组元素的个数初始化为0.
2.2、顺序表的插入操作
我们现在来考虑&＃xff0c;如果要实现线性的插入操作&＃xff0c;即在顺序表的第i个位置插入新元素e&＃xff0c;应该如何操作&＃xff1f;
举个栗子&＃xff0c;本来我们在春运时去买火车票&＃xff0c;大家都排队排的好好的。这时来了一个抱着孩子的年轻妈妈&＃xff0c;对着队伍中排在第三位的你说&＃xff0c;“大哥&＃xff0c;求求你帮帮忙&＃xff0c;我家里母亲有病&＃xff0c;我得急着回去看她&＃xff0c;你看我还抱着孩子&＃xff0c;这队伍这么长&＃xff0c;你可否让我排在你的前面&＃xff0c;你心一软&＃xff0c;就同意了。这时&＃xff0c;你必须得退后一步。骂声四起。但后面得人不清楚这加塞是怎么回事&＃xff0c;没什么办法。
这个例子已经说明了线性表得顺序存储结构&＃xff0c;在插入数据时得实现过程&＃xff08;如下图所示&＃xff09;
实现代码如下&＃xff1a;
void CheckCapacity(SeqList* ps)
{
if (ps->size &＃61;&＃61; ps->capacity)
{
SLDateType* tmp &＃61; (SLDateType*)realloc(ps->a,sizeof(SLDateType) * ps->capacity * 2);
if (tmp &＃61;&＃61; NULL)
{
perror("realloc fail:");
exit(-1);
}
ps->capacity *&＃61; 2;
ps->a &＃61; tmp;
}
}
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
assert(ps);
CheckCapacity(ps);//检查容量函数&＃xff0c;只要是插入元素得操作&＃xff0c;都应该检查容量
int end &＃61; ps->size-1;
while (end >&＃61; pos)//每个元素往后移动
{
ps->a[end &＃43; 1] &＃61; ps->a[end];
end--;
}
ps->a[pos] &＃61; x;
ps->size&＃43;&＃43;;
}
插入算法得思路&＃xff1a;
&＃xff08;1&＃xff09;如果顺序表得长度大于等于数组长度&＃xff0c;则动态增加容量&＃xff1b;
&＃xff08;2&＃xff09;从最后一个元素开始向前遍历到第i个位置&＃xff0c;分别将它们都向后移动一个位置&＃xff1b;
&＃xff08;3&＃xff09;将要插入得元素填入位置i处
&＃xff08;4&＃xff09;表长加1&＃xff1b;
2.3、顺序表的删除操作
接着刚才的栗子。此时后面的人群意见都很大&＃xff0c;都说怎么可以这样&＃xff0c;不管什么原因&＃xff0c;插队就是不行&＃xff0c;有本事&＃xff0c;找火车站开后门去。就在这时&＃xff0c;远处跑来一胖子&＃xff0c;对着这个美女喊&＃xff0c;可找到你了&＃xff0c;你这个骗子&＃xff0c;还我钱。只见女子二话不说&＃xff0c;突然就冲出了队伍&＃xff0c;胖子追在其后。哦&＃xff0c;原来她是倒卖火车票的黄牛&＃xff0c;刚才还在装可怜。于是排队的人群&＃xff0c;又像蠕虫一样&＃xff0c;都向前移动了一步&＃xff0c;骂声渐息&＃xff0c;队伍又恢复了平静。
这就是顺序表的顺序存储结构的删除元素的过程实现&＃xff08;如下图所示&＃xff09;
实现代码如下&＃xff1a;
void SeqListErase(SeqList* ps, int pos)
{
assert(ps);
assert(ps->size);//如果容量为0&＃xff0c;就抛出异常&＃xff0c;不可以再删除
int begin &＃61; pos;
while (begin size-1)
{
ps->a[begin] &＃61; ps->a[begin &＃43; 1];
begin&＃43;&＃43;;
}
ps->size--;
}
删除算法的思路&＃xff1a;
&＃xff08;1&＃xff09;从删除元素位置开始遍历到最后一个元素位置&＃xff0c;分别将它们都向前移动一个位置&＃xff1b;
&＃xff08;2&＃xff09;表长减1&＃xff1b;
2.4、顺序表的插入和删除的时间复杂度
- 先看最好的情况&＃xff0c;如果元素要插入到最后一个位置&＃xff0c;或者删除最后一个元素时的时间复杂度为O(1)&＃xff0c;因为不需要移动元素。
- 最坏的情况呢&＃xff0c;如果元素要插入到第一个位置或者删除第一个元素&＃xff0c;此时的时间复杂度是多少呢&＃xff1f;这就意味着要移动所有的元素向后或者向前&＃xff0c;所以这个时间复杂度为O(n).
2.5、线性表的顺序存储结构的优缺点
优点&＃xff1a;
- 无需为表示表中的元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任意位置的元素
缺点&＃xff1a;
2.6、顺序表的查找
实现代码如下&＃xff1a;
int SeqListFind(SeqList* ps, SLDateType x)
{
assert(ps);
for (int i &＃61; 0; i size; i&＃43;&＃43;)
{
if (ps->a[i] &＃61;&＃61; x)
{
return i;
}
}
return -1;
}
注&＃xff1a;就是遍历查找的过程
2.7、顺序表的销毁
实现代码如下&＃xff1a;
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->size &＃61; ps->capacity &＃61; 0;
ps->a &＃61; NULL;
}
3、顺序表源码
SList.c
//SList.c
#include"SList.h"
void SeqListInit(SeqList* ps)
{
assert(ps);
ps->a &＃61; (SLDateType*)malloc(sizeof(SLDateType) * 4);
ps->size &＃61; 0;
ps->capacity &＃61; InitCapa;
}
void CheckCapacity(SeqList* ps)
{
if (ps->size &＃61;&＃61; ps->capacity)
{
SLDateType* tmp &＃61; (SLDateType*)realloc(ps->a,sizeof(SLDateType) * ps->capacity * 2);
if (tmp &＃61;&＃61; NULL)
{
perror("realloc fail:");
exit(-1);
}
ps->capacity *&＃61; 2;
ps->a &＃61; tmp;
}
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{
assert(ps);
CheckCapacity(ps);
ps->a[ps->size] &＃61; x;
ps->size&＃43;&＃43;;
}
void SeqListPopBack(SeqList* ps)
{
assert(ps->size);
ps->size--;
}
void SeqListPopFront(SeqList* ps)
{
//assert(ps);
//assert(ps->size);
//int begin &＃61; 0;
//int end &＃61; 1;
//while (end size)
//{
// ps->a[begin] &＃61; ps->a[end];
// begin&＃43;&＃43;;
// end&＃43;&＃43;;
//}
//ps->size--;
SeqListErase(ps, 0);
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{
//assert(ps);
//CheckCapacity(ps);
//int end &＃61; ps->size;
//int begin &＃61; ps->size - 1;
//while (begin >&＃61; 0)
//{
// ps->a[end] &＃61; ps->a[begin];
// begin--;
// end--;
//}
//ps->a[0] &＃61; x;
//ps->size&＃43;&＃43;;
SeqListInsert(ps, 0, x);
}
int SeqListFind(SeqList* ps, SLDateType x)
{
assert(ps);
for (int i &＃61; 0; i size; i&＃43;&＃43;)
{
if (ps->a[i] &＃61;&＃61; x)
{
return i;
}
}
return -1;
}
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
assert(ps);
CheckCapacity(ps);
int end &＃61; ps->size-1;
while (end >&＃61; pos)
{
ps->a[end &＃43; 1] &＃61; ps->a[end];
end--;
}
ps->a[pos] &＃61; x;
ps->size&＃43;&＃43;;
}
void SeqListErase(SeqList* ps, int pos)
{
assert(ps);
assert(ps->size);
int begin &＃61; pos;
while (begin size-1)
{
ps->a[begin] &＃61; ps->a[begin &＃43; 1];
begin&＃43;&＃43;;
}
ps->size--;
}
void SeqListPrint(SeqList* ps)
{
for (int i &＃61; 0; i size; i&＃43;&＃43;)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->size &＃61; ps->capacity &＃61; 0;
ps->a &＃61; NULL;
}
SList.h
#pragma once
#include
#include
#include
#define InitCapa 4;
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;
int size;
int capacity;
}SeqList;
// 对数据的管理:增删查改
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);
void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);
注&＃xff1a;这里的尾插、头插、尾删、头删都是插入删除函数的复用
Test.c
#include"SList.h"
void TestSList()
{
SeqList SL;
SeqListInit(&SL);
SeqListPushBack(&SL, 1);
SeqListPushBack(&SL, 2);
SeqListPushBack(&SL, 3);
SeqListPushBack(&SL, 4);
SeqListPrint(&SL);
SeqListInsert(&SL, 1, 5);
SeqListInsert(&SL, 1, 6);
SeqListPrint(&SL);
SeqListDestroy(&SL);
}
int main()
{
TestSList();
return 0;
}
好了&＃xff01;&＃xff01;&＃xff01;小编的分享到这里就结束了&＃xff0c;想要继续了解数据结构的知识的&＃xff0c;敬请期待博主的更新&＃xff0c;有什么不足的地方请各位大佬多多指教&＃xff01;&＃xff01;&＃xff01;
京公网安备 11010802041100号