南大C++:《程序设计教程 用C++语言编写》答案（七）

这些是我自己写的代码，全部通过编译。

5.8.20 把在链表中删除一个结点的操作写成一个函数：

bool remove(Node *&h,int &a,int pos);
其中，h为头指针，a用于存放删除的结点的值，pos(>0)表示删除结点的位置。操作成功返回true，否则返回false。

/*
P167 5.8.20
把在链表中删除一个结点的操作写成一个函数：
bool remove(Node *&h,int &a,int pos);
其中，h为头指针，a用于存放删除的结点的值，pos(>0)表示删除结点的位置。操作成功返回true，否则返回false。
*/
#include <iostream>
using namespace std;

struct Node
{
    int val;
    Node *next;
};

bool remove1(Node *&h, int &a, int pos)
{
    Node *q=h;
    if (pos == 1)
    {
        h = h->next;
        a = q->val;
        delete q;
        return true;
    }
    Node *p=h;
    while (pos-1)
    {
        p = q;
        q = q->next;
        pos--;
    }
    if (q == NULL)
        return false;
    else
    {
        p->next = q->next;
        a = q->val;
        delete q;
        return true;
    }
}

Node *insert(Node *&h, int a, int pos = 0)
{
    if (h == NULL)
    {
        h = new Node;
        h->val = a;
        h->next = NULL;
        return h;
    }
    Node *p = new Node;

    p->val = a;
    p->next = NULL;
    if (pos == 0)
    {
        p->next = h;
        h = p;
        return h;
    }
    Node *q = h;
    while (pos - 1)
    {
        if (q == NULL)
        {
            cout << "can't add" << endl;
            return h;
        }
        q = q->next;
        pos--;
    }
    p->next = q->next;
    q->next = p;
    return h;
}

void print(Node *h)
{
    while (h != NULL)
    {
        cout << h->val;
        h = h->next;
    }
    cout << endl;
}

int main()
{
    while (1)
    {
        int t;
        int pos;
        Node *h = NULL;
        while (1)
        {
            cout << "插入值和位置（最后一个以-1结束）：";
            cin >> t >> pos;
            if (t == -1)
                break;
            insert(h, t, pos);
        }
        cout << "链表：" << endl;
        print(h);
        while (1)
        {
            cout << "删除的位置：";
            cin >> pos;
            remove1(h, t, pos);
            print(h);
            cout << "删除的值：" << t << endl;

        }
    }
}

5.8.21 编写一个程序。首先建立两个集合（从键盘输入集合的元素），然后计算这两个集合的交集、并集以及差集，最后输出计算结果。要求用链表实现集合的表示。

/*
P167 5.8.21
编写一个程序。首先建立两个集合（从键盘输入集合的元素），然后计算这两个集合的交集、并集以及差集，最后输出计算结果。要求用链表实现集合
的表示。
*/

#include <iostream>
using namespace std;

struct Node
{
    int val;
    Node *next;
};

bool insert1(Node *h, int n)
{
    if (h->next == NULL)
    {
        h->next = new Node;
        h->next->val = n;
        h->next->next = NULL;
        return true;
    }
    while (h->next!=NULL&&h->next->val < n)
        h = h->next;
    if (h->next!=NULL&&h->next->val == n)
        return true;
    else
    {
        Node *q = new Node;
        q->val = n;
        q->next = h->next;
        h->next = q;
        return true;
    }
    return false;
}

bool find(Node *h, int a)
{
    while (h->next != NULL)
    {
        if (h->next->val == a)
            return true;
        h = h->next;
    }
    return false;
}

void print(Node *h)
{
    while (h->next != NULL)
    {
        cout << h->next->val << ' ';
        h= h->next;
    }
    cout << endl;
}


Node *or(Node *h1, Node *h2)
{
    Node *h3 = new Node;
    h3->next = NULL;
    while (h1->next != NULL)
    {
        insert1(h3, h1->next->val);
        h1 = h1->next;
    }
    while (h2->next != NULL)
    {
        if (!find(h3, h2->next->val))
            insert1(h3, h2->next->val);
        h2 = h2->next;
    }
    return h3;
}

Node *and(Node *h1, Node *h2)
{
    Node *h3 = new Node;
    h3->next = NULL;
    while (h1->next != NULL)
    {
        if (find(h2, h1->next->val))
            insert1(h3, h1->next->val);
        h1 = h1->next;
    }
    return h3;
}

Node *sub(Node *h1, Node *h2)
{
    Node *h3 = new Node;
    h3->next = NULL;
    while (h1->next != NULL)
    {
        if (!find(h2, h1->next->val))
            insert1(h3, h1->next->val);
        h1 = h1->next;
    }
    return h3;
}

int main()
{
    while (1)
    {
        int t;
        Node *h1 = new Node;
        h1->next = NULL;
        Node *h2 = new Node;
        h2->next = NULL;
        cout << "集合1元素（以-1结尾）：";
        while (1)
        {
            cin >> t;
            if (t == -1)
                break;
            insert1(h1, t);
            //cout << h1->next->val << endl;
        }
        cout << "集合2元素（以-1结尾）：";
        while (1)
        {
            cin >> t;
            if (t == -1)
                break;
            insert1(h2, t);
        }
        cout << "集合1：";
        print(h1);
        cout << "集合2：";
        print(h2);
        cout << "交集：";
        print(and(h1,h2));
        cout << "并集：";
        print(or(h1,h2));
        cout << "集合1与集合2的差集：";
        print(sub(h1, h2));
        cout << "集合2与集合1的差集：";
        print(sub(h2, h1));
    }
}

5.8.22 链表插入排序。

/*
P167 5.8.22
链表插入排序。
*/
#include <iostream>
using namespace std;

struct Node
{
    int val;
    Node *next;
};

void insert(Node *h, int n)
{
    if (h == NULL)
    {
        h = new Node;
        h->next = new Node;
        h->next->val = n;
        h->next->next = NULL;
    }
    else
    {
        while (h->next != NULL)
            h = h->next;
        h->next = new Node;
        h->next->val = n;
        h->next->next = NULL;
    }
}

void sort(Node *h)
{
    Node *q = NULL;
    Node *p = NULL;
    Node *s = h->next->next;
    while(s!= NULL)
    {
        q = h;
        while (q->next != s&&q->next->val < s->val)
            q = q->next;
        p = s;
        s = s->next;
        p->next = q->next;
        q->next = p;
    }
}

void print(Node *h)
{
    while (h->next != NULL)
    {
        cout << h->next->val << ' ';
        h = h->next;
    }
    cout << endl;
}

int main()
{
    while (1)
    {
        int t;
        Node *h = new Node;
        h->next = NULL;
        cout << "输入链表元素（以-1结尾）：";
        while (1)
        {
            cin >> t;
            if (t == -1)
                break;
            insert(h, t);
        }
        cout << "原链表：";
        print(h);
        cout << "排序后：";
        sort(h);
        print(h);
    }
}

6.8.13 定义一个描述二维坐标系中点对象的类Point，它具有下述成员函数：

1. double r();//计算极坐标的极半径
2. double theta();//计算极坐标的极角
3. double distance(const Point& p);//计算与点p的距离
4. Point relative(const Point& p);//计算相对于p的相对坐标
5. bool is_above_left(const Point& p);//判断是否在点p的左上方
   改为直角坐标

/*
P201 6.8.13
定义一个描述二维坐标系中点对象的类Point，它具有下述成员函数：
    1)double r();//计算极坐标的极半径
    2)double theta();//计算极坐标的极角
    3)double distance(const Point& p);//计算与点p的距离
    4)Point relative(const Point& p);//计算相对于p的相对坐标
    5)bool is_above_left(const Point& p);//判断是否在点p的左上方
**改为直角坐标**
*/
#include <iostream>
#include <cmath>
using namespace std;

class Point
{
private:
    double a;
    double b;
public:
    Point()
    {
        b = a = 0;
    }
    Point(double c,double d)
    {
        a = c;
        b = d;
    }
    double r()
    {
        return sqrt(a*a+b*b);
    }
    double theta()
    {
        return atan(b / a)*180/3.14159;
    }
    double distance(const Point &p)
    {
        return sqrt((a - p.a)*(a - p.a) + (b - p.b)*(b - p.b));
    }
    Point relative(const Point &p)
    {
        return Point(p.a - a, p.b - b);
    }
    bool is_above_left(const Point &p)
    {
        if (p.a<a&&p.b>b)
            return true;
        return false;
    }
    void print()
    {
        cout << a << ' ' << b << endl;
    }
};

int main()
{
    double x, y;
    while (1)
    {
        cout << "点1坐标：";
        cin >> x >> y;
        Point m(x, y);
        cout << "点2坐标：";
        cin >> x >> y;
        Point n(x, y);
        cout << "点1与原点距离：" << m.r() << endl;
        cout << "点1与x轴夹角：" << m.theta() << endl;
        cout << "点1与点2距离：" << m.distance(n) << endl;
        cout << "点1与点2相对坐标";
        m.relative(n).print();
        cout << "点2与原点距离：" << n.r() << endl;
        cout << "点2与x轴夹角：" << n.theta() << endl;
        cout << "点2与点1距离：" << n.distance(m) << endl;
        cout << "点2与点1相对坐标:";
        n.relative(m).print();
    }
}

6.8.14 定义一个时间类Time，它能表示时、分、秒，并提供以下操作：

1. Time(int h,int m,int s);//构造函数
2. void set(int h,int m,int s);//调整时间
3. void increment();//时间增加一秒
4. void display();//显示时间值
5. bool equal(Time &other_time);//比较是否与某个时间相等
6. bool less_than(Time &other_time);//比较是否与早于某个时间

/*
P202 6.8.14
定义一个时间类Time，它能表示时、分、秒，并提供以下操作：
    1)Time(int h,int m,int s);//构造函数
    2)void set(int h,int m,int s);//调整时间
    3)void increment();//时间增加一秒
    4)void display();//显示时间值
    5)bool equal(Time &other_time);//比较是否与某个时间相等
    6)bool less_than(Time &other_time);//比较是否与早于某个时间
*/
#include <iostream>
#include <iomanip>
using namespace std;

class Time
{
    int h, m, s;
public:
    Time()
    {
        h = m = s = 0;
    }
    Time(int th, int tm, int ts)
    {
        h = th;
        m = tm;
        s = ts;
    }
    void set(int th, int tm, int ts)
    {
        h = th;
        m = tm;
        s = ts;
    }
    void increment()
    {
        if (s == 59)
        {
            if (m == 59)
            {
                if (h == 23)
                    h = 0;
                else
                    h++;
                m = 0;
            }
            else
                m++;
            s = 0;
        }
        else
            s++;
    }
    void display()
    {
        cout << setfill('0') << setw(2) << h << ':' <<setw(2)<< m << ':' <<setw(2)<< s << endl;
    }
    bool equal(const Time &t)
    {
        if (t.h == h&&t.m == m&&t.s == s)
            return true;
        return false;
    }
    bool less_than(const Time &t)
    {
        if (h * 60 * 60 + m * 60 + s < t.h * 60 * 60 + t.m * 60 + t.s)
            return true;
        return false;
    }
};

int main()
{
    int h, m, s;
    cout << "输入一个时间（时 分 秒）";
    cin >> h >> m >> s;
    Time t(h, m, s);
    for (int i = 0; i <= 10000; i++)
    {
        cout << "增加1秒：";
        t.increment();
        t.display();
    }
}