FrequencyList.java

//The linked list of nodes containing frequency data

class FrequencyList {

Node head;

int count;

FrequencyList() {

head = null;

count = 0;

}

//search for node in linked list that contains key. Returns a reference to node if found, else returns null.

public Node search(String key) {

Node curr=head;

while (curr != null) {

if (key.compareTo(curr.data.symbol) == 0) {

break;

}

curr = curr.next;

}

return curr;

}

//print contents of linked list.

public void printList() {

Node curr;

curr = head;

while (curr != null) { //print each node

curr.print();

curr = curr.next;

}

}

//insert a new node if key is not in the linked list. Otherwise increment frequency by 1.

public void insert(String key) {

Node curr;

curr = search(key);

if (curr == null) { //key not in list, add it to front.

curr = new Node(key); //insert new node at front of list

curr.next = head;

head = curr;

count = count + 1;

}

else { //already in list. Increment the frequency by 1.

curr.data.frequency = curr.data.frequency + 1; //increment frequency of symbol

}

}

}

//A node of the Linked List class FrequencyList.

class Node {

FrequencyData data;

Node next;

Node(String key) {

data = new FrequencyData(key,1);

}

void print() {

data.print();

}

}

//This class contains a symbol and its frequency

class FrequencyData {

String symbol; //using a string type will become handy when build the Huffman encoding tree.

int frequency;

FrequencyData (FrequencyData data) {

symbol = data.symbol;

frequency = data.frequency;

}

FrequencyData(String s, int freq) {

symbol = s;

frequency = freq;

}

//print content of symbol (which may contain more than one character

//for debugging purposes only.

void printSymbol() {

int i;

int a;

String s="";

for (i = 0; i

a = (int) symbol.charAt(i);

if (a==10)

s = s+""; //instead of printing a newline, print instead

else if (a == 32)

s =s+""; //same for space

else if (a == 9)

s =s+""; //same for tab. Should probably do same for "escaped" characters

else

s = s+ symbol.charAt(i);

}

System.out.print(s);

}

/*used to print symbol(s) and frequency*/

/*used for debugging*/

void print() {

printSymbol();

System.out.println(":"+frequency);

}

}

FrequencyTest.java

import javax.swing.JOptionPane;

import java.io.*;

import java.util.*;

//This class shows how to use compute the frequencies of the symbols in a file.

public class FrequencyTester {

FrequencyList fList;

public FrequencyTester() {

fList = null;

}

public static void main(String args[]) {

String fileName;

Scanner file;

String s;

String inputLine;

int i;

FrequencyList fList;

FrequencyTester ft = new FrequencyTester();

ft.fList = new FrequencyList();

fList = ft.fList;

fileName = JOptionPane.showInputDialog("Enter filename.");

System.out.println("Input File:"+fileName);

System.out.println("**********Content of Input File**************");

try {

file = new Scanner( new File( fileName ) );

while (file.hasNextLine()) { //read in line

inputLine = file.nextLine();

System.out.println(inputLine);

for ( i = 0;i

s = ""+inputLine.charAt(i);

fList.insert(s); //insert symbol into linked list (increment count by 1 if already in list)

}

s = " "; //each line ends with a newline character (which is not captured in inputLine)

fList.insert(s); //add it manually

}

System.out.println("**********End of Input File*************");

System.out.println("Symbols and their frequencies");

fList.printList(); //print the contents of the linked list of symbols and their frequencies.

file.close();

}catch (IOException e) {

System.out.println("IO Error: " + e.getMessage());

}

catch (Exception e) {

System.out.println("Error: " + e.getMessage());

}

}

}

Thank you

Objective In this assignment, you will use binary trees and heaps to implement the Huffman coding scheme. Your Program General Overview: In this assignment, your task is to implement the encoding and decoding algorithms for Huffman coding. Huffman coding will be discussed in class and therefore we will not spend much time talking about how the algorithms work. There are three major steps to the solution that needs to be dealt with: 1. Reading in a data file and computing the frequency of characters. 2. Using these frequencies, build an Huffman encoding tree and encode the data file using it 3. Using the encoding of the data file and the Huffman tree, decode to obtain original data file. Important: Before you go any further, you should go through the slides from the lecture notes on Huffman coding and have them handy as you are reading the rest of the assignment 1-Reading Data File and Frequency Computation In this step, you are to prompt for a text data file, open it and compute (and store) the freqency of each character that occurs. To help you in computing the frequencies, a set of helper classes in the file FrequencyList.java is provided that will do this for you. These classes will create a linked list where each node's data consists of a character and its frequency (in the data file). In addition, the class FrequencyTester.java shows how to use these helper classes. You are free to modify the code as you please, if you want Note: When you are using a method to read in a line from the input file, the result does not include a newline ( ). Therefore, you have to manually add it as an input character at the end of each line (see code for FrequencyTester.java) In this step, your program should output the frequency table of the symbols. The code to print this table is already part of the code provided. See FrequencyTester.java on how to do this. For example, on the test file smalltest.txt provided, your output should look like: Objective In this assignment, you will use binary trees and heaps to implement the Huffman coding scheme. Your Program General Overview: In this assignment, your task is to implement the encoding and decoding algorithms for Huffman coding. Huffman coding will be discussed in class and therefore we will not spend much time talking about how the algorithms work. There are three major steps to the solution that needs to be dealt with: 1. Reading in a data file and computing the frequency of characters. 2. Using these frequencies, build an Huffman encoding tree and encode the data file using it 3. Using the encoding of the data file and the Huffman tree, decode to obtain original data file. Important: Before you go any further, you should go through the slides from the lecture notes on Huffman coding and have them handy as you are reading the rest of the assignment 1-Reading Data File and Frequency Computation In this step, you are to prompt for a text data file, open it and compute (and store) the freqency of each character that occurs. To help you in computing the frequencies, a set of helper classes in the file FrequencyList.java is provided that will do this for you. These classes will create a linked list where each node's data consists of a character and its frequency (in the data file). In addition, the class FrequencyTester.java shows how to use these helper classes. You are free to modify the code as you please, if you want Note: When you are using a method to read in a line from the input file, the result does not include a newline ( ). Therefore, you have to manually add it as an input character at the end of each line (see code for FrequencyTester.java) In this step, your program should output the frequency table of the symbols. The code to print this table is already part of the code provided. See FrequencyTester.java on how to do this. For example, on the test file smalltest.txt provided, your output should look like