Originally Posted by
jsrig88
You said your grasp of linked lists, binary trees, and recursion is a little weaker. You might try coming up with your own projects that center around creating different sorts of ADTs; in college students are generally given a course that involves those sorts of programming assignments. For your first project, do something that involves making a class of a dynamically-sized linked list of another class. Then do the same for a stack. Then a queue. Then a binary tree. Then other ADTs, if you like.
This will really solidify in your mind a lot of the big differences between Java and C++. Java has these sorts of structures in libraries, as does C++, but making your own in C++ can be a very different ball game than it is in Java, due to how detailed C++ is.
Also if you don't already know what the Towers of Hanoi is, look that up. Then make a program that will automatically solve it with a user-specified number of disks (don't go much more than 10). This will probably really help you with recursion, as well as help you with stacks (which this should have three of).
Ok first project done. A linked list that uses recursion to add nodes, print them and search the list for specific values. I learned a lot doing it and can feel a few of the concepts really solidifying in my mind. I even had fun doing it. Guess I'm one of those people who enjoy programming. Tell me where there's room for improvement, I can take and even like constructive criticism, so don't hold back. Well here it is... Damn, I hope I'm doing this code tag thing right...
Code:
//Basic linked list using loops, structures, pointers and recursion.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// my global variables
struct listNode{
int contents;
int index;
listNode *next;
};
void buildList(int i);
void printList();
int searchList(int i);
listNode *root;
listNode *cNode;
int counter;
int main()
{
//initailizing my random number generator to the system clock... At least I think that's what it
//does... 60 to 75 percent sure.
srand((unsigned)time(0));
//variables local to the main method. The root node and its values, the current node, an int I used for my while
//loop, and a counter for the number of elements in my list.
root = new listNode;
root->contents=rand();
root->index=1;
root->next=0;
cNode = root;
int i = 0;
counter=2;
//while loop that uses my buildList() method to fill my linked list with 100 random numbers.
while (i<100)
{
buildList(rand());
i++;
}
//resets the current node pointer to root, so my printList() method can use it to print out the full
//list.
cNode = root;
printList();
//again resets the current node pointer to root, this time for my searchList() method. Then asks the
//user to enter a number between 1 and 100, which is then passed into searchlist. This will tell you what
//random number is at what index number in the apropriate listNode object.
cNode=root;
cout<< "Please enter a number between 1 and 100.\n";
cin>>i;
cout<<"The number "<<searchList(i)<<" is found at index "<<i<<". \n";
return 0;
}
//My list building method. Uses recursion to find the next NULL node on the list and add the number passed into
//it. Also adds the counter number to index, and increments counter by 1.
void buildList(int i)
{
if (cNode->next == 0)
{
cNode->next=new listNode;
cNode=cNode->next;
cNode->index = counter;
cNode->contents = i;
counter++;
}
else
{
cNode=cNode->next;
buildList(i);
}
}
//my Printlist method runs through the whole linked list using recursion, printing out the index number and the contents
//separated by a full stop. Then it starts a new line for the next node and continues until the whole Linked list is printed.
void printList()
{
if (cNode->next != 0)
{
cout<<cNode->index<<". "<<cNode->contents<<" \n";
cNode=cNode->next;
printList();
}
else
return;
}
//this final method takes in a index number entered by the user, finds the listNode object with said number, and returns
//its contents.
int searchList(int i)
{
if(i != cNode->index)
{
cNode=cNode->next;
searchList(i);
}
return cNode->contents;
}
I just noticed that when the print method reaches index number 75 it prints 0.0. Can't fiugure that one out, could you help please? =)