//Sorted linked list
#include <iostream>
using namespace std;
class linklist
{
private:
struct node
{
int data;
node *link;
}*p;
public:
linklist();
void display();
void append(int);
void del(int);
int count();
}list1;
linklist::linklist()
{
p=NULL;
}
void linklist::display()
{
node *temp;
if(p==NULL)
cout<<"\nEmpty List!\n";
else
{
temp = new node[1];
temp = p;
cout<<"\nList is: ";
while(temp)
{
cout<<temp->data<<" ";
temp = temp->link;
}
}
}
void linklist::append(int num)
{
node *temp = new node;
node *r = new node;
temp = p;
r->data = num;
if(p==NULL || p->data>num)
{
p = r;
p->link = temp;
}
else
{
while(temp->link)
{
if((temp->data<=num)
&& (temp->link->data>num || temp->link==NULL))
{
r->link = temp->link;
temp->link = r;
return;
}
temp = temp->link;
}
}
}
void linklist::del(int num)
{
node *temp = new node;
node *r = new node;
temp = p;
if(p==NULL)
cout<<"Empty List. Nothing to delete...";
else if(p->data == num)//first node to be deleted
{
temp = p;
p = p->link;
delete temp;
}
else
{
while(temp->data != num)
{
r = temp;
temp = temp->link;
}
r->link = temp->link;
delete temp;
}
}
int linklist::count()
{
int count=0;
node *temp;
if(p==NULL)
return 0;
else
{
temp = new node;
temp = p;
while(temp)
{
count++;
temp = temp->link;
}
return count;
}
}
int main()
{
cout<<"\nAdding 10, 8, 34, 19, -4 to list.";
cout<<"\nDone.";
list1.append(10);
list1.append(8);
list1.append(34);
list1.append(19);
list1.append(-4);
list1.display();
cout<<'\n';
system("PAUSE");
return 0;
}
Linklist problem
Author
Hello.
I was making a program that would accept data and store it in a linked list in ascendind order.
Here's the code:
However, the list does not store numbers that should go to the last, as a sample run of the program might show:
The List is: -4 8 10
Press any key to continue...
Plz help me with it, any help is welcome.
couple observations
1) single letter variable names make your code extremely hard to follow. variable names should be meaningful to people other than yourself
2) you seem to use an excessive number of allocations. for instance, why do you allocate new memory just to display the list.
the mantra with new is "use sparingly and wherever you use it be sure to call delete".
Your problem in the append function is simmilarly an excessive number of calls to new. the only thing you should ever be new'ing in your linklist is the p variable or the link variable.
the algorithm for append is:
if p is NULL then allocate memory for p and store num in p
if p is not NULL then iterate the list to find the last node. allocate memory for the link of the last node and store your result in the new node.
again for your program to be correct, the _only_ thing you should ever new is the p variable or a link variable.
-me
1) single letter variable names make your code extremely hard to follow. variable names should be meaningful to people other than yourself
2) you seem to use an excessive number of allocations. for instance, why do you allocate new memory just to display the list.
void linklist::display(){ node *temp; if(p==NULL) cout<<"\nEmpty List!\n"; else { temp = new node[1]; //why are you allocating memory here??? this is a memory leak temp = p; cout<<"\nList is: "; while(temp) { cout<<temp->data<<" "; temp = temp->link; } }}the mantra with new is "use sparingly and wherever you use it be sure to call delete".
Your problem in the append function is simmilarly an excessive number of calls to new. the only thing you should ever be new'ing in your linklist is the p variable or the link variable.
//neither of these lines should exist.... node *temp = new node; node *r = new node;the algorithm for append is:
if p is NULL then allocate memory for p and store num in p
if p is not NULL then iterate the list to find the last node. allocate memory for the link of the last node and store your result in the new node.
again for your program to be correct, the _only_ thing you should ever new is the p variable or a link variable.
-me
This looks kinda homework-y (?), so just a couple of hints. In the append function, look carefully at the following code:
1. The conditional for the while loop is that temp->link is non-null, and yet you test it for equality to null a couple of lines later, which points to the problem (or at least part of it).
2. Even if temp->link were not guaranteed to be non-null when you reach the second conditional, you're accessing link's data before you check to see if it's valid.
3. It looks like you have some memory leaks and other errant bits of code that don't do anything (other than leak memory, that is).
4. Probably some other things that I didn't see right off.
while(temp->link) { if((temp->data<=num) && (temp->link->data>num || temp->link==NULL)) { r->link = temp->link; temp->link = r; return; } temp = temp->link; }1. The conditional for the while loop is that temp->link is non-null, and yet you test it for equality to null a couple of lines later, which points to the problem (or at least part of it).
2. Even if temp->link were not guaranteed to be non-null when you reach the second conditional, you're accessing link's data before you check to see if it's valid.
3. It looks like you have some memory leaks and other errant bits of code that don't do anything (other than leak memory, that is).
4. Probably some other things that I didn't see right off.
After only a few seconds of looking at your code, it appears to leak memory like a sieve. I think you will want to study pointers and dynamic memory allocation a lot more before you attempt to create your own linked list class. When you make such a fundamental error as this...
... you show that you don't have a firm grasp of these concepts. That first line creates a new node and has "temp" point at it. Then you leak memory when you have "temp" point at something else. You don't have to use "new" with every pointer you create. Remember, "new" and "delete" don't create/destroy pointers. They allocate/deallocate memory, and that memory is leaked if you don't have any pointers pointing to it any more.
node *temp = new node;// Two lines downtemp = p;... you show that you don't have a firm grasp of these concepts. That first line creates a new node and has "temp" point at it. Then you leak memory when you have "temp" point at something else. You don't have to use "new" with every pointer you create. Remember, "new" and "delete" don't create/destroy pointers. They allocate/deallocate memory, and that memory is leaked if you don't have any pointers pointing to it any more.
Quote:Original post by PalidineNote that the OP's 'append' function is actually a poorly named sorted insertion function, so the above doesn't actually do what he's wanting.
the following should be a working version of append. but please study it and don't just copy-paste and call it done.
*** Source Snippet Removed ***
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
