Author : Alexander Allain
Page : << Previous 8 Next >>
node root points to has its next pointer
//set equal to NULL
root->x=5; //By using the -> operator, you can modify the node
return 0; //a struct (root in this case) points to.
}
This so far is not very useful for doing anything. It is necessary to understand how to traverse (go through) the linked list before going further.
Think back to the train. Lets imagine a conductor who can only enter the train through the engine, and can walk through the train down the line as long as the connector connects to another car. This is how the program will traverse the linked list. The conductor will be a pointer to node, and it will first point to root, and then, if the root's pointer to the next node is pointing to something, the "conductor" (not a technical term) will be set to point to the next node. In this fashion, the list can be traversed. Now, as long as there is a pointer to something, the traversal will continue. Once it reaches a NULL pointer, meaning there are no more nodes (train cars) then it will be at the end of the list, and a new node can subsequently be added if so desired.
Here's what that looks like:
struct node
{
int x;
node *next;
};
int main()
{
node *root; //This won't change, or we would lose the list in memory
node *conductor; //This will point to each node as it traverses
//the list
root=new node; //Sets it to actually point to something
root->next=NULL; //Otherwise it would not work well
root->x=12;
conductor=root; //The conductor points to the first node
if(conductor!=NULL)
{
while(conductor->next!=NULL)
{
conductor=conductor->next;
}
}
conductor->next=new node; //Creates a node at the end of the list
conductor=conductor->next; //Points to that node
conductor->next=NULL; //Prevents it from going any further
conductor->x=42;
}
That is the basic code for traversing a list. The if statement ensures that there is something to begin with (a first node). In the example it will always be so, but if it was changed, it might not be true. If the if statement is true, then it is okay to try and access the node pointed to by conductor. The while loop will continue as long as there is another pointer in the next. The conductor simply moves along. It changes what it points to by getting the address of conductor->next.
Finally, the code at the end can be used to add a new node to the end. Once the while loop as finished, the conductor will point to the last node in the array. (Remember the conductor of the train will move on until there is nothing to move on to? It works the same way in the while loop.) Therefore, conductor->next is set to null, so it is okay to allocate a new area of memory for it to point to. Then the conductor traverses one more element(like a train conductor moving on the the newly added car) and makes sure that it has its pointer to next set to NULL so that the list has an end. The NULL functions like a period, it means there is no more beyond. Finally, the new node has its x value set. (It can be set through user input. I simply wrote in the '=42' as an example.)
To print a linked list, the traversal function is almost the same. It is necessary to ensure that the last element is printed after the while loop terminates.
For example:
conductor=root;
if(conductor!=NULL) //Makes sure there is a place to start
{
while(conductor->next!=NULL)
{
cout<<conductor->x;
conductor=conductor->next;
}
cout<<conductor->x;
}
The final output is necessary because the while loop will not run once it reaches the last node, but it will still be necessary to output the contents of the next node. Consequently, the last output deals with this.
Recursion is defined as a function calling itself. It is in some ways similar to a loop because it repeats the same code, but it requires passing in the looping variable and being more careful. Many programming languages allow it because it can simplify some tasks, an it is often more elegant than a loop.
A simple example of recursion would be:
void recurse()
{
recurse(); //Function calls itself
}
int main()
{
recurse(); //Sets off the recursion
return 0; //Rather pitiful, it will never be reached
}
This program will not continue forever, however. The computer keeps function calls on a stack and once too many are called without ending, the program will terminate. Why not write a program to see how many times the function is called before the program terminates?
#include <iostream.h>
void recurse(int count) //The count variable is initalized by each function call
{
cout<<count;
recurse(count+1); //It is not necessary to increment count
//each function's variables
} //are separate (so each count will be initialized one greater)
int main()
{
recurse(1); //First function call, so it starts at one
return 0;
}
This simple program will show the number of times the recurse function has been called by initializing each individual function call's count variable one greater than it was previous by passing in count+1. Keep in mind, it is not a function restarting itself, it is hundreds of functions that are each unfinished with the last one calling a new recurse function.
It can be thought of like those little chinese dolls that always have a smaller doll inside. Each doll calls another doll, and you can think of the size being a counter variable that is being decremented by one.
Think of a really tiny doll, the size of a few atoms. You can't get any smaller than that, so there are no more dolls. Normally, a recursive function will have a variable that performs a similar action; one that controls when the function will finally exit. The condition where the functin will not call itself is termed the base case of the function. Basically, it is an if-statement that checks some variable for a condition (such as a number being less than zero, or greater than some other number) and if that condition is true, it will not allow the function to call itself again. (Or, it could check if a certain condition is true and only then allow the function to call itself).
A quick example:
void doll(int size)
{
if(size==0)//No doll can be smaller than 1 atom (10^0==1) so doesn't call itself
return; //Return does not have to return something, it can be used
//to exit a function
doll(size-1); //Decrements the size variable so the next doll will be smaller.
}
int main()
{
doll(10); //Starts off with a large doll (its a logarithmic scale)
return 0; //Finally, it will be used
}
This program ends when size equals one. This is a good base case, but if it is not properly set up, it is possible to have an base case that is always true (or always false).
Once a function has called itself, it will be ready to go to the next line after the call. It can still perform operations. One function you could write could print out the numbers 123456789987654321. How can you use recursion to write a function to do this? Simply have it keep incrementing a variable passed in, and then output the variable...twice, once before the function recurses, and once after...
void printnum(int begin)
{
cout<<begin;
if(begin<9) //The base case is when begin is greater than 9
printnum(begin+1); //for it will not recurse after the if-statement
cout<<begin; //Outputs the second begin, after the program has
//gone through and output
} //the numbers from begin to 9.
This function works because it will go through and print the numbers begin to 9, and then as each printnum function terminates it will continue printing the value of begin in each function from 9 to begin.
This is just the beginning of the usefulness of recursion. Heres a little challenge, use recursion to write a program that returns the factorial of any number greater than 0. (Factorial is number*number-1*number-2...*1).
Hint: Recursively find the factorial of the smaller numbers first, ie, it takes a number, finds the factorial of the previous number, and multiplies the number times that factorial...have fun, email me at webmaster@cprogramming.com if you get it.
Perhaps you would like to have a function that will accept any number of values and then return the average. You don't know how many arguments will be passed in to
Page : << Previous 8 Next >>