第6章-List的存储及应用(2020.04.23)

第6章-List的存储及应用

1. List的顺序实现【简单】

（List的顺序实现）请用顺序存储实现通用线性表的数据结构MyList。你所实现的List应包括：Intsert，Remove，Retrieve，Replace, Traverse，Size，Full等功能。利用你实现的MyList实现对所输入的整数序列的顺序输出。
【输入】整数序列以-1结束，序列长度小于100
【输出】输入整数序列的顺序序列
例如：
【输入】3 9 8 2 5 -1
【输出】3 9 8 2 5

#include <iostream>
using namespace std;
enum Error_code { underflow, overflow, range_Error, success };
const int max_list = 100;
typedef int List_entry;

//list的顺序实现
class List
{
public:
    List();
    int size()const;
    bool full()const;
    bool empty()const;
    void clear();
    Error_code insert(int position, const List_entry& x);
    Error_code remove(int position, List_entry& x);
    Error_code retrieve(int position, List_entry& x)const;
    Error_code replace(int position, List_entry& x);
    void traverse(void(*visit)(List_entry& x));
protected:
    int count;
    List_entry entry[max_list];
};

List::List()
{
    count = 0;
}

int List::size()const
{
    return count;
}

bool List::full()const
{
    if (count == max_list) return true;
    return false;
}

bool List::empty()const
{
    if (count == 0) return true;
    return false;
}

void List::clear()
{
    count = 0;
}

Error_code List::retrieve(int position, List_entry& x)const
{
    if (position < 0 || position >= count) return range_Error;
    x = entry[position];
    return success;
}

Error_code List::insert(int position, const List_entry& x)
{
    if (full()) return overflow;
    if (position<0 || position>count) return range_Error;
    for (int i = count - 1; i >= position; i--) entry[i + 1] = entry[i];
    entry[position] = x;
    count++;
    return success;
}

Error_code List::remove(int position, List_entry& x)
{
    if (empty()) return underflow;
    if (position < 0 || position >= count) return range_Error;
    x = entry[position];
    for (int i = position; i < count - 1; i++) entry[i] = entry[i + 1];
    count--;
    return success;
}

Error_code List::replace(int position, List_entry& x)
{
    if (position < 0 || position >= count) return range_Error;
    entry[position] = x;
    return success;
}

void List::traverse(void(*visit)(List_entry& x))
{
    for (int i = 0; i < count; i++)
        (*visit)(entry[i]);
}

int main()
{
    int a, x;
    cin >> a;
    List b;
    while (a != -1) {
        b.insert(b.size(), a);
        cin >> a;
    }
    while (b.size() > 0) {
        b.remove(0, x);
        cout << x << ' ';
    }
    return 0;
}

2. List的单链表实现【简单】

（害人不浅的代码，这里retrieve写错了还提交成功了，为我以后写代码直接套模板埋下了好几个大雷！气死我了气死我了！）
（List的单链表实现）请用单链表（需要记录最后一次访问的位置）实现通用线性表的数据结构MyList。你所实现的List应包括：Insert，Remove，Retrieve，Replace, Traverse，Size，Full等功能。利用你实现的MyList实现输入序列的增删及修改。
【输入】输入数据共4行，操作过程中序列长度始终小于100；
第1行为输入的整数序列，以-1结束；
第2行为N（N>=0）对数a b（0<=a<=length），表示在第a个位置前插入数b，以-1 -1结束；
第3行为M（M>=0）个数c（0<=c<=length-1），表示删除第c个位置的元素，以-1结束；
第4行为P（P>=0）对数d e（0<=d<=length-1），表示修改第d个位置的元素，以-1 -1结束。
**注意：插入，删除，修改操作均按照顺序在同一个序列中进行。
【输出】操作后的新序列。
例如：
【输入】
3 7 8 4 6 -1
1 2 -1 -1 //在第1个位置的元素7前插入数2，此时序列为3 2 7 8 4 6
3 -1 // 删除序列3 2 7 8 4 6第3个位置的元素8，此时序列为3 2 7 4 6
4 9 -1 -1//将现有序列第4个位置的元素6修改为9，此时序列为3 2 7 4 9
【输出】
3 2 7 4 9 // 输出操作后的新序列

#include <iostream>
using namespace std;
enum Error_code { underflow, overflow, range_Error, success };
const int max_list = 100;
typedef int List_entry;
typedef int Node_entry;

struct Node
{
    Node_entry entry;
    Node* next;
    Node();
    Node(Node_entry item, Node* add_on = NULL);
};

Node::Node()
{
    next = NULL;
}

Node::Node(Node_entry item, Node* add_on)
{
    entry = item;
    next = add_on;
}

//list的链式实现
class List
{
public:
    List();
    ~List();
    List(const List& copy);
    void operator=(const List& copy);
    int size()const;
    bool full()const;
    bool empty()const;
    void clear();
    Error_code insert(int position, const List_entry& x);
    Error_code remove(int position, List_entry& x);
    Error_code retrieve(int position, List_entry& x)const;
    Error_code replace(int position, List_entry& x);
    void traverse(void(*visit)(List_entry& x));
protected:
    int count;
    Node* head;
    Node* set_position(int position)const;//返回指定位置的节点的地址；
};

Node* List::set_position(int position)const
{
    Node* q = head;
    for (int i = 0; i < position; i++) q = q->next;
    return q;
}


List::List()
{
    count = 0;
    head = NULL;
}

List::~List()
{
   List_entry x;
    while (!empty()) 
        remove(0, x);
}

List::List(const List& copy)
{
    count = 0;
    head = NULL;
    Node* newptr = copy.head;
    while (newptr) {
        insert(size(), newptr->entry);
        newptr = newptr->next;
    }
}

void List::operator=(const List& copy) {
    List_entry x;
    if (this == &copy) return;//是否为本身
    while (!empty()) remove(0, x);
    Node* newptr = copy.head;
    while (newptr) {
        insert(size(), newptr->entry);
        newptr = newptr->next;
    }
}

int List::size()const
{
    return count;
}

bool List::full()const
{
    //看堆满了没
    Node* newptr = new Node();
    if (newptr == NULL) return true;
    delete newptr;//不要忘了删
    return false;
}

bool List::empty()const
{
    if (count == 0) return true;
    return false;
}

void List::clear()
{
    List_entry x;
    remove(0, x);
}

Error_code List::insert(int position, const List_entry& x)
{
    if (position < 0 || position > count) return range_Error;
    Node* newptr, * previous = NULL, * following;
    if (position > 0) {
        //1.定位previous和following
        previous = set_position(position - 1);
        following = previous->next;
    }
    else following = head;
    //2.产生新的节点空间
    newptr = new Node(x, following);
    //堆空间不足，产生失败
    if (newptr == NULL) return overflow;
    //3.将新产生的节点加入链表
    if (position == 0) head = newptr;
    else previous->next = newptr;
    count++;
    return success;
}

Error_code List::remove(int position, List_entry& x)
{
    if (position < 0 || position >= count) return range_Error;
    Node* previous, * following;
    if (position > 0) {
        previous = set_position(position - 1);
        following = previous->next;
        previous->next = following->next;
    }
    else {
        following = head;
        head = head->next;
    }
    x = following->entry;
    delete following;
    count--;
    return success;
}

Error_code List::retrieve(int position, List_entry& x)const
{//就是这里的count！气死我了！
    if (position < 0 || position >= count) return range_Error;
    Node* newptr = set_position(position);
    x = newptr->entry;
    return success;
}

Error_code List::replace(int position, List_entry& x)
{
    if (position < 0 || position >= count) return range_Error;
    Node* newptr = set_position(position);
    newptr->entry = x;
    return success;
}

void List::traverse(void(*visit)(List_entry& x))
{
    Node* newptr = head;
    while (newptr) {
        (*visit)(newptr->entry);
        newptr = newptr->next;
    }
}

int main()
{
    int a, c;
    cin >> a;
    List b;
    //输入
    while (a != -1) {
        b.insert(b.size(), a);
        cin >> a;
    }
    //插入
    cin >> a >> c;
    while (a != -1 || c != -1) {
        b.insert(a, c);
        cin >> a >> c;
    }
    //删除
    cin >> a;
    while (a != -1) {
        b.remove(a, c);
        cin >> a;
    }
    //修改
    cin >> a >> c;
    while (a != -1 || c != -1) {
        b.replace(a, c);
        cin >> a >> c;
    }
    //输出
    while (b.size() > 0) {
        b.remove(0, a);
        cout << a << ' ';
    }
    return 0;
}

3. List的双链表实现【简单】

（List的双链表实现）请用双链表（需要记录最后一次访问的位置）实现通用线性表的数据结构MyList。你所实现的List应包括：Insert，Remove，Retrieve，Replace, Traverse，Size，Full等功能。利用你实现的MyList实现输入序列的增删、修改及正逆序输出。
【输入】输入数据共4行，操作过程中序列长度始终小于100；
第1行为输入的整数序列，以-1结束；
第2行为N（N>=0）对数a b（0<=a<=length），表示在第a个位置前插入数b，以-1 -1结束；
第3行为M（M>=0）个数c（0<=c<=length-1），表示删除第c个位置的元素，以-1结束；
第4行为P（P>=0）对数d e（0<=d<=length-1），表示修改第d个位置的元素，以-1 -1结束。
**注意：插入，删除，修改操作均按照顺序在同一个序列中进行。
【输出】操作后新序列的正逆序输出，第1行为正序，第2行为逆序。
例如：
【输入】
3 7 8 4 6 -1
1 2 -1 -1// 在第1个位置的元素7前插入数2，此时序列为3 2 7 8 4 6
3 -1// 删除序列3 2 7 8 4 6第3个位置的元素8，此时序列为3 2 7 4 6
4 9 -1 -1//将现有序列第4个位置的元素6修改为9，此时序列为3 2 7 4 9
【输出】
3 2 7 4 9 // 新序列的正序输出
9 4 7 2 3 // 新序列的逆序输出

#include <iostream>
using namespace std;
enum Error_code { underflow, overflow, range_Error, success };
const int max_list = 100;
typedef int List_entry;
typedef int Node_entry;

struct Node
{
    Node_entry entry;
    Node* back, * next;
    Node();
    Node(Node_entry item, Node* link_back = NULL, Node* link_next = NULL);
};

Node::Node()
{
    back = NULL;
    next = NULL;
}

Node::Node(Node_entry item, Node* link_back, Node* link_next)
{
    entry = item;
    back = link_back;
    next = link_next;
}

//list的双向链表实现，且存储最后一次访问的位置
class DList
{
public:
    DList();
    ~DList();
    DList(const DList& copy);
    void operator=(const DList& copy);
    int size()const;
    bool full()const;
    bool empty()const;
    void clear();
    Error_code insert(int position, const List_entry& x);
    Error_code remove(int position, List_entry& x);
    Error_code retrieve(int position, List_entry& x)const;
    Error_code replace(int position, List_entry& x);
    void traverse(void(*visit)(List_entry& x));
protected:
    int count;
    Node* head;
    mutable int current_position;
    mutable Node* current;
    void set_position(int position)const;//不再有返回值，直接更新current
};

void DList::set_position(int position)const
{
    //current在前面
    if (current_position <= position) {
        for (; current_position != position; current_position++)
            current = current->next;
    }
    //current在后面
    else {
        for (; current_position != position; current_position--)
            current = current->back;
    } 
}

DList::DList()
{
    count = 0;
    head = NULL;
    current_position = 0;
    current = NULL;
}

DList::~DList()
{
    List_entry x;
    while (!empty())
        remove(0, x);
}

DList::DList(const DList& copy)
{
    count = 0;
    head = NULL;
    Node* newptr = copy.head;
    while (newptr) {
        insert(size(), newptr->entry);
        newptr = newptr->next;
    }
}

void DList::operator=(const DList& copy) {
    List_entry x;
    if (this == &copy) return;//是否为本身
    while (!empty()) remove(0, x);
    Node* newptr = copy.head;
    while (newptr) {
        insert(size(), newptr->entry);
        newptr = newptr->next;
    }
}

int DList::size()const
{
    return count;
}

bool DList::full()const
{
    //看堆满了没
    Node* newptr = new Node();
    if (newptr == NULL) return true;
    delete newptr;//不要忘了删
    return false;
}

bool DList::empty()const
{
    if (count == 0) return true;
    return false;
}

void DList::clear()
{
    List_entry x;
    remove(0, x);
}

Error_code DList::insert(int position, const List_entry& x)
{
    if (position < 0 || position > count) return range_Error;
    Node* newptr, * previous, * following;
    if (position == 0) { //在第0号位置插入的特殊情况
        if (count == 0)
            following = NULL;
        else {
            set_position(0);
            following = current;
        }
        previous = NULL;
    }
    else {//一般情况，在链表中间或末尾插入
        set_position(position - 1);
        previous = current;
        following = previous->next;
    }//给f和p赋初始值
    newptr = new Node(x, previous, following);
    if (newptr == NULL) return overflow;
    //除了头和尾
    if (previous != NULL) previous->next = newptr;
    if (following != NULL) following->back = newptr;
    //调整current和c_p
    current = newptr;
    current_position = position;
    if (position == 0) head = newptr;//不要忘了head
    count++;
    return success;
}

Error_code DList::remove(int position, List_entry& x)
{
    if (position < 0 || position >= count) return range_Error;
    Node* previous, * following;
    if (position > 0) {
        set_position(position - 1);//
        previous = current;
        following = previous->next;
        previous->next = following->next;
        if (following->next) following->next->back = previous;
    }
    else {
        following = head;
        head = head->next;
        if (head) head->back = NULL;
        current_position = 0;
        current = head;//删除后记得更新
    }
    x = following->entry;
    delete following;
    count--;
    return success;
}

Error_code DList::retrieve(int position, List_entry& x)const
{
    if (position < 0 || position >= count) return range_Error;
    set_position(position);
    x = current->entry;
    return success;
}

Error_code DList::replace(int position, List_entry& x)
{
    if (position < 0 || position >= count) return range_Error;
    set_position(position);
    current->entry = x;
    return success;
}

void DList::traverse(void(*visit)(List_entry& x))
{
    Node* newptr = head;
    while (newptr) {
        (*visit)(newptr->entry);
        newptr = newptr->next;
    }
}

int main()
{
    List_entry a, c;
    cin >> a;
    DList b;
    //输入
    while (a != -1) {
        b.insert(b.size(), a);
        cin >> a;
    }
    //插入
    cin >> a >> c;
    while (a != -1 || c != -1) {
        b.insert(a, c);
        cin >> a >> c;
    }
    //删除
    cin >> a;
    while (a != -1) {
        b.remove(a, c);
        cin >> a;
    }
    //修改
    cin >> a >> c;
    while (a != -1 || c != -1) {
        b.replace(a, c);
        cin >> a >> c;
    }
    //输出
    for (int i = 0; i < b.size(); i++){
        b.retrieve(i, a);
        cout << a << ' ';
    }
    cout << endl;
    for (int i = b.size() - 1; i >= 0; i--) {
        b.retrieve(i, a);
        cout << a << ' ';
    }
    return 0;
}

4. 单词分组【中等】

（单词分组）给定一系列的单词，请把由相同字母组成的单词分为一组，并将所有的分组输出。（要求：按照单词在输入序列中出现的顺序输出分组）
【输入】一系列的单词（单词数量少于1000）
【输出】
分组数x
第一个分组的单词
第二个分组的单词
第x个分组的单词
例如：
【输入】
eat tea tan ate nat bat eate
【输出】
3
eat tea ate eate
tan nat
bat

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

int main() {
    string str;
    vector<int> type;
    vector<vector<string>> print; //二维字符串数组
    int i, j;
    while (cin >> str) {
        int temp = 0;
        //用从右起第1位到第26位记录字母是否出现( •̀ ω •́ )y
        for (i = 0; i < str.size(); i++) {
            temp = temp | (1 << (str[i] - 'a')); //看好了这是或！！
        }
        //看相同的字母组合是否出现过
        for (i = 0; i < type.size(); i++) {
            if (temp == type[i]) {
                print[i].push_back(str);
                break;
            }
        }
        //如果type里没有这个组合，i==type.size
        if (i == type.size()) {
            type.push_back(temp);//把这个组合加进去
            vector<string> d = { str };//看这里！！！
            print.push_back(d);//把字符串加进去
        }
    }
    cout << type.size() << endl;
    for (i = 0; i < print.size(); i++) {
        for (j = 0; j < print[i].size(); j++) {
            cout << print[i][j] << ' ';//输出的是字符串
        }
        cout << endl;
    }
    return 0;
}

5. 前向和后向的最近邻值【中等】

（前向和后向的最近邻值）给定一个包含有m个节点的双链表，链表每个节点的值均为正整数：
（1）节点i的前向最近邻值需要满足j<i,且节点j的值小于节点i的值，j为满足条件的最大位置点。节点j的值即为节点i的前向最近邻值。若j不存在，节点i的前向最近邻值为0。
（2）节点i的后向最近邻值需要满足j>i,且节点j的值大于节点i的值，j为满足条件的最小位置点。节点j的值即为节点i的后向最近邻值。若j不存在，节点i的后向最近邻值为0。
【输入】双链表中的m个值以-1结束
【输出】
按顺序输出每个节点的前向最近邻值；
按顺序输出每个节点的后向最近邻值；
例如：
【输入】 2 1 5 -1
【输出】
0 0 1
5 5 0
【输入】 2 7 3 4 5 -1
【输出】
0 2 2 3 4
7 0 4 5 0

#include <iostream>
using namespace std;
enum Error_code { underflow, overflow, range_Error, success };
const int max_list = 100;
typedef int List_entry;
typedef int Node_entry;

struct Node
{
    Node_entry entry;
    Node* back, * next;
    Node();
    Node(Node_entry item, Node* link_back = NULL, Node* link_next = NULL);
};

Node::Node()
{
    back = NULL;
    next = NULL;
}

Node::Node(Node_entry item, Node* link_back, Node* link_next)
{
    entry = item;
    back = link_back;
    next = link_next;
}

//list的双向链表实现，且存储最后一次访问的位置
class DList
{
public:
    DList();
    ~DList();
    DList(const DList& copy);
    void operator=(const DList& copy);
    int size()const;
    bool full()const;
    bool empty()const;
    void clear();
    Node* get_current();
    Error_code insert(int position, const List_entry& x);
    Error_code remove(int position, List_entry& x);
    Error_code retrieve(int position, List_entry& x)const;
    Error_code replace(int position, List_entry& x);
    void traverse(void(*visit)(List_entry& x));
protected:
    int count;
    Node* head;
    mutable int current_position;
    mutable Node* current;
    void set_position(int position)const;//不再有返回值，直接更新current
};

void DList::set_position(int position)const
{
    //current在前面
    if (current_position <= position) {
        for (; current_position != position; current_position++)
            current = current->next;
    }
    //current在后面
    else {
        for (; current_position != position; current_position--)
            current = current->back;
    } 
}

DList::DList()
{
    count = 0;
    head = NULL;
    current_position = 0;
    current = NULL;
}

DList::~DList()
{
    List_entry x;
    while (!empty())
        remove(0, x);
}

DList::DList(const DList& copy)
{
    count = 0;
    head = NULL;
    Node* newptr = copy.head;
    while (newptr) {
        insert(size(), newptr->entry);
        newptr = newptr->next;
    }
}

void DList::operator=(const DList& copy) {
    List_entry x;
    if (this == &copy) return;//是否为本身
    while (!empty()) remove(0, x);
    Node* newptr = copy.head;
    while (newptr) {
        insert(size(), newptr->entry);
        newptr = newptr->next;
    }
}

int DList::size()const
{
    return count;
}

bool DList::full()const
{
    //看堆满了没
    Node* newptr = new Node();
    if (newptr == NULL) return true;
    delete newptr;//不要忘了删
    return false;
}

bool DList::empty()const
{
    if (count == 0) return true;
    return false;
}

void DList::clear()
{
    List_entry x;
    remove(0, x);
}

Node* DList::get_current()
{
    return current;
}


Error_code DList::insert(int position, const List_entry& x)
{
    if (position < 0 || position > count) return range_Error;
    Node* newptr, * previous, * following;
    if (position == 0) { //在第0号位置插入的特殊情况
        if (count == 0)
            following = NULL;
        else {
            set_position(0);
            following = current;
        }
        previous = NULL;
    }
    else {//一般情况，在链表中间或末尾插入
        set_position(position - 1);
        previous = current;
        following = previous->next;
    }//给f和p赋初始值
    newptr = new Node(x, previous, following);
    if (newptr == NULL) return overflow;
    //除了头和尾
    if (previous != NULL) previous->next = newptr;
    if (following != NULL) following->back = newptr;
    //调整current和c_p
    current = newptr;
    current_position = position;
    if (position == 0) head = newptr;//不要忘了head
    count++;
    return success;
}

Error_code DList::remove(int position, List_entry& x)
{
    if (position < 0 || position >= count) return range_Error;
    Node* previous, * following;
    if (position > 0) {
        set_position(position - 1);//
        previous = current;
        following = previous->next;
        previous->next = following->next;
        if (following->next) following->next->back = previous;
    }
    else {
        following = head;
        head = head->next;
        if (head) head->back = NULL;
        current_position = 0;
        current = head;//删除后记得更新
    }
    x = following->entry;
    delete following;
    count--;
    return success;
}

Error_code DList::retrieve(int position, List_entry& x)const
{
    if (position < 0 || position >= count) return range_Error;
    set_position(position);
    x = current->entry;
    return success;
}

Error_code DList::replace(int position, List_entry& x)
{
    if (position < 0 || position >= count) return range_Error;
    set_position(position);
    current->entry = x;
    return success;
}

void DList::traverse(void(*visit)(List_entry& x))
{
    Node* newptr = head;
    while (newptr) {
        (*visit)(newptr->entry);
        newptr = newptr->next;
    }
}

int main()
{
    List_entry a, x;
    int i;
    cin >> a;
    DList b;
    //输入
    while (a != -1) {
        b.insert(b.size(), a);
        cin >> a;
    }
    int front[100], behind[100];
    //前向最近邻值
    for (i = 0; i < b.size(); i++) {
        bool none = true;
        b.retrieve(i, x);
        Node* temp = b.get_current();
        temp = temp->back;
        while (temp != NULL) {
            if (temp->entry < x) {
                front[i] = temp->entry;
                none = false;
                break;
            }
            else temp = temp->back;
        }
        if (none) front[i] = 0;
    }
    //后向最近邻值
    for (i = 0; i < b.size(); i++) {
        bool none = true;
        b.retrieve(i, x);
        Node* temp = b.get_current();
        temp = temp->next;
        while (temp != NULL) {
            if (temp->entry > x) {
                behind[i] = temp->entry;
                none = false;
                break;
            }
            else temp = temp->next;
        }
        if (none) behind[i] = 0;
    }

    //输出
    for (i = 0; i < b.size(); i++){
        cout << front[i] << ' ';
    }
    cout << endl;
    for (i = 0; i < b.size(); i++) {
        cout << behind[i] << ' ';
    }
    return 0;
}

6. 大数运算【困难】

参考：数据结构与算法(c++)04–list-空空雪上琉璃瓦
（我猜这个博主和我一个学校 嘿嘿）
（大数运算）long long类型一般占8个字节是C/C++中的精度最高的整数类型，其取值范围是： -9223372036854775808～+9223372036854775807。在很多场景中，整数范围超出了long long的最值，例如在非对称加密中密钥长度一般为1024bit，转换为十进制数将超过300位，因此不能直接用内置的整数类型来运算。请编写大数运算类型MyBigInteger，使其支持大数据的加法，减法，乘法的运算。（除法为选做功能，除法运算符合C/C++中的整数除法运算的规则，有20%的测试用例包含除法运算，）
【输入】
大整数n，n的位数<=200
大整数m，m的位数<=200
运算符（+，-，*, /）
【输出】n和m的运算结果
例如：
【输入】
56891237265
32156789215
/-
（第三行输入是-，请忽略/，如果只有-上面就变成粗体了……我也不知道咋回事……）
【输出】
24734448050

#include <iostream>
#include <string>
using namespace std;

int str_cmp(string str1, string str2);
string add(string str1, string str2);
string sub(string str1, string str2);
string multiply(string str1, string str2);
string divide(string str1, string str2);

int main()
{
    char ch;
    string s1, s2, s;
    cin >> s1 >> s2 >> ch;
    switch (ch) {
    case'+':s = add(s1, s2); break;
    case'-':s = sub(s1, s2); break;
    case'*':s = multiply(s1, s2); break;
    case'/':s = divide(s1, s2); break;
    default:break;
    }
    cout << s << endl;
    return 0;
}

int str_cmp(string str1, string str2)
{
    if (str1.size() > str2.size()) return 1;
    else if (str1.size() < str2.size()) return -1;
    return str1.compare(str2);
}

string add(string str1, string str2)
{
    int sign = 1;//符号位
    string str;
    if (str1[0] == '-') {
        if (str2[0] == '-') {
            sign = -1;
            //全负处理一下
            str = add(str1.erase(0, 1), str2.erase(0, 1));
        }
        else {
            str = sub(str2, str1.erase(0, 1));
        }
    }
    else {
        if (str2[0] == '-') {
            str = sub(str1, str2.erase(0, 1));
        }
        else {
            int len1 = str1.size();
            int len2 = str2.size();
            int i;
            //在前后加0
            if (len1 < len2) {
                for (i = 1; i <= len2 - len1; i++)
                    str1 = "0" + str1;
            }
            else {
                for (i = 1; i <= len1 - len2; i++)
                    str2 = "0" + str2;
            }
            int current = 0, carry = 0;//记录加法后的本位和进位
            for (int i = str1.size() - 1; i >= 0; i--) {
                current = ((int)str1[i] - '0' + (int)str2[i] - '0' + carry) % 10;
                carry = ((int)str1[i] - '0' + (int)str2[i] - '0' + carry) / 10;
                str = (char)(current + '0') + str;
            }
            if (carry != 0) {
                str = (char)(carry + '0') + str;
            }
        }
    }
    //处理符号位
    if (sign == -1)
        str = "-" + str;
    return str;
}

string sub(string str1, string str2)
{
    int sign = 1, i;
    string str;
    if (str2[0] == '-') {
        str = add(str1, str2.erase(0, 1));
    }
    else {
        int flag = str_cmp(str1, str2);
        if (flag == 0) return "0";
        if (flag < 0) {
            sign = -1;//减数更长，为负数
            string temp = str1;
            str1 = str2;
            str2 = temp;
        }
        int len = str1.size() - str2.size();
        int jiewei;
        for (i = str2.size() - 1; i >= 0; i--) {
            //按位减法
            if (str1[i + len] < str2[i]) {
                jiewei = 1;
                while (1) {
                    //是0的时候要一直往前借位
                    if (str1[i + len - jiewei] == '0') {
                        str1[i + len - jiewei] = '9';
                        jiewei++;
                    }
                    else {
                        str1[i + len - jiewei] = char(int(str1[i + len - jiewei]) - 1);
                        break;
                    }
                }
                //这里：是加上10，借位
                str = char(str1[i + len] - str2[i] + ':') + str;
            }
            else str = char(str1[i + len] - str2[i] + '0') + str;
        }
        for (i = len - 1; i >= 0; i--)
            str = str1[i] + str;
    }
    //去除结果中多余的前导0
    str.erase(0, str.find_first_not_of('0'));
    if (str.empty()) str = "0";
    if (sign == -1)
        str = "-" + str;
    return str;
}

string multiply(string str1, string str2)
{
    int sign = 1, i, j;
    string str;
    if (str1[0] == '-') {
        sign *= -1;
        str1 = str1.erase(0, 1);
    }
    if (str2[0] == '-') {
        sign *= -1;
        str2 = str2.erase(0, 1);
    }
    int len1 = str1.size();
    int len2 = str2.size();
    for (i = len2 - 1; i >= 0; i--) {
        string tempstr;//储存每一位乘完后的结果
        //本位算完的结果，进位，取的乘数
        int current = 0, carry = 0, str2_cur = int(str2[i]) - '0';
        if (str2_cur != 0) {
            //注意注意注意！！在最前面加个0(太巧妙了QAQ)
            for (j = 1; j <= (int)(len2 - 1 - i); j++)
                tempstr = "0" + tempstr;
            //按位乘str1
            for (j = len1 - 1; j >= 0; j--) {
                current = (str2_cur * (int(str1[j]) - '0') + carry) % 10;
                carry = (str2_cur * (int(str1[j]) - '0') + carry) / 10;
                tempstr = char(current + '0') + tempstr;
            }
            if (carry != 0)
                tempstr = char(carry + '0') + tempstr;
        }
        str = add(str, tempstr);
    }
    str.erase(0, str.find_first_not_of('0'));
    if (str.empty())
        str = "0";
    if (sign == -1)
        str = "-" + str;
    return str;
}

//choose == 1时, 返回商; choose == 0时, 返回余数
string divide(string str1, string str2)
{
    int choose = 1;
    string quo, res;//商和余数
    int sign1 = 1, sign2 = 1;
    int i;
    if (str2 == "0") {
        quo = "wrong";
        res = "'wrong";
        if (choose == 1) return quo;//这题只让返回商
        return res;
    }
    if (str1 == "0") {
        quo = "0";
        res = "0";
    }
    if (str1[0] == '-') {
        str1 = str1.erase(0, 1);
        sign1 *= -1;
        sign2 *= -1;
    }
    if (str2[0] == '-') {
        str2 = str2.erase(0, 1);
        sign1 *= -1;
    }
    int flag = str_cmp(str1, str2);
    //被除数比除数小
    if (flag < 0) {
        quo = "0";
        res = str1;
    }
    //俩数相等
    else if (flag == 0) {
        quo = "1";
        res = "0";
    }
    else {
        int len1 = str1.size();
        int len2 = str2.size();
        string tempstr;
        tempstr.append(str1, 0, len2 - 1);//腾出一些零
        for (i = len2 - 1; i < len1; i++) {
            tempstr = tempstr + str1[i];
            tempstr.erase(0, tempstr.find_first_not_of('0'));
            if (tempstr.empty())
                tempstr = "0";
            for (char ch = '9'; ch >= '0'; ch--) {
                string str;
                str = str + ch;
                if (str_cmp(multiply(str2, str), tempstr) <= 0) {
                    quo = quo + ch;
                    tempstr = sub(tempstr, multiply(str2, str));
                    break;
                }
            }
        }
        res = tempstr;
    }
    quo.erase(0, quo.find_first_not_of('0'));
    if (quo.empty()) quo = "0";
    if (sign1 == -1) quo = "-" + quo;
    if (sign2 == -1) res = "-" + res;
    if (choose == 1) return quo;
    return res;
}