西电 程序设计基础课程设计 作业

警告
本文最后更新于 2021-04-17,文中内容可能已过时。

当时做的程序设计课程的作业. 一共五题, 以报告的形式提交.

质量应该比较高(高傲).

高精度计算

涉及知识点: 数组, 流程控制, 函数等

要求:

用整型数组表示10进制大整数(超过 $2^{32}$ 的整数), 数组的每个元素存储大整数的一位数字, 实现大整数的加减法.

可将高精度整数写成一个类.

成员变量有:

1
2
int a[MAXN], len;
bool negative;

其中, 数组a用来存储大整数的一个数位, a[1]为个位上的数字, a[2]为十位上的数字… len表示数字的位数, negative 表示是否为负数.

先判断两数的位数, 位数小的数小.

位数不相等, 再从高位到低位判断数值的大小, 数值小的数小.

数值都相等, 则两数相等.

代码中的abs_lower()即为绝对值比较大小的具体实现.

设两加数为$x, y$

先创建一个高精度整数对象ans. 将ans.len设为max(x.len, y.len) + 1. 因为结果的位数不会超过这个值.

从个位开始, 两个数的对应位数相加存入ans的对应位置. 如果和大于$10$, 则进位, 即ans的下一位$+1$, 然后这一位对$10$取模.

最后考虑是否ans.len是不是大了(因为一开始设置的是可能达到的最大值), 依次判断前面是不是$0$, 如果是, 则减小len, 如果不是, 则说明len正好.

注意当len=1ans=0时, 不应该继续减小len, 且要设置negative=0. 即这个数是$0$, $0$的位数是$1$, $-0$应该表示为$0$.

返回ans.

代码中的abs_plus()即为无符号加法的具体实现.

设被减数与减数分别为$x, y$.

创建高精度整数对象ans.

先判断正负号, 利用绝对值比较大小. 如果$x < y$, 那么设置ans.negative=1, 数值为 $y-x$的数值.

所以不妨假设 $x > y$, 具体实现和加法类似, 先设ans.len为可能的最大值, 即max(x.len, y.len), 从低位到高位计算各个数位, 注意借位即可.

和加法一样, 最后处理一下ans.len以及ans.negative, 然后返回ans.

代码中的abs_minus()即位无符号减法的具体实现.

有符号的加减法可以通过对两参数的符号分类讨论, 进而转化为无符号加减法.

设两加数为$x, y$, 其绝对值为$|x|, |y|$

若$x, y$符号相同, 则和的数值$|x|+|y|$, 符号为加数的符号;

若$x, y$符号不同, 则加法转化为绝对值的减法:

若$x$为负, 则结果为$|y|-|x|$; 若$y$为负, 则结果为$|x|-|y|$.

代码中重载运算符 + 即为加法的具体实现.

设被减数和减数分别为$x, y$

若$x, y$符号相同, 若参数符号为正, 则差为$|x|-|y|$; 若为负, 则差为绝对值相减后的相反数;

若$x, y$符号不同, 则转化为绝对值加法, 符号与$x$一致.

代码中重载运算符 - 即为减法的具体实现.

比较运算符基于已重载的 <, 自增自减基于已重载的 +-.

重载的原理比较简单, 这里不再赘述.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

class BigInt {
private:
	static const int MAXN = 100;
	int a[MAXN], len;	// a中每一位存数字, len为大整数的长度
	bool negative;		// 是否是负数
	bool abs_lower(const BigInt &x, const BigInt &y) const;
	BigInt abs_plus(const BigInt &x, const BigInt &y) const;
	BigInt abs_minus(const BigInt &x, const BigInt &y) const;
	void adjust();
public:
	BigInt(const int x = 0);
	BigInt(const char s[]);
	bool operator < (const BigInt &y) const;
	bool operator == (const BigInt &y) const;
	bool operator != (const BigInt &y) const;
	bool operator >= (const BigInt &y) const;
	bool operator > (const BigInt &y) const;
	bool operator <= (const BigInt &y) const;
	BigInt operator += (const BigInt &y);
	BigInt operator -= (const BigInt &y);
	BigInt operator ++ ();
	BigInt operator -- ();
	BigInt operator ++ (int);
	BigInt operator -- (int);
	BigInt operator + (const BigInt &y) const;
	BigInt operator - (const BigInt &y) const;
	BigInt operator = (const BigInt &y);
	BigInt operator = (const int &y);
	BigInt operator = (const char s[]);
	BigInt operator - () const;
	void print();
};

/********************************
/ 构造函数, int转大整数
/ para x: 需要转成大整数的int型
********************************/
BigInt::BigInt(const int x) {
	memset(a, 0, sizeof(a));
	len = 0;
	negative = x < 0;
	int tmp = abs(x);
	do {
		a[++len] = tmp % 10;
		tmp /= 10;
	} while(tmp);
}

/********************************
/ 构造函数, string转大整数
/ para s: 需要转成大整数的字符串
********************************/
BigInt::BigInt(const char s[]) {
	memset(a, 0, sizeof(a));
	negative = s[0] == '-';
	len = strlen(s) - negative;
	for (int i = 0; i < len; i++)
		a[len - i] = s[i + negative] - '0';
	adjust();
}

/********************************
/ 重载 =, 同类型直接赋值
********************************/
BigInt BigInt::operator = (const BigInt &y) {
	len = y.len;
	negative = y.negative;
	memcpy(a, y.a, sizeof(a));
	return *this;
}

/********************************
/ 重载 =, 通过构造函数实现int转BigInt
********************************/
BigInt BigInt::operator = (const int &y) {
	return *this = BigInt(y);
}

/********************************
/ 重载 =, 通过构造函数实现string转BigInt
********************************/
BigInt BigInt::operator = (const char s[]) {
	return *this = BigInt(s);
}

/********************************
/ 重载 <
/ return: 是否小于 y
********************************/
bool BigInt::operator < (const BigInt &y) const {
	if (negative == y.negative)
		return negative ^ abs_lower(*this, y);
	else
		return negative;
}

/********************************
/ 重载 ==
/ return: 是否等于 y
********************************/
bool BigInt::operator == (const BigInt &y) const {
	if (len == y.len) {
		for (int i = 1; i <= len; i++)
			if (a[i] != y.a[i])
				return false;
		return true;
	}
	return false;
}

/********************************
/ 重载 !=
/ return: 是否不等于 y
********************************/
bool BigInt::operator != (const BigInt &y) const {
	return !(*this == y);
}

/********************************
/ 重载 >=
/ return: 是否不小于 y
********************************/
bool BigInt::operator >= (const BigInt &y) const {
	return !(*this < y);
}

/********************************
/ 重载 >
/ return: 是否大于 y
********************************/
bool BigInt::operator > (const BigInt &y) const {
	return *this >= y && *this != y;
}

/********************************
/ 重载 <=
/ return: 是否不大于 y
********************************/
bool BigInt::operator <= (const BigInt &y) const {
	return !(*this > y);
}

/********************************
/ 重载 +=
/ return: 加上y后的值
********************************/
BigInt BigInt::operator += (const BigInt &y) {
	return *this = (*this + y);
}

/********************************
/ 重载 -=
/ return: 减去y后的值
********************************/
BigInt BigInt::operator -= (const BigInt &y) {
	return *this = (*this - y);
}

/********************************
/ 重载前置 ++
/ return: +1 后的值
********************************/
BigInt BigInt::operator ++ () {
	return *this = (*this + BigInt(1));
}

/********************************
/ 重载前置 --
/ return: -1 后的值
********************************/
BigInt BigInt::operator -- () {
	return *this = (*this - BigInt(1));
}

/********************************
/ 重载后置 ++
/ return: 原值
********************************/
BigInt BigInt::operator ++ (int) {
	BigInt tmp = *this;
	++(*this);
	return tmp;
}

/********************************
/ 重载后置 --
/ return: 原值
********************************/
BigInt BigInt::operator -- (int) {
	BigInt tmp = *this;
	--(*this);
	return tmp;
}

/********************************
/ 重载 +
/ return: 加上y之后的值
********************************/
BigInt BigInt::operator + (const BigInt &y) const {
	if (negative == y.negative) {
		BigInt ans = abs_plus(*this, y);
		ans.negative = negative;
		return ans;
	}
	else
		return negative ? abs_minus(y, *this) : abs_minus(*this, y);
}

/********************************
/ 重载 -
/ return: 大整数减去y之后的值
********************************/
BigInt BigInt::operator - (const BigInt &y) const {
	if (negative == y.negative) {
		BigInt ans = abs_minus(*this, y);
		ans.negative ^= negative;
		return ans;
	}
	else {
		BigInt ans = abs_plus(*this, y);
		ans.negative = negative;
		return ans;
	}
}

/********************************
/ 重载前置负号, 取相反数
/ return: 相反数
********************************/
BigInt BigInt::operator - () const {
	BigInt ans = *this;
	ans.negative ^= 1;
	ans.adjust();
	return ans;
}

/********************************
/ 输出大整数
********************************/
void BigInt::print() {
	if (negative)
		printf("-");
	for (int i = len; i; i--)
		printf("%d", a[i]);
}

/********************************
/ 判断两个大整数的绝对值大小
/ para x, y: 两个大整数
/ return: |x| 是否小于 |y|
********************************/
bool BigInt::abs_lower(const BigInt &x, const BigInt &y) const {
	if(x.len == y.len) {
		for(int i = x.len; i >= 1; i--)
			if(x.a[i] < y.a[i])
				return true;
			else if (x.a[i] > y.a[i])
				return false;
		return false;
	}
	return x.len < y.len;
}

/********************************
/ 两大整数的绝对值相加
/ para x, y: 两大整数
/ return: 大整数|x| + |y|, 符号为正
********************************/
BigInt BigInt::abs_plus(const BigInt &x, const BigInt &y) const {
	BigInt ans;
	ans.len = max(x.len, y.len) + 1;
	for(int i = 1; i <= ans.len; i++) {
		ans.a[i] += x.a[i] + y.a[i];
		ans.a[i+1] = ans.a[i] / 10;
		ans.a[i] %= 10;
	}
	ans.adjust();
	return ans;
}

/********************************
/ 两大整数的绝对值相减
/ para x, y: 两大整数
/ return: 大整数|x| - |y|, 有符号
********************************/
BigInt BigInt::abs_minus(const BigInt &x, const BigInt &y) const {
	if(abs_lower(x, y)) {
		BigInt ans = abs_minus(y, *this);
		ans.negative = 1;
		return ans;
	}
	BigInt ans;
	ans.len = max(x.len, y.len);
	for(int i = 1; i <= ans.len; i++) {
		if(x.a[i] < y.a[i]) {
			ans.a[i + 1]--;
			ans.a[i] += 10;
		}
		ans.a[i] += x.a[i] - y.a[i];
	}
	ans.adjust();
	return ans;
}

/********************************
/ 调整len的值, 用于加减法运算中
********************************/
void BigInt::adjust() {
	while(len > 1 && !a[len])
		len--;
	if (len == 1 && !a[1])
		negative = 0;
}

简单数据结构-堆栈模拟

涉及知识点: 内存管理, 结构体定义, 基本数据结构

要求:

编写一个程序模拟堆栈, 要求能够模拟, 入栈, 出栈, 返回栈顶元素等基本操作. 栈中元素可用整数代替. 不能使用C++模板库预定义的类型. 程序运行中可输入多组入栈, 出栈操作, 每次操作后展示栈中元素.

考虑到栈的可拓展性, 可将其写成模板类.

首先定义一个模板节点, 除了存储数据意外, 还存储一个指针. 这个指针指向栈中的下一个元素.

其次是栈类, 成员变量有数据的栈顶指针Node<T> *head, 以及栈中的元素个数(栈的大小)sz.

初始化栈的大小为$0$, 栈顶指针为空, 表示空栈.

新建节点, 将该节点的值设为输入值, 指针指向当前栈顶元素.

将栈顶指针指向新建的节点.

代码中的push()即push的具体实现

直接调用栈顶指针head, 返回其所指的元素的值.

代码中的top()即top的具体实现

栈顶元素的nxt指针指向的是倒数第二个元素. 所以将栈顶指针指向该元素, 并将栈顶删除.

代码中的pop()即pop的具体实现

根据实际问题, 实现了其他辅助性的函数.

这些函数比较简单, 不再赘述.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cstdio>
using namespace std;

template<typename T>
struct Node {
	T val;
	Node* nxt;
	Node(T v, Node* n):val(v), nxt(n) {}
};

template<typename T>
class stack {
private:
	Node<T>* head;
	Node<T>* new_node(const T& v, Node<T>* n);
	int sz;
public:
	stack();
	void push(const T& v);
	T pop();
	T top();
	int size();
	bool empty();
	void clear();
};

/*******************
/ 构造函数
/ 初始化sz为0
/ 初始化head为NULL
********************/
template<typename T>
stack<T>::stack() {
	sz = 0;
	head = NULL;
}

/*******************
/ 压入
/ para v: 压入栈的值
/ return: none
********************/
template <typename T>
void stack<T>::push(const T& v) {
	sz++;
	head = new_node(v, head);
}

/*******************
/ 弹出
/ return: 栈顶元素
********************/
template <typename T>
T stack<T>::pop() {
	if (sz) {
		T val = top();
		Node<T>* node = head;
		head = head -> nxt;
		delete(node);
		sz--;
		return val;
	}
	else
		return T();
}

/*******************
/ 栈顶
/ return: 栈顶元素
********************/
template <typename T>
T stack<T>::top() {
	return head -> val;
}

/*******************
/ 获取栈中元素个数
/ return: 元素个数
********************/
template<typename T>
int stack<T>::size() {
	return sz;
}

/*******************
/ 判断栈是否为空
/ return: 元素个数
********************/
template <typename T>
bool stack<T>::empty() {
	return sz == 0;
}

/*******************
/ 清空栈
********************/
template <typename T>
void stack<T>::clear() {
	while (!empty())
		pop();
}

/*******************
/ 新建元素
/ para v: 元素值
/ para n: 元素节点
/ return: 元素
********************/
template <typename T>
Node<T>* stack<T>::new_node(const T& v, Node<T>* n) {
	return new Node<T>(v, n);
}

位图图像文件缩放

涉及知识点: 文件读写, 结构体定义, 内存管理, 基本图像处理算法, 命令行参数

要求:

编写一个程序, 可以在命令行输入参数, 完成指定文件的缩放, 并存储到新文件, 命令行参数如下

zoom file1.bmp 200 file2.bmp

第一个参数为可执行程序名称, 第二个参数为原始图像文件名, 第三个参数为缩放比例(百分比), 第四个参数为新文件名

位图文件由三部分组成: 文件头 + 位图信息 + 位图像素数据

1, 位图文件头. 位图文件头主要用于识别位图文件. 以下是位图文件头结构的定义:

1
2
3
4
5
6
7
typedef struct tagBITMAPFILEHEADER { // bmfh
    WORD    bfType;
    DWORD   bfSize;
    WORD    bfReserved1;
    WORD    bfReserved2;
    DWORD   bfOffBits;
} BITMAPFILEHEADER;

其中的bfType值应该是"BM" (0x4d42) , 标志该文件是位图文件. bfSize的值是位图文件的大小.

2, 位图信息中所记录的值用于分配内存, 设置调色板信息, 读取像素值等. 以下是位图信息结构的定义:

1
2
3
4
typedef struct tagBITMAPINFO {
    BITMAPINFOHEADER    bmiHeader;
    RGBQUAD             bmiColors[1];
} BITMAPINFO;

可见位图信息也是由两部分组成的: 位图信息头 + 颜色表

2.1位图信息头. 位图信息头包含了单个像素所用字节数以及描述颜色的格式, 此外还包括位图的宽度, 高度, 目标设备的位平面数, 图像的压缩格式. 以下是位图信息头结构的定义:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
typedef struct tagBITMAPINFOHEADER{ // bmih
    DWORD  biSize;
    LONG   biWidth;
    LONG   biHeight;
    WORD   biPlanes;
    WORD   biBitCount
    DWORD  biCompression;
    DWORD  biSizeImage;
    LONG   biXPelsPerMeter;
    LONG   biYPelsPerMeter;
    DWORD  biClrUsed;
    DWORD  biClrImportant;
} BITMAPINFOHEADER;

下表是对结构体当中各个成员的说明:

结构成员 说 明
biSize 结构BITMAPINFOHEADER的字节数, 即sizeof(BITMAPINFOHEADER)*
biWidth 以像素为单位的图像宽度*
biHeight 以像素为单位的图像长度*
biplanes 目标设备的位平面数
biBitCount 每个像素的位数* (1)
biCompression 图像的压缩格式 (这个值几乎总是为0)
biSizeImage 以字节为单位的图像数据的大小 (对BI_RGB压缩方式而言)
biXPelsPermeter 水平方向上的每米的像素个数
biYpelsPerMeter 垂直方向上的每米的像素个数
biClrused 调色板中实际使用的颜色数 (2)
biClrImportant 现实位图时必须的颜色数 (3)

说明: *是需要加以注意的部分, 因为它们是我们在进行位图操作时经常参考的变量

(1) 对于每个像素的字节数, 分别有一下意义:

  • 0, 用在JPEG格式中
  • 1, 单色图, 调色板中含有两种颜色, 也就是我们通常说的黑白图片
  • 4, 16色图
  • 8, 256色图, 通常说的灰度图
  • 16, 64K图, 一般没有调色板, 图像数据中每两个字节表示一个像素, 5个或6个位表示一个RGB分量
  • 24, 16M真彩色图, 一般没有调色板, 图像数据中每3个字节表示一个像素, 每个字节表示一个RGB分量
  • 32, 4G真彩色, 一般没有调色板, 每4个字节表示一个像素, 相对24位真彩图而言, 加入了一个透明度, 即RGBA模式

(2) 这个值通常为0, 表示使用biBitCount确定的全部颜色, 例外是使用的颜色树木小于制定的颜色深度的颜色数目的最大值.

(3) 这个值通常为0, 表示所有的颜色都是必需的

2.2颜色表. 颜色表一般是针对16位一下的图像而设置的, 对于16位和16位以上的图像, 由于其位图像素数据中直接对对应像素的RGB(A)颜色进行描述, 因而省却了调色板. 而对于16位一下的图像, 由于其位图像素数据中记录的只是调色板索引值, 因而需要根据这个索引到调色板去取得相应的RGB(A)颜色. 颜色表的作用就是创建调色板.

颜色表是由颜色表项组成的, 颜色表项结构的定义如下:

1
2
3
4
5
6
typedef struct tagRGBQUAD { // rgbq
    BYTE    rgbBlue;
    BYTE    rgbGreen;
    BYTE    rgbRed;
    BYTE    rgbReserved;
} RGBQUAD;

其中需要注意的问题是, RGBQUAD结构中的颜色顺序是BGR, 而不是平常的RGB.

3, 位图数据. 最后, 在位图文件头, 位图信息头, 位图颜色表之后, 便是位图的主体部分: 位图数据. 根据不同的位图, 位图数据所占据的字节数也是不同的, 比如, 对于8位位图, 每个字节代表了一个像素, 对于16位位图, 每两个字节代表了一个像素, 对于24位位图, 每三个字节代表了一个像素, 对于32位位图, 每四个字节代表了一个像素.

由于比 8 位更小的位深一个像素不到一个字节, 处理需完全展开字节, 较为麻烦, 练习只处理 8 位以上的位图.

头文件windows.h中定义了与位图有关的结构体, 直接拿来用即可.

根据位图定义进行读入和输出.

需要注意的是, 八位及以下的位图具有调色板, 需要读入, 且调色板大小为 $256 \times 4$.

输入和输出较为简单, 不再赘述.

由缩放比例$r$和缩放后的坐标$(x, y)$, 可以得到原图中对应坐标$(x/r, y/r)$. 其中, / 和c中的一致, 当$x(y)>0, r>0$时取下整.

用原图中对应坐标像素填充缩放后的坐标, 这种简单的缩放方法成为临近插值法.

具体实现也很简单. 需要注意的是, 不同位深的位图存储一个像素的数据大小是不同的, 对于bitCount位深, 每bitCount/8个字节代表一个像素. 在赋值的过程中需注意. 利用memcopy函数可以方便进行复制.

代码中scale()即为缩放的具体实现.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include <windows.h>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

class BitMap {
private:
	BITMAPFILEHEADER fileHeader;
	BITMAPINFOHEADER infoHeader;
	LPRGBQUAD colorTable;
	int width, height, bitCount;
	int getLineSize();
	int getDataSize();
	int getHeaderSize();
	int getColorTableSize();
	void setFileHeader();
	void setInfoHeader();
	bool writeFile(FILE *f);
public:
	unsigned char *dataBuf;
	BitMap(){}
	BitMap(int width, int height, int bitCount);
	bool load(const char *fileName);
	bool save(const char *fileName);
	BitMap scale(const double rate);
	int getBitCount();
};

/**********************************
/ 构造函数
/ para width: 图片宽度
/ para height: 图片高度
/ para bitCount: 图片位深
**********************************/
BitMap::BitMap(int width, int height, int bitCount):
			width(width), height(height), bitCount(bitCount) {
	colorTable = NULL;
	int dataSize = getDataSize();
	dataBuf = (unsigned char*)malloc(dataSize); // 分配数据空间
	memset(dataBuf, 0, sizeof(dataSize));
}

/**********************************
/ 计算一行的大小
/ return: 当前属性对应的一行的数值大小
**********************************/
int BitMap::getLineSize() {
	return (width * bitCount / 8 + 3) / 4 * 4;
}

/**********************************
/ 计算整个图像的大小
/ return: 当前属性对应的图像真实大小
**********************************/
int BitMap::getDataSize() {
	return sizeof(unsigned char) * bitCount / 8 * height * getLineSize();
}

/**********************************
/ 计算位图文件的 header 大小
/ return: 当前属性对应的 header 大小
**********************************/
int BitMap::getHeaderSize() {
	return sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + getColorTableSize();
}

/**********************************
/ 计算位图文件的调色板大小
/ return: 调色板大小
**********************************/
int BitMap::getColorTableSize() {
	if (colorTable == NULL)
		return 0;
	else
		return sizeof(RGBQUAD) * 256;
}

/**********************************
/ 设置 BITMAPFILEHEADER 的属性
**********************************/
void BitMap::setFileHeader() {
	fileHeader.bfType = 0x4D42;
	fileHeader.bfSize = getHeaderSize() + getDataSize();
	fileHeader.bfOffBits = getHeaderSize();
	fileHeader.bfReserved1 = 0;
	fileHeader.bfReserved2 = 0;
}

/**********************************
/ 设置 BITMAPINFOHEADER 的属性
**********************************/
void BitMap::setInfoHeader() {
	infoHeader.biWidth = width;
	infoHeader.biHeight = height;
	infoHeader.biBitCount = bitCount;
	infoHeader.biSizeImage = getDataSize();
	infoHeader.biSize = 40;
	infoHeader.biPlanes = 1;
	infoHeader.biCompression = 0;
	infoHeader.biClrImportant = 0;
	infoHeader.biXPelsPerMeter = 0;
	infoHeader.biYPelsPerMeter = 0;
}

/**********************************
/ 读取位图
/ para fileName: 位图文件
/ return: 是否读取成功, 文件不存在读取失败
**********************************/
bool BitMap::load(const char *fileName) {
	FILE *f = fopen(fileName, "rb");
	if (!f)
		return false;
	fread(&fileHeader, sizeof(BITMAPFILEHEADER), 1, f); // 读取 BITMAPFILEHEADER
	fread(&infoHeader, sizeof(BITMAPINFOHEADER), 1, f); // 读取 BITMAPINFOHEADER
	width = infoHeader.biWidth;
	height = infoHeader.biHeight;
	bitCount = infoHeader.biBitCount;
	// 位深小于等于8的位图还需读入调色板
	if (bitCount <= 8) {
	    colorTable = new RGBQUAD[256];
	    fread(colorTable, 1, getColorTableSize(), f);
	}
	else
		colorTable = NULL;
	// 读取位图数据
	dataBuf = new unsigned char[infoHeader.biSizeImage];
	fread(dataBuf, 1, infoHeader.biSizeImage, f);
	fclose(f);
	return true;
}

/**********************************
/ 将位图所有数据写入文件
/ para f: 需要写如的目标文件
/ return: 是否写入成功, 文件不存在写入失败
**********************************/
bool BitMap::writeFile(FILE *f) {
	if (!f)
		return false;
	// 将header写入位图文件
	fwrite(&fileHeader, sizeof(BITMAPFILEHEADER), 1, f);
	fwrite(&infoHeader, sizeof(BITMAPINFOHEADER), 1, f);
	// 将调色板写入位图文件
	if (colorTable != NULL)
		fwrite(colorTable, 1, getColorTableSize(), f);
	// 将数据写入位图文件
	fwrite(dataBuf, 1, infoHeader.biSizeImage, f);
	return true;
}

/**********************************
/ 保存位图
/ para fileName: 位图文件
/ return: 是否保存成功
**********************************/
bool BitMap::save(const char *fileName) {
	FILE* f = fopen(fileName, "wb"); // 创建或打开文件
	if (!f)
		return false;
	// 设置Header属性
	setFileHeader();
	setInfoHeader();
	// 将数据写入文件
	if (!writeFile(f))
		return false;
	fclose(f);
	return true;
}

/**********************************
/ 缩放位图
/ para ratio: 缩放比例
/ return: 缩放后的位图
**********************************/
BitMap BitMap::scale(const double ratio) {
	// 新建一个缩放后的位图, 数据为空
	BitMap bitmap(round(width * ratio), round(height * ratio), bitCount);
	if (colorTable != NULL) {
		bitmap.colorTable = new RGBQUAD[256];
		memcpy(bitmap.colorTable, colorTable, getColorTableSize());
	}
	else
		bitmap.colorTable = NULL;
	int lineSize = bitmap.getLineSize(), originLineSize = getLineSize();
	int l = bitCount / 8;
	for(int i = 0; i < bitmap.height; i++) {
		for(int j = 0; j < bitmap.width; j++) {
			int x = j / ratio, y = i / ratio; // 原图像对应的点
			if (x >= 0 && x < width && y >= 0 && y < height){
				unsigned char *dst = bitmap.dataBuf + (lineSize * i + j * l);
				unsigned char *src = dataBuf + (originLineSize * y + x * l);
				memcpy(dst, src, l);
			}
		}
	}
	return bitmap;
}

/*********************************
/ 获取位深
/ return: 位图位深
*********************************/
int BitMap::getBitCount() {
	return bitCount;
}

int main(int argc, char const *argv[]) {
	const char *inputFile = argv[1];
	const char *outputFile = argv[3];
	double ratio = atoi(argv[2]) / 100.0;
	BitMap input, output;
	if (!input.load(inputFile)) {
		printf("ERROR: File \"%s\" Not Exists\n", inputFile);
		exit(EXIT_FAILURE);
	}
	// 由于比 8 位更小的位深一个像素不到一个字节, 处理需完全展开字节, 较为麻烦, 所以不处理了 ^_^
	if (input.getBitCount() < 8) {
		printf("ERROR: Unsupported File Format\n");
		exit(EXIT_FAILURE);
	}
	output = input.scale(ratio);
	if (!output.save(outputFile)) {
		printf("ERROR: Can't Save To File \"%s\"\n", outputFile);
		exit(EXIT_FAILURE);
	}
	puts("Zoom Successfully!");
	return 0;
}

RLE压缩解压算法

涉及知识点: 文件读写, 位操作, 内存管理, 结构体定义, RLE算法, 命令行参数

要求:

编写一个程序, 可以在命令行输入参数, 完成指定文件的压缩解压 命令行参数如下

$$rle\ file1\ -c(-d)\ file2$$

第一个参数为可执行程序名称, 第二个参数为原始文件名, 第三个参数为压缩或解压缩选项, 第四个参数为新文件名

RLE压缩算法是将连续相同段用两个字节表示, 一个字节表示长度, 另一个字节表示数据, 从而达到压缩效果. 连续不相同的数据也多用一个字节来表示长度, 从而达到统一.

用来表示长度的字节的最高位用来做标记, 如果为1, 则说明后续是连续相同的数据; 如果为0, 则说明后续是连续不相同的数据.

由于使用了最高位作为标记位, 实际能够表示的最大长度为127. 当连续或不连续段长度超过127, 需要分块处理.

设当前位置为cur. 判断后续数据是否连续相同. 如果是, 则找到最远位置r, 设长度len = r-cur+1, 打上标记len |= 0x80. 存两个字节的数据.

若后续数据连续不相同, 则找到最远位置r, 设长度len = r-cur+1, 先存这个字节的数据, 然后依次存后续len个数据.

注意最远位置r受块大小127的限制和总数据大小的限制.

处理完cur到r这一段数据, 令cur=r+1, 重复上述操作, 直到所有数据处理完成.

代码中的compress()即为压缩的具体实现.

设当前位置为cur, 该位置保存的是长度数据len. 先判断是有标记(len & 0x80 ?), 如果有, 则说明是一段连续的区间压缩而来. 令len ^= 0x80得到真实长度, 输出lencur+1位置(即数据位置)的数据; 如果没有标记, 则说明后续是len个不连续的数据. 直接输出这len个数据即可.

处理完这些数据, 令cur跳到第一个未处理部分, 重复上述操作, 直到数据全部处理完毕.

代码中的decompress()即为压缩的具体实现.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <cstdio>
#include <cstring>
#include <cstdlib>

const static int BUFFER_SIZE 	= 128 * 1024 * 1024;	// 缓存区大小128MB
const static int BLOCK_SIZE 	= 127;				// 块大小

unsigned char inbuf[BUFFER_SIZE], outbuf[BUFFER_SIZE];
int insize = 0, outsize = 0;

/****************************
/ 打开文件
/ para fileName: 文件名
/ return: 是否打开成功
****************************/
int load(const char *fileName) {
	FILE *f = fopen(fileName, "rb");
	if (!f)
		return 0;
	insize = fread(inbuf, sizeof(unsigned char), BUFFER_SIZE, f);
	if (!feof(f))
		return -1;
	fclose(f);
	return 1;
}

/****************************
/ 保存文件
/ para fileName: 文件名
/ return: 是否保存成功
****************************/
bool save(const char *fileName) {
	FILE *f = fopen(fileName, "wb");
	if (!f)
		return false;
	fwrite(outbuf, sizeof(unsigned char), outsize, f);
	return false;
}

/****************************
/ 输入数据
/ para buf: 数据存储区
/ para fsize: 当前大小
/ return: 是否输入成功
****************************/
bool push_back(unsigned char *buf, int &fsize, const unsigned char data) {
	if (fsize >= BUFFER_SIZE)
		return 0;
	buf[fsize++] = data;
	return 1;
}

/****************************
/ RLE压缩
/ return: 是否压缩成功
****************************/
bool compress() {
	int cur = 0;	// 当前位置
	while (cur < insize) {
		int r = cur;
		// 找到最远的相同连续段区间右端点, 区间长度不超过块大小
		while (r < insize - 1 &&
			   r - cur + 1 < BLOCK_SIZE &&
			   inbuf[r + 1] == inbuf[cur])
			r++;
		// 有相同的连续段
		if (r > cur) {
			unsigned char len = r - cur + 1;
			len |= 0x80;	// 打上标记, 并输入数据
			if (!push_back(outbuf, outsize, len))
				return false;
			if (!push_back(outbuf, outsize, inbuf[cur]))
				return false;
			cur = r + 1;
		}
		// 当前是最后一个点
		else if (cur == insize - 1) {
			if (!push_back(outbuf, outsize, 1))
				return false;
			if (!push_back(outbuf, outsize, inbuf[cur]))
				return false;
			cur++;
		}
		// 没有相同连续段
		else {
			// 找最远连续不相同区间右端点, 区间长度不超过块大小
			r = cur + 1;
			while (r < insize - 1 &&
					 r - cur + 1 < BLOCK_SIZE &&
					 inbuf[r] != inbuf[r + 1])
				r++;
			r -= (r < insize - 1);
			// 输入数据
			unsigned char len = r - cur + 1;
			if (!push_back(outbuf, outsize, len))
				return false;
			for(int i = cur; i <= r; i++)
				if (!push_back(outbuf, outsize, inbuf[i]))
					return false;
			cur = r + 1;
		}
	}
	return true;
}

/****************************
/ RLE解压
/ return: 是否解压成功
****************************/
bool decompress() {
	int cur = 0;	// 当前位置
	while (cur < insize) {
		unsigned char len = inbuf[cur++];
		// 具有连续相同段标记
		if (len & 0x80) {
			len ^= 0x80;	// 得到真实长度
			unsigned char c = inbuf[cur++];
			while (len--)
				if (!push_back(outbuf, outsize, c))
					return false;
		}
		// 没有连续相同段标记, 后续连续不相同
		else
			while (len--)
				if (!push_back(outbuf, outsize, inbuf[cur++]))
					return false;
	}
	return true;
}

int main(int argc, char *argv[]) {
	const char *operation = argv[2];
	const char *inputFile = argv[1];
	const char *outputFile = argv[3];

	int op = -1;
	if (!strcmp(operation, "-c"))
		op = 1;
	else if (!strcmp(operation, "-d"))
		op = 0;
	else {
		printf("ERROR: Unknown operation: \"%s\"\n", operation);
		exit(EXIT_FAILURE);
	}

	switch (load(inputFile)) {
		case 0: printf("ERROR: File \"%s\" Not Exists\n", inputFile); exit(EXIT_FAILURE);
		case -1: printf("ERROR: File \"%s\" Is Too Large\n", inputFile); exit(EXIT_FAILURE);
	}

	if (!(op ? compress() : decompress())) {
		printf("ERROR: %s Failed\n", op ? "Compressed" : "Decompressed");
		exit(EXIT_FAILURE);
	}

	if (save(outputFile)) {
		printf("ERROR: Can't Save To File \"%s\"\n", outputFile);
		exit(EXIT_FAILURE);
	}

	printf("%s Successfully!", op ? "Compressed" : "Decompressed");
	return 0;
}

简单文件数据库-模拟图书馆管理系统

涉及知识点: 文件读写, 内存管理, 结构体定义, 基本数据结构, 高级格式化输入输出

要求:

编写一个程序模拟图书管理系统. 用户分为管理员和读者两类, 分别显示不同文本格式菜单, 通过菜单项对应数字进行选择. 读者菜单包括借书, 还书, 查询等功能. 管理员菜单包括图书和读者信息录入, 修改和删除. 图书信息至少应包括: 编号, 书名, 数量, 读者信息至少应包括: 编号, 姓名, 所借图书. 可根据图书名称或编号进行图书信息查询, 可查询某本书现在被哪些读者借走. 命令行参数如下:

$$Libsim\ -a(-u)\ xxxx$$

第一个参数为可执行程序名称; 第二个参数为用户身份, -a表示管理员, -u表示读者; 第三个参数为用户名

参考数据库的思想, 创建两张表, 第一张为books, 保存图书信息; 第二张为info, 保存借阅信息.

图书信息包含以下内容:

图书编号(ID), 书名(Name), 总量(Amount), 剩余量(Stock).

借阅信息包含一下内容:

借阅者用户名(Borrower), 图书编号(ID).

图书可写成一个类, 实现借阅, 归还等函数.

借阅信息可写成结构体.

重载输入<<, 输出>>符号, 使用文件流的方式读写.

读者和管理员都是用户, 所以可以写三个类, 其中用户User是父类, 读者Reader和管理员Admin继承User. 这样可以使用多态, 增强可拓展性和可读性, 同时减少重复代码, 降低工作量.

读者和管理员都共同具有的属性以及共同进行的操作可以写在User里, 包括用户名, 查询所有图书, 搜索图书, 查询图书借阅情况等.

读者比父类用户多一个成员变量borrowed_books, 类型为multiset<int>保存借阅了哪些图书.

读者还有更多的操作: 查看已借阅图书, 借书, 还书等.

管理员具有更多的操作: 对图书以及借阅信息的增加, 删除, 修改.

其中, 对图书的增加, 删除, 修改要注意是否有书被借出. 如果有, 则不应该进行非法的修改.

对借阅信息的增加, 删除, 修改可以通过实例化对应读者Reader, 调用Reader的借书, 还书等函数实现.

这种写法不仅化减小了工作量, 而且具有很强的实际意义: 管理员能够管理所有用户, 能够进入用户账号进行相应操作.


操作的实现基本上都是遍历数据, 进行相应的修改. 比较简单, 不再赘述.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <set>
using namespace std;

// 借阅信息
struct Info {
	string borrower;	// 借阅者用户名
	int book_id;		// 图书id
	bool operator < (const Info &I) const {
		return borrower == I.borrower ? book_id < I.book_id : borrower < I.borrower;
	}
};

// 重载借阅信息输出输入操作
istream& operator >> (istream &in, Info &I) {
	in >> I.borrower >> I.book_id;
	return in;
}
ostream& operator << (ostream &out, Info &I) {
	out << I.borrower << "		" << I.book_id;
	return out;
}

// 借阅信息
multiset<Info> infos;

/**************************************
/ 从借阅信息中找某书的借阅者
/ para book_id: 书的id
/ return 借阅者用户名列表
**************************************/
vector<string> findBorrowersByBookId(int book_id) {
	vector<string> borrowers;
	for (auto info : infos)
		if (info.book_id == book_id)
			borrowers.push_back(info.borrower);
	return borrowers;
}

// 图书
class Book {
public:
  	int id;				// 图书编号, 为0表示被删除
	string name;		// 图书名称
	int amount, stock;	// 总量和剩余量
	Book(){}
	Book(int id, string name, int amount, int stock):
		id(id),name(name),amount(amount),stock(stock) {}

	/**************************************
	/ 借书
	/ para borrower: 借阅者用户名
	/ return: 是否借阅成功
	**************************************/
	bool borrow(string borrower) {
		if (!stock)
			return false;
		stock--;
		infos.insert({borrower, id});
		return true;
	}

	/**************************************
	/ 还书
	/ para borrower: 借阅者用户名
	/ return: 是否还书成功
	**************************************/
	bool returnBook(string borrower) {
		if (stock >= amount)
			return false;
		stock++;
		multiset<Info>::iterator it = infos.find({borrower, id});
		if (it == infos.end())
			return false;
		infos.erase(it);
		return true;
	}

	/**************************************
	/ 删除该书
	**************************************/
	void clear() {
		id = amount = stock = 0, name = "";
	}

	// 重载 < 排序用
	bool operator < (const Book &b) const {
		return id < b.id;
	}
};

// 重载图书输入输出
ostream& operator << (ostream &out, Book &B) {
    out << B.id << "		" << B.name << "		" << B.amount << "		" << B.stock;
    return out;
}
istream& operator >> (istream &in, Book &B) {
	in >> B.id >> B.name >> B.amount >> B.stock;
	return in;
}

// 图书
vector<Book> books;

/**************************************
/ 根据书名查找图书
/ para name: 书名
/ return: 该书的地址, 没有则返回NULL
**************************************/
Book* findBookByName(string name) {
	for (int i = 0; i < (int)books.size(); i++)
		if (books[i].id && books[i].name == name)
			return &books[i];
	return NULL;
}

/**************************************
/ 根据图书编号查找图书
/ para id: 图书编号
/ return: 该书的地址, 没有则返回NULL
**************************************/
Book* findBookById(int id) {
	for (int i = 0; i < (int)books.size(); i++)
		if (books[i].id && books[i].id == id)
			return &books[i];
	return NULL;
}

// 用户类
class User {
protected:
	string user_name;	// 用户名

	/**************************************
	/ 列出所有图书信息
	**************************************/
	void listAllBooks() {
		printBooksInfoTitle();
		int cnt = 1;
		for (auto book : books)
			if (book.id)
				cout << cnt++ << "		" << book << endl;
	}

	/**************************************
	/ 根据图书名称搜索图书信息
	/ para name: 图书名称
	**************************************/
	void searchBooksByName(string name) {
		Book *book = findBookByName(name);
		if (book != NULL) {
			printBooksInfoTitle();
			cout << "1		" << *book << endl;
		}
		else
			cout << "No such book in this library!" << endl;
	}

	/**************************************
	/ 根据图书id搜索图书信息
	/ para id: 图书编号
	**************************************/
	void searchBooksById(int id) {
		Book *book = findBookById(id);
		if (book != NULL) {
			printBooksInfoTitle();
			cout << "1		" << *book << endl;
		}
		else
			cout << "No such book in this library!" << endl;
	}

	/**************************************
	/ 查询图书的借阅者
	/ para *book: 查询的图书的指针
	**************************************/
	void searchBorrowers(Book *book) {
		if (book == NULL)
			cout << "Search Error: No such book in this library!" << endl;
		else {
			cout << "Borrower(s) of Book " << book->id << " " << book->name << ":" << endl;
			vector<string> borrowers = findBorrowersByBookId(book->id);
			for (auto borrower : borrowers)
				cout << borrower << endl;
		}
	}

	/**************************************
	/ 打印第一栏信息
	**************************************/
	void printBooksInfoTitle() {
		cout << "No.		" << "ID		" << "Name		" << "Amount		" << "Stock		" << endl;
	}

public:
	const static int OPERATION_EXIT = 0;
	const static int OPERATION_LIST = 1;
	const static int OPERATION_SEARCH_BY_NAME = 2;
	const static int OPERATION_SEARCH_BY_ID = 3;
	const static int OPERATION_SEARCH_BORROWER_BY_NAME = 4;
	const static int OPERATION_SEARCH_BORROWER_BY_ID = 5;

	/**************************************
	/ 显示命令面板
	**************************************/
	virtual void showCommand(){
  		cout << "--------Library System--------" << endl;
  		cout << "0. Exit" << endl;
  		cout << "1. List all books in library" << endl;
  		cout << "2. Search books by book name" << endl;
  		cout << "3. Search books by book id" << endl;
  		cout << "4. Search borrowers by book name" << endl;
  		cout << "5. Search borrowers by book id" << endl;
	}
	/**************************************
	/ 处理命令操作
	/ para op: 操作序号
	/ return: 退出系统 false, 否则 true
	**************************************/
	virtual bool operate(int op) {
		if (op == OPERATION_EXIT)
			return false;
		else if (op == OPERATION_LIST)
			listAllBooks();
		else if (op == OPERATION_SEARCH_BY_NAME) {
			cout << "Book Name: ";
			string book_name;
			cin >> book_name;
			searchBooksByName(book_name);
		}
		else if (op == OPERATION_SEARCH_BY_ID) {
			cout << "Book ID: ";
			int book_id;
			cin >> book_id;
			searchBooksById(book_id);
		}
		else if (op == OPERATION_SEARCH_BORROWER_BY_NAME) {
			cout << "Book Name: ";
			string book_name;
			cin >> book_name;
			Book *book = findBookByName(book_name);
			searchBorrowers(book);
		}
		else if (op == OPERATION_SEARCH_BORROWER_BY_ID) {
			cout << "Book ID: ";
			int book_id;
			cin >> book_id;
			Book *book = findBookById(book_id);
			searchBorrowers(book);
		}
		return true;
	}
	User(){}
	User(string user_name):user_name(user_name){}
};

// 读者用户
class Reader : public User {
private:
  	multiset<int> borrowedBooks;	// 借阅的图书编号

  	/**************************************
	/ 查询已借阅图书
	**************************************/
	void listBorrowedBooks() {
		cout << "User Name:" << user_name << endl;
		cout << "Borrowed books:" << endl;
		cout << "No.		"<< "ID		" << "Name		" << endl;
		int cnt = 1;
		for (auto book_id : borrowedBooks) {
			Book *book = findBookById(book_id);
			cout << cnt++ << "		" << book->id << "		" << book->name << endl;
		}
	}

	/**************************************
	/ 还书
	/ para no: 已借阅图书的序号
	/ return: 是否还书成功
	**************************************/
	bool returnBook(int no) {
		if (no <= 0 || no > (int)borrowedBooks.size())
			return false;
		int cnt = 1;
		for (multiset<int>::iterator it = borrowedBooks.begin(); it != borrowedBooks.end(); ++it)
			if (no == cnt++) {
				Book* book = findBookById(*it);
				book->returnBook(user_name);
				borrowedBooks.erase(it);
				break;
			}
		return true;
	}

	/**************************************
	/ 输出借阅操作交互信息
	/ para flag: 借阅操作结果标识
	**************************************/
	void printBorrowLog(int flag) {
		if (flag == BORROW_FLAG_SUC)
			cout << "Borrowed successfully!" << endl;
		else if (flag == BORROW_FLAG_NO_REMAIN)
			cout << "Borrowed failed! All books have been borrowed!" << endl;
		else if (flag == BORROW_FLAG_NO_BOOK)
			cout << "Borrowed failed! No such book in this library!" << endl;
	}

	/**************************************
	/ 输出还书操作交互信息
	/ para flag: 还书操作结果标识
	**************************************/
	void printReturnLog(bool flag) {
		if (flag)
			cout << "Return successfully!" << endl;
		else
			cout << "Return Error: Please check your input!" << endl;
	}

public:
	const static int OPERATION_LIST_BORROWED = 6;
	const static int OPERATION_BORROW_BY_NAME = 7;
	const static int OPERATION_BORROW_BY_ID = 8;
	const static int OPERATION_RETURN = 9;
	const static int BORROW_FLAG_SUC = 1;
	const static int BORROW_FLAG_NO_BOOK = 2;
	const static int BORROW_FLAG_NO_REMAIN = 3;
	Reader(string user_name):User(user_name) {
		// 初始化, 找到借阅的图书
		borrowedBooks.clear();
		for (auto info : infos)
			if (info.borrower == user_name)
				borrowedBooks.insert(info.book_id);
	}

	/**************************************
	/ 显示命令面板
	**************************************/
  	virtual void showCommand() {
  		User::showCommand();
  		cout << "6. List borrowed books" << endl;
  		cout << "7. Borrow book by book name" << endl;
  		cout << "8. Borrow book by book id" << endl;
  		cout << "9. Return book" << endl;
  	}

	/**************************************
	/ 处理命令操作
	/ para op: 操作序号
	/ return: 退出系统 false, 否则 true
	**************************************/
  	virtual bool operate(int op) {
  		if (!User::operate(op))
  			return false;
  		if (op == OPERATION_LIST_BORROWED)
  			listBorrowedBooks();
  		else if (op == OPERATION_BORROW_BY_NAME) {
  			cout << "Book Name: ";
			string book_name;
			cin >> book_name;
			Book *book = findBookByName(book_name);
  			printBorrowLog(borrowBook(book));
  		}
  		else if (op == OPERATION_BORROW_BY_ID) {
			cout << "Book ID: ";
			int book_id;
			cin >> book_id;
			Book *book = findBookById(book_id);
  			printBorrowLog(borrowBook(book));
  		}
  		else if (op == OPERATION_RETURN) {
  			listBorrowedBooks();
  			cout << "Please choose the number of borrowed book to return: ";
  			int no;
  			cin >> no;
  			printReturnLog(returnBook(no));
  		}
  		return true;
  	}

	/**************************************
	/ 借书
	/ para *book: 借阅书籍指针
	/ return: 借书操作结果标识
	**************************************/
	int borrowBook(Book *book) {
		if (book == NULL)
			return BORROW_FLAG_NO_BOOK;
		if (book->borrow(user_name)) {
			borrowedBooks.insert(book->id);
			return BORROW_FLAG_SUC;
		}
		return BORROW_FLAG_NO_REMAIN;
	}
};

// 管理员用户
class Admin : public User {
private:
	/**************************************
	/ 添加图书
	/ para id: 图书编号
	/ para name: 书名
	/ para amount: 数量
	/ return: 添加图书操作结果标识
	**************************************/
	int addBook(int id, string name, int amount) {
		if (findBookById(id) != NULL)
			return ADD_BOOK_FLAG_ID_NOT_UNIQUE;
		if (amount <= 0)
			return ADD_BOOK_FLAG_AMOUNT_NOT_POSTIVE;
		books.emplace_back(id, name, amount, amount);
		return ADD_BOOK_FLAG_SUC;
	}

	/**************************************
	/ 删除图书
	/ para id: 图书编号
	/ return: 删除图书操作结果标识
	**************************************/
	int deleteBook(int book_id) {
		Book *book = findBookById(book_id);
		if (book == NULL)
			return DELETE_BOOK_FLAG_NO_BOOK;
		if (book->amount > book->stock)
			return DELETE_BOOK_FLAG_ON_LOAN;
		book->clear();
		return DELETE_BOOK_FLAG_SUC;
	}

	/**************************************
	/ 编辑图书
	/ para id: 图书编号
	/ return: 编辑图书操作结果标识
	**************************************/
	int editBook(int book_id) {
		Book *book = findBookById(book_id);
		if (book == NULL)
			return EDIT_BOOK_FLAG_NO_BOOK;
		printBooksInfoTitle();
		cout << "1		" << *book << endl;
		cout << "Name		" << "Amount" << endl;
		string new_name;
		int new_amount;
		cin >> new_name >> new_amount;
		int delta = new_amount - book->amount;
		if (book->stock + delta <= 0)
			return EDIT_BOOK_FLAG_NO_STOCK;
		book->name = new_name;
		book->stock += delta;
		book->amount = new_amount;
		return EDIT_BOOK_FLAG_SUC;
	}

	/**************************************
	/ 查询所有借阅信息
	**************************************/
	void listBorrowing() {
		cout << "No.		borrower(s)	Book id 	Book name" << endl;
		int cnt = 1;
		for (auto info : infos) {
			string book_name = findBookById(info.book_id)->name;
			cout << cnt++ << "		" << info << "		" << book_name << endl;
		}
	}

	/**************************************
	/ 添加借阅信息
	/ para borrower_name: 借阅者用户名
	/ para amount: 图书编号
	/ return: 添加借阅信息操作结果标识
	**************************************/
	int addBorrowing(string borrower_name, int book_id) {
		Reader borrower(borrower_name);
		return borrower.borrowBook(findBookById(book_id));
	}

	/**************************************
	/ 删除借阅信息
	/ para no: 借阅信息的序号
	/ return: 删除借阅信息操作结果标识
	**************************************/
	bool deleteBorrowing(int no) {
		if (no <= 0 ||  no > (int)infos.size())
			return false;
		int cnt = 1;
		for (auto info : infos)
			if (no == cnt++) {
				Book *book = findBookById(info.book_id);
				book->returnBook(info.borrower);
				break;
			}
		return true;
	}

	/**************************************
	/ 编辑借阅信息
	/ para no: 借阅信息的序号
	/ return: 编辑借阅信息操作结果标识
	**************************************/
	int editBorrowing(int no) {
		if (no <= 0 ||  no > (int)infos.size())
			return EDIT_BORROWING_FLAG_INVALID_INPUT;
		int cnt = 1;
		cout << "Borrower	Book ID" << endl;
		string borrower;
		int book_id;
		cin >> borrower >> book_id;
		for (auto info : infos)
			if (no == cnt++) {
				deleteBorrowing(no);
				return addBorrowing(borrower, book_id);
			}
		return -1;
	}

	/**************************************
	/ 输出添加图书操作交互信息
	/ para flag: 添加图书操作结果标识
	**************************************/
	void printAddBookLog(int flag) {
		if (flag == ADD_BOOK_FLAG_SUC)
			cout << "Added successfully!" << endl;
		else if (flag == ADD_BOOK_FLAG_ID_NOT_UNIQUE)
			cout << "Add Error: Book ID is not unique!" << endl;
		else if (flag == ADD_BOOK_FLAG_AMOUNT_NOT_POSTIVE)
			cout << "Add Error: The amount is invalid!" << endl;
	}

	/**************************************
	/ 输出删除图书操作交互信息
	/ para flag: 删除图书操作结果标识
	**************************************/
	void printDeleteBookLog(int flag) {
		if (flag == DELETE_BOOK_FLAG_SUC)
			cout << "Deleted successfully!" << endl;
		else if (flag == DELETE_BOOK_FLAG_NO_BOOK)
			cout << "Delete Error: No such book in this library!" << endl;
		else if (flag == DELETE_BOOK_FLAG_ON_LOAN)
			cout << "Deleted Error: Book is on loan!" << endl;
	}

	/**************************************
	/ 输出编辑图书操作交互信息
	/ para flag: 编辑图书操作结果标识
	**************************************/
	void printEditBookLog(int flag) {
		if (flag == EDIT_BOOK_FLAG_SUC)
			cout << "Edited successfully!" << endl;
		else if (flag == EDIT_BOOK_FLAG_NO_BOOK)
			cout << "Edit Error: No such book in this library!" << endl;
		else if (flag == EDIT_BOOK_FLAG_NO_STOCK)
			cout << "Edit Error: No stocked book!" << endl;
	}

	/**************************************
	/ 输出添加借阅信息操作交互信息
	/ para flag: 添加借阅信息操作结果标识
	**************************************/
	void printAddBorrowingLog(int flag) {
		if (flag == Reader::BORROW_FLAG_SUC)
			cout << "Added successfully!" << endl;
		else if (flag == Reader::BORROW_FLAG_NO_BOOK)
			cout << "Add Error: No such book in this library!" << endl;
		else if (flag == Reader::BORROW_FLAG_NO_REMAIN)
			cout << "Add Error: All books have been borrowed!" << endl;
	}

	/**************************************
	/ 输出删除借阅信息操作交互信息
	/ para flag: 删除借阅信息操作结果标识
	**************************************/
	void printDeleteBorrowingLog(bool flag) {
		if (flag)
			cout << "Deleted successfully!" << endl;
		else
			cout << "Delete Error: Please check your input!" << endl;
	}

	/**************************************
	/ 输出编辑借阅信息操作交互信息
	/ para flag: 编辑借阅信息操作结果标识
	**************************************/
	void printEditBorrowing(int flag) {
		if (flag == EDIT_BORROWING_FLAG_INVALID_INPUT)
			cout << "Edit Error: Please check your input!" << endl;
		else if (flag == Reader::BORROW_FLAG_SUC)
			cout << "Edited successfully!" << endl;
		else if (flag == Reader::BORROW_FLAG_NO_BOOK)
			cout << "Edit Error: No such book in this library!" << endl;
		else if (flag == Reader::BORROW_FLAG_NO_REMAIN)
			cout << "Edit Error: All books have been borrowed!" << endl;
	}

public:
	const static int OPERATION_ADD_BOOK = 6;
	const static int OPERATION_EDIT_BOOK = 7;
	const static int OPERATION_DELETE_BOOK = 8;
	const static int OPERATION_LIST_BORROWING = 9;
	const static int OPERATION_ADD_BORROWING = 10;
	const static int OPERATION_EDIT_BORROWING = 11;
	const static int OPERATION_DELETE_BORROWING = 12;
	const static int ADD_BOOK_FLAG_SUC = 1;
	const static int ADD_BOOK_FLAG_ID_NOT_UNIQUE = 2;
	const static int ADD_BOOK_FLAG_AMOUNT_NOT_POSTIVE = 3;
	const static int DELETE_BOOK_FLAG_SUC = 1;
	const static int DELETE_BOOK_FLAG_NO_BOOK = 2;
	const static int DELETE_BOOK_FLAG_ON_LOAN = 3;
	const static int EDIT_BOOK_FLAG_SUC = 1;
	const static int EDIT_BOOK_FLAG_NO_BOOK = 2;
	const static int EDIT_BOOK_FLAG_NO_STOCK = 3;
	const static int EDIT_BORROWING_FLAG_INVALID_INPUT = 0;
	const static int EDIT_BORROWING_FLAG_SUC = 1;

	/**************************************
	/ 显示命令面板
	**************************************/
	virtual void showCommand() {
		User::showCommand();
		cout << "6. Add book" << endl;
		cout << "7. Edit book" << endl;
		cout << "8. Delete book" << endl;
		cout << "9. List borrowing information" << endl;
		cout << "10. Add borrowing information" << endl;
		cout << "11. Edit borrowing information" << endl;
		cout << "12. Delete borrowing information" << endl;
	}

	/**************************************
	/ 处理命令操作
	/ para op: 操作序号
	/ return: 退出系统 false, 否则 true
	**************************************/
	virtual bool operate(int op) {
		if (!User::operate(op))
			return false;
		if (op == OPERATION_ADD_BOOK) {
			cout << "ID		" << "Name		" << "Amount" << endl;
			int id, amount;
			string name;
			cin >> id >> name >> amount;
			printAddBookLog(addBook(id, name, amount));
		}
		else if (op == OPERATION_DELETE_BOOK) {
			cout << "Book ID: ";
			int id;
			cin >> id;
			printDeleteBookLog(deleteBook(id));
		}
		else if (op == OPERATION_EDIT_BOOK) {
			cout << "Book ID: ";
			int id;
			cin >> id;
			printEditBookLog(editBook(id));
		}
		else if (op == OPERATION_LIST_BORROWING)
			listBorrowing();
		else if (op == OPERATION_ADD_BORROWING) {
			cout << "Borrower	Book ID" << endl;
			string borrower;
			int book_id;
			cin >> borrower >> book_id;
			printAddBorrowingLog(addBorrowing(borrower, book_id));
		}
		else if (op == OPERATION_DELETE_BORROWING) {
			listBorrowing();
			cout << "Please choose the number of borrowing information to delete: ";
			int no;
			cin >> no;
			printDeleteBorrowingLog(deleteBorrowing(no));
		}
		else if (op == OPERATION_EDIT_BORROWING) {
			listBorrowing();
			cout << "Please choose the number of borrowing information to edit: ";
			int no;
			cin >> no;
			printEditBorrowing(editBorrowing(no));
		}
		return true;
	}
	Admin(string user_name):User(user_name) {}
};

/**************************************
/ 加载图书信息
/ para file_name: 存放图书信息的文件名
**************************************/
void loadBooks(string file_name) {
	ifstream f(file_name, ios::in);
	Book book;
	while (f >> book)
		books.push_back(book);
	sort(books.begin(), books.end());
	f.close();
}

/**************************************
/ 加载借阅信息
/ para file_name: 存放借阅信息的文件名
**************************************/
void loadInfo(string file_name) {
	ifstream f(file_name, ios::in);
	Info info;
	while (f >> info)
		infos.insert(info);
	f.close();
}

/**************************************
/ 加载数据信息
/ para book_file_name: 存放图书信息的文件名
/ para info_file_name: 存放借阅信息的文件名
**************************************/
void loadLibrary(string book_file_name, string info_file_name) {
	loadBooks(book_file_name);
	loadInfo(info_file_name);
}

/**************************************
/ 保存图书信息
/ para file_name: 存放图书信息的文件名
**************************************/
void updateBooks() {
	ofstream f("books.txt", ios::out);
	for (auto book : books)
		if (book.id)
			f << book << endl;
	f.close();
}

/**************************************
/ 保存借阅信息
/ para file_name: 存放借阅信息的文件名
**************************************/
void updateInfo() {
	ofstream f("info.txt", ios::out);
	for (auto info : infos)
		f << info << endl;
	f.close();
}

/**************************************
/ 保存数据信息
/ para book_file_name: 存放图书信息的文件名
/ para info_file_name: 存放借阅信息的文件名
**************************************/
void updateLibrary(string book_file_name, string info_file_name) {
	updateBooks();
	updateInfo();
}

int main(int argc, char const *argv[]) {
	const string book_data_file_name = "books.txt";
	const string info_data_file_name = "info.txt";
	// 进入系统, 加载信息
	loadLibrary(book_data_file_name, info_data_file_name);
	string identity = argv[1];
	string user_name = argv[2];
	User *user;		// 多态
	if (identity == "-u")
		user = new Reader(user_name);
	else if (identity == "-a")
		user = new Admin(user_name);
	else {
		cout << "ERROR: Unknown operation: \"" << identity << "\"" << endl;
		exit(EXIT_FAILURE);
	}
	while (1) {
		user->showCommand();
		int op;
		cin >> op;
		if (!user->operate(op))
			break;
	}
	// 退出系统, 更新信息
	updateLibrary(book_data_file_name, info_data_file_name);
	return 0;
}