X.4作业

  • 参考C++标准库的string构造一个自定义的字符串类。
  • 使用C++构造一个矩阵类模板，至少能够完成行列数读取和元素访问。

实现效果

main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include "lnpbqc.hpp"

void testString(){
	
	// 默认无参 
	lnpbqc::string s1;
	std::cout<<s1<<std::endl;
	
	// char* 构造 
	lnpbqc::string s2("lnpbqc");
	std::cout<<s2<<std::endl;
	
	// 复制构造 
	lnpbqc::string s3(s2);
	std::cout<<s3<<std::endl;
	
	lnpbqc::string s4("hnust");
	// 子串构造 
	lnpbqc::string s5(s4,2,4);
	s5[0] = 'c';// operator[]
	std::cout<<s5.at(0)<<std::endl;// at()
	std::cout<<s5<<std::endl;
	s5 += " go";// +=
	std::cout<<s5<<std::endl;
	
	// +
	lnpbqc::string s6 = s5 + ":2";
	std::cout<<s6<<std::endl;
	
	lnpbqc::string s7("12"),s8("12"),s9("123");
	std::cout<<(s7==s8)<<std::endl;// ==
	std::cout<<(s7!=s9)<<std::endl;// !=
	std::cout<<(s7<s9)<<std::endl;// <
	std::cout<<(s7>s9)<<std::endl;// >
	std::cout<<(s7<=s9)<<std::endl;// <=
	std::cout<<(s7>=s9)<<std::endl;// >=
	
	std::cout<<s6.substr(3,5)<<std::endl;
	std::cout<<s6.find("go")<<std::endl;
	std::cout<<s6.find("go2")<<std::endl;
	s6+="21321" ;
	std::cout<<s6<<std::endl;
}

void testMatrix(){
	{// 加
		std::cerr<<"加法"<<std::endl;
		lnpbqc::matrix<int> m1(4,4);
		lnpbqc::matrix<int> m2(4,4);
		for(int i = 0;i<4;i++){
			for(int j = 0;j<4;j++)m1.set(i,j,i*j);
		}
		m1.PrintMatrix();
		for(int i = 0;i<4;i++){
			for(int j = 0;j<4;j++)m2.set(i,j,i+j);
		}
		m2.PrintMatrix();
		m1 = m1+m2;
		m1.PrintMatrix();
	}
	{// 减
		std::cerr<<"减法"<<std::endl;
		lnpbqc::matrix<int> m1(4,4);
		lnpbqc::matrix<int> m2(4,4);
		for(int i = 0;i<4;i++){
			for(int j = 0;j<4;j++)m1.set(i,j,i*j);
		}
		m1.PrintMatrix();
		for(int i = 0;i<4;i++){
			for(int j = 0;j<4;j++)m2.set(i,j,i+j);
		}
		m2.PrintMatrix();
		m1 = m1-m2;
		m1.PrintMatrix();
	}
	
	{// 乘
		std::cerr<<"乘法"<<std::endl;
		lnpbqc::matrix<int> m1(4,5);
		lnpbqc::matrix<int> m2(5,6);
		for(int i = 0;i<4;i++){
			for(int j = 0;j<5;j++)m1.set(i,j,i*j);
		}
		m1.PrintMatrix();
		for(int i = 0;i<5;i++){
			for(int j = 0;j<6;j++)m2.set(i,j,i+j);
		}
		m2.PrintMatrix();
		m1 = m1*m2;
		m1.PrintMatrix();
	}
	{// 转置
		std::cerr<<"转置"<<std::endl;
		lnpbqc::matrix<int> m1(4,4);
		for(int i = 0;i<4;i++){
			for(int j = 0;j<4;j++)m1.set(i,j,i+j-((i%2==0)?12:21));
		}
		m1.PrintMatrix();
		auto m2 = m1.TransposeMatrix();
		m2.PrintMatrix();
	}
}
int main(int argc, char** argv) {
	testString();
	testMatrix();
	return 0;
}

运行效果图

具体实现内容

string
lnpbqc_string.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
namespace lnpbqc{
	class string{
		private:
			char* _str;
			int _capacity;
			int _length;
			
			void _cp(const string& src,char* des,int begin,int end){
				int i = 0;
				for(;begin<=end;begin++)des[i++] = src[begin];
			}
		public:
			string():_str(nullptr),_capacity(0),_length(0){}
			string(const char* s){
				_length = strlen(s);
				_capacity = _length*2;
				_str = new char[_capacity];
				strcpy(_str,s);
			}
			string(const string& s){
				_length = s.length();
				_capacity = _length*2;
				_str = new char[_capacity];
				
				_cp(s,_str,0,s.length());
			}
			string(const string& s,int begin,int end){
				_length = end-begin;
				_capacity = _length*2;
				_str = new char[_capacity];
				
				_cp(s,_str,begin,end);
				_str[end] = '\0';
			}
			~string(){
				delete []_str;
			}
			
			friend std::ostream& operator<<(std::ostream& os,const string& s){
				int i = 0;
				while(s.length()!=0&&i<s.length())os<<s[i++];
				return os;
			}
			char* operator&()const{
				return this->_str;
			}
			char operator[](int i)const{
				return _str[i];
			}
			char& operator[](int i){
				return _str[i];
			}
			char at(int i)const{
				return this->operator[](i);
			}
			int length()const{
				return _length;
			}
			int capacity()const{
				return _capacity;
			}
			void operator+=(const string& s){
				if(this->length()+s.length()>this->capacity()){
					this->_capacity*=2;
					char* t = new char[this->_capacity];
					strcpy(t,this->_str);
					char* tt = this->_str;
					this->_str = t;
					delete []tt;
				}
				strncpy(this->_str+this->length(),&s,s.length());
				this->_length = this->length()+s.length();
			}
			
			string substr(int begin,int end){
				return string(*this,begin,end);
			}
			
			int find(const string& s){
				std::vector<int> matches = _KMP(*this, s);
				return matches.empty()?-1:matches[0];
			}
			
			friend string operator+(const string&s1,const string& s2){
				string s(s1);
				s+=s2;
				return s;
			}
			
			friend bool operator>(const string&s1,const string& s2){
				return strcmp(&s1,&s2) > 0;
			}
			
			friend bool operator<(const string&s1,const string& s2){
				return strcmp(&s1,&s2) < 0;
			}
			friend bool operator>=(const string&s1,const string& s2){
				return s1>s2||s1==s2;
			}
			
			friend bool operator<=(const string&s1,const string& s2){
				return s1<s2||s1==s2;
			}
			
			friend bool operator==(const string&s1,const string& s2){
				return strcmp(&s1,&s2) == 0;
			}
			friend bool operator!=(const string&s1,const string& s2){
				return !(s1==s2);
			}
			
			// 构建部分匹配表（前缀函数表）
			std::vector<int> _buildPartialMatchTable(const string& pattern) {
			    int m = pattern.length();
			    std::vector<int> partialMatchTable(m, 0);
			    int j = 0;
			
			    for (int i = 1; i < m; ++i) {
			        while (j > 0 && pattern[i] != pattern[j]) {
			            j = partialMatchTable[j - 1];
			        }
			        if (pattern[i] == pattern[j]) {
			            j++;
			        }
			        partialMatchTable[i] = j;
			    }
			    return partialMatchTable;
			}
			
			// KMP字符串匹配算法
			std::vector<int> _KMP(const string& text, const string& pattern) {
			    std::vector<int> result;
			    int n = text.length();
			    int m = pattern.length();
			    if (m == 0 || n < m) {
			        return result;
			    }
			
			    std::vector<int> partialMatchTable = _buildPartialMatchTable(pattern);
			    int j = 0;
			
			    for (int i = 0; i < n; ++i) {
			        while (j > 0 && text[i] != pattern[j]) {
			            j = partialMatchTable[j - 1];
			        }
			        if (text[i] == pattern[j]) {
			            j++;
			        }
			        if (j == m) {
			            result.push_back(i - m + 1);
			            j = partialMatchTable[j - 1];
			        }
			    }
			    return result;
			}
			
	};
}
matrix
lnpbqc_matrix.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
namespace lnpbqc{
	template<typename DataType>
	struct matrixAtom{
		int row,col;
		DataType ele;
		bool operator==(const matrixAtom<DataType>&others){
			return row==others.row&&col==others.col&&ele==others.ele;
		}
	};
	
	template<typename DataType>
	class matrix{
		private:
			vector<matrixAtom<DataType> > _data; /*存储实际的矩阵数据，自包含非零元个数*/
			int _matrixRowNum; /*矩阵行数，从零开始*/
			int _matrixColNum; /*矩阵列数，从零开始*/
		public:
			int row()const{return _matrixRowNum;}
			int col()const{return _matrixColNum;}
			void row(int r){_matrixRowNum=r;}
			void col(int c){_matrixColNum=c;}
			vector<int> shape()const{
				vector<int> v;
				v.push_back(row());
				v.push_back(col());
				return v;
			}
			vector<matrixAtom<DataType> > data()const{return _data;}
			// 构造函数
			matrix() : _matrixRowNum(0), _matrixColNum(0) {
				std::cout<<"需要设置row和col"<<std::endl;
			}
			matrix(int rows, int cols) : _matrixRowNum(rows), _matrixColNum(cols) {}

	    matrix(const vector<vector<DataType> > &inArray){
	        	_matrixRowNum = inArray.size();
				_matrixColNum = _matrixRowNum > 0 ? inArray[0].size() : 0;
				
				for (int i = 0; i < _matrixRowNum; ++i) {
					for (int j = 0; j < _matrixColNum; ++j) {
						if (inArray[i][j] != 0) {
							_data.push_back({i, j, inArray[i][j]});
						}
					}
				}
			}
			matrix(const matrix<DataType>& other) {
				_matrixRowNum = other.row();
				_matrixColNum = other.col();
				_data = other.data(); // 直接复制data向量
			}
			matrix<DataType>& operator=(const matrix<DataType>& other) {
				if (this != &other) { // 防止自赋值
					_matrixRowNum = other.row();
					_matrixColNum = other.col();
					_data = other.data(); // 直接复制data向量
				}
				return *this;
			}
	    
      ~matrix(){}
		
			// 获取元素值
			DataType get(int row, int col) const {
				for (const auto& atom : _data) {
					if (atom.row == row && atom.col == col)
						return atom.ele;
				}
				return DataType(0); // 如果未找到非零元素，返回0
			}
			// 设置元素值
			void set(int row, int col, DataType value) {
				if(row>=_matrixRowNum||col>=_matrixColNum)throw "超出范围";
				
				bool found = false;
				for (auto& atom : _data) {
					if (atom.row == row && atom.col == col) {
						found = true;
						if (value == 0) {
							_data.erase(std::find(_data.begin(), _data.end(), atom));
						} else {
							atom.ele = value;
						}
						return;
					}
				}
				if (!found&&value != 0) {
					_data.push_back({row, col, value});
				}
			}
      
      matrix<DataType> TransposeMatrix()const{/*常规转置思路*/
				matrix<DataType> result(_matrixColNum, _matrixRowNum);
				for (const auto& atom : _data) {
					result.set(atom.col, atom.row, atom.ele);
				}
				return result;
			}
		
      void FastTransposeMatrix(){/*快速转置*/
				// todo:待完成
			}
		
	    matrix<DataType> AddMatrix(const matrix<DataType> &otherMatrix){ /*加上另外一个矩阵，第二个矩阵保持不变*/
				if (_matrixRowNum != otherMatrix.row() || _matrixColNum != otherMatrix.col()){
					throw "矩阵形状不匹配";
				}
				matrix<DataType> result(_matrixRowNum, _matrixColNum);
				for (const auto& atom : _data) {
					result.set(atom.row, atom.col, atom.ele);
				}
				for (const auto& atom : otherMatrix.data()) {
					result.set(atom.row, atom.col, result.get(atom.row, atom.col) + atom.ele);
				}
				return result;
			}
			matrix<DataType> operator+(const matrix<DataType>& otherMatrix){
				return this->AddMatrix(otherMatrix);
			}
		
		
	    matrix<DataType> SubMatrix(const matrix<DataType> &otherMatrix){/*减去另外一个矩阵，第二个矩阵保持不变*/
				if (_matrixRowNum != otherMatrix.row() || _matrixColNum != otherMatrix.col()){
					throw "矩阵形状不匹配";
				}
				matrix<DataType> result(_matrixRowNum, _matrixColNum);
				for (const auto& atom : _data) {
					result.set(atom.row, atom.col, atom.ele);
				}
				for (const auto& atom : otherMatrix.data()) {
					result.set(atom.row, atom.col, result.get(atom.row, atom.col) - atom.ele);
				}
				return result;
			}
			matrix<DataType> operator-(const matrix<DataType>& otherMatrix){
				return this->SubMatrix(otherMatrix);
			}
		
	    matrix<DataType> MultiMatrix(const matrix<DataType> &otherMatrix){/*乘上另外一个矩阵，第二个矩阵保持不变*/
				if (_matrixColNum != otherMatrix.row()){
					throw "矩阵形状不匹配";
				}
				matrix<DataType> result(_matrixRowNum, otherMatrix.col());
				for (const auto& atomA : _data) {
					for (const auto& atomB : otherMatrix.data()) {
						if (atomA.col == atomB.row) {
							DataType newValue = result.get(atomA.row, atomB.col) + atomA.ele * atomB.ele;
							result.set(atomA.row, atomB.col, newValue);
						}
					}
				}
				return result;
			}
			matrix<DataType> operator*(const matrix<DataType> & other){
				return this->MultiMatrix(other);
			}
		
			matrix<DataType> inverse() const {
				//待实现
				return matrix<DataType>();
			}
		
	    vector<vector<DataType> > TransformTo2DArray(){/*转换成二维数组*/
				vector<vector<DataType>> result(_matrixRowNum, vector<DataType>(_matrixColNum, 0));
				for (const auto& atom : _data) {
					result[atom.row][atom.col] = atom.ele;
				}
				return result;
			}
	    void PrintMatrix(){/*打印矩阵*/
				std::cout <<"Address::"<<this<< "\nMatrix Rows: " << _matrixRowNum << ", Columns: " << _matrixColNum << std::endl;
				for (int i = 0; i < _matrixRowNum; i++) {
					for (int j = 0; j < _matrixColNum; j++) {
						std::cout << get(i, j) << "\t";
					}
					std::cout << std::endl;
				}
			}
	};
}