Project 2: You are to implement the Huffman coding algorithm step 2 -- Construct
ID: 3744901 • Letter: P
Question
Project 2: You are to implement the Huffman coding algorithm step 2 -- Construct Huffman ordered linked list
using insertion sort.
********************************
I. Language: C++ and Java
********************************
********************************
II. Input : A text file contains a list of <char prob> pairs with the following format.
// note: The input prob are integer, has been multiplied by 100, i.e., a prob equal to .40 will be given as 40.
********************************
char 1 prob 1
char 2 prob 2
char 3 prob 3
:
:
char n prob n
********************************
II. Outputs (use argv): a text file. The output format is given below.
********************************
III. Data structure: Both of your C++ and Java must have all the object classes as given below.
********************************
- listNode class
- chStr (string)
- prob (int)
- next (listNode *)
- constructor(s)
- linkedList class
- listHead (listNode *)
- constructor (..)
- insertNewNode (listHead newNode)
// Use the algorithm steptaught in class.
- findSpot (…) // Use the findSpot algorithm steps taught in class.
- printList (…)
// print the list to outFIle, from listHead to the end of the list in the following format:
listHead -->(“dummy”, 0, next’s chStr 1 )-->( chStr 1 , prob 1 , next’s chStr 2 )...... --> (chStr j , probj , NULL)-->
NULL
For example:
listHead -->(“dummy”, 0, “b”)-->( “b”, 5, “a”) -->( “a”, 7, “d”)............ --> (“x”, 45, NULL)--> NULL
2
******************************************
IV. Main(argv)
******************************************
Step 1: listHead get a newNode as the dummy listNode with (“dummy” ,0), listHead to point to.
Step 2: inFile open input file using argv
outFIle open ouput file using argv
Step 3: chr get from inFile
Prob get from inFile
newNode get a new listNode
newNode.chStr chr
newNode.prob Prob
newNode.next null
Step 4: insertNewNode (listHead, newNode) // use algorithm steps given in class
Step 5: printList (listHead) // Out put the list to outFile, use the format given in the above.
Step 6: repeat step 3 – step 5 until the end of inFile .
Step 7: close inFile
close outFile
Explanation / Answer
HuffmanCode.java
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
public class HuffmanCode {
public static void main(String[] args) throws IOException{
try {
File file = new File(args[0]);
BufferedWriter outFile1 = new BufferedWriter(new FileWriter(args[1], true));
BufferedWriter outFile2 = new BufferedWriter(new FileWriter(args[2], true));
BufferedWriter outFile3 = new BufferedWriter(new FileWriter(args[3], true));
BufferedWriter outFile4 = new BufferedWriter(new FileWriter(args[4], true));
Scanner inFile = new Scanner(file);
HuffmanLListTree construct = new HuffmanLListTree();
outFile1.append("The creation of the linked list using the insertion sort: ");
outFile1.newLine();
construct.ConstructLinkedList(inFile, outFile1);
outFile1.newLine();
outFile1.newLine();
outFile1.append("The creation of the binary tree root using the linked list: ");
outFile1.newLine();
construct.ContructBinTree(outFile1, outFile2);
outFile3.append("Symbol Code");
outFile3.newLine();
construct.ConstructCode(construct.Root, "", outFile3);
outFile4.append("Pre Order: ");
construct.preOrder(construct.Root, outFile4);
outFile4.newLine();
outFile4.append("In Order: ");
construct.inOrder(construct.Root, outFile4);
outFile4.newLine();
outFile4.append("Post Order: ");
construct.postOrder(construct.Root, outFile4);
inFile.close();
outFile1.close();
outFile2.close();
outFile3.close();
outFile4.close();
} catch (FileNotFoundException e){
e.printStackTrace();
}
}
}
HuffmanLListTree.java
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
public class HuffmanLListTree {
listBinTreeNode listHead;
listBinTreeNode Root;
//constructor
void ConstructLinkedList(Scanner inFile, BufferedWriter outFile1) throws IOException{
listBinTreeNode dummy = new listBinTreeNode("dummy", 0);
listHead = dummy;
listBinTreeNode spot;
listBinTreeNode newNode;
while(inFile.hasNext()){
newNode = new listBinTreeNode(inFile.next(), inFile.nextInt());
spot = findSpot(listHead, newNode.prob);
insertNewNode(spot, newNode);
printList(outFile1);
}
inFile.close();
}
public void ContructBinTree(BufferedWriter outFile1, BufferedWriter outFile2) throws IOException{
listBinTreeNode newNode;
listBinTreeNode spot;
outFile2.append("The new nodes created in the binary tree creation process: ");
while(listHead.next.next!= null){
newNode = new listBinTreeNode((listHead.next.chStr + listHead.next.next.chStr),(listHead.next.prob + listHead.next.next.prob));
newNode.left = listHead.next;
newNode.right = listHead.next.next;
newNode.printNode(outFile2);
spot = findSpot(listHead, newNode.prob);
insertNewNode(spot, newNode);
listHead.next = listHead.next.next.next;
printList(outFile1);
}
Root = listHead.next;
}
void ConstructCode(listBinTreeNode Root, String f, BufferedWriter outFile3) throws IOException{
String code = f;
if(Root == null){
System.out.println("this is an empty string");
return;
}
else if(isLeaf(Root)){
Root.code = code;
outFile3.append(Root.chStr + " " + Root.code);
outFile3.newLine();
} else {
ConstructCode(Root.left, code + '0', outFile3);
ConstructCode(Root.right, code + '1', outFile3);
}
}
private boolean isLeaf(listBinTreeNode t) {
return t.left == null && t.right == null;
}
void preOrder(listBinTreeNode T, BufferedWriter outFile4) throws IOException{
if(T == null) return;
T.printNode(outFile4);
preOrder(T.left, outFile4);
preOrder(T.right, outFile4);
}
void inOrder(listBinTreeNode T, BufferedWriter outFile4) throws IOException{
if(T == null) return;
inOrder(T.left, outFile4);
T.printNode(outFile4);
inOrder(T.right, outFile4);
}
void postOrder(listBinTreeNode T, BufferedWriter outFile4) throws IOException{
if(T == null) return;
postOrder(T.left, outFile4);
postOrder(T.right, outFile4);
T.printNode(outFile4);
}
listBinTreeNode findSpot(listBinTreeNode listHead, int prob){
listBinTreeNode spot = listHead;
while(spot.next != null && spot.next.prob < prob)
if(spot.next != null && spot.next.prob < prob) spot = spot.next;
return spot;
}
void insertNewNode(listBinTreeNode spot, listBinTreeNode newNode){
spot = findSpot(listHead, newNode.prob);
if(spot != null){
newNode.next = spot.next;
spot.next = newNode;
}
}
boolean isEmpty(){
return listHead.next.next == null;
}
void printList(BufferedWriter outFile) throws IOException{
outFile.append("listHead-->");
listBinTreeNode current = listHead;
while(current.next != null){
outFile.append("(" + """ + current.chStr + """ + "," + current.prob + "," + """ + current.next.chStr + """ + ")" + "-->");
current = current.next;
}
outFile.append("(" + """ + current.chStr + """ + "," + current.prob + "," + """ + "NULL" + """ + ")" + "--> NULL");
outFile.newLine();
}
}
listBinTreeNode.java
import java.io.BufferedWriter;
import java.io.IOException;
public class listBinTreeNode {
String chStr;
int prob;
String code;
listBinTreeNode next;
listBinTreeNode left;
listBinTreeNode right;
public listBinTreeNode(){
chStr = "";
prob = 0;
code = "";
}
public listBinTreeNode(String chStr, int prob){
this.chStr = chStr;
this.prob = prob;
}
public void printNode(BufferedWriter outFile) throws IOException{
outFile.append(this.chStr + ", ");
}
}
=================================================================================================
// main.cpp
#include <iostream>
#include <fstream>
using namespace std;
ifstream inFile;
ofstream outFile1;
ofstream outFile2;
ofstream outFile3;
ofstream outFile4;
class listBinTreeNode {
public:
string chStr;
int prob;
string code;
listBinTreeNode* next;
listBinTreeNode* left;
listBinTreeNode* right;
listBinTreeNode(){
this->chStr = "";
this->prob = 0;
this->code = "";
this->next = NULL;
this->left = NULL;
this->right = NULL;
}
listBinTreeNode(string chStr, int prob){
this->chStr = chStr;
this->prob = prob;
this->code = "";
this->next = NULL;
this->left = NULL;
this->right = NULL;
}
void printNode(ofstream& outFile){
outFile << (chStr + ", ");
}
bool isLeaf(){
return this->left == NULL && this->right == NULL;
}
};
class HuffmanLListTree {
private:
listBinTreeNode* listHead;
listBinTreeNode* Root;
public:
void ConstructLinkedList(ofstream& outFile){
listBinTreeNode* dummy;
dummy = new listBinTreeNode("dummy", 0);
listHead = dummy;
listBinTreeNode* spot;
listBinTreeNode* newNode;
string x;
int y;
while(inFile >> x){
inFile >> y;
newNode = new listBinTreeNode(x, y);
spot = findSpot(listHead,newNode->prob);
insertNewNode(spot, newNode);
printList();
}
}
void ConstructBinTree(ofstream& outFile1, ofstream& outFile2){
listBinTreeNode* newNode;
listBinTreeNode* spot;
outFile2 << "The new nodes created in the binary tree creation process: ";
while(listHead->next->next != NULL){
newNode = new listBinTreeNode((listHead->next->chStr + listHead->next->next->chStr), (listHead->next->prob + listHead->next->next->prob));
newNode->left = listHead->next;
newNode->right = listHead->next->next;
newNode->printNode(outFile2);
spot = findSpot(listHead, newNode->prob);
insertNewNode(spot, newNode);
listHead->next = listHead->next->next->next;
printList();
}
Root = listHead->next;
}
void ConstructCode(listBinTreeNode* t, string f, ofstream& outFile3){
string code = f;
if(t == 0){
cout << "this is an empty string";
return;
} else if(t->isLeaf()){
t->code = code;
outFile3 << t->chStr + " " + t->code;
outFile3 << endl;
} else {
ConstructCode(t->left, code + '0', outFile3);
ConstructCode(t->right, code + '1', outFile3);
}
}
void preOrder(listBinTreeNode* T, ofstream& outFile4){
if(T == NULL) return;
T->printNode(outFile4);
preOrder(T->left, outFile4);
preOrder(T->right, outFile4);
}
void inOrder(listBinTreeNode* T, ofstream& outFile4){
if(T == NULL) return;
inOrder(T->left, outFile4);
T->printNode(outFile4);
inOrder(T->right, outFile4);
}
void postOrder(listBinTreeNode* T, ofstream& outFile4){
if(T == NULL) return;
postOrder(T->left, outFile4);
postOrder(T->right, outFile4);
T->printNode(outFile4);
}
listBinTreeNode* findSpot(listBinTreeNode* node ,int prob){
listBinTreeNode* spot = node;
while(spot->next != NULL && spot->next->prob < prob)
if(spot->next != NULL && spot->next->prob < prob) spot = spot->next;
return spot;
}
void insertNewNode(listBinTreeNode* spot, listBinTreeNode* newNode){
spot = findSpot(listHead, newNode->prob);
if(spot != NULL){
newNode->next = spot->next;
spot->next = newNode;
}
}
bool isEmpty(){
return listHead->next->next == NULL;
}
void printList(){
outFile1 << "listHead-->";
listBinTreeNode* current;
current = listHead;
while(current->next != NULL){
outFile1 << "(" << """ << current->chStr + """ << "," << current->prob << "," << """ + current->next->chStr << """ << ")" << "-->";
current = current->next;
}
outFile1 << "(" << """ << current->chStr + """ << "," << current->prob << "," << """ << "NULL" << """ << ")" << "--> NULL";
outFile1 << endl;
}
void HuffManCode(){
outFile1 << "The creation of this linked list using insertion sort:" <<endl;
ConstructLinkedList(outFile1);
outFile1 << endl << endl <<"The creation of the binary tree root using the linked list: " <<endl;
ConstructBinTree(outFile1, outFile2);
outFile3<< "Symbol Code" << endl;
ConstructCode(Root, "", outFile3);
outFile4 << "Pre Order: ";
preOrder(Root, outFile4);
outFile4<< endl << "In Order: ";
inOrder(Root, outFile4);
outFile4<< endl << "Post Order: ";
postOrder(Root, outFile4);
listHead = NULL;
inFile.close();
outFile1.close();
outFile2.close();
outFile3.close();
outFile4.close();
}
};
int main(int argc, const char * argv[]) {
inFile.open(argv[1]);
outFile1.open(argv[2]);
outFile2.open(argv[3]);
outFile3.open(argv[4]);
outFile4.open(argv[5]);
HuffmanLListTree construct;
construct.HuffManCode();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.