数据结构之线性表操作(C++) ╰+攻爆jí腚メ 2022-01-17 06:01 323阅读 0赞 #include<iostream> using namespace std; //线性表的抽象数据类型定义 template <typename T> 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 <typename elemType> //elemType为顺序表存储的元素类型 class seqList : public List<elemType> { 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<elemType> & B); //合并顺序表 }; /* 构造函数 */ template <typename elemType> seqList<elemType>::seqList(int initSize) { if (initSize <= 0) throw badSize(); maxSize = initSize; data = new elemType[maxSize]; curLength = 0; } /* 拷贝构造函数(自定义实现深拷贝) */ template <typename elemType> seqList<elemType>::seqList(seqList & s1) { maxSize = s1.maxSize; curLength = s1.curLength; data = new elemType[maxSize]; //动态分配内存资源 for (int i = 0; i < curLength; i++) { data[i] = s1.data[i]; } } /*遍历顺序表*/ template <typename elemType> void seqList<elemType>::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==data[i],则查找成功,返回data[i]的位序,否则查找失败返回-1. */ template <typename elemType> int seqList<elemType>::search(const elemType& value) const { for (int i = 0; i < curLength; i++) { if (value == data[i]) return i; } return -1; //查找失败返回-1 } /** 插入运算:指定位序插入一个值为value的新元素 */ template <class elemType> void seqList<elemType>::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 <typename elemType> void seqList<elemType>::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 <typename elemType> void seqList<elemType>::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 <typename elemType> void seqList<elemType>::resize() { elemType* p = data; //p指向原来顺序表空间 maxSize *= 2; //表空间扩大为原来的二倍 data = new elemType[maxSize]; //data指向新的表空间 for (int i = 0; i < curLength; i++) { data[i] = p[i]; //元素拷贝 } delete[] p; } /* 合并两个有序线性表*/ template <typename elemType> bool seqList<elemType>::Union(seqList<elemType> &B) { int m, 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<int> *sq = new seqList<int>(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<int> *B = new seqList<int>(10); for (int i = 0; i < 5;i++) { B->insert(i, 10 + i); } sq->Union(*B); sq->traverse(); }
还没有评论,来说两句吧...