网站开发工具特点总结,国际营销网站建设,沂水建设局网站,青海建设厅网站证件查询✨✨ 欢迎大家来到贝蒂大讲堂✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;数据结构与算法 贝蒂的主页#xff1a;Betty’s blog 1. 什么是顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元… ✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 养成好习惯先赞后看哦~ 所属专栏数据结构与算法 贝蒂的主页Betty’s blog 1. 什么是顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构它与数组非常类似但是相比于数组顺序表有一个非常明显的优点——可以动态内存增长空间大小 2. 顺序表的功能
顺序表可以大致包含以下几个功能 初始化顺序表中的数据。 打印顺序表中的数据。 对顺序表进行尾插(末尾插入数据)。 对顺序表进行尾删(末尾删除数据)。 对顺序表进行头插(开头插入数据)。 对顺序表进行头删(开头删除数据)。 对顺序表就像查找数据。 对顺序表数据进行修改。 任意位置的删除和插入数据。 销毁顺序表。 3. 顺序表的定义
定义顺序表我们首先需要一个动态内存开辟的空间当前数据的个数(size)以及方便扩容的容量大小(capacity)。
typedef int SLDataType; //类型重命名方便后续修改类型
#define N 4 //初始化空间大小
typedef struct SeqList
{SLDataType* a; //指向动态开辟的数组size_t size; //有效数据个数size_t capacity; //容量大小
}SeqList;4. 功能的具体实现
4.1 初始化顺序表
(1) 代码实现
初始化顺序表时我们可以先开辟四个空间之后不够再进行扩容。
void SeqListInit(SeqList* p)
{assert(p); //断言p-a (SLDataType*)malloc(N*sizeof(SLDataType)); //初始顺序表为四个空间if (p-a NULL){perror(malloc fail:);return ;}p-size 0; //初始数据个数为0p-capacity 4; //初始空间容量为4
}(2) 复杂度分析
时间复杂度由于没有其他未知数的引入所以所需时间是个常数也就是O(1)。空间复杂度动态开辟N个空间所以空间复杂度为O(N)。
4.2 打印数据
(1) 代码实现
打印数据只用循环打印就可以了。
void SeqListPrint(const SeqList* p)
{assert(p); //断言if (p-size 0) //判断顺序表是否为空{printf(顺序表为空\n);return;}int i 0;for (i 0; i p-size; i) //打印顺序表{printf(%d , p-a[i]);}printf(\n);
}(2) 复杂度分析
时间复杂度因为会打印顺序表中的所有数据所以时间复杂度为O(N)。空间复杂度打印顺序表并不需要开辟格外的空间所以空间复杂度为O(1)。
4.3 尾插数据
尾插数据顾名思义就是在顺序表末尾插入数据在插入数据之前我们应该检查顺序表是否为满。 (1) 检查是否已满
void CheckCapacity(SeqList* p)
{assert(p); //断言if (p-size p-capacity) //检查容量满了则增容{size_t newcapacity 2 * p-capacity; //扩容为原来的2倍SLDataType* prt (SLDataType*)realloc(p-a, newcapacity * sizeof(SLDataType)); //扩容if (prt NULL){perror(realloc fail:);return ;}p-a prt; // prt不为空开辟成功p-capacity newcapacity; //更新容量}
}(2) 插入数据
void SeqListPushBack(SeqList* p, SLDataType x)
{assert(p); //断言CheckCapacity(p); //检查顺序表容量是否已满p-a[p-size] x; //尾插数据p-size; //有效数据个数1
}(3) 复杂度分析
时间复杂度没有变量影响时间时间复杂度为O(1)。空间复杂度以最坏的情况考虑会进行扩容空间复杂度为O(N)。
4.4 尾删数据
同理尾删数据就是删除顺序表中最后一个元素我们只需将size–。注意删除之前要保证顺序表中有数据。 (1) 代码实现
void SeqListPopBack(SeqList* p)
{assert(p); //断言assert(p-size 0); //顺序表不能为空p-size--; //有效数据个数-1
}(2) 复杂度分析
时间复杂度没有变量影响时间时间复杂度为O(1)。空间复杂度没有变量影响空间空间复杂度为O(1)。
4.5 头插数据
头部插入数据就是在第一个元素位置插入一个元素。 (1) 代码实现
void SeqListPushFront(SeqList* p, SLDataType x)
{assert(p); //断言CheckCapacity(p); //检查顺序表容量是否已满int i 0;for (i p-size - 1; i 0; i--) //顺序表中[0,size-1]的元素依次向后挪动一位{p-a[i 1] p-a[i];}p-a[0] x; //头插数据p-size; //有效数据个数1
}(2) 复杂度分析
时间复杂度因为从头部插入数据后续数据需要依次覆盖所以时间复杂度为O(N)。空间复杂度因为可能会进行扩容按最坏的情况来算空间复杂度为O(N)。
4.5 头删数据
从头部删除数据与尾部删除数据不同需要依次往前覆盖。 (1) 代码实现
void SeqListPopFront(SeqList* p)
{assert(p); //断言assert(p-size 0); //顺序表不能为空int i 0;for (i 1; i p-size; i) //顺序表中[1,size-1]的元素依次向前挪动一位{p-a[i - 1] p-a[i];}p-size--; //有效数据个数-1
}(2) 复杂度分析
时间复杂度因为需要往前覆盖数据所以时间复杂度自然为O(N)。空间复杂度因为并没有开辟其他空间所以空间复杂度为O(1)。
4.6 查找指定值
根据输入参数在顺序表中查找指定的值并返回其下标若未找到则返回-1。
(1) 代码实现
int SeqListFind(const SeqList* p, SLDataType x)
{assert(p); //断言int i 0;for (i 0; i p-size; i){if (p-a[i] x){return i; //查找到返回该值在数组中的下标}}return -1; //没有查找到
}(2) 复杂度分析
时间复杂度以最坏的情况分析时间复杂度为O(N)。空间复杂度并没有格外的空间消耗空间复杂度为O(1)。
4.7 指定位置修改
我们可以通过指定下标或者查找指定值的下标来修改任意位置的值。 (1) 代码实现
void SeqListModify(SeqList* p, int pos, SLDataType x)
{assert(p); //断言assert(p-size 0); //顺序表不能为空assert(pos 0 pos p-size); //检查pos下标的合法性p-a[pos] x; //修改pos下标处对应的数据
}(2) 复杂度分析
时间复杂度因为是通过指定下标修改所以时间复杂度为O(1)。空间复杂度没有开辟额外的空间所以空间复杂度为O(1)。
4.8 指定位置插入
和前面其他插入一样指定位置插入也需要判断是否扩容。 (1) 代码实现
void SeqListInsert(SeqList* p, int pos, SLDataType x)
{assert(p);//断言assert(pos p-size); //检查pos下标的合法性SeqListCheck(p);//扩容int cur p-size;while (cur pos){p-a[cur] p-a[cur - 1];//覆盖--cur;}p-a[pos] x;p-size;
}(2) 复杂度分析
时间复杂度需要依次覆盖时间复杂度为O(N)。空间复杂度可能需要扩容空间复杂度为O(N)。
4.9 指定位置删除
和前面的删除差不多但是指定删除可能会依次覆盖。 (1) 代码实现
void SeqListErase(SeqList* p, int pos)
{assert(p); //断言assert(p-size 0); //顺序表不能为空assert(pos 0 pos p-size); //检查pos下标的合法性int i 0;for (i pos 1; i p-size; i) //将pos位置后面的数据依次向前挪动一位{p-a[i - 1] p-a[i];}p-size--; //有效数据个数-1
}(2) 复杂度分析
时间复杂度需要依次覆盖时间复杂度为O(N)。空间复杂度没有额外的空间消耗空间复杂度为O(1)。
4.10 回收空间
在结束操作之后需要释放开辟的空间以防止内存泄漏。
(1) 代码实现
void SeqListDestory(SeqList* p)
{assert(p); //断言free(p-a); //释放动态开辟的空间p-a NULL; //置空p-size 0; //数据个数置0p-capacity 0; //空间容量大小置0
}(2) 复杂度分析
时间复杂度没有额外的时间消耗时间复杂度为O(1)。空间复杂度没有额外的空间消耗空间复杂度为O(1)。
5. 完整代码
5.1 SeqList.h
#includestdio.h
#includestdlib.h
#includeassert.h
#define N 4 //初始化空间大小
typedef int SLDataType; //类型重命名方便后续修改类型
typedef struct SeqList
{SLDataType* a; //指向动态开辟的数组size_t size; //有效数据个数size_t capacity; //容量大小
}SeqList;void SeqListInit(SeqList* p);//初始化顺序表
void SeqListPrint(const SeqList* p);//打印顺序表
void SeqListPushBack(SeqList* p, SLDataType x);//尾插
void SeqListPopBack(SeqList* p);//尾删
void SeqListPushFront(SeqList* p, SLDataType x);//头插
void SeqListPopFront(SeqList* p);//头删
int SeqListFind(const SeqList* p, SLDataType x);//查找数据
void SeqListModify(SeqList* p, int pos, SLDataType x);//修改数据
void SeqListInsert(SeqList* p, int pos, SLDataType x);//指定插入
void SeqListErase(SeqList* p, int pos);//指定删除
void SeqListDestory(SeqList* p);//释放空间5.2 SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqList.h
void SeqListInit(SeqList* p)
{assert(p); //断言p-a (SLDataType*)malloc(N*sizeof(SLDataType)); //初始顺序表为四个空间if (p-a NULL){perror(malloc fail:);return ;}p-size 0; //初始数据个数为0p-capacity 4; //初始空间容量为4
}
void CheckCapacity(SeqList* p)
{assert(p); //断言if (p-size p-capacity) //检查容量满了则增容{size_t newcapacity 2 * p-capacity; //扩容为原来的2倍SLDataType* prt (SLDataType*)realloc(p-a, newcapacity * sizeof(SLDataType)); //扩容if (prt NULL){perror(realloc);return ;}p-a prt; // prt不为空开辟成功p-capacity newcapacity; //更新容量}
}
void SeqListPushBack(SeqList* p, SLDataType x)
{assert(p); //断言CheckCapacity(p); //检查顺序表容量是否已满p-a[p-size] x; //尾插数据p-size; //有效数据个数1
}
void SeqListPrint(const SeqList* p)
{assert(p); //断言if (p-size 0) //判断顺序表是否为空{printf(顺序表为空\n);return;}int i 0;for (i 0; i p-size; i) //打印顺序表{printf(%d , p-a[i]);}printf(\n);
}
void SeqListPopBack(SeqList* p)
{assert(p); //断言assert(p-size 0); //顺序表不能为空p-size--; //有效数据个数-1
}
void SeqListPushFront(SeqList* p, SLDataType x)
{assert(p); //断言CheckCapacity(p); //检查顺序表容量是否已满int i 0;for (i p-size - 1; i 0; i--) //顺序表中[0,size-1]的元素依次向后挪动一位{p-a[i 1] p-a[i];}p-a[0] x; //头插数据p-size; //有效数据个数1
}
void SeqListPopFront(SeqList* p)
{assert(p); //断言assert(p-size 0); //顺序表不能为空int i 0;for (i 1; i p-size; i) //顺序表中[1,size-1]的元素依次向前挪动一位{p-a[i - 1] p-a[i];}p-size--; //有效数据个数-1
}
int SeqListFind(const SeqList* p, SLDataType x)
{assert(p); //断言int i 0;for (i 0; i p-size; i){if (p-a[i] x){return i; //查找到返回该值在数组中的下标}}return -1; //没有查找到
}
void SeqListModify(SeqList* p, int pos, SLDataType x)
{assert(p); //断言assert(p-size 0); //顺序表不能为空assert(pos 0 pos p-size); //检查pos下标的合法性p-a[pos] x; //修改pos下标处对应的数据
}
void SeqListInsert(SeqList* p, int pos, SLDataType x)
{assert(p);//断言assert(pos p-size); //检查pos下标的合法性SeqListCheck(p);//扩容int cur p-size;while (cur pos){p-a[cur] p-a[cur - 1];//覆盖--cur;}p-a[pos] x;p-size;
}
void SeqListErase(SeqList* p, int pos)
{assert(p); //断言assert(p-size 0); //顺序表不能为空assert(pos 0 pos p-size); //检查pos下标的合法性int i 0;for (i pos 1; i p-size; i) //将pos位置后面的数据依次向前挪动一位{p-a[i - 1] p-a[i];}p-size--; //有效数据个数-1
}
void SeqListDestory(SeqList* p)
{assert(p); //断言free(p-a); //释放动态开辟的空间p-a NULL; //置空p-size 0; //数据个数置0p-capacity 0; //空间容量大小置0
}
