文章目录
一、头文件声明部分
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#include<iostream>
#include<cassert>
using namespace std;
typedef int DataType;
class Seqlist
{
public:
Seqlist();//初始化工作
~Seqlist();//收尾工作
void SeqlistPrint();//打印出顺序表中元素
void AdjustCapacity();//调整容量
//增删插查改
void SeqlistPushBack(int val);//尾插
void SeqlistPushFront(int val);//头插
void SeqlistInsert(int pos, int val);//在特定位置插入元素
void SeqlistPopBack();//尾删
void SeqlistPopFront();//头删
void SeqlistErase(int pos);//删除特定位置的元素
int SeqlistFind(int val);//查找元素
void SeqlistModify(int pos, int val);//修改特定位置的元素
private:
DataType* m_arr;
int m_size;
int m_capacity;
};
#endif
二、源文件实现部分
#include "Seqlist.h"
Seqlist::Seqlist() //初始化工作
{
this->m_arr = NULL;
this->m_capacity = 0;
this->m_size = 0;
}
Seqlist::~Seqlist()//收尾工作
{
delete []this->m_arr;
this->m_arr = NULL;
this->m_capacity = 0;
this->m_size = 0;
}
void Seqlist::SeqlistPrint()//打印出顺序表中元素
{
for (int i = 0; i < this->m_size; i++)
{
cout << this->m_arr[i] << ' ';
}
}
void Seqlist::AdjustCapacity()//调整容量
{
if (this->m_capacity == this->m_size)
{
int newCapacity = this->m_capacity == 0 ? 4 : this->m_capacity << 1;
try
{
DataType* tmp = new DataType[newCapacity];
this->m_capacity = newCapacity;
for (int i = 0; i < this->m_size; i++)
{
tmp[i] = this->m_arr[i];
}
delete []this->m_arr;
this->m_arr = tmp;
}
catch (bad_alloc& e)
{
cout << "bad_alloc caught: " << e.what() << endl;
}
//或者像下面这样，开辟内存失败后，返回空指针
//DataType* tmp = new(nothrow) DataType[newCapacity];
//if (NULL == tmp)
//{
// cout << "开辟内存失败" << endl;
// exit(-1);
//}
//this->m_capacity = newCapacity;
//for (int i = 0; i < this->m_size; i++)
//{
// tmp[i] = this->m_arr[i];
//}
//delete[]this->m_arr;
//this->m_arr = tmp;
}
}
//增删插查改
void Seqlist::SeqlistPushBack(int val)//尾插
{
AdjustCapacity();
this->m_arr[this->m_size] = val;
this->m_size++;
//this->SeqlistInsert(this->m_size, val);
}
void Seqlist::SeqlistPushFront(int val)//头插
{
AdjustCapacity();
int end = this->m_size - 1;
for (int i = end; i >= 0; i--)
{
this->m_arr[i + 1] = this->m_arr[i];
}
this->m_arr[0] = val;
this->m_size++;
//this->SeqlistInsert(0, val);
}
void Seqlist::SeqlistInsert(int pos, DataType val)//在特定位置插入元素
{
AdjustCapacity();
assert(pos <= this->m_size && pos >= 0);
int end = this->m_size - 1;
for (int i = end; i >= pos; i--)
{
this->m_arr[end - 1] = this->m_arr[end];
}
this->m_arr[pos] = val;
this->m_size++;
}
void Seqlist::SeqlistPopBack()//尾删
{
assert(this->m_size > 0);
this->m_size--;
//this->SeqlistErase(this->m_size - 1);
}
void Seqlist::SeqlistPopFront()//头删
{
assert(this->m_size > 0);
for (int i = 0; i < this->m_size; i++)
{
this->m_arr[i] = this->m_arr[i + 1];
}
this->m_size--;
//this->SeqlistErase(0);
}
void Seqlist::SeqlistErase(int pos)//删除特定位置元素
{
assert(pos < this->m_size && pos >= 0);
for (int i = pos; i < this->m_size; i++)
{
this->m_arr[i] = this->m_arr[i + 1];
}
this->m_size--;
}
int Seqlist::SeqlistFind(DataType val)//查找元素
{
for (int i = 0; i < this->m_size; i++)
{
if (val == this->m_arr[i])
{
return i;
}
}
return -1;
}
void Seqlist::SeqlistModify(int pos, DataType val)//修改特定位置元素
{
assert(pos < this->m_size&& pos >= 0);
this->m_arr[pos] = val;
}
三、分析
1、初始化工作
完成m_arr、m_capacity、m_size的初始化；
2、收尾工作
释放m_arr后即置空。实际上，我认为，后面将m_capacity和m_size都置为0其实没有必要，因为实际上销毁这个顺序表对象后，我要用顺序表时，会重新实例化一个的。并且销毁对象，一般来说就是delete对象指针时，或函数结束时。
3、打印出顺序表中元素
依次打出即可。
4、调整容量
Ⅰ该环节在全局规划的分析
在增加和插入元素的环节中，当容量与实际现有大小将要（解释一下“将要”：还有一个元素之差时。因为增加和插入环节一次只能插入一个）相等时，需要调整容量。直接封装出去。
Ⅱ环节内容分析
- 首先要注意new的使用，new存在失败的情况，于是我做了相关处理，有两个解决方案，第一个是代码处未注释掉的内容，new在失败后会扔出一个异常；第二个是代码处注释掉的内容，通过使用语句“std::nothrow”让new在失败后返回一个空指针而不是异常，回顾：在C语言中malloc失败后，返回的就是空指针。
- 其次注意在new成功后的扩容操作，我们创建了一个临时的容量，转移数据，释放原容量，指针替换。
5、尾插、头插、特定位置插入
- 尾插：正因为数组是从0开始的，而数组的大小是从1开始的，于是我们可以在最后数组m_size的位置插入新元素。最后m_size加一。
- 头插：先有一个原地移动数组（出了第一个元素外）的操作，在数组第一个元素的位置上覆盖上新元素。
- 特定位置插入：同样是先原地移动数组后，覆盖上新元素。使用断言来防止输入的pos不规范。
- 补充：完全可以通过限制特定位置插入的功能来实现尾插和头插。注释部分即是这样实现的。
6、尾删、头删、特定位置删除
- 尾删：直接使用m_size减一的举措来达到目的，这都要归功于我们通过m_size来限制数组的访问范围的操作。
- 头删：首先通过原地向前移动数组来覆盖掉第一个元素，然后通过m_size减一来限制访问数组权限。
- 特定位置删除：原地移动数组覆盖。使用断言来防止输入的pos不规范。
- 补充：同“尾插、头插、特定位置插入”环节中的补充思想一样。
7、查找元素
如果用二分查找效率更高，但是我们需要先对数组进行排序，排序在不同的情境下会起到截然相反的效果，有时是使数据更有序的行为，但有时是破环原来数据的顺序的行为。并且实际上，我对二分查找的边界问题还是处于不解状态，于是选择使用遍历进行查找元素的操作，找到返回位置，没找到返回-1；并且使用断言来防止输入的pos不规范。
8、特定位置修改
首先用断言对输入的pos进行检查，在pos这个位置进行覆盖修改。