|
#include<iostream>
#include<string>
#include<cstdlib>
#include<iomanip>
using namespace std;
template<class T>
class SqureList
{
private:
?? ?int m_length; ? //元素数量
?? ?int m_capicity; ?//容量(开辟的内存)
?? ?T *m_List; ?//存储元素
public:
?? ?SqureList();
?? ?~SqureList();
?? ?int GetCapicity(); ?//获取线性表的容量
?? ?int SetCapicity(int capicity); ?//设置线性表的容量
?? ?int Getlength(); ? ? ? ? //获取线性表的当前长度
?? ?bool push_back(T elemnum); ? ? //尾插法插入元素
?? ?bool GetElem(int index,T *e); ? ?//获取线性表的相应下标的元素
?? ?bool For_each();//遍历输出线性顺序表
?? ?bool IsEmpty(); ?//查询线性表是否为空
?? ?bool ClearSq(); ?//清空顺序表
?? ?bool Insert(T elemnum, int i); ?//向指定位置插入元素
?? ?bool Remove(int i,T*e);//删除并返回线性表的第i个下标位置的元素。
?? ?int find_elem(T elemnum);//查找指定元素返回线性表中元素首次出现的下标位置
?? ?
};
int main(int agrc, char* agrv[])
{
?? ?SqureList<string> kk;
?? ?string k[5];
?? ?kk.push_back("asd");
?? ?kk.push_back("dsdd");
?? ?kk.Insert("sasa",1);
?? ?kk.Insert("kkk", 1);
?? ?kk.Insert("jjjj", 1);
?? ?kk.Remove(2, &k[0]);
?? ?//kk.Remove(2, &k[0]);
?? ?//kk.Remove(2, &k[0]);
?? ?kk.Remove(1, &k[0]);
?? ?/*kk.GetElem(0, &k[0]);
?? ?kk.GetElem(1, &k[1]);
?? ?kk.GetElem(2, &k[2]);
?? ?kk.GetElem(3, &k[3]);
?? ?kk.GetElem(4, &k[4]);
?? ?cout << k[0] << " ?" << k[1] << " ?" << k[2]<<" ?"<<k[3]<<" ?"<<k[4] << endl;*/
?? ?kk.For_each();
?? ?cout << kk.find_elem("sasa") << endl;
?? ?cout << kk.GetCapicity() << endl;
?? ?return 0;
}
//构造函数
template<class T>
SqureList<T>::SqureList()
{
?? ?this->m_capicity = 4;
?? ?this->m_List = new T[this->m_capicity];
?? ?this->m_length = 0;
}
//析构函数
template<class T>
SqureList<T>::~SqureList()
{
?? ?delete[] this->m_List; // 释放数组内存
?? ?this->m_List = NULL;
}
//设置顺序表的容量
template<class T>?
int SqureList<T>::SetCapicity(int capicity)
{
?? ?if (this->m_length == 0)
?? ?{
?? ??? ?this->m_List = new T[capicity];
?? ??? ?this->m_capicity = capicity;
?? ??? ?return this->m_capicity;
?? ?}
? ? T* temp = this->m_List;
?? ?this->m_List = new T[capicity];
?? ?this->m_capicity = capicity;
?? ?for (int i = 0; i < this->m_length; i++)
?? ?{
?? ??? ?this->m_List[i] = temp[i]; ? ? ? ? ? ? ? ? ??
?? ?}
?? ?delete[] temp;
?? ?temp = NULL;
?? ?return this->m_capicity;
}
//获取当前顺序表的容量
template<class T>
int SqureList<T>::GetCapicity()
{
?? ?return this->m_capicity;
} ??
? //尾插法插入元素，定容，应修改为自动变容
template<class T>
bool SqureList<T>::push_back(T elemnum) ?
{
?? ?if ((this->m_length) == (this->m_capicity))
?? ?{
?? ??? ?(this->m_capicity) *= 2;
?? ??? ?this->SetCapicity(this->m_capicity);
?? ?}
?? ?this->m_List[m_length] = elemnum;
?? ?this->m_length++;
?? ?return true;
}
//向指定位置插入元素（变容修改）
template<class T>
bool SqureList<T>::Insert(T elemnum, int i)
{
?? ?if (i<0 || i>this->m_length)
?? ?{
?? ??? ?return false; ?//下标越界（小于零，或比最后元素的下标+1 还大）
?? ?}
?? ?if ((this->m_length) == (this->m_capicity)) ?//容量扩展
?? ?{
?? ??? ?(this->m_capicity) *= 2;
?? ??? ?this->SetCapicity(this->m_capicity);
?? ?}
?? ?for (int j = this->m_length; j >i;j--) ?//将下标i在内的后续所有元素后移一位
?? ?{
?? ??? ?this->m_List[j] = this->m_List[j-1];
?? ?}
?? ?this->m_List[i] = elemnum;
?? ?this->m_length++;
?? ?return true;
}
//获取指定下标元素,从零开始，失败返回false
template<class T>
bool SqureList<T>::GetElem(int index,T *e) ?
{
?? ?if (index<0||index >= m_length)
?? ?{
?? ??? ?return false;
?? ?}
?? ?else
?? ?{
?? ??? ?*e = this->m_List[index];
?? ??? ?return true;
?? ?}
}
//遍历输出线性顺序表
template<class T>
bool SqureList<T>::For_each() ?//遍历输出线性顺序表
{
?? ?if (this->m_length == 0)return false;
?? ?T temp;
?? ?for (int i = 0; i < this->m_length-1; i++)
?? ?{
?? ??? ?this->GetElem(i, &temp);
?? ??? ?cout << temp << ",";
?? ?}
?? ?this->GetElem(this->m_length - 1, &temp);
?? ?cout << temp << endl;
?? ?return true;
}
//获取线性表的当前长度
template<class T>
int SqureList<T>::Getlength() ? ? ? ? //获取线性表的当前长度
{
?? ?return this->m_length;
}
//判断线性表是否为空
template<class T>
bool SqureList<T>::IsEmpty()
{
?? ?if (this->Getlength() == 0)
?? ??? ?return true;
?? ?else
?? ?{
?? ??? ?return false;
?? ?}
}
//清空顺序表
template<class T>
bool SqureList<T>::ClearSq()
{
?? ?this->m_length = 0;
}
//删除并返回线性表的第i个下标位置的元素。
template<class T>
bool SqureList<T>::Remove(int i,T *e) ?//删除并返回线性表的第i个下标位置的元素。
{
?? ?if (i < 0 || i >= this->m_length)
?? ?{
?? ??? ?return false; ?//下标越界
?? ?}
?? ?*e = this->m_List[i];
?? ?for (int j = i; j < this->m_length-1; j++)
?? ?{
?? ??? ?this->m_List[j] = this->m_List[j + 1];
?? ?}
?? ?this->m_length--;
?? ?if (this->m_length < (this->m_capicity) / 4)
?? ?{
?? ??? ?this->SetCapicity(this->m_capicity / 2);
?? ?}
?? ?return true;
}
//查找指定元素返回线性表中元素首次出现的下标位置
template<class T>
int SqureList<T>::find_elem(T elemnum)//查找指定元素返回线性表中元素首次出现的下标位置
{
?? ?int index = -1;
?? ?for (int i = 0; i < this->m_length; i++)
?? ?{
?? ??? ?if (this->m_List[i] == elemnum)
?? ??? ?{
?? ??? ??? ?index = i;
?? ??? ??? ?break;
?? ??? ?}
?? ?}
?? ?return index;
}
|