实验环境
Windows 11 专业版22H2 Feature Experience Pack 1000.22642.1000.0
Microsoft Visual Studio Code 1.78.1 with MingW-W64-builds 10.0.0 & GCC 12.1.0
Qt Creator 9.0.2 Based on Qt 6.4.2 (MSVC 2019, x86_64)
实验目的
练习类编写&动态内存分配
Problem 1 Designing & Implementing a Proud String Class
问题分析与算法设计
define:
# define INIT_MEMORY 16
初始分配的内存;
private:
char *ptr;
源文件自带的指针,不去动他;- 添加私有成员
unsigned int allocated_memory;
用来记录当前分配的内存;
public:
- As default constructor OurString() with no arguments:
- 默认的构造函数;
- 初始状态为
ptr=new char [INIT_MEMORY]; allocated_memory=INIT_MEMORY;
- As OurString(const char* cstr) from a constant string in C style:
- 以C字符串为参数的构造函数;
- 分配内存设置为
((strlen(cstr)+1)/INIT_MEMORY+1)*INIT_MEMORY
;
- As OurString(string str) from a C++ string:
- 以C++
string
类为参数的构造函数; - 分配内存设置为
((str.size()+1)/INIT_MEMORY+1)*INIT_MEMORY
- 通过for循环遍历将
str
对应的字符串赋值给ptr
;
- 以C++
- As OurString(string str) from another OurString:
- 以另一个
OurString
为参数的构造函数; - 实现方式和 from a C++ string 的方式基本一致;
- 以另一个
- A destructor that frees any heap storage allocated by the String:
- 析构函数;
delete [] ptr;
即可;
- A toString() method that converts one of your String objects into a C++ string:
- 直接返回
string(ptr)
即可;
- 直接返回
- A method length() that returns the number of characters in the Strin:
- 直接返回
strlen(ptr)
即可;
- 直接返回
- A method substr(start, n) that returns an entirely new string that contains all the characters from the original string beginning with the index position start and continuing for n characters or through the end of the string, whichever comes first. The parameter n should be optional. If it is missing, the substring should always extend through the end of the original string.
- 针对
OurString OurString::subStr(unsigned int start, unsigned int n) const
函数中默认n
的传入参数为MAX_LENGTH
,因此使用if语句进行分支判定,如果n<MAX_LENGTH
则截取长度为n的字符串,否则(包括n留空的情况在内)截取到字符串结束为止. - 截取操作用
strncpy()
函数完成;
- 针对
- A redefinition of the operator relational and comparison operators ( ==, !=, >, <, >=, <= ).
- 添加一个外部接口
OurString.c_str()
,返回一个ptr
的拷贝以供外部访问; - 创建一个临时的
char* temp=dstr.c_str()
; - 使用
strcmp()
函数进行结果比较,存储到bool res
中; - 手动释放
temp
的空间; - 返回
res
; - 对于>=,<=,!=这类运算符,直接返回诸如
!(*this<dstr)
的形式即可;
- 添加一个外部接口
- A redefinition of the assignment operator and the copy constructor for the String class so that any copying operations make a deep copy that creates a new character array.
- 赋值运算符重载,先比较内存地址防止自己复制自己;
- 释放
ptr
的空间; ptr
和allocated
值的设置与构造函数类似;- 返回
*this
- A redefinition of the bracket-selection operator that invoking str[i] returns the character at index position i in str as an lvalue. As an improvement over the string class in the C++ libraries, your implementation of String should call error if the string index is out of bounds.
- 下标运算符重载,检查是否越界,不越界就返回
ptr[index]
;
- 下标运算符重载,检查是否越界,不越界就返回
- A redefinition of the operator + that concatenates two String objects.
- 创建一个结果字符串
res_str
,长度为左值和右值的长度之和; - 使用
strcpy()
函数将左值复制到res_str
中; - 使用
strcat()
函数将右值拼接到res_str
后; - 使用
res_str
构造一个结果字符串,完成后释放其内存; - 返回结果字符串;
- 创建一个结果字符串
- A redefinition of the operator += that performs the operation of the binary operator + on both strings and store the result into the left string.
- 先计算结果
OurString new_str=*this+dstr;
- 将
new_str
的ptr
通过c_str()
方法新拷贝一个字符串; - 释放
this->ptr
的空间,将拷贝字符串的地址赋值给this->ptr
; - 返回
*this
- 先计算结果
- A redefinition of the operator << so that String objects can be written to output streams.
- for循环遍历,输出;
- A redefinition of the operator >> so that String objects can be read from input Assignments of PAiC++ 2 / 5 streams
- 定义一个
char temp[MAX_LENGTH];
- 用
is.getline()
函数输入; - 构造
dstr
,返回is
;
- 定义一个
测试数据和结果
实验小结
- 时刻注意不要造成内存泄漏,比如
c_str()
方法的返回值需要手动释放内存,否则会内存泄漏. - 时刻注意新创建的字符串数组有没有以
\0
结尾,否则使用字符串函数就会造成乱码错误.
Problem 2 Designing & Implementing Powerful SuperInt Class
问题分析与算法设计
public
struct num
:链表的节点,存储两个成员:int value
:该节点的整数值;num* next
:下一个节点的地址;
- 构造函数:
- 依赖于私有成员函数
construct_from_string()
完成,传入string
类型字符串构造类型; - 如果构造函数的参数不是
string
类型,则先将其转换为string
类型;
- 依赖于私有成员函数
- 析构函数:
- 依赖于私有成员函数
delete_num()
完成;
- 依赖于私有成员函数
- 一些访问私有成员内容的函数: bool isPositive() const; // 返回私有成员is_positive
unsigned int size() const; // 返回私有成员length
int& operator[](int index) const; // 重载索引运算符,返回第index位num的value
num* getStart() const; // 返回链表的起始地址,危险的操作 string SuperInt::toString() const;
- 创建一个结果字符串
string res="";
- 遍历链表,将
value
转换为char
类型push入res
; - 如果为负数,在字符串结尾push一个
'-'
; - 反转
res
并返回;
- 创建一个结果字符串
SuperInt SuperInt::abs() const;
- 如果是正值,返回一个以
*this
为参数的拷贝构造函数; - 如果是负值,将
*this
转换为字符串后截掉负号再作为参数传入构造一个新SuperInt
返回;
- 如果是正值,返回一个以
- 重载赋值运算符:
- 先通过
delete_num()
释放原链表的内存空间; - 再通过
construct_from_string()
将右值传入;
- 先通过
- 重载
==
运算符:- 针对右值是
SuperInt
类型:先比较左值和右值的正负性和长度,如果都一致则逐个比较链表的每一项,如果有一项不同返回false
,否则返回true
; - 如果右值是其他类型,先将其转换为
SuperInt
类型;
- 针对右值是
- 重载
>
和<
运算符:- 针对右值是
SuperInt
类型:先比较左值和右值的正负性和长度,如果都一致,使用toString()
函数将其转换为字符串并进行大小比较,如果正数直接返回结果,如果负数则互换左右值后再返回结果; - 如果右值是其他类型,先将其转换为
SuperInt
类型;
- 针对右值是
- 重载
>=
,<=
,!=
运算符:- 直接返回
<
,>
,==
的非值;
- 直接返回
- 重载
+
运算符:- 针对右值是
SuperInt
:先比较正负性,只有一致时继续,否则调用-
运算符; - 正负号一致时,比较左值和右值的长度,如果左值短于右值,则左右互换,必须保证左值长度>=右值;
- 定义
int advance=0
来记录进位,string res_str
来记录结果字符串; - 使用while循环同时遍历左值和右值链表:
int temp=
左右值value
之和+advance
;- 更新值
advance=temp/10; temp%=10
; - 将
'0'+temp
push入res_str
; - 左右值指针后移继续遍历;
- 使用while循环继续遍历左值链表:
- 将
'0'+left->value+advance
push入res_str
; - 更新
advance=0
; - 左值指针后移继续遍历;
- 将
- 如果
advance
依然不为0,将'0'+advance
push入res_str
; - 如果是负数,在
res_str
结尾push一个'-'
; - 反转
res_str
,以此作为参数构造一个SuperInt
返回; - 正负号不一致时,如果左正右负,返回左值-右值的绝对值;如果右正左负,返回右值-左值的绝对值;
- 右值不是
SuperInt
类型时,先转换为SuperInt
类型;
- 针对右值是
- 重载
-
运算符:- 针对右值是
SuperInt
:先比较正负性,只有一致时继续,否则调用+
运算符; - 正负号一致时,比较左值和右值的大小,如果左值短于右值,则左右互换,必须保证左值>=右值;
- 定义
int retreat=0
来记录退位,string res_str
来记录结果字符串; - 使用while循环同时遍历左值和右值链表:
int temp=
左右值value
之差-retreat
;- 更新值
retreat=temp<0?1:0; temp+=10*retreat;
- 将
'0'+temp
push入res_str
; - 左右值指针后移继续遍历;
- 使用while循环继续遍历左值链表:
- 将
'0'+left->value-retreat
push入res_str
; - 更新
advance=0
; - 左值指针后移继续遍历;
- 将
- 如果
advance
依然不为0,将'0'+advance
push入res_str
; - 如果左值<右值,且均为正值或左值>=右值,且均为负值在
res_str
结尾push一个'-'
; - 反转
res_str
,以此作为参数构造一个SuperInt
返回; - 正负号不一致时,如果左正右负,返回左值+右值的绝对值;如果右正左负,返回-(右值+左值的绝对值);
- 针对右值是
void multiplyTen(int times);
- 向链表的开头添加一个以
0
为value
的num*
,并使得其next
指向原链表的start
,以此来实现自乘10的效果,随后调用递归multiplyTen(times-1);
- 当
times<=0
时return;
结束递归;
- 向链表的开头添加一个以
void divideTen(int times);
- 删除原链表的
start
,并令新start
指向原start->next
,以实现自整除10的效果,随后调用递归divideTen(times-1);
- 当
times<=0
时return;
结束递归;
- 删除原链表的
- 重载
*
运算符:- 针对右值是
SuperInt
:分两种情况: - 如果右值的长度=1:和加法重载的思路类似,最后在输出时判断左右值正负号是否一致,来决定是否要加负号;
- 如果右值长度!=1:
- 定义
res1
=左值乘以右值的start->value
; - 定义
res2
=右值; - 对
res2
进行如下操作: res2.divideTen(1);
res2=res2*(*this);
res2.multiplyTen(1); - 根据左右值正负号是否一致返回
res+res2
或-res1-res2
;
- 定义
- 针对右值是
- 重载
<<
运算符:- 只需要调用
toString()
方法再直接输出字符串即可;
- 只需要调用
private:
num* start;
链表开始的地址;bool is_positive;
正负性;unsigned int length;
长度;int char2int(char c);
在将char
转换为int
时同时检查转换结果是否为数字;void SuperInt::construct_from_string(string str)
;- 如果
str
长度为0,则默认为参数为0的构造函数,; start=new num;
start->value=0;
start->next=nullptr;
is_positive=true;
length=1;
return; - 根据
str[0]!='-'
来为is_positive
赋值; - 定义一个新字符串
string ss=is_positive?"":"-";
- 对
str
进行遍历,跳过'-'
,直到找到第一个非0的字符为止,将该字符开始到str
结尾的内容拼接到ss
后; - 如果
ss==""||ss=="-"
,则默认为参数为0的构造函数; length=is_positive?ss.size():(ss.size()-1);
- 使用for循环根据
length
的值创建链表;
- 如果
void SuperInt::delete_num()
- 如果
start->next==nullptr
,直接delete start
; - 否则使用while循环遍历整个链表来释放内存;
- 如果
测试数据和结果
实验小结
- 由于时间原因存在可以改进的部分:
- 针对不同类型参数的构造函数均将其转换为了string类再进行构造,可能会增加时间复杂度;
- 有些语句存在重复的SuperInt和string类型之间的来回转换,可以进行优化;
- 由于时间原因未能实现的部分:
/
和%
运算符的重载;+=
,-=
,*=
运算符的重载(实现方式和直接运算类似,但是可以直接在左值链表上进行操作);- 更加完善的测试;