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

bool remove(Node *&h,int &a,int pos);

``````/*
P167 5.8.20

bool remove(Node *&h,int &a,int pos);

*/
#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

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

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();
}
}``````