写在前面
本篇实验代码非本人写，代码源自外部，经调试解决了部分warning和error后在本地vs上可以正常运行，如有运行失败可换至vs
未来会重构实现该两个实验
哈夫曼树及哈夫曼编码的算法实现
实验内容
内容要求：
1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树
2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
测试数据：
输入字符串“thisprogramismyfavourite”，完成这28个字符的编码和译码。
代码实现
#include<iostream>
#include<string.h>
#include<queue>
#define MAX 10000
using namespace std;
char a[100], buff[1024], p;
typedef struct
{
char letter, * code;
int weight;
int parent, lchild, rchild;
}HTNode, * HuffmanTree;
int n;
char coding[100];
int Min(HuffmanTree& HT, int i)
{
int j;
int k = MAX;
int flag=0;
for (j = 0; j <= i; ++j)
{
if (HT[j].weight < k && HT[j].parent == 0)
{
k = HT[j].weight;
flag = j;
}
}
HT[flag].parent = 1;
return flag;
}
void Select(HuffmanTree& HT, int i, int& s1, int& s2)
{
s1 = Min(HT, i);
s2 = Min(HT, i);
}
void CreateHuffmanTree(HuffmanTree& HT, char t[], int w[])
{
int m;
int i, s1, s2;
if (n <= 1)
return;
m = 2 * n - 1;
HT = new HTNode[m + 1];
for (i = 0; i < n; i++)
{
char arr[] = "0";
char* pa = arr;
HT[i].code = pa;
HT[i].parent = 0;
HT[i].lchild = -1;
HT[i].rchild = -1;
HT[i].letter = t[i];
HT[i].weight = w[i];
}
for (i = n; i <= m; i++)
{
char arr[] = "0";
char* pa = arr;
HT[i].code = pa;
HT[i].parent = 0;
HT[i].lchild = -1;
HT[i].rchild = -1;
HT[i].letter = ' ';
HT[i].weight = 0;
}
cout << "********************************" << endl;
for (i = n; i < m; i++)
{
Select(HT, i - 1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
void CreatHuffmanCode(HuffmanTree HT)
{
int start, c, f;
int i;
char* cd = new char[n];
cd[n - 1] = '\0';
cout << "字符编码为：" << endl;
for (i = 0; i < n; i++)
{
start = n - 1;
c = i;
f = HT[i].parent;
while (f != 0)
{
--start;
if (HT[f].lchild == c)
{
cd[start] = '0';
}
else
{
cd[start] = '1';
}
c = f;
f = HT[f].parent;
}
HT[i].code = new char[n - start];
strcpy(HT[i].code, &cd[start]);
cout << HT[i].letter << ":" << HT[i].code << endl;
}
delete[] cd;
}
void HuffmanTreeDecode(HuffmanTree HT, char cod[], int b)
{
char sen[100];
char temp[50];
char voidstr[] = " ";
int t = 0;
int s = 0;
int count = 0;
for (int i = 0; i < b; i++)
{
temp[t++] = cod[i];
temp[t] = '\0';
for (int j = 0; j < n; j++)
{
if (!strcmp(HT[j].code, temp))
{
sen[s] = HT[j].letter;
s++;
count += t;
strcpy(temp, voidstr);
t = 0;
break;
}
}
}
if (t == 0)
{
sen[s] = '\0';
cout << "译码为:" << endl;
cout << sen << endl;
}
else
{
cout << "二进制源码有错！从第" << count + 1 << "位开始" << endl;
}
}
int main()
{
HuffmanTree HT;
int b[100]={0};
int i, j;
int symbol = 1, x, k;
cout << "请输入一段文字:";
cin >> buff;
int len = (int)strlen(buff);
for (i = 0; i < len; i++)
{
for (j = 0; j < n; j++)
{
if (a[j] == buff[i])
{
b[j] = b[j] + 1;
break;
}
}
if (j >= n)
{
a[n] = buff[i];
b[n] = 1;
n++;
}
}
cout << "字符和权值信息如下" << endl;
for (i = 0; i < n; i++)
{
cout << "字符：" << a[i] << " 权值：" << b[i] << endl;
}
CreateHuffmanTree(HT, a, b);
CreatHuffmanCode(HT);
cout << "文字编码为：\n";
for (int i = 0; i < len; i++)
{
for (int j = 0; j < n; j++)
{
if (buff[i] == HT[j].letter)
{
cout << HT[j].code;
break;
}
}
}
cout << "\n译码：" << endl;
while (1)
{
cout << "请输入要译码的二进制字符串,输入'#'结束：";
x = 1;
k = 0;
symbol = 1;
while (symbol)
{
cin >> p;
if (p != '1' && p != '0' && p != '#')
{
x = 0;
}
coding[k] = p;
if (p == '#')
symbol = 0;
k++;
}
if (x == 1)
{
HuffmanTreeDecode(HT, coding, k - 1);
}
else
{
cout << "有非法字符！" << endl;
}
cout << "是否继续?(Y/N):";
cin >> p;
if (p == 'y' || p == 'Y')
continue;
else
break;
}
return 0;
}
图的基本操作
实验内容
分别用邻接矩阵和邻接表对如下有向图实现：
1.输出存储结果；
2.计算各结点的出度和入度，并输出；
3.实现图的深度优先遍历和广度优先遍历，并输出。文章来源：https://www.toymoban.com/news/detail-638217.html
文章来源地址https://www.toymoban.com/news/detail-638217.html
代码实现
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <stack>
using namespace std;
namespace matrix
{
// 顶点的类型，权值的类型，权值的最大值，是否是有向图
template<class V, class W, W W_MAX = INT_MAX, bool Direction = true>
class Graph
{
public:
Graph() = default;
Graph(const V* vertexs, size_t n)
{
// 建立顶点和下标的映射关系
for (size_t i = 0; i < n; i++)
{
_vertexs.push_back(vertexs[i]);
_vIndexMap[vertexs[i]] = i;
}
_matrix.resize(n, vector<W>(n, W_MAX));
}
// 给一个顶点取出来它对应的下标
size_t GetVertexsIndex(const V& vertex)
{
auto it = _vIndexMap.find(vertex);
if (it != _vIndexMap.end())
{
return it->second;
}
else
{
throw invalid_argument("不存在的顶点");
return -1;
}
}
// 给邻接矩阵加值
void _AddEdge(size_t srci, size_t dsti, W w)
{
_matrix[srci][dsti] = w;
if (Direction == false)
_matrix[dsti][srci] = w;
}
// 加边
void AddEdge(const V& src, const V& dst, W w)
{
size_t srci = GetVertexsIndex(src);
size_t dsti = GetVertexsIndex(dst);
_AddEdge(srci, dsti, w);
}
// 显示邻接矩阵
void Print()
{
cout << " ";
for (size_t i = 0; i < _vertexs.size(); ++i)
{
cout << i << " ";
}
cout << endl;
// 打印矩阵
for (size_t i = 0; i < _matrix.size(); ++i)
{
cout << i << " ";
for (size_t j = 0; j < _matrix[i].size(); ++j)
{
if (_matrix[i][j] != W_MAX)
cout << _matrix[i][j] << " ";
else
cout << "#" << " ";
}
cout << endl;
}
// 打印所有的边
for (size_t i = 0; i < _matrix.size(); ++i)
{
for (size_t j = 0; j < _matrix[i].size(); ++j)
{
if (_matrix[i][j] != W_MAX)
{
cout << _vertexs[i] << "-" << _vertexs[j] << endl;
}
}
}
}
// 计算结点的入度和出度
void cal_inward_outward()
{
for (int i = 0; i < _matrix.size(); i++)
{
int inward = 0, outward = 0;
for (int j = 0; j < _matrix[i].size(); j++)
{
if (_matrix[j][i] != W_MAX)
inward++;
if (_matrix[i][j] != W_MAX)
outward++;
}
cout << _vertexs[i] << "的入度为:" << inward << " " << "出度为" << outward << endl;
}
}
// 图的BFS遍历，从某个顶点开始遍历
void BFS(const V& Vertex)
{
queue<V> qe;
qe.push(Vertex);
size_t d = 1;
vector<bool> visited(_matrix.size(), false);
while (!qe.empty())
{
size_t dsize = qe.size();
cout << Vertex << "的" << d << "度好友:";
while (dsize--)
{
V front = qe.front();
qe.pop();
size_t index = GetVertexsIndex(front);
visited[index] = true;
for (size_t i = 0; i < _matrix.size(); i++)
{
if (_matrix[index][i] != W_MAX && visited[i] == false)
{
//找到了
visited[i] = true;
cout << _vertexs[i] << " ";
qe.push(_vertexs[i]);
}
}
}
cout << endl;
d++;
}
}
// 图的DFS遍历，从某个顶点开始遍历
void DFS(const V& Vertex)
{
size_t index = GetVertexsIndex(Vertex);
vector<bool> visited(_vertexs.size(), false);
_DFS(index, visited);
}
void _DFS(size_t index, vector<bool>& visited)
{
visited[index] = true;
cout << _vertexs[index] << " ";
for (size_t i = 0; i < _vertexs.size(); i++)
{
if (_matrix[index][i] != W_MAX && visited[i] == false)
{
_DFS(i, visited);
}
}
}
private:
// 下标到顶点的映射
vector<V> _vertexs;
// 邻接矩阵的存储
vector<vector<W>> _matrix;
// 顶点到下标的映射
map<V, size_t> _vIndexMap;
};
}
namespace list_table
{
// 对于边的结构来说，需要存储的有边的两个顶点，边的权值，以及链接属性
template <class W>
struct Edge
{
Edge() = default;
Edge(size_t srci, size_t dsti, W w)
:_srci(srci)
, _dsti(dsti)
, _w(w)
, _next(nullptr)
{}
size_t _srci;
size_t _dsti;
W _w;
Edge<W>* _next;
};
// 顶点的类型，权值的类型，权值的最大值，是否是有向图
template<class V, class W, bool Direction = true>
class Graph
{
typedef Edge<W> Edge;
public:
Graph() = default;
Graph(const V* vertexs, size_t n)
{
// 建立顶点和下标的映射关系
for (size_t i = 0; i < n; i++)
{
_vertexs.push_back(vertexs[i]);
_vIndexMap[vertexs[i]] = i;
}
_link_tables.resize(n, nullptr);
}
// 给一个顶点取出来它对应的下标
size_t GetVertexsIndex(const V& vertex)
{
auto it = _vIndexMap.find(vertex);
if (it != _vIndexMap.end())
{
return it->second;
}
else
{
throw invalid_argument("不存在的顶点");
return -1;
}
}
// 给邻接表加值
void _AddEdge(size_t srci, size_t dsti, W w)
{
// 创建一个边的结构
Edge* EdgePtr = new Edge(srci, dsti, w);
Edge* tail = _link_tables[srci];
while (tail && tail->_next)
tail = tail->_next;
// 把这个边的结构头插链入到邻接表
if (tail == nullptr)
{
_link_tables[srci] = EdgePtr;
}
else
{
tail->_next = EdgePtr;
tail = tail->_next;
}
}
// 加边
void AddEdge(const V& src, const V& dst, W w)
{
size_t srci = GetVertexsIndex(src);
size_t dsti = GetVertexsIndex(dst);
_AddEdge(srci, dsti, w);
// 如果是无向图，就把对应的边也加到邻接表中
if (Direction == false)
{
_AddEdge(dsti, srci, w);
}
}
// 显示邻接矩阵
void Print()
{
// 打印邻接表
for (size_t i = 0; i < _link_tables.size(); ++i)
{
cout << _vertexs[i] << " ";
Edge* cur = _link_tables[i];
while (cur)
{
cout << "[" << _vertexs[cur->_srci] << "->" << _vertexs[cur->_dsti] << "]" << " ";
cur = cur->_next;
}
cout << endl;
}
}
private:
// 下标到顶点的映射
vector<V> _vertexs;
// 邻接表的存储
vector<Edge*> _link_tables;
// 顶点到下标的映射
map<V, size_t> _vIndexMap;
};
}
// 创建邻接矩阵和邻接表
void CreateGraph(matrix::Graph<int, int>& mph, list_table::Graph<int, int>& lph)
{
cout << "输入顶点个数->";
int vernum = 0;
cin >> vernum;
cout << "输入" << vernum << "个顶点->";
vector<int> vertex(vernum);
for (int i = 0; i < vernum; i++)
cin >> vertex[i];
matrix::Graph<int, int> tmp_mph(vertex.data(), vertex.size());
list_table::Graph<int, int> tmp_lph(vertex.data(), vertex.size());
cout << "输入要添加的边的个数->";
int edgenum = 0;
cin >> edgenum;
cout << "输入" << edgenum << "条边->" << endl;
int srci = 0, dsti = 0;
vector<pair<int, int>> edge(edgenum);
for (int i = 0; i < edgenum; i++)
{
cin >> srci >> dsti;
tmp_mph.AddEdge(srci, dsti, 0);
tmp_lph.AddEdge(srci, dsti, 0);
}
mph = tmp_mph;
lph = tmp_lph;
}
// 输出存储结果
void PrintInfo(matrix::Graph<int, int> mph, list_table::Graph<int, int> lph)
{
cout << "邻接矩阵存储结果" << endl;
mph.Print();
cout << endl;
cout << "邻接表的存储结果" << endl;
lph.Print();
cout << endl;
cout << "各顶点的入度和出度" << endl;
mph.cal_inward_outward();
cout << endl;
}
// 输出遍历结果
void PrintOrder(matrix::Graph<int, int> mph, list_table::Graph<int, int> lph)
{
int vertex = 0;
cout << "输入要进行遍历的顶点" << endl;
cin >> vertex;
cout << "图的深度优先遍历:" << endl;
mph.DFS(vertex);
cout << endl;
cout << "图的广度优先遍历:" << endl;
mph.BFS(vertex);
cout << endl;
}
int main()
{
matrix::Graph<int, int> mph;
list_table::Graph<int, int> lph;
CreateGraph(mph, lph);
PrintInfo(mph, lph);
PrintOrder(mph, lph);
return 0;
}
到了这里，关于C语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
