数据结构之线性表操作(C++)

╰+攻爆jí腚メ 2022-01-17 06:01 384阅读 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();
    }