实验环境

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:

1. char *ptr; 源文件自带的指针,不去动他;
2. 添加私有成员unsigned int allocated_memory; 用来记录当前分配的内存;

public:

1. As default constructor OurString() with no arguments:
   1. 默认的构造函数;
   2. 初始状态为ptr=new char [INIT_MEMORY]; allocated_memory=INIT_MEMORY;
2. As OurString(const char* cstr) from a constant string in C style:
   1. 以C字符串为参数的构造函数;
   2. 分配内存设置为((strlen(cstr)+1)/INIT_MEMORY+1)*INIT_MEMORY ;
3. As OurString(string str) from a C++ string:
   1. 以C++string类为参数的构造函数;
   2. 分配内存设置为((str.size()+1)/INIT_MEMORY+1)*INIT_MEMORY
   3. 通过for循环遍历将str对应的字符串赋值给ptr;
4. As OurString(string str) from another OurString:
   1. 以另一个OurString为参数的构造函数;
   2. 实现方式和 from a C++ string 的方式基本一致;
5. A destructor that frees any heap storage allocated by the String:
   1. 析构函数;
   2. delete [] ptr;即可;
6. A toString() method that converts one of your String objects into a C++ string:
   1. 直接返回string(ptr)即可;
7. A method length() that returns the number of characters in the Strin:
   1. 直接返回strlen(ptr)即可;
8. 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.
   1. 针对OurString OurString::subStr(unsigned int start, unsigned int n) const函数中默认n的传入参数为MAX_LENGTH,因此使用if语句进行分支判定,如果n<MAX_LENGTH则截取长度为n的字符串,否则(包括n留空的情况在内)截取到字符串结束为止.
   2. 截取操作用strncpy()函数完成;
9. A redefinition of the operator relational and comparison operators ( ==, !=, >, <, >=, <= ).
   1. 添加一个外部接口OurString.c_str(),返回一个ptr的拷贝以供外部访问;
   2. 创建一个临时的char* temp=dstr.c_str();
   3. 使用strcmp()函数进行结果比较,存储到bool res中;
   4. 手动释放temp的空间;
   5. 返回res;
   6. 对于>=,<=,!=这类运算符,直接返回诸如!(*this<dstr)的形式即可;
10. 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.
    1. 赋值运算符重载,先比较内存地址防止自己复制自己;
    2. 释放ptr的空间;
    3. ptr和allocated值的设置与构造函数类似;
    4. 返回*this
11. 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.
    1. 下标运算符重载,检查是否越界,不越界就返回ptr[index];
12. A redefinition of the operator + that concatenates two String objects.
    1. 创建一个结果字符串res_str,长度为左值和右值的长度之和;
    2. 使用strcpy()函数将左值复制到res_str中;
    3. 使用strcat()函数将右值拼接到res_str后;
    4. 使用res_str构造一个结果字符串,完成后释放其内存;
    5. 返回结果字符串;
13. A redefinition of the operator += that performs the operation of the binary operator + on both strings and store the result into the left string.
    1. 先计算结果OurString new_str=*this+dstr;
    2. 将new_str的ptr通过c_str()方法新拷贝一个字符串;
    3. 释放this->ptr的空间,将拷贝字符串的地址赋值给this->ptr;
    4. 返回*this
14. A redefinition of the operator << so that String objects can be written to output streams.
    1. for循环遍历,输出;
15. A redefinition of the operator >> so that String objects can be read from input Assignments of PAiC++ 2 / 5 streams
    1. 定义一个char temp[MAX_LENGTH];
    2. 用is.getline()函数输入;
    3. 构造dstr,返回is;

测试数据和结果

实验小结

1. 时刻注意不要造成内存泄漏,比如c_str()方法的返回值需要手动释放内存,否则会内存泄漏.
2. 时刻注意新创建的字符串数组有没有以\0结尾,否则使用字符串函数就会造成乱码错误.

Problem 2 Designing & Implementing Powerful SuperInt Class

问题分析与算法设计

public

1. struct num:链表的节点,存储两个成员:
   1. int value:该节点的整数值;
   2. num* next:下一个节点的地址;
2. 构造函数:
   1. 依赖于私有成员函数construct_from_string()完成,传入string类型字符串构造类型;
   2. 如果构造函数的参数不是string类型,则先将其转换为string类型;
3. 析构函数:
   1. 依赖于私有成员函数delete_num()完成;
4. 一些访问私有成员内容的函数: bool isPositive() const; // 返回私有成员is_positive
    unsigned int size() const; // 返回私有成员length
    int& operator[](int index) const; // 重载索引运算符,返回第index位num的value
    num* getStart() const; // 返回链表的起始地址,危险的操作
5. string SuperInt::toString() const;
   1. 创建一个结果字符串string res="";
   2. 遍历链表,将value转换为char类型push入res;
   3. 如果为负数,在字符串结尾push一个'-';
   4. 反转res并返回;
6. SuperInt SuperInt::abs() const;
   1. 如果是正值,返回一个以*this为参数的拷贝构造函数;
   2. 如果是负值,将*this转换为字符串后截掉负号再作为参数传入构造一个新SuperInt返回;
7. 重载赋值运算符:
   1. 先通过delete_num()释放原链表的内存空间;
   2. 再通过construct_from_string()将右值传入;
8. 重载==运算符:
   1. 针对右值是SuperInt类型:先比较左值和右值的正负性和长度,如果都一致则逐个比较链表的每一项,如果有一项不同返回false,否则返回true;
   2. 如果右值是其他类型,先将其转换为SuperInt类型;
9. 重载>和<运算符:
   1. 针对右值是SuperInt类型:先比较左值和右值的正负性和长度,如果都一致,使用toString()函数将其转换为字符串并进行大小比较,如果正数直接返回结果,如果负数则互换左右值后再返回结果;
   2. 如果右值是其他类型,先将其转换为SuperInt类型;
10. 重载>=,<=,!=运算符:
    1. 直接返回<,>,==的非值;
11. 重载+运算符:
    1. 针对右值是SuperInt:先比较正负性,只有一致时继续,否则调用-运算符;
    2. 正负号一致时,比较左值和右值的长度,如果左值短于右值,则左右互换,必须保证左值长度>=右值;
    3. 定义int advance=0来记录进位,string res_str来记录结果字符串;
    4. 使用while循环同时遍历左值和右值链表:
       1. int temp=左右值value之和+advance;
       2. 更新值advance=temp/10; temp%=10;
       3. 将'0'+temppush入res_str;
       4. 左右值指针后移继续遍历;
    5. 使用while循环继续遍历左值链表:
       1. 将'0'+left->value+advancepush入res_str;
       2. 更新advance=0;
       3. 左值指针后移继续遍历;
    6. 如果advance依然不为0,将'0'+advancepush入res_str;
    7. 如果是负数,在res_str结尾push一个'-';
    8. 反转res_str,以此作为参数构造一个SuperInt返回;
    9. 正负号不一致时,如果左正右负,返回左值-右值的绝对值;如果右正左负,返回右值-左值的绝对值;
    10. 右值不是SuperInt类型时,先转换为SuperInt类型;
12. 重载-运算符:
    1. 针对右值是SuperInt:先比较正负性,只有一致时继续,否则调用+运算符;
    2. 正负号一致时,比较左值和右值的大小,如果左值短于右值,则左右互换,必须保证左值>=右值;
    3. 定义int retreat=0来记录退位,string res_str来记录结果字符串;
    4. 使用while循环同时遍历左值和右值链表:
       1. int temp=左右值value之差-retreat;
       2. 更新值retreat=temp<0?1:0; temp+=10*retreat;
       3. 将'0'+temppush入res_str;
       4. 左右值指针后移继续遍历;
    5. 使用while循环继续遍历左值链表:
       1. 将'0'+left->value-retreatpush入res_str;
       2. 更新advance=0;
       3. 左值指针后移继续遍历;
    6. 如果advance依然不为0,将'0'+advancepush入res_str;
    7. 如果左值<右值,且均为正值或左值>=右值,且均为负值在res_str结尾push一个'-';
    8. 反转res_str,以此作为参数构造一个SuperInt返回;
    9. 正负号不一致时,如果左正右负,返回左值+右值的绝对值;如果右正左负,返回-(右值+左值的绝对值);
13. void multiplyTen(int times);
    1. 向链表的开头添加一个以0为value的num*,并使得其next指向原链表的start,以此来实现自乘10的效果,随后调用递归multiplyTen(times-1);
    2. 当times<=0时return;结束递归;
14. void divideTen(int times);
    1. 删除原链表的start,并令新start指向原start->next,以实现自整除10的效果,随后调用递归divideTen(times-1);
    2. 当times<=0时return;结束递归;
15. 重载*运算符:
    1. 针对右值是SuperInt:分两种情况:
    2. 如果右值的长度=1:和加法重载的思路类似,最后在输出时判断左右值正负号是否一致,来决定是否要加负号;
    3. 如果右值长度!=1:
       1. 定义res1=左值乘以右值的start->value;
       2. 定义res2=右值;
       3. 对res2进行如下操作: res2.divideTen(1);
           res2=res2*(*this);
           res2.multiplyTen(1);
       4. 根据左右值正负号是否一致返回res+res2或-res1-res2;
16. 重载<<运算符:
    1. 只需要调用toString()方法再直接输出字符串即可;

private:

1. num* start;链表开始的地址;
2. bool is_positive;正负性;
3. unsigned int length;长度;
4. int char2int(char c);在将char转换为int时同时检查转换结果是否为数字;
5. void SuperInt::construct_from_string(string str);
   1. 如果str长度为0,则默认为参数为0的构造函数,; start=new num;
       start->value=0;
       start->next=nullptr;
       is_positive=true;
       length=1;
       return;
   2. 根据str[0]!='-'来为is_positive赋值;
   3. 定义一个新字符串string ss=is_positive?"":"-";
   4. 对str进行遍历,跳过'-',直到找到第一个非0的字符为止,将该字符开始到str结尾的内容拼接到ss后;
   5. 如果ss==""||ss=="-",则默认为参数为0的构造函数;
   6. length=is_positive?ss.size():(ss.size()-1);
   7. 使用for循环根据length的值创建链表;
6. void SuperInt::delete_num()
   1. 如果start->next==nullptr,直接delete start;
   2. 否则使用while循环遍历整个链表来释放内存;

测试数据和结果

实验小结

1. 由于时间原因存在可以改进的部分:
   1. 针对不同类型参数的构造函数均将其转换为了string类再进行构造,可能会增加时间复杂度;
   2. 有些语句存在重复的SuperInt和string类型之间的来回转换,可以进行优化;
2. 由于时间原因未能实现的部分:
   1. /和%运算符的重载;
   2. +=,-=,*=运算符的重载(实现方式和直接运算类似,但是可以直接在左值链表上进行操作);
   3. 更加完善的测试;