一丶文本文件的编码解码（文本文件压缩为01编码，解码01编码为文本文件）

有一篇英文文章存储在一个文本文件中，现在要以报文形式将文章发送。编写程序，设计Haffman编码将文章转换为01编码。报文接收端要将01编码转换为英文文章，编写程序将Haffman编码报文译码。若编码是等长编码，是给出Haffman码与等长码的压缩比。基本要求：

（1）读英文文章“Text.txt”，统计每个字符在文章中出现的频率；将结果打印到文件“Freq.txt”

（2）构建Haffman树，求出每个字符的Haffman编码；将结果打印到文件“HaffCode.txt”

（3）将英文文章“Text.txt”转换为01字符串，将结果打印到文件“EngtoCode.txt”

（4）读文件“EngtoCode.txt”，将01字符串转换成英文文章。（译码）

(5)若对文章“Text.txt”进行等长编码，试与Haffman 编码比较，求出该篇文章的压缩比。

CODE：

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<char,int> fre; //任务一中记录出现频率。 
set<char> line;   
map<string,char> Decode;
map<char,string> Code;
int relnum;//有效字符数量 
int sumnum;//总字符数量 
void Freq() {
	freopen("Text.txt","r",stdin);//调用输入流 
	freopen("Freq.txt","w",stdout);//调用输出流 
	char ch ;
	while(~scanf("%c",&ch)) {
		fre[ch]++;
		line.insert(ch);
		sumnum++;
		if(fre[ch] == 1)
			relnum++;
	}
	for(auto it : line) 
		cout<<it<<" "<<fre[it]<<endl;
	fclose(stdin);//关闭输入流 
	fclose(stdout);	//关闭输出流 
}
struct Node {
	int data; 
	int parent,lchild,rchild;
};//定义哈弗曼树的结构。 
struct Num {
	int w;
	int ch;
}W[1000];
void CreateNode(Node *H,int w,int parent,int lchild,int rchild) {
	H -> lchild = lchild;
	H -> rchild = rchild;
	H -> parent = parent;
	H -> data = w;
}//创建节点 
void CreateHuffmanTree(Node*& HT,int n) { //指针传引用 
	//最终的节点数 = 2 * n - 1;
	HT = (Node*)malloc((2*n-1) * sizeof(Node));
	for(int i=0;i<n;i++) {
		CreateNode(HT+i,W[i].w,-1,-1,-1);
	}//创建初始化叶子节点(最末端的) 
	//开始寻找最小的两个叶子节点，构建哈夫曼树 
	for(int i=n;i<2*n-1;i++) {
		int min1 = 0x3f3f3f3f,min2 = min1; //min1第一小，min2第二小。 
		int x1 = -1 , x2 = -1;//位置 
		for(int j = 0;j < i;j++) {
			if((HT+j) -> parent == -1) {
				if((HT+j) -> data < min1) {
				min2 = min1;
				min1 = (HT+j) -> data;
				x2 = x1,x1 = j;
				}
				else if((HT+j)->data < min2) {
				min2 = (HT+j) -> data;
				x2 = j;
				}
			} 
		}
		(HT+x1) -> parent = i; //最小 
		(HT+x2) -> parent = i; //次小 
		CreateNode(HT+i,min1+min2,-1,x1,x2);
	} 
}//建立哈夫曼树 
void HuffmanTreeCode(Node *HT,char *str,int n,int path,int &len) {
	int j,child,parent;
	j = 0;
	child = path; 
	parent = (HT+child) -> parent;
	while(parent != -1) {
		if((HT+parent) -> lchild == child) 
			str[j++] = '0';	
		else 
			str[j++] = '1';
		child = parent;
		parent = (HT+child) -> parent;
	}
	len = j;
}//获得哈夫曼编码，n是指叶子个数，path是我们要获得的字符的编号 
void HuffmanTree() {
	freopen("Freq.txt","r",stdin);
	freopen("HaffCode.txt","w",stdout);
	int len;
	Node* HT; //根节点 
	for(int i=0;i<relnum;i++)//录入叶子权值和字符 
		scanf("%c %d\n",&W[i].ch,&W[i].w);
	CreateHuffmanTree(HT,relnum);
	char str[relnum];
	
	for(int k=0;k<relnum;k++) {
		HuffmanTreeCode(HT,str,relnum,k,len);
		string s;
		for(int j=len-1;j>=0;j--)
			s+=str[j];
		Code[W[k].ch] = s;
		Decode[s] = W[k].ch;
	}
	for(auto it : line) 
		cout<<it<<" : "<<Code[it]<<endl;
	free(HT);
	fclose(stdin);//关闭输入流 
	fclose(stdout);	//关闭输出流 
}
int codelen;
void CodeText() {
	freopen("Text.txt","r",stdin);
	freopen("EngtoCode.txt","w",stdout);
	char ch;
	while(~scanf("%c",&ch)) {
		cout<<Code[ch];
		codelen += Code[ch].size();
	}
	fclose(stdin);//关闭输入流 
	fclose(stdout);	//关闭输出流 
}
int numnum;
void DecodeText() {
	freopen("EngtoCode.txt","r",stdin);
	freopen("DecodeText.txt","w",stdout);
	char ch;
	string s;
	while(~scanf("%c",&ch)) {
		s+=ch;
		if(Decode[s]) {
			cout<<Decode[s];
			s.clear();
			numnum++;
		}
	}
	fclose(stdin);//关闭输入流 
	fclose(stdout);	//关闭输出流 
}
int main() {
	Freq();
	freopen("CON","w",stdout);
	cout<<"Freq.txt文件已创建"<<endl; 
	cout<<"字符总数 : "<<sumnum<<endl;
	cout<<"有效字符 : "<<relnum<<endl<<endl;
	cout<<"--------------------"<<endl<<endl;
	fclose(stdout); 
	HuffmanTree();
	freopen("CON","w",stdout);
	cout<<"HaffCode.txt文件已创建"<<endl<<endl; 
	cout<<"--------------------"<<endl<<endl;
	fclose(stdout); 
	CodeText();
	freopen("CON","w",stdout);
	cout<<"EngtoCode.txt文件已创建"<<endl; 
	cout<<"编码后位数 : "<<codelen<<endl<<endl; 
	cout<<"--------------------"<<endl<<endl;
	fclose(stdout); 
	DecodeText();
	freopen("CON","w",stdout);
	cout<<"DecodeText.txt文件已创建"<<endl;
	cout<<"字符总数 : "<<numnum<<endl<<endl;  
	cout<<"--------------------"<<endl<<endl;
	fclose(stdout); 
	freopen("CON","w",stdout);
	cout<<"压缩前位数:"<<sumnum<<" * "<<8<<" = "<<sumnum*8<<endl;
	cout<<"压缩后位数:"<<codelen<<endl;
	cout<<"压缩比:"<<codelen<<" / "<<sumnum*8<<" = "<<1.0*codelen/(sumnum*8);
	printf("(%.2lf",1.0*codelen/(sumnum*8)*100);
	cout<<"%)"<<endl<<endl;
	cout<<"--------------------"<<endl<<endl;
	fclose(stdout);
	return 0;
}

二丶中缀表达式求值问题

给定一个四则运算的中缀表达式，编程计算表达式的值。基本要求：

（1）在给定的表达式中要包含括号；

（2）栈的操作要求自己完成，不允许调用类库中的方法；

（3）对不同的操作编写相应的函数。

CODE：

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>class Stack{
	private:
	struct Node{
		T data;
		Node *next;
	};
	Node *head;
	Node *p;
	int length;
	public:
	Stack(){
		head=NULL;
		length=0;
	}
	void push(T n){//入栈
		Node *q=new Node;
		q->data=n;
		if(head==NULL){
			q->next=head;
			head=q;
			p=q;
		}
		else{
			q->next=p;
			p=q;
		}
		length++;
	}
	void pop(){
		Node *q;
		q=p;
		p=p->next;
		delete(q);
		length--;
	}
	int size(){//返回元素个数
		return length;
	}
	T top(){//返回栈顶元素
		return p->data;
	}
	bool empty(){//判断栈是否为空 
		if(length==0)
			return true;
		else
			return false;
	}
	void clear(){//清空栈中的所有元素
		while(length>0)
			pop();
	}
};
int GetP(char ch)
{
	if (ch == '(') return 1;
	else if (ch == '+' || ch == '-') return 2;
	else if (ch == '*' || ch == '/') return 3;
	else return 4;
}//获取运算符优先级 
void Calc(Stack<double> &st, char op)
{
	double num1, num2, num3;
	num2 = st.top();
	st.pop();
	num1 = st.top();
	st.pop();
	if (op == '+') 
		num3 = num1 + num2;
	else if (op == '-') 
		num3 = num1 - num2;
	else if (op == '*') 
		num3 = num1 * num2;
	else if (op == '/') 
		num3 = num1 / num2;
	st.push(num3);
}
double calculator(string s)
{
	Stack<double> MyNum;
	Stack<char> MyOper;
	int i = 0, j;
	int size = s.size();
	char tmp;
	string tmp_num;
	for(int i=0;i<size;i++) {
		if (s[i] >= '0' && s[i] <= '9') {
			j = i;
			while (j < size && s[j] >= '0' && s[j] <= '9') { j++; }
			tmp_num = s.substr(i, j - i);
			MyNum.push(atoi(tmp_num.c_str()));
			i = j - 1;
		}
		else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
			if (MyOper.empty()) {
				MyOper.push(s[i]);
			}
			else {
				while (!MyOper.empty()) {
					tmp = MyOper.top();
					if (GetP(tmp) >= GetP(s[i])) {
						//计算
						Calc(MyNum, tmp);
						MyOper.pop();
					}
					else break;
				}
				MyOper.push(s[i]);
			}
		}
		else {
			if (s[i] == '(') MyOper.push(s[i]);
			else {
				while (MyOper.top() != '(') {
					tmp = MyOper.top();
					Calc(MyNum, tmp);
					MyOper.pop();
				}
				MyOper.pop();
			}
		}
 
	}
	//遍历完后，若栈非空，弹出所有元素
	while(!MyOper.empty()) {
		tmp = MyOper.top();
		Calc(MyNum, tmp);
		MyOper.pop();
	}
	return MyNum.top();
}//计算中缀表达式,默认输入是合法的
int main()
{
	while(1){
		string s;
		cout << "请输入中缀表达式 : "<<endl;
		cin>>s;
		double res = calculator(s);
		cout << "计算结果 : " <<  res << endl;
		
		cout<<"输入Y/y继续输入，输入其他退出 : "; 
		char ch;
		cin>>ch;
		if(ch != 'Y' && ch != 'y')
			break;
		cout<<endl;
	} 
	return 0;
}