- 首页 > it技术 > >
#include
using namespace std;
//线性表的抽象数据类型定义
template
class List {
public:
virtual void clear() = 0;
//清空线性表
virtual bool empty() const = 0;
//判空,真返回true,非空返回false
virtual int size() const = 0;
//求线性表的长度
virtual void insert(int i, const T& value) = 0;
//在位序i处插入元素,值为value
virtual void remove(int i) = 0;
//位序i处删除元素
virtual int search(const T& value) const = 0;
//查找值为value的元素第一次出现的位序
virtual void traverse() const = 0;
//遍历线性表
virtual void inverse() = 0;
//匿置线性表
virtual ~List() {};
};
//自定义异常处理类
class outOfRange :public exception {//用于检查范围的有效性
public:
const char* what() const throw() {
return "ERROR! OUT OF RANGE.\n";
}
};
class badSize :public exception {//用于检查长度的有效性
public:
const char* what() const throw() {
return "ERROR! BAD SIZE.\n";
}
};
/*
顺序表的类型定义
*/
template //elemType为顺序表存储的元素类型
class seqList : public List {
private:
elemType* data;
//动态数组
int curLength;
//当前顺序表中存储的元素个数
int maxSize;
//顺序表最大长度
void resize();
//表满时,扩大表空间public:
seqList(int initSize = 10);
//构造函数
seqList(seqList& s1);
//拷贝构造函数
~seqList() { delete[] data;
}//析构函数
void clear() { curLength = 0;
}//清空表
bool empty() const { return curLength == 0;
} //判空
int size() const { return curLength;
}//返回顺序表中当前存储元素的个数 void traverse() const;
//遍历顺序表
void inverse();
//匿置顺序表
void insert(int i, const elemType& value);
//在位序i处插入值为value的元素,表长加1 void remove(int i);
//删除位序为i处的元素,表长减一
int search(const elemType& value) const;
//查找值为value的元素第一次出现的位序 bool Union(seqList & B);
//合并顺序表
};
/*
构造函数
*/
template
seqList::seqList(int initSize) {
if (initSize <= 0) throw badSize();
maxSize = initSize;
data = https://www.it610.com/article/new elemType[maxSize];
curLength = 0;
}/*
拷贝构造函数(自定义实现深拷贝)
*/
template
seqList::seqList(seqList & s1) {
maxSize = s1.maxSize;
curLength = s1.curLength;
data = https://www.it610.com/article/new elemType[maxSize];
//动态分配内存资源
for (int i = 0;
i < curLength;
i++) {
data[i] = s1.data[i];
}
}/*遍历顺序表*/
template
void seqList::traverse() const{
if (empty()) cout << "is empty!" << endl;
else {
//cout << "Output element: " << endl;
for (int i = 0;
i < curLength;
i++) {
cout << data[i] << "";
}
cout << endl;
}
}/*
查找值为value的元素
顺序查找值为value的元素在线性表中第一次出现的位置,遍历线性表中元素
若value=https://www.it610.com/article/=data[i],则查找成功,返回data[i]的位序,否则查找失败返回-1.
*/
template
int seqList::search(const elemType& value) const {
for (int i = 0;
i < curLength;
i++) {
if (value =https://www.it610.com/article/= data[i]) return i;
}
return -1;
//查找失败返回-1
}/**
插入运算:指定位序插入一个值为value的新元素
*/
template
void seqList::insert(int i, const elemType& value) {
if (i<0 || i>curLength) throw outOfRange();
if (curLength == maxSize) resize();
for (int j = curLength;
j > i;
j--) {
data[j] = data[j - 1];
//下标在[curLength-1...i]范围内的元素后移一步.
}
data[i] = value;
//将值为value的元素放置在位序为i的位置上
++curLength;
//表的长度加1
}/*
移除指定位置的值
*/
template
void seqList::remove(int i) {
if (i<0 || i>curLength) throw outOfRange();
for (int j = i;
j < curLength-1;
j++) {
data[j] = data[j+1];
}
--curLength;
//表的长度减1
}/*
匿置运算:
*/
template
void seqList::inverse() {
elemType temp;
for (int i = 0;
i < curLength / 2;
i++) {
temp = data[i];
data[i] = data[curLength - i - 1];
data[curLength - i - 1] = temp;
}
}/*
扩大表空间
*/
template
void seqList::resize() {
elemType* p = data;
//p指向原来顺序表空间
maxSize *= 2;
//表空间扩大为原来的二倍
data = https://www.it610.com/article/new elemType[maxSize];
//data指向新的表空间
for (int i = 0;
i < curLength;
i++) {
data[i] = p[i];
//元素拷贝
}
delete[] p;
}/*
合并两个有序线性表*/
template
bool seqList::Union(seqList &B) {
intm, n, k, i, j;
m = this->curLength;
//当前线性表长度
n = B.curLength;
//与之合并的线性表长度
k = m + n - 1;
//k为结果线性表的工作指针(下标)
i = m - 1;
j = n - 1;
//i,j分别为指向线性表a和b的指针(下标)
if (m + n > this->maxSize) {//判断a空间是否足够大
resize();
//扩大表空间
}
while (i >= 0 && j >= 0)//合并顺序表,直到有一个表为空
if (data[i] >= B.data[j]) {
data[k--] = data[i--];
}
else {
data[k--] = B.data[j--];
//默认当前对象,this指针可以省略
}
while (j >= 0)
data[k--] = B.data[j--];
curLength = m + n;
//修改表的长度
return true;
}int main() {
seqList *sq = new seqList(10);
for (int i = 0;
i < 5;
i++) {
sq->insert(i, i + 10);
}
cout << "线性表遍历:";
sq->traverse();
cout << "线性表长度:";
cout << sq->size();
/*cout << "\n指定位置插入指定值:" ;
sq->insert(2, 1999);
sq->traverse();
*/ /*cout << "线性表反转:";
sq->inverse();
sq->traverse();
*/ cout << "\n查询指定元素值的位序:";
int num=sq->search(10);
cout << num;
cout << "\n移除指定位序处的值:";
sq->remove(2);
sq->traverse();
cout << "合并两n个线性表:";
seqList *B = new seqList(10);
for (int i = 0;
i < 5;
i++) {
B->insert(i, 10 + i);
}
sq->Union(*B);
sq->traverse();
}
推荐阅读
