C28.【C++ Cont】顺序表的实现
🧨🧨🧨🧨🧨🧨🧨🧨🧨初二篇🧨🧨🧨🧨🧨🧨🧨🧨🧨
目录
1.知识回顾
2.静态方式实现顺序表
创建和初始化
打印
尾插
头插
任意位置插入
尾删
头删
任意位置删除
查找指定下标位置的元素(即随机访问,不需要从数组的起始位置逐个遍历)
查找指定的值是否存在
修改元素
清空顺序表
3.封装静态顺序表
4.测试代码
运行结果
1.知识回顾
82.【C语言】数据结构之顺序表的初始化和销毁
83.【C语言】数据结构之顺序表的尾部插入和删除
84.【C语言】数据结构之顺序表的头部插入和删除
85.【C语言】数据结构之顺序表的中间插入和删除及遍历查找
上面是用动态申请的方法实现的,在竞赛中不使用,竞赛中使用STL库,下篇会讲
2.静态方式实现顺序表
在竞赛中由于动态申请内存空间操作过多(空间的申请和释放,数据的拷贝)运行速度慢,效率低,因此使用静态实现,创建一个足够大空间的数组
实现时注意特殊情况:
1.顺序表已满,不能插入
2.无论是指定位置插入、删除还是修改,指定位置index的取值一定要合理!
3.空表不能删除
创建和初始化
const int N = 1e6;//控制数组的大小,按实际情况而定
class SeqList
{
int a[N];
int num;//记录数组元素的个数
public:
SeqList()//构造函数初始化
{
num = 0;
}
//......
}下面直接写自定义函数
打印
void print_seqlist()
{
if (num == 0)
{
cout << "NULL" << endl;
return;
}
for (int i = 0; i < num; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}尾插
void push_back(int data)//尾插
{
if (num > N)
{
cout << "顺序表已满,禁止尾插" << endl;
return;
}
arr[++num] = data;//注意是前置++!!!
}注意是前置++!!!
头插
从后向前覆盖
void push_front(int data)//头插
{
if (num > N)
{
cout << "顺序表已满,禁止头插" << endl;
return;
}
for (int i = num; i >= 0; i--)
{
arr[i+1] = arr[i];//最后一次是arr[0]=arr[1],以此来确定循环结束的条件
}
arr[0] = data;
num++;
}任意位置插入
void insert(int index, int data)//中间插入,在index处插入(index最小取0)
{
if (num > N)
{
cout << "顺序表已满,禁止头插" << endl;
return;
}
if (index < 0 || index >= num)//排除index的非法取值
{
cout << "index的取值非法,禁止插入" << endl;
return;
}
for (int i = num; i >= index; i--)
{
arr[i + 1] = arr[i];//最后一次是arr[index+1]=arr[index],以此来确定循环结束的条件
}
arr[index] = data;
num++;
}尾删
void pop_back()//尾删
{
if (num == 0)
{
cout << "顺序表为空,禁止尾删" << endl;
return;
}
num--;//不用改动arr[num-1]
}头删
void pop_front()//头删
{
if (num == 0)
{
cout << "顺序表为空,禁止尾删" << endl;
return;
}
for (int i = 1; i <= num-1; i++)
{
arr[i-1] = arr[i];//最后一次为arr[num-2]=arr[num-1],以此来确定循环结束的条件
}
num--;
}
任意位置删除
void erase(int index)//任意位置index删除
{
if (index < 0 || index >= num)
{
cout << "index的取值非法, 禁止删除" << endl;
return;
}
if (num == 0)
{
cout << "顺序表为空,禁止删除" << endl;
return;
}
for (int i = index+1; i <= num-1; i++)
{
arr[i - 1] = arr[i];//最后一次是arr[num-2]=arr[num-1],以此来确定循环结束的条件
}
num--;
}查找指定下标位置的元素(即随机访问,不需要从数组的起始位置逐个遍历)
int find_index(int index)//查找指定下标位置的元素
{
if (index < 0 || index >= num)
{
cout << "index的取值非法, 无法查找" << endl;
return -1;
}
if (num == 0)
{
cout << "顺序表为空, 无法查找" << endl;
return -1;
}
return arr[index];
}查找指定的值是否存在
void find_data(int data)//查找指定的值是否存在
{
if (num == 0)
{
cout << "顺序表为空, 无法查找" << endl;
return;
}
for (int i = 0; i < num; i++)
{
if (arr[i] == data)
{
cout << data << "在下标为" << i << "处" << endl;
}
}
}修改元素
void change(int index, int data)//修改指定下标处的元素
{
if (num == 0)
{
cout << "顺序表为空, 无法修改" << endl;
return;
}
if (index < 0 || index >= num)
{
cout << "index的取值非法, 无法查找" << endl;
return;
}
arr[index] = data;
}清空顺序表
写入析构函数
~SeqList()
{
num = 0;
}3.封装静态顺序表
直接使用结构体或类封装
const int N = 1e2;//控制数组的大小,按实际情况而定
class SeqList
{
int arr[N];
int num;//记录数组元素的个数
public:
SeqList()//构造函数初始化
{
num = 0;
}
void print_seqlist()
{
//......
}
void push_back(int data)//尾插
{
//......
}
void push_front(int data)//头插
{
//......
}
void insert(int index, int data)//中间插入,在index处插入(index最小取0)
{
//......
}
void pop_back()//尾删
{
//......
}
void pop_front()//头删
{
//......
}
void erase(int index)//任意位置index删除
{
//......
}
int find_index(int index)//查找指定下标位置的元素
{
//......
}
void find_data(int data)//查找指定的值是否存在
{
//......
}
void change(int index, int data)//修改指定下标处的元素
{
//......
}
~SeqList()
{
num = 0;
}
};4.测试代码
int main()
{
SeqList sq;
sq.push_front(2);
sq.push_front(1);
sq.push_front(3);
sq.push_front(4);
sq.print_seqlist();
sq.pop_front();
sq.pop_front();
sq.pop_front();
sq.pop_front();
sq.pop_front();
sq.insert(2, 5);
sq.erase(2);
sq.print_seqlist();
sq.push_front(2);
sq.push_front(1);
sq.push_front(3);
sq.push_front(4);
sq.insert(2, 5);
sq.erase(2);
sq.print_seqlist();
}类似上方代码,STL也可以通过 "." 调用各种各样的接口
运行结果
🎉❤️🎉❤️🎉❤️🎉❤️🎉❤️祝各位码农们蛇年大吉 巳巳如意!❤️🎉❤️🎉❤️🎉❤️🎉❤️🎉