#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; }
完成m_arr、m_capacity、m_size的初始化;
释放m_arr后即置空。实际上,我认为,后面将m_capacity和m_size都置为0其实没有必要,因为实际上销毁这个顺序表对象后,我要用顺序表时,会重新实例化一个的。并且销毁对象,一般来说就是delete对象指针时,或函数结束时。
依次打出即可。
在增加和插入元素的环节中,当容量与实际现有大小将要(解释一下“将要”:还有一个元素之差时。因为增加和插入环节一次只能插入一个)相等时,需要调整容量。直接封装出去。
如果用二分查找效率更高,但是我们需要先对数组进行排序,排序在不同的情境下会起到截然相反的效果,有时是使数据更有序的行为,但有时是破环原来数据的顺序的行为。并且实际上,我对二分查找的边界问题还是处于不解状态,于是选择使用遍历进行查找元素的操作,找到返回位置,没找到返回-1;并且使用断言来防止输入的pos不规范。
首先用断言对输入的pos进行检查,在pos这个位置进行覆盖修改。