sorted linked-list
I have an assignment for class to write a sorted linked-list. The way our teacher wants it done is for the list to be deleted everytime a new number is added and a new sorted list to come out. This is what I have right now but I can't get it to save the list because Im putting the clearList() function in the wrong spot.
#include<iostream>
using namespace std;
struct Node{
int num;
Node * next;
};
typedef struct Node N;
typedef struct Node * nptr;
void addNode(nptr);
void clearList();
int isEmpty(nptr);
void selection(int );
void DisplayList(nptr);
void addNumber();
void sort();
nptr pHead = NULL;
int count = 0;
main()
{
int choice;
cout << "1. Add number to list"<< endl;
cout << "2. Display list"<< endl;
cout << "3. Clear List" << endl;
cout << "4. Exit" << endl;
cout << "Make a selection: ";
cin >> choice;
selection(choice);
return 0;
}
///////////////////////////
void clearList()
{
nptr temp;
while(!isEmpty(pHead))
{
temp = pHead;
pHead = pHead->next;
delete temp;
}
system("pause");
system("cls");
main();
}
///////////////////////////
void addNumber()
{
nptr y;
y = new N;
cout << "Enter a number: ";
cin >> y->num;
y->next = NULL;
addNode(y);
sort();
y = pHead;
system("pause");
system("cls");
main();
}
////////////////////////////////
void selection(int a)
{
switch(a)
{
case 1: addNumber();
break;
case 2: DisplayList(pHead);
break;
case 3: clearList();
break;
}
}
////////////////////////////////
int isEmpty(nptr n)
{
return n == NULL;
}
/////////////////////////////////
void addNode(nptr newNode)
{
nptr temp;
if(isEmpty(pHead))
{
pHead = newNode;
}
else
{
temp = pHead;
while(!isEmpty(temp->next))
{
temp = temp->next;
}
temp->next = newNode;
}
}
///////////////////////////////
void DisplayList(nptr n)
{
nptr temp;
temp = n;
while(!isEmpty(temp))
{
cout << temp->num << endl;
temp = temp ->next;
}
system("pause");
system("cls");
main();
}
//////////////////////////////
void sort()
{
count++;
nptr tmp;
tmp = pHead;
int * f = NULL;
f = new int[count];
for(int i = 0; i<count; i++)
{
for(int m = 0; m< count; m++)
{
int j;
j = tmp->num;
f[m] = j;
if(f[i] > f[m])
{
int t = f[i];
f[i] = f[m];
f[m] = t;
}
tmp = tmp->next;
}
}
clearList();
delete f;
}
[3042 byte] By [
lmpb17] at [2007-11-20 11:18:44]

# 1 Re: sorted linked-list
Your program should never call main().
A called function will return to its caller automatically. Don't call the calling function from inside a function you called. You'll end up with uncontrolled recursion and eventually crash. If you need to call a function repeatedly, set up a loop in the calling function.
As to your problem, that seems like a very odd requirement. Are you sure you understand the prof correctly?
GCDEF at 2007-11-9 1:25:18 >

# 2 Re: sorted linked-list
The way our teacher wants it done is for the list to be deleted everytime a new number is added and a new sorted list to come out.Then your list would never have more than one element, so it would always be sorted (and would be not very recognizable as a list...)
# 3 Re: sorted linked-list
Yea i did misunderstand. Anyway he just wanted a basic sorted list.
I fixed it up but Im still having a problem with storing the numbers (addNode function)
#include<iostream>
using namespace std;
struct Node{
int num;
Node * next;
};
typedef struct Node N;
typedef struct Node * nptr;
void addNode(nptr, int);
void clearList();
int isEmpty(nptr);
void selection();
void DisplayList(nptr);
void addNumber();
nptr pHead = NULL;
main()
{
selection();
return 0;
}
///////////////////////////
void clearList()
{
nptr temp;
while(!isEmpty(pHead))
{
temp = pHead;
pHead = pHead->next;
delete temp;
}
system("pause");
system("cls");
selection();
}
///////////////////////////
void addNumber()
{
nptr y;
y = new N;
cout << "Enter a number: ";
cin >> y->num;
y->next = NULL;
addNode(pHead, y->num);
y = pHead;
system("pause");
system("cls");
selection();
}
////////////////////////////////
void selection()
{
int choice;
cout << "1. Add number to list"<< endl;
cout << "2. Display list"<< endl;
cout << "3. Clear List" << endl;
cout << "4. Exit" << endl;
cout << "Make a selection: ";
cin >> choice;
switch(choice)
{
case 1: addNumber();
break;
case 2: DisplayList(pHead);
break;
case 3: clearList();
break;
}
}
////////////////////////////////
int isEmpty(nptr n)
{
return n == NULL;
}
/////////////////////////////////
void addNode(nptr newNode, int number)
{
nptr current, previous, newPtr;
newPtr = new Node;
if(newPtr != NULL)
{
newPtr->num = number;
newPtr->next = NULL;
previous = NULL;
current = newNode;
while(current != NULL && number > current->num)
{
previous = current;
current = current->next;
}
if( previous == NULL)
{
newPtr->next = newNode;
newNode = newPtr;
}
else
{
previous->next = newPtr;
newPtr->next = current;
}
}
}
///////////////////////////////
void DisplayList(nptr n)
{
if( n == NULL)
cout << "List is empty." << endl;
else
cout << "The list is: \n: ";
while(n != NULL)
{
cout << n->num;
n = n->next;
}
system("pause");
system("cls");
selection();
}
//////////////////////////////
# 4 Re: sorted linked-list
I fixed it up but Im still having a problem with storing the numbers (addNode function)
1) main returns int.
int main()
2) The clearlist() should only do what it is stated, and that is clearing the list. It shouldn't be redisplaying stuff on the screen or anything like that. It should only be this:
void clearList()
{
nptr temp;
while(!isEmpty(pHead))
{
temp = pHead;
pHead = pHead->next;
delete temp;
}
}
What if you want to use this code in a program that has no screen I/O? In general, leave the screen and file I/O out of the internals of classes such as linked lists. Let the functions that are using the linked list to be responsible for any I/O.
3) What data did you use? What exactly is the problem?
Regards,
Paul McKenzie
# 5 Re: sorted linked-list
Another problem:
Why is your "addNumber" function so complicated? It shouldn't be doing anything except giving a number to the linked list, and the linked list should be responsible for creating the node for the number and adding the node to the list.
Imagine if you had to give this linked list class for someone to use. Why would the user of your linked list class have to do so much to add a number to it?
As it stands now, your addNumber function also has a memory leak:
void addNumber()
{
nptr y;
y = new N; // where/when is this deleted?
Rewrite the addNumber function to just ask the user for the number, and send the number to the linked list addNode() function to add. That is all that addNumber should be doing.
Regards,
Paul McKenzie
# 6 Re: sorted linked-list
The structure of your code is still "wrong", because you have an unecessary recursion in there: Imagine the user will enter 200 numbers, then you have selection() calling addNumber() calling selection() calling addNumber() calling ... At some point you will get a stack overflow for that.
Suggestion: Have your selection() function return the selection (change return type from void to int) and put your switch statement inside a while loop in your main(). Your main function should look something like:int main()
{
while ((int choice = selection()) != 4)
{
switch(choice)
{
case 1: addNumber();
break;
case 2: DisplayList(pHead);
break;
case 3: clearList();
break;
}
}
clearList(); // be a good boy and free all memory before exiting
}
# 7 Re: sorted linked-list
The structure of your code is still "wrong", because you have an unecessary recursion in there: Imagine the user will enter 200 numbers, then you have selection() calling addNumber() calling selection() calling addNumber() calling ... At some point you will get a stack overflow for that.
Suggestion: Have your selection() function return the selection (change return type from void to int) and put your switch statement inside a while loop in your main(). Your main function should look something like:
I already mentioned that above. Frustrating when advice gets ignored.
The other thing is it's bad design. The list class shouldn't know anything about selection or the program that's using it. I think Paul mentioned that already too.
GCDEF at 2007-11-9 1:31:35 >
