#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#define SIZE 100
typedef struct ASCII {
char str[SIZE];
int code;
struct ASCII* point;
} Dictionary; //assigne a struct node to be the dictionary for new strings
Dictionary *head=NULL;
void addDiction (Dictionary **head, char *Prefix, char *Char, int Codeword) //head is passed by refrence,
{ //if head changed iside the function, it will change in all the code
Dictionary* spare = *head; //assign spare as haed to travers using it
size_t prefixLength = strlen(Prefix);
size_t charLength = strlen(Char); //assign length of prefix and char
char temp[prefixLength+charLength+ 1]; //temp size is size of prefix+char plus 1 just in case
strcpy(temp,Prefix); //copy prefix to temp
strcat(temp,Char); //add char to temp without deleting temp (temp=prefix+char)
Dictionary* diction = (Dictionary *)malloc(sizeof(Dictionary)); //allocate a new node struct
strcpy(diction->str, temp); //add prefi+char to sting in the node
diction->code = Codeword; // add the code word to the code in the node
diction->point = NULL;
if(*head==NULL)
{
*head=diction;//if linkedlist is empty add the node as the first nose
return;
}
else
{
while (spare->point != NULL) {
spare = spare->point; //if not empty travers using spare till end of linked list
}
spare->point = diction; //add node at the dend of the linke list
}
return;
}
int checkDiction (Dictionary *head, char *Prefix, char *Char)
{
Dictionary* spare = head; //assign spare as haed to travers using it
size_t prefixLength = strlen(Prefix);
size_t charLength = strlen(Char); //assign length of prefix and char
char temp[prefixLength+charLength+ 1]; //temp size is size of prefix+char (plus 1 just in case)
strcpy(temp, Prefix); //copy prefix to temp
strcat(temp, Char); //add char to temp without deleting temp (temp=prefix+char)
while (spare != NULL) // travers among the linked list
{
if (strcmp(spare->str, temp) == 0) //if temp(prefix+char) is in the linkedlist (dectionary)
{
return spare->code; //return codeword of prefix+char
}
spare = spare->point; //next node
}
return -1; //if not in dectionary return -1
}
int ReturnPrefix (Dictionary *head, char *Prefix)
{
Dictionary* spare = head; //assign spare as haed to travers using it
while (spare != NULL)
{
if (strcmp(spare->str, Prefix) == 0) //check of prefix is in dectionary
{
return spare->code; //return the code of prefix only
}
spare = spare->point;
}
return -1;
}
void freeDictionary(Dictionary **head) {
*head = NULL; //to empty the dictionary and use it again
}
void Encoding (char string[SIZE], char comp[SIZE])
{
char Prefix[SIZE]="";
char Char[SIZE]=""; //assigne 2 stings prefix & char
Prefix[0]=*string; //prefix is the first character in the string (string)
int Codeword=256; //codeword starts from 256
int c=1; //initialise c
for(int i=1; string[i] != '\0'; i++) //loop until the end of the string
{
Char[0]=string[i]; //char (one character) is the next character in the string
if (checkDiction (head, Prefix, Char) != -1) //it returns the code word of (prefix+char) so in dectionary
{
strcat(Prefix, Char); //add the char in prefix (prefix=prefix+char)
}
else//not in dectionary
{
if(Prefix[1]== '\0')//if prefix is one char only
{
char t[10]=" ";
sprintf(t, "<%d>", Prefix[0]); //add the prefix number from ascii table to string T
strcat(comp, t); //add codword of prefix to string comp
}
else //prefix is a sting
{
int codew=ReturnPrefix(head, Prefix); //codew is prefix codeword
char t[10]=" ";
sprintf(t, "<%d>", codew);//add codeword to string t
strcat(comp, t);//add codword of prefix to string comp
}
addDiction (&head, Prefix, Char, Codeword);//add prefix + char in dectionary to be used in compression
Codeword++; //increment codeword for the next character to be added in dectionary
strcpy(Prefix, Char);//replace prefix with char value
}
}
//add the codeword of the last characters in string (saved in prefix for the last time)
if(Prefix[1]== '\0')
{
char t[10]=" ";
sprintf(t, "<%d>", Prefix[0]);
strcat(comp, t);
}
else
{
int codew=ReturnPrefix(head, Prefix);
char t[10]=" ";
sprintf(t, "<%d>", codew);
strcat(comp, t);
}
}
void print() { //print the dictionary
Dictionary* spare = head;
printf("\nDictionary: \n");
printf("____________________\n");
printf("Code Word String\n");
printf("--------------------\n");
while (spare != NULL) {
printf(" %d %s\n", spare->code, spare->str);//print each node (string+codeword)
spare = spare->point; //travers among the linked list using spare
}
printf("____________________\n");
}
int countAfter(Dictionary *head) //count string after compression ()
{
Dictionary *spare = head;
int c=1; //count first node in dictionary(the linked list)
while (spare != NULL)
{
c++; //add one for each node to count them
spare = spare->point;
}
return c; //return number of nodes(oength of string after comprssion)
}
int main()
{
int choice;
bool state= true;
char string [SIZE]="";
printf("\n\n\n Welcome!\n");
while(state){
printf("\n\n----------LZW encoding procesor--------\n");
printf("\n\nTo encode your string enter:1\n");
printf("To print Corresponding Table enter:2\n");
printf("To find Threshold enter:3\n");
printf("To delete string enter:4\n");
printf("to exit enter:0\n");
printf("NOTE: To encode a new string, previouse string should be deleted, Thank You!\n");
printf("================================\n\n");
printf("enter your choice:\t");
scanf("%d",&choice);
char comp[SIZE]="";
switch(choice)
{
case 1:{
printf("\nenter your string to encode:");
scanf("%s",string);
Encoding(string, comp);
printf("Compressed Message is: %s", comp);
break;
}
case 2:{
print();
break;
}
case 3:{
float before=strlen(string);
float after=countAfter(head);
float AB = ((after*12)/(before*8));
float Threshold = AB*100;
printf("\nThreshold= %.2f %% \n",Threshold);
float change= 100- Threshold;
if(change<0)
{
change=-change;
printf("Size increased by %.2f %%",change);
}
else
{
printf("Size decreased by %.2f %%",change);
}
break;
}
case 4:{
freeDictionary(&head);
printf("\nstring has been deleted, you can now add a new one!");
break;
}
case 0:{
printf("\nThanks for using LZW encoding procesor \n");
state = false;
break;
}
default:{
printf("wrong choice!!\n please try again!");
}
}}
free(head);
return 0;
}
in the main function I tried to scan by writing ((scanf("%[^\n]%*c",stirng);) but it printed (Compressed Message is: <0>) without even writing any string, while when it is (scanf("%s",string);) it print the compressed message right but cannot accept the space in the string And another question, If string after comression is a string like(<23><65><765>) I mean not a string characters, how can I count the numbers to return 3 for example here
I believe I have seen this problem submitted before, but there were missing bits of code to really work on any type of possible solution. Trying out this code and also noting the good comments, following are some areas in your code that might get refactored to either provide you with the desired outcome or get you closer.
First off, as noted in the good comments, you might utilize the "fgets" function in lieu of the "scanf" function if the entered string will contain spaces. So instead of this block of code.
case 1:{
printf("\nenter your string to encode:");
scanf("%s",string);
Encoding(string, comp);
printf("Compressed Message is: %s", comp);
break;
}
The following refactored code would allow for a clause or sentence.
case 1:
{
printf("\nEnter your string to encode:");
//scanf("%s",string);
fgets(string, (SIZE - 1), stdin);
for (int i = 0; i < strlen(string); i++)
{
if (string[i] == '\n')
{
string[i] = '\0';
break;
}
}
Encoding(string, comp);
printf("Compressed Message is: %s", comp);
break;
}
Following was a simple test of this refinement with the entry of two similar words.
NOTE: To encode a new string, previouse string should be deleted, Thank You!
================================
enter your choice: Mello Yello
Enter your string to encode:Compressed Message is: <77><101><108><108><111><32><89><257><259>
----------LZW encoding procesor--------
To encode your string enter:1
To print Corresponding Table enter:2
To find Threshold enter:3
To delete string enter:4
to exit enter:0
NOTE: To encode a new string, previouse string should be deleted, Thank You!
================================
enter your choice: 0
Thanks for using LZW encoding procesor
Also, if the space character is to be ignored, one might refine the dictionary test as such, adding in a test with a subsequent "continue" statement.
for(int i=1; string[i] != '\0'; i++) //loop until the end of the string
{
if (string[i] == ' ') /* If the space character is to be ignored */
continue;
Char[0]=string[i]; //char (one character) is the next character in the string
Adding that results in a slightly more compact output.
NOTE: To encode a new string, previouse string should be deleted, Thank You!
================================
enter your choice: Mello Yello
Enter your string to encode:Compressed Message is: <77><101><108><108><111><89><257><259>
----------LZW encoding procesor--------
To encode your string enter:1
To print Corresponding Table enter:2
To find Threshold enter:3
To delete string enter:4
to exit enter:0
NOTE: To encode a new string, previouse string should be deleted, Thank You!
================================
enter your choice: 0
Thanks for using LZW encoding procesor
Note that the code for the space ("32") is not included in this variation.
Analyze that to see if it gets you closer to your goal. Also, you might want to delve into some additional "C" tutorials as it pertains to the usage of "fgets" and the usage of "continue" in loops.