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也可以通过 "." 调用各种各样的接口

运行结果

🎉❤️🎉❤️🎉❤️🎉❤️🎉❤️祝各位码农们蛇年大吉 巳巳如意!❤️🎉❤️🎉❤️🎉❤️🎉❤️🎉