密云重庆网站建设,网站有了域名然后怎么做,旅游做的视频网站,网站自动生成系统顺序表的模拟实现 文章目录顺序表的模拟实现1.线性表2.顺序表2.1概念结构2.2顺序表的模拟实现2.2.1顺序表的初始化2.2.2顺序表的销毁2.2.3尾插数据2.2.4尾删数据2.2.5头插数据2.2.6头删数据2.2.7中间插入数据2.2.8中间删除数据2.2.9打印顺序表2.2.10查找数据2.2.11复用Insert和…顺序表的模拟实现 文章目录顺序表的模拟实现1.线性表2.顺序表2.1概念结构2.2顺序表的模拟实现2.2.1顺序表的初始化2.2.2顺序表的销毁2.2.3尾插数据2.2.4尾删数据2.2.5头插数据2.2.6头删数据2.2.7中间插入数据2.2.8中间删除数据2.2.9打印顺序表2.2.10查找数据2.2.11复用Insert和Erase实现尾部操作和头部操作2.3顺序表的优缺点3.顺序表OJ题目训练1.线性表 线性表 linear list 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑结构是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 ps 逻辑结构想象的该数据结构在内存中的存储方式逻辑结构便于我们的思考。 物理结构实际的该数据结构在内存中的存储方式。 例如C语言中的二维数组int arr[M][N] 逻辑结构M行N列的元素集合不是连续存放的 物理结构1行M*N列的元素集合是连续存放的 线性表在物理上存储时通常以数组和链式结构的形式存储。 2.顺序表 2.1概念结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为 静态顺序表使用定长数组存储元素。(静态数组) 动态顺序表使用动态开辟的数组存储。(malloc动态开辟空间)
2.2顺序表的模拟实现 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。 SeqList.h中的声明(因为需要通过函数来修改顺序表所以要传址)
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLDateType;//顺序表的成员
typedef struct SeqList
{SLDateType* a;//顺序表的首元素地址size_t size;//顺序表的数据个数size_t capacity;//顺序表的容量
}SL;void SLInit(SL* ps);//顺序表的初始化void SLDestroy(SL* ps);//顺序表的销毁//尾部操作
void SLPushBack(SL* ps, SLDateType x);//尾插
void SLPopBack(SL* ps);//尾删//头部操作
void SLPushFront(SL* ps, SLDateType x);//头插
void SLPopFront(SL* ps);//头删//中间
size_t SLFind(SL* ps, SLDateType x);//查找(返回下标)
void SLInsert(SL* ps, size_t pos, SLDateType x);//在pos前插入数据x
void SLErase(SL* ps, size_t pos);//删除pos处的数据void SLPrint(SL* ps);//打印顺序表SeqList.c结构功能实现
包含头文件#includeSeqList.h
2.2.1顺序表的初始化
void SLInit(SL* ps)//顺序表的初始化
{assert(ps);ps-a NULL;ps-size 0;ps-capacity 0;
}2.2.2顺序表的销毁
ps由于是动态开辟的空间使用完要还给操作系统不然会造成内存泄漏。
void SLDestroy(SL* ps)//顺序表的销毁
{assert(ps);free(ps-a);ps-a NULL;ps-size 0;ps-capacity 0;
}2.2.3尾插数据
void Enhance(SL* ps)
{size_t newcapacity (ps-capacity 0) ? 4 : ps-capacity * 2;//如果容量为0开辟4否则两倍开辟SLDateType* tmp (SLDateType*)realloc(ps-a, sizeof(SLDateType)*newcapacity);//这里要考虑异地增容的情况if (tmp NULL)//增容失败{perror(realloc fail\n);return;}else{ps-a tmp;ps-capacity newcapacity;}
}void SLPushBack(SL* ps, SLDateType x)//尾插
{assert(ps);//防止ps为空进行断言//考虑增容if (ps-size ps-capacity)//空间不足时需要增容{Enhance(ps);}ps-a[ps-size] x;
}ps顺序表插入操作都要检查是否需要增容
时间复杂度O(1) 2.2.4尾删数据
void SLPopBack(SL* ps)//尾删
{assert(ps);assert(ps-size 0);//顺序表为空则不可继续再删除--(ps-size);
}ps顺序表的删除操作都要检查是是否为空顺序表
时间复杂度O(1) 2.2.5头插数据
void SLPushFront(SL* ps, SLDateType x)//头插
{assert(ps);//考虑增容if (ps-size ps-capacity){Enhance(ps);}//挪动数据size_t end ps-size;while (end 0){ps-a[end] ps-a[end - 1];--end;}//插入数据ps-a[end] x;(ps-size);
}ps由于顺序表是连续存储的在头部插入数据时需要将整体数据向后挪动一次再将数据插入到头部 时间复杂度O(N) 2.2.6头删数据
void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps-size 0);//挪动数据--(ps-size);size_t begin 0;while (begin ps-size){ps-a[begin] ps-a[begin 1];begin;}}ps头删数据将后面的数据向前移动将第一个数据覆盖即可 时间复杂度O(N) 2.2.7中间插入数据
void SLInsert(SL* ps, size_t pos, SLDateType x)//中间插
{assert(ps);assert(pos 0 pos ps-size);//0是头插等于ps-size是尾插//考虑增容if (ps-size ps-capacity){Enhance(ps);}//挪动数据size_t cur ps-size;while (cur pos){ps-a[cur] ps-a[cur - 1];--cur;}//插入ps-a[cur] x;(ps-size);}ps中间插入数据同样也需要向后挪动数据
时间复杂度O(N) 2.2.8中间删除数据
void SLErase(SL* ps, size_t pos)//中间删
{assert(ps);assert(pos 0 pos ps-size);//等于0相等于头删等于ps-size-1等于尾删//assert(ps-size 0);//对pos的检查间接检查了size要大于0--(ps-size);size_t cur pos;while (cur ps-size){ps-a[cur] ps-a[cur 1];cur;}
}ps中间删除数据同样也需要向前挪动数据
时间复杂度O(N) 2.2.9打印顺序表
void SLPrint(const SL* ps)//打印顺序表
{assert(ps);for (size_t i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}2.2.10查找数据
size_t SLFind(const SL* ps, SLDateType x)//查找(返回下标)
{assert(ps);for (size_t i 0; i ps-size; i){if (ps-a[i] x){return i;}}return EOF;//找不到
}2.2.11复用Insert和Erase实现尾部操作和头部操作
Insert和Erase功能中是包含了尾部操作和头部操作的所以尾部操作和头部操作可以使用Insert和Erase来复用
void SLPushBack(SL* ps, SLDateType x)//尾插
{SLInsert(ps, ps-size, x);
}void SLPopBack(SL* ps)//尾删
{SLErase(ps, ps-size - 1);
}void SLPushFront(SL* ps, SLDateType x)//头插
{SLInsert(ps, 0, x);
}void SLPopFront(SL* ps)//头删
{SLErase(ps, 0);
}2.3顺序表的优缺点
优点
1. 尾插和尾删的效率很高时间复杂度为O(1) 2. 支持随机访问知道了一个元素的下标就可以直接访问和修改 缺点 1. 头部操作和中间操作中需要挪动数据时间复杂度为O(N)效率较低 2. 增容会带来一定的性能消耗特别是异地增容代价是极大的 3. 2倍增容方式会有一部分的空间浪费 3.顺序表OJ题目训练
原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)。OJ链接删除排序数组中的重复项。OJ链接合并两个有序数组。OJ链接
