Tenemos un diseño de curso sobre codificación y decodificación de estructuras de datos de Huffman, ¿pueden ayudarme?
1. Propósito del experimento
Practicar las operaciones relacionadas de árboles y árboles de Huffman y varios procedimientos algorítmicos, y comprender la codificación y decodificación de los árboles de Huffman
Entorno experimental
Microsoft visual c
III. Descripción del problema experimental
1. Descripción del problema: cree un árbol binario almacenado en una lista binaria vinculada y recorralo (primero, medio y último). orden) e imprima los resultados del recorrido.
Requisitos básicos: aceptar la secuencia a priori ingresada desde el teclado, usar una lista binaria enlazada como estructura de almacenamiento (en orden a priori) para construir un árbol binario, imprimir el árbol binario en "forma de árbol". ", y luego recorrer el árbol binario (en orden a priori (orden a priori, orden intermedio y posterior), y finalmente imprimir los resultados del recorrido. Al menos un algoritmo transversal debe ser no recursivo.
Datos de prueba:
ABC?DE?G?F (donde? representa un carácter de espacio)
La salida es:
A priori: ABCDEGF
Prioridad: CBEGDFA
Precedencia: CGEFDBA
2 Descripción del problema: el uso de la codificación Huffman para la comunicación puede mejorar en gran medida la utilización del canal y acortar el tiempo. tiempo de transmisión de información y reducir los costos de transmisión. Sin embargo, esto requiere un sistema de codificación en el extremo emisor para precodificar los datos a transmitir y en el extremo receptor para decodificar (restaurar) los datos de entrada. Para un canal dúplex (es decir, un canal que puede transmitir información en ambas direcciones), se requiere un sistema completo de codificación/decodificación en cada extremo. Intente escribir un sistema de codificación/decodificación de codificación Huffman para dicho transceptor de mensajes.
Requisitos básicos: (al menos completar funciones 1-2)
Un sistema completo debe tener las siguientes funciones:
I: Inicialización. Lea un conjunto de caracteres de tamaño n, así como n caracteres y n pesos desde la terminal, cree un árbol Huffman y guárdelo en el archivo hfmTree.
Requisitos básicos:
E: Codificación. Usando el árbol Huffman construido (leído del archivo hfmTree si el archivo hfmTree no está en la memoria), codifique el cuerpo en el archivo ToBeTran y almacene el resultado en el archivo CodeFile.
D: Decodificación. Utilice el árbol Huffman creado para decodificar el código en el archivo CodeFile y almacene los resultados en el archivo TextFile.
P: Imprimir archivo de código (imprimir). Muestra el archivo CodeFile en el terminal en un formato compacto con 50 líneas de código. Al mismo tiempo, el archivo de código se escribe en el archivo CodePrint en este formato de caracteres.
T: Imprimir árbol de Huffman (TreePrinting). Muestra visualmente el árbol de Huffman que ya está en la memoria (árbol o tabla cóncava) en el terminal y escribe el árbol de Huffman en este formato de caracteres en el archivo TreePrint.
Datos de prueba:
Establecer peso w= (5, 29, 7, 8, 14, 23, 3, 11), n=8.
Según el carácter "0" o "1", se determina si se busca el hijo izquierdo o el hijo derecho. El peso correspondiente de la codificación es:
5: 0001, 29:11, 7:1110, 8:1111
14:110, 23:01, 3:0000, 11:001
Huff se construye en base a estadísticas reales de conjuntos de caracteres y frecuencias dados en la siguiente tabla Manshu, e implementa la codificación y decodificación de la siguiente información: "Este programa es mi favorito".
IV. Flujo del programa principal del experimento
Pregunta experimental un programa principal:
1.
void CreatBiTree(BitTree *bt)/ /Cree un árbol binario con una secuencia transversal previa extendida; si es #, la raíz actual del árbol se establece en nula; de lo contrario, solicite un nuevo nodo//
{
char ch;
ch=getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BitTree)malloc(sizeof(BitNode));
(*bt)-gt; datos=ch;
CreatBiTree(amp;((*bt)-gt;LChild));
CreatBiTree(amp;((*bt)-gt;RChild));
}
}
}
2.void Visit(char ch)//Visita el nodo raíz
{
printf("c ",ch);
}
3
void PreOrder(raíz de BitTree)
{
if (root!=NULL)
{
Visita(root -gt;data);
PreOrder(root -gt;LChild ) ;
PreOrder(root -gt;RChild);
}
}
4. void InOrder(BitTree root)
p>{
if (root != NULL)
{
InOrder(root -gt;LChild
Visita(root -gt; datos);
InOrder(root -gt; RChild); p> 5 .int PostTreeDepth(BitTree bt) //Algoritmo recursivo transversal post-orden para encontrar la altura del árbol binario //
{
int hl, hr, max;
si (por cierto! =NULL)
{
hl=PostTreeDepth(bt- gt;LChild); //Encontrar la profundidad del subárbol izquierdo
hr=PostTreeDepth(bt) - gt;RChild); //Encontrar la profundidad del subárbol derecho
max=hlgt;hr?hl:hr //Obtener el valor mayor de la profundidad de los subárboles izquierdo y derecho
return(max 1); //Devuelve la profundidad del árbol
}
else return(0); //Si es un árbol vacío, devuelve 0
}
6.void PrintTree(BitTree Boot, int nLayer) // Árbol vertical que imprime el árbol binario //
{
int i;
if(Boot==NULL) return;
PrintTree(Boot-gt;RChild, nLayer 1); ; ilt; nLayer; i )
printf(" ");
printf("c\n", Arranque-gt;
PrintTree); (Boot-gt;LChild,nCapa 1);
}
7.void main()
{
BitTree T;
int h;
int capa;
int hoja de árbol;
capa = 0; "Ingrese los elementos del árbol binario (ingresados como una secuencia transversal de precedencia extendida, donde . representa un subárbol vacío):\n"); p > printf("La secuencia transversal del pedido previo es: ");
Pedido previo(T);
printf("/n La secuencia transversal del pedido medio es: ");
InOrder(T).
printf("/n La secuencia transversal de PostOrder es: ");
PostOrder(T); ( T);
printf("/nLa profundidad de este árbol binario es:\d\n",h);
printf("/nEste árbol binario se muestra como un la visualización horizontal es:\n");
PrintTree(T, capa);
}
Experimento 2 Flujo principal del programa:
1.int main(){
HuffmanTree huftree;
char Elegir
while(1){
coutlt;lt; ; "\n************************Bienvenido al sistema de codificación/decodificación de Huffman ************** *** *****\n";
coutlt;lt; "*Puedes hacer lo siguiente:*\Crear un árbol de Huffman*\n";
coutlt ;lt; "* 2. Codificación (el texto fuente ya está en el archivo ToBeTra o ingresado en el teclado) *\n";
coutlt;lt "* 3. Decodificación (el texto del código) ya está en el archivo CodeFile) *\n ";
coutlt; lt; "* 4. Mostrar el texto del código *\n";
coutlt; lt; "* 5. Mostrar árbol de Huffman *\n n";
coutlt; lt; "* 6.Salir *\n"; coutlt; lt; "*************** ******* ** ***
*************************************************\ n" ;
coutlt;lt; "Por favor, elija una acción:";
cingt;gt;Elegir;
cambiar(Elegir)
{
caso '1':
huftree.CreateHuffmanTree();
descanso
caso '2';
huftree.CreateHuffmanTree();
ruptura
caso '3':
huftree.CreateHuffmanTree(); >
caso '5':
"* 6.PrintHuffmanTree();
descanso;
caso '6':
coutlt;lt;"\n************************¡Gracias por usar este sistema!*********** ******* ****\n\n";
sistema("pausa");
devuelve 0;
}/ /switch
}// while
}///main
2./// Crear función de árbol de Huffman
// Función: Crear árbol de Huffman función Árbol de Huffman (llame al teclado para crear un árbol de Huffman o llame a una función que cree un árbol de Huffman a partir de un archivo)
void HuffmanTree::CreateHuffmanTree()
{char Choose;
p>
coutlt;lt; "¿Quieres leer el árbol Huffman desde un archivo (presiona 1) o ingresar el árbol Huffman desde el teclado (presiona 2) ?";
cingt;gt ;Choose;
if(Choose=='2') { //Crear árbol de Huffman usando el teclado inputCreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //del archivo hfmTree.dat del árbol Huffman y cree un árbol Huffman
CreateHuffmanTreeFromFile(); p> }
}
3. // Crear árbol Huffman desde la función del teclado
// Función función: Crear árbol Huffman desde el teclado
// Parámetros: ninguno.
p>// Parámetros de función: Ninguno
// Valor de retorno del parámetro: Ninguno
void HuffmanTree::CreateHuffmanTreeFromKeyboard(){
int Num;
coutlt;lt;"/nIngrese el número de juegos de caracteres de origen:"
cingt;gt;Num;
if (Numlt;=1) {
coutlt;lt; "No se puede construir el árbol Huffman con menos de 2 nodos de hoja.\n\n";
LeafNum=Num;
Nodo=new HuffmanNode[2*Num-1];
for(int i=0; ilt; Num; i) {//read Obtenga la información del nodo de hoja del árbol de Huffman
coutlt;lt; "Ingrese el primer "lt;lt;i 1lt;lt; "El valor del carácter";
getchar ();
Node[i].sourcecode=getchar(); // Los caracteres del texto fuente se almacenarán en la matriz de caracteres Info[]
getchar(). ;
coutlt;lt; "Ingrese el peso o la frecuencia del carácter";
cingt;gt; Node[i].weight; el texto se almacena en Nodo[]. peso
Nodo[i].parent=-1
Nodo[i].lchild=-1; Nodo[i].rchild=- 1;
Nodo[i].code="\0"
}
for(int j=Núm. ; jlt; 2*Num-1 ; j ) {// Bucle para construir el árbol de Huffman dentro de
for(int k=j-1;kgt;=0;k--) {
if (Node [k].parent==-1){ //si es el nodo raíz de un subárbol particular
if (Node[k].weightlt;max1){ / /encontrar un peso que sea mayor que el máximo actual
max2=max1;
max1=Node[k].weight
pos2=pos1; p>
pos1=k ;
}
else
if (Node[k].weightlt; max2){ //busca el siguiente más grande peso mayor que el nodo actual en el subíndice i, cuyos hijos izquierdo y derecho son el nodo señalado por pos1 y pos2 arriba
Nodo[pos1].//for
//genera la codificación de los caracteres en todos los nodos hoja
for (int m=0; mlt; Num; m) {
//genera la codificación del Nodo [i].código fuente, guárdelo en Nodo[i].code
int j=m
int j1
while(Node[j] .parent! =-1) { // Comenzando desde el nodo hoja hasta el nodo raíz, se generará un fragmento de código en cada nivel superior y se almacenará en code[]
j1=Node[j] .parent;
if(Nodo[j1].lchild==j)
Nodo[m].code.insert(0, "0"); /p>
else
Nodo[m].code.insert(0, "1"
j=j1 }}
; coutlt;lt; "El árbol Huffman se ha construido exitosamente.\n";
//Escribe el árbol Huffman construido en el archivo hfmTree.dat
char ch;
coutlt;lt; "Si desea reemplazar el archivo del árbol Huffman original (Y/N):";
cingt;gt;ch;
if (ch! ='Y ' amp; ch! = 'Y') retorno;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios:: binario |ios::trunc); //abre el archivo
if(fop.fail()) {
coutlt;lt;"\n Error al abrir el archivo del árbol Huffman Árbol de Huffman al archivo hfmTree.dat.write((char*)amp;Node[n], sizeof(Node[n]));
flush(cout }
fop .close(); //cerrar archivo
coutlt;lt;"\n El árbol Huffman se ha escrito correctamente en el archivo hfmTree.dat. \n";}
4. //Crear la función del árbol Huffman desde el archivo
//Función función: Crear el árbol Huffman desde el archivo
// Parámetros de la función : Ninguno
// Valor de retorno del parámetro: Ninguno
void HuffmanTree::CreateHuffmanTreeFromFile (){
ifstream fip
fip. open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
coutlt;lt; El archivo hfmTree.dat no se pudo abrir y no se pudo construir el árbol Huffman.
\n";
return;
}
fip.read((char*)amp; LeafNum, sizeof(LeafNum));
if (LeafNumlt;=1) {
coutlt;lt; "Los datos en el archivo del árbol de Huffman son incorrectos, el número de nodos de hoja es menor que 2 y el árbol de Huffman no se puede construir. . \n";
fip.close();
return;
}
Nodo=nuevo HuffmanNode[2*LeafNum- 1];
for(int i=0; ilt; 2*LeafNum-1; i )
fip.close(); SourceTextlt;
//iniciar decodificación
ofstream fop("CodeFile.dat",ios::trunc); //Abrir archivo de almacenamiento de texto de código
int k= 0;
while(SourceText[k]!= '\0') //Codifica los caracteres en la cadena de texto fuente uno por uno comenzando desde el primero
{
int i;
for(i=0; ilt; LeafNum; i ){ //Encuentra el subíndice del carácter del texto fuente que actualmente se codificará en el árbol de Huffman. Node[]
if(Node[i].sourcecode==SourceText[k]) { //Escribe el código correspondiente en el archivo de texto del código
foplt;lt;Node[ i].code;
romper
};
}
if (igt;=LeafNum) {
coutlt;lt; "Hay caracteres no codificables en el código fuente. No se puede continuar la ejecución. \n"lt;lt;endl;
fop.close();
return;
}
k; // Los caracteres en la cadena del código fuente se mueven hacia atrás uno
}
fop.close();
coutlt;lt "Codificación completa, texto del código Se ha escrito el archivo CodeFile.dat.
\n\n";
}
6.// Función decodificadora
// Función: Decodificar el árbol de Huffman
// Parámetros de función: Ninguno
// Valor de retorno del parámetro: Ninguno
void HuffmanTree:: Decoder()
{// Si no hay ha en la memoria Árbol de Huffman, luego construya el árbol de Huffman a partir del archivo de árbol de Huffman hfmTree.dat
if (Node==NULL)
{
CreateHuffmanTreeFromFile ();
if (LeafNumlt;=1) {
coutlt;lt; "No hay ningún árbol de Huffman en la memoria. Operación deshacer.
()) {
coutlt;lt; "No hay texto de código para decodificar.\n";
Retorno;
}
char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch)){
k;
}
fip1.close();
CodeStr=nuevo char[k 1]
ifstream fip2; ("CodeFile.dat");
k=0
while(fip2.get(ch))
CodeStr[k ]=ch; /p>
fip2.close();
CodeStr[k]='\0';
coutlt;lt; "El texto fuente decodificado es: "; /p>
ofstream fop("TextFile.dat");
int j= LeafNum*2-1-1; //j apunta a la raíz del árbol de Huffman
int i=0; // El texto del código comienza desde el primer símbolo y desciende desde la raíz según el árbol de Huffman. Se decide según el símbolo actual del texto del código si baja al hijo izquierdo o. el hijo correcto
while(CodeStr[i]!= '\0') { // Baja al nodo hoja del árbol de Huffman y luego traduce el símbolo del texto fuente correspondiente al nodo hoja
if(CodeStr[i] =='0')
j=Node[j].lchild
else
j; =Node[j].rchild;
if(Node[j].rchild==-1) { // Dado que el árbol de Huffman no tiene un nodo de orden 1, esta condición es equivalente a Node [j] siendo un nodo hoja
coutlt;lt; Node[j].sourcecode; // La salida de pantalla traduce un carácter fuente
foplt;lt; ;
j=LeafNum*2 -1-1; //j apunta a la raíz del árbol de Huffman nuevamente
}
i; >
}
fop. close();
coutlt;lt;"\n descodificado correctamente y guardado en el archivo TextFile.dat.\n\n" ;
}
7. // Función de archivo de código de salida
//Función: genera el archivo de código del árbol Huffman desde el archivo
// Parámetros de función: Ninguno
// Valor de retorno del parámetro: Ninguno
void HuffmanTree::PrintCodeFile()
{
Void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1
ifstream fip("CodeFile. dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
if(fip.fail())
{
coutlt;lt; archivo, no se puede mostrar el contenido del archivo de código.\n";
return;
}
while(fip.get(ch))
{coutlt;lt;ch;
foplt;lt;ch;
foplt;lt;ch
if(i==50 )
{
cout lt;lt;endl;
foplt;lt;endl;
i=0;
}
i;
}
coutlt;lt;endl;
foplt;lt;endl;
p>
fip.close();
fop.close();
}
8.
// Función de función: Generar árbol de Huffman directamente desde la memoria o archivo
// Parámetros de función: Ninguno
// Valor de retorno del parámetro: Ninguno
void HuffmanTree::PrintHuffmanTree()
{
Si no hay ningún árbol de Huffman en la memoria, se recuperará del archivo del árbol Huffman hfmTree.dat y creará un árbol Huffman
if(Node==NULL)
{
CreateHuffmanTreeFromFile(. );
if (LeafNumlt;=1) {
coutlt;lt; "No hay ningún árbol de Huffman en la memoria. La operación se deshace.\n\n";
Retorno; }}
ofstream fop("TreePrint.dat", ios_base::trunc
fop.close(); > PrintHuffmanTree_aoru(2* LeafNum-1-1);
Regresar
}