- Forum
- General C++ Programming
- PROCESSING A LINKED LIST RECURSIVELY
PROCESSING A LINKED LIST RECURSIVELY
C++ Project 4
DESCRIPTION
Design, implement, test, and document a C++ program that reads an input file of text and builds a concordance of the words in the file. The program will also report the number of distinct words in the file.
A class will contain the implementation of a concordance type as a linked list; each node of a list/concordance will contain a word and a count of the word's appearances in the input text, and these entries will be ordered alphabetically by their words.
Words may be any length in the input file, but the program should consider only their first eight characters. Thus, "manipulated" and "manipulation" are two instances of the word "manipula."
This is my code:
/**concordance.h*/
#include "stdafx.h"
#include<string>
using namespace std;
const int MAX = 8;
//Concordance list
class Concordance
{
public:
typedef char Word[MAX+1];
struct Node
{
Word wd;
int count;
Node *next;
};
Node *first;
Concordance();
void insert(Word);
int length();
int get_count(Word);
private:
Node* getnode(Word s,int c ,struct Node* st);
};
/**concordance.cpp**/
#include "stdafx.h"
#include "concordance.h"
#include <iostream>
#include <cstring>
using namespace std;
Concordance::Concordance()
{
}
Concordance::Node * Concordance::getnode(Concordance::Word s,int c,Concordance::Node * nextPtr)
{
Concordance::Node * newNode= new Node;
newNode->count=c;
newNode->next=nextPtr;
strcpy(newNode->wd,s);
return newNode;
}
//returns the frequncy of a word in the list
int Concordance::get_count(Word str)
{
Node * newNode,*temp,*prev;
if(first ==NULL)
return 0;
else
{
temp=first;
while(temp!=NULL)
{
if(strcmp(temp->wd,str)==0)
return temp->count;
temp=temp->next;
}
}
return 0;
}
//prints the words in the concordance
//and returns the length of the list(number of words in the concordance)
int Concordance::length()
{
int l=0;
Node * newNode,*temp,*prev;
cout<<"word"<<"\t"<<"Count"<<endl;
cout<<"--------------------"<<endl;
if(first ==NULL)
return 0;
else
{
temp=first;
while(temp!=NULL)
{
//print the word
cout<<temp->wd<<"\t"<<temp->count<<endl;
temp=temp->next;
l++;
}
cout<<"--------------------"<<endl;
return l;
}
}
//inserts the given word into the concordance
//according to lexicographic order, if the word is
//not already in the concordance.
//otherwise, increases the count of the word in the concordance
void Concordance::insert(Word w)
{
Node * newNode,*temp,*prev;
//if there are no words in the list
if(first==NULL)
{
first=getnode(w,1,NULL);
}
//if the list is not empty
else
{
prev=temp=first;
//loop until find a suitable position for new word or the word
//is matched with existing word
while(strcmp(temp->wd,w)<=0 && temp->next!=NULL)
{
prev=temp;
if(strcmp(temp->wd,w)==0)
{
temp->count=temp->count+1;
return;
}
temp=temp->next;
}
//inserting possibilities
if( temp==first && strcmp(temp->wd,w)>0 )
{
newNode=getnode(w,1,first);
first=newNode;
}
else if( temp==first && strcmp(temp->wd,w)<0 )
{
newNode=getnode(w,1,NULL);
first->next=newNode;
}
else
{
if(temp->next==NULL)
{
if(strcmp(temp->wd,w)<0 )
{
newNode=getnode(w,1,NULL);
temp->next=newNode;
}
else
{
newNode=getnode(w,1,temp);
prev->next=newNode;
}
}
else
{
newNode=getnode(w,1,temp);
prev->next=newNode;
}
}
}
}
/**main.cpp**/
#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>
#include <cstring>
#include "concordance.h"
using namespace std;
void read_word();
fstream ifs;
Concordance c;
//main
int main()
{
ifs.open("input.txt");
read_word();
cout<<"The file contains "<<c.length()<<" distinct words."<<endl;
cout<<"Count of SMALL : "<<c.get_count("SMALL")<<endl;
system("pause");
return 0;
}
//reads the file character by character to make a word.
//and inserts the word into list, by calling the insert()
void read_word()
{
char ch;
char w[9];
int i=0;
while(ifs.get(ch))
{
ch=toupper(ch);
//enter , only if the character is alphabet
if(ch>=65 && ch<=90)
{
//saves only up to 8 characters
if(i<8)
w[i]=ch;
i++;
}
else
{
if(i>=8)
w[8]='\0';
else
w[i]='\0';
//insert the word
if(i!=0)
c.insert(w);
//clear the temparary variable w
w[0]=w[1]=w[2]=w[3]=w[4]=w[5]=w[6]=w[7]=w[8]=' ';
i=0;
}
}
return;
}
This program works.
Now, C++ Project 5
INTRODUCTION
As we saw in Project 4, a concordance of a text is an alphabetical listing of the words that appear in the text with the number of times each word appears. Concordances summarize the frequencies of words in texts and are used in statistical analyses of authors' works, to determine authorship of disputed works, and to see how an author's writing changes over time.
DESCRIPTION
Modify the Concordance class in the earlier project to perform as many operations as possible recursively. For this project, the necessary operations are these:
-The default constructor
-The destructor
-insert(word) - Insert word into the concordance. If word is already in the concordance, increment its count.
-length() - Return the length of the invoking concordance; that is, the number of distinct words that it contains.
-Output - Overload the "<<" operator to write the invoking concordance to an output stream.
-get_node(word,count,link) - Return a pointer to a new Node that contains a word, its count, and the pointer value link.
Implement the destructor and the operations to insert a word, determine the length of the concordance, and write out the contents of a concordance recursively. Thus each of these requires two functions: a public member function that can be called by the client program and a private recursive member function, called by its public function, that does the actual work.
The problem itself---building and reporting a concordance of a text read from an input file---remains as described in Project 4, whose entire main program can be re-used here.
How can I do this?
DESCRIPTION
Design, implement, test, and document a C++ program that reads an input file of text and builds a concordance of the words in the file. The program will also report the number of distinct words in the file.
A class will contain the implementation of a concordance type as a linked list; each node of a list/concordance will contain a word and a count of the word's appearances in the input text, and these entries will be ordered alphabetically by their words.
Words may be any length in the input file, but the program should consider only their first eight characters. Thus, "manipulated" and "manipulation" are two instances of the word "manipula."
This is my code:
/**concordance.h*/
#include "stdafx.h"
#include<string>
using namespace std;
const int MAX = 8;
//Concordance list
class Concordance
{
public:
typedef char Word[MAX+1];
struct Node
{
Word wd;
int count;
Node *next;
};
Node *first;
Concordance();
void insert(Word);
int length();
int get_count(Word);
private:
Node* getnode(Word s,int c ,struct Node* st);
};
/**concordance.cpp**/
#include "stdafx.h"
#include "concordance.h"
#include <iostream>
#include <cstring>
using namespace std;
Concordance::Concordance()
{
}
Concordance::Node * Concordance::getnode(Concordance::Word s,int c,Concordance::Node * nextPtr)
{
Concordance::Node * newNode= new Node;
newNode->count=c;
newNode->next=nextPtr;
strcpy(newNode->wd,s);
return newNode;
}
//returns the frequncy of a word in the list
int Concordance::get_count(Word str)
{
Node * newNode,*temp,*prev;
if(first ==NULL)
return 0;
else
{
temp=first;
while(temp!=NULL)
{
if(strcmp(temp->wd,str)==0)
return temp->count;
temp=temp->next;
}
}
return 0;
}
//prints the words in the concordance
//and returns the length of the list(number of words in the concordance)
int Concordance::length()
{
int l=0;
Node * newNode,*temp,*prev;
cout<<"word"<<"\t"<<"Count"<<endl;
cout<<"--------------------"<<endl;
if(first ==NULL)
return 0;
else
{
temp=first;
while(temp!=NULL)
{
//print the word
cout<<temp->wd<<"\t"<<temp->count<<endl;
temp=temp->next;
l++;
}
cout<<"--------------------"<<endl;
return l;
}
}
//inserts the given word into the concordance
//according to lexicographic order, if the word is
//not already in the concordance.
//otherwise, increases the count of the word in the concordance
void Concordance::insert(Word w)
{
Node * newNode,*temp,*prev;
//if there are no words in the list
if(first==NULL)
{
first=getnode(w,1,NULL);
}
//if the list is not empty
else
{
prev=temp=first;
//loop until find a suitable position for new word or the word
//is matched with existing word
while(strcmp(temp->wd,w)<=0 && temp->next!=NULL)
{
prev=temp;
if(strcmp(temp->wd,w)==0)
{
temp->count=temp->count+1;
return;
}
temp=temp->next;
}
//inserting possibilities
if( temp==first && strcmp(temp->wd,w)>0 )
{
newNode=getnode(w,1,first);
first=newNode;
}
else if( temp==first && strcmp(temp->wd,w)<0 )
{
newNode=getnode(w,1,NULL);
first->next=newNode;
}
else
{
if(temp->next==NULL)
{
if(strcmp(temp->wd,w)<0 )
{
newNode=getnode(w,1,NULL);
temp->next=newNode;
}
else
{
newNode=getnode(w,1,temp);
prev->next=newNode;
}
}
else
{
newNode=getnode(w,1,temp);
prev->next=newNode;
}
}
}
}
/**main.cpp**/
#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>
#include <cstring>
#include "concordance.h"
using namespace std;
void read_word();
fstream ifs;
Concordance c;
//main
int main()
{
ifs.open("input.txt");
read_word();
cout<<"The file contains "<<c.length()<<" distinct words."<<endl;
cout<<"Count of SMALL : "<<c.get_count("SMALL")<<endl;
system("pause");
return 0;
}
//reads the file character by character to make a word.
//and inserts the word into list, by calling the insert()
void read_word()
{
char ch;
char w[9];
int i=0;
while(ifs.get(ch))
{
ch=toupper(ch);
//enter , only if the character is alphabet
if(ch>=65 && ch<=90)
{
//saves only up to 8 characters
if(i<8)
w[i]=ch;
i++;
}
else
{
if(i>=8)
w[8]='\0';
else
w[i]='\0';
//insert the word
if(i!=0)
c.insert(w);
//clear the temparary variable w
w[0]=w[1]=w[2]=w[3]=w[4]=w[5]=w[6]=w[7]=w[8]=' ';
i=0;
}
}
return;
}
This program works.
Now, C++ Project 5
INTRODUCTION
As we saw in Project 4, a concordance of a text is an alphabetical listing of the words that appear in the text with the number of times each word appears. Concordances summarize the frequencies of words in texts and are used in statistical analyses of authors' works, to determine authorship of disputed works, and to see how an author's writing changes over time.
DESCRIPTION
Modify the Concordance class in the earlier project to perform as many operations as possible recursively. For this project, the necessary operations are these:
-The default constructor
-The destructor
-insert(word) - Insert word into the concordance. If word is already in the concordance, increment its count.
-length() - Return the length of the invoking concordance; that is, the number of distinct words that it contains.
-Output - Overload the "<<" operator to write the invoking concordance to an output stream.
-get_node(word,count,link) - Return a pointer to a new Node that contains a word, its count, and the pointer value link.
Implement the destructor and the operations to insert a word, determine the length of the concordance, and write out the contents of a concordance recursively. Thus each of these requires two functions: a public member function that can be called by the client program and a private recursive member function, called by its public function, that does the actual work.
The problem itself---building and reporting a concordance of a text read from an input file---remains as described in Project 4, whose entire main program can be re-used here.
How can I do this?
First, please use code tags and sanitize your whitespace. See: http://www.cplusplus.com/articles/jEywvCM9/
You write code?
You do have the iterative version:
You need to replace the loop with recursive function.
You must have been told what a recursion is.
I have a pointer to node. How many nodes are there?
* If the pointer is null, then there are none
* Else there is one plus whatever follows this node
| Implement the length recursively. requires two functions: a public member function that can be called by the client program and a private recursive member function, called by its public function How can I do this? |
You write code?
You do have the iterative version:
|
|
You need to replace the loop with recursive function.
You must have been told what a recursion is.
I have a pointer to node. How many nodes are there?
* If the pointer is null, then there are none
* Else there is one plus whatever follows this node
Use a
There's something wrong with your insert() function. When I run your program on a file where the last word in the list appears multiple times, I get two entries for the word. This is actually a good excuse to rewrite insert() because it's way more complicated than necessary.
Instead of using a "prev" pointer, use a variable that points to the pointer to the current node. In other words, it either points to first, or to the next member of some node. Then insert() has two parts: (1) find the point in the list where the node is, or where it should go, then (2) either increment the counter if you found the word, or insert a new node if you didn't:
for loop to iterate over a list. It makes the code much easier to read in my opinion because it separates the "looping over the items" code from the "doing something with each item" code: |
|
There's something wrong with your insert() function. When I run your program on a file where the last word in the list appears multiple times, I get two entries for the word. This is actually a good excuse to rewrite insert() because it's way more complicated than necessary.
Instead of using a "prev" pointer, use a variable that points to the pointer to the current node. In other words, it either points to first, or to the next member of some node. Then insert() has two parts: (1) find the point in the list where the node is, or where it should go, then (2) either increment the counter if you found the word, or insert a new node if you didn't:
|
|
Topic archived. No new replies allowed.