Help

[Jigglychu]

this is my linked list program, when i try to use the sort function, i either get an error or it freezes (i think its an endless loop). Please help me!

// File lnklst.cpp
// This program builds and prints a linked list of integers.

#include <iostream.h>
#include "apqueue.h"

struct node
{
int data;
node *next;
};

apqueue <int> listrev;

void menu (node *);
void quit (void);
bool isEmpty(node *);
void initlist(node * &);
void createlist(node * &, apqueue <int> &);
void printlist(node *);
void insertAtFront(node * &, int);
void newinsert(node * &, apqueue <int> &);
void createNode(node * &, int);
void searchlist(node *);
void listlength(node *);
void del(node *);
node *find_previous(int, node *);
void displaylist(node *, apqueue <int>);
void sort (node * &);

int main(void)
{
node * head;
menu(head);

return 0;
}

void menu (node * head)
{
char choice;

cout << "Welcome to the uber-list program. Type:\n";
cout << "\t(C)reate a list\n";
cout << "\t(D)isplay the list\n";
cout << "\t(L)Print the length of the list\n";
cout << "\t(S)earch for an element in the list\n";
cout << "\t(X)Delete an item in the list\n";
cout << "\t(P)rint the list\n";
cout << "\t(Q)uit the Program\n";
cout << "\t(I)nsert a node at the front of the list\n";
cout << "\t(O)Sort the list\n";
cout << "\nPlease enter your selection:\t";
cin >> choice;

switch(choice)
{
case 'C': case 'c':
initlist(head);
createlist(head, listrev);
break;
case 'D': case 'd':
displaylist(head, listrev);
break;
case 'L': case 'l':
listlength(head);
break;
case 'S': case 's':
searchlist(head);
break;
case 'X': case 'x':
del(head);
break;
case 'P': case 'p':
printlist(head);
break;
case 'Q': case 'q':
quit();
break;
case 'I': case 'i':
newinsert(head, listrev);
break;
case 'O': case 'o':
sort(head);
break;
}
}
void initlist(node * & p)
//pre: pointer to list is declared
//post: pointer to list points to NULL
{
p = NULL;
}

void createlist(node * & p, apqueue <int> & listrev)
//pre: pointer to list has been initialized
//post: list has been created (length >= 0)
{
int number = 0;

cout << "Building list: \n\n";
while (number != -9999)
{

cout << "Enter an integer (-9999 to quit): ";
cin >> number;
if (number != -9999)
{
insertAtFront(p,number);
listrev.enqueue(number);
}
}//end while

menu(p);
}

void printlist(node * p)
//pre: list exists
//post: list is printed in reverse ordered of entry
{
int counter = 0;
node * temp = p;
cout << "\nPrint the list:\n\n";
while (temp != NULL)
{
counter++;
cout << "data item " << counter << " = " << temp -> data << endl;
temp = temp -> next;
}
menu(p);
}

void newinsert(node * & p, apqueue <int> & listrev)
//pre: head of list initialized
//post: item inserted at front of list
{
int item;

cout << "\nWhat would you like to enter at the front of the list?:\t";
cin >> item;
cout << endl;
node * temp;
if (isEmpty(p))
createNode(p,item);
else
{
createNode(temp,item);
temp -> next = p;
p = temp;
listrev.enqueue(item);
}
menu(p);
}

void insertAtFront(node * & p, int item)
//pre: head of list initialized
//post: item inserted at front of list
{

node * temp;
if (isEmpty(p))
createNode(p,item);
else
{
createNode(temp,item);
temp -> next = p;
p = temp;
}
}

void createNode(node * & p, int item)
//pre: pointer to node declared
//post: node created
{
p = new node;
p -> data = item;
p -> next = NULL;
}


bool isEmpty(node * p)
//pre: pointer to list declared
//post: list is determined to be empty or not
{
if (p == NULL)
return true;
else
return false;
}

void searchlist(node *p)
{
node * temp = p;
int found = 0, pos = 1;

int search;
cout << "\nWhat would you like to search for?";
cin >> search;
cout << "\nSearching...\n";
while (temp != NULL)
{

if (temp->data == search)
{
cout << "\n" << search << " was found in the list at position " << pos << ".\n\n";
found = 1;
menu(p);

}
else
{
temp = temp->next;
pos++;
}
}
if (found == 0)
{
cout << "\nThe item was not found.\n\n";
}

delete temp;
menu (p);


}

void listlength (node *p)
{
int counter = 0;
node * temp = p;
while (temp != NULL)
{
counter++;
temp = temp -> next;
}
cout << "There were " << counter << " items in the list." << endl;
menu(p);
}

void quit (void)
{

}

void displaylist (node * p, apqueue <int> listrev)
{
int output, count = 1;

while (!listrev.isEmpty())
{
listrev.dequeue(output);
cout << "Data Item " << count << ":\t" << output << endl;
count++;
}
menu(p);
}

node * find_previous(int i, node * p)
{
node *previous = NULL;
node *x;

for (x = p; x != NULL; x = x->next)
{
if (x->data == i)
return previous;
previous = x;
}

return NULL;
}

void del(node * p)
{
int i;

cout << "Which position would you like to delete?:\n";
cin >> i;

node *deleted = NULL;
node *previous = find_previous(i, p);

if (previous != NULL)
{
deleted = previous->next;
previous->next = previous->next->next;

}
else if (p != NULL && p->data == i)
{
deleted = p;
p = p->next;
}
if (deleted != NULL)
delete deleted;

menu(p);
}

void sort (node * & p)
{
int switchtemp, switchtemp2;
int headtemp;
bool exchanges;

do
{
exchanges = false;
while (p != NULL)
{
if (p->data < p->next->data)
{
switchtemp = p->data;
switchtemp2 = p->next->data;
p->data = switchtemp2;
p -> next->data = switchtemp;
exchanges = true;
sort(p->next);
}
}
}
while (exchanges = true);

menu(p);
}

[Bob Davis]

I see a couple problems.


void sort (node * & p)
{
int switchtemp, switchtemp2;
int headtemp;
bool exchanges;

do
{
exchanges = false;
while (p != NULL)
{
if (p->data < p->next->data)
{
switchtemp = p->data;
switchtemp2 = p->next->data;
p->data = switchtemp2;
p -> next->data = switchtemp;
exchanges = true;
sort(p->next);
}
}
}
while (exchanges = true);

menu(p);
}


First of all, a recursive sort function is probably not what you're looking for. Linked lists don't lend themselves to this type of algorithm. Recursion is used more in "divide and conquer" type applications, such as traversing a tree. In this case, I think this may be part of your problem; you're performing a bubble sort that recursively traverses your list, which doesn't sound valid to me. Instead of sort(p->next), why not use p = p->next and let the while loop take you through the list?

Secondly, you do have an infinite loop. It occurs because of this line.


while (exchanges = true);


Note the single equals sign. This statement assigns the value true to the boolean variable "exchanges," which returns a value of true to the loop test. Therefore, this line is functionally equivalent to


while (true)


, which is an infinite loop. Change this to the double equals (==) comparison operator, and it should fix that problem.

Thirdly, what you're doing isn't necessary at all. I'm thinking that you may be writing this linked list program for a school assignment, which wouldn't be your fault. If you're writing it for another reason, there's no need to! Judging by the fact that you're using apqueue <int>, I can tell you're using C++, with the STL available to you. Use it! std::list is already written by programmers who (no offense intended) have much more experience than you or I, and it is guaranteed to work, without any risk of a stray pointer issue or something like that on your part. No need to reinvent the wheel.

If you are writing this for school, this program begs to be wrapped into a class. Your code as you have it organized is procedural, C-style code. Object-oriented programming (C++-style) recommends that you wrap all of this commonly bound code together into a list object, instead of having all of those free functions laying around. C and C++ have distinctly different styles, and this is one of those cases.

Lastly, do not include <iostream.h>. Include <iostream>. The old headers are deprecated. If necessary, after including the <iostream> header, do a "using namespace std" to bring in the std:: namespace for you to use so you don't have to fully qualify class names, such as std::list, std::vector, or others.

[Jigglychu]

thank you very much for your excellent assistance :) This is a school assignment, and yes i agree that it would be much better off in a class (everything i searched for sorting a linked list on the web always used classes :) ) unfortunately, i don't think our teacher is very good.. he makes us use the old headers, and doesn't advocate the use of classes. All the example code he gives us almost always non object oriented. I'm going to hang out here more to learn about this :) Just for curiosity's sake, what's the difference between <iostream> and <iostream.h> ?

Also, what are STL and STD?

[Bob Davis]

I'm sorry to hear that your instructor is teaching it that way. The way he's teaching it, it's better off being a C class, not C++. I'm guessing he's had a good deal of experience in C in the past and is resistant to change; there's a lot of those out there.

As far as the differences between <iostream.h> and <iostream>, I'm not 100% sure. I know that in <iostream>, the standard input and output (cout/cin/cerr) are brought into the std:: namespace. I'm not sure if there are other differences or not. Graham or one of the Pauls would know, I'm sure.

It's a shame that your professor hasn't mentioned the STL either. The STL is the Standard Template Library. Basically, your implementation of C++ should include this set of classes, which consists of containers and algorithms that you can use on any object. For instance, in many cases, you can replace your use of an array with a std::vector. This is a dynamic array that automatically grows in size as you push items into it. Other commonly used classes in the STL are std::string and std::list, and a commonly used function is std::sort. Since all of these are template based, they are extensible to whatever datatype you're working with. I searched Google for some STL resources, so here's some places you may want to start to get some info:

http://www.cs.rpi.edu/projects/STL/htdocs/stl.html

http://www.msoe.edu/eecs/ce/courseinfo/stl/

http://directory.google.com/Top/Computers/Programming/Languages/C%2B%2B/Class_Libraries/STL/Tutorials/?il=1



As always, these are good places to start, but if you want good understanding, you're probably best off buying a book at some point. I don't own it, but I've heard that Scott Meyers' book, Effective STL, is an excellent title.

As for STD, I don't think I should be the one to explain those to you. :)http://www.codeproject.com/vcpp/stl/stlintroduction.asp

[Graham]

The most important difference between <iostream.h> and <iostream> is that <iostream> is in the Standard, and <iostream.h> is deprecated (i.e. the ISO committee have explicitly stated do not use it). Beyond that, apart from the std namespace, there are a few implementation differences between the two. To the OP: you really ought to tell your teacher that he is lying to you - he is feeding you false information that could seriously compromise your employability in the future. This sort of thing is a total abrogation of responsibility on his part and he should be severly reprimanded for his actions.

Regarding Effective STL: it is an excellent book and everyone should have access to a copy: [b]but[/i] it won't teach you STL - you'll need a good knowledge of that first before the book will be of any real benefit. Try Josuttis or Audern for reference material.

[Jigglychu]

once again, thank you for the excellent input graham and bob :) don't make the mistake of calling my teacher a professor its just an ap course in high school and i dont think hes qualified ;) I don't know if hes just following the conventions of the ap course or just a bad teacher (probably the latter)

Originally posted by Bob Davis
As for STD, I don't think I should be the one to explain those to you. :)


hehe nice there ;P

lol i find it funny that he could be compromising our employability