Ad:

C++ Discussion Thread
Marked Solved
Views: 993

Jun 19th, 2008

help with Sorting a Linked list is needed!

Expand Post »

hello,
ok i have this simple linked list program, as u can see below i got three functions: one to insert a node in the first of the list, the second to insert a node in the middle and the third to insert a node in the last of the list.
And now i want to merge all of them in only one function that will sort the list and decide where to put the new node according to its value.
Can you help me please?

(Toggle Plain Text)

#include<iostream.h>

class node{
public:
int data;
node* next;
node(int x){
data=x;
next=NULL;};

void display(){
cout<<data<<"  ";
};
};

class linked_list{
private:
node* first;
public:
linked_list(){
first=NULL;};

void insert_last(int d){
node* newnode=new node(d);
node* current=first ;
if(first==NULL)
first=newnode;
else{
while(current->next!=NULL)
current=current->next;
current->next=newnode;
}};

void insert_first(int z){
node* newnode= new node(z);
if(first==NULL)
first=newnode;
else{
newnode->next=first;
first=newnode;}
};

void display(){
node* current=first;
while(current!=NULL){
current->display();
current=current->next;}
};

void insert_mid(int d){
node* newnode=new node(d);
node* current=first;
node* temp;
while(current->next->data<d)
current=current->next;

temp=current->next;
current->next=newnode;
newnode->next=temp;
};

int l_delete(int x){
node* current=first;
if(first==NULL){
cout<<"List is empty"<<endl;
return -1;}
if(first->data==x)
first=first->next;
else{
while((current->next->data!=x)&&(current->next!=NULL))
current=current->next;}
if(current->next==NULL)
cout<<"error"<<endl;
else{
current->next=current->next->next;
delete current;}
return x;};
};



main(){
linked_list list;
int no, g, h, d, e;
char c, a0, a1, a2, a3;
do{
cout<<"Please choose the number of the option"<<endl<<endl;
cout<<"\t\t______________________ MENU _____________________"<<endl;
cout<<"\t\t1. Add new node to the end of the list"<<endl;
cout<<"\t\t2. Add new node to the beginning of the list"<<endl;
cout<<"\t\t3. Add new node in the middle of the list"<<endl;
cout<<"\t\t4. Delete a node from the list"<<endl;
cout<<"\t\t5. Display the list"<<endl;
cout<<"\t\t_________________________________________________"<<endl;
cin>>no;
switch(no){
case 1: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>g;
list.insert_last(g);
cout<<"Do you want to add more to the end of the list? y/n"<<endl;
cin>>a0;}
while(a0=='y');
break;
case 2: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>h;
list.insert_first(h);
cout<<"Do you want to add more to the beginning of the list? y/n"<<endl;
cin>>a1;}
while(a1=='y');
break;
case 3: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>d;
list.insert_mid(d);
cout<<"Do you want to add more to the mid of the list? y/n"<<endl;
cin>>a2;}
while(a2=='y');
break;
case 4: do{
cout<<"Please enter the value of the element you want to delete:"<<endl;
cin>>e;
list.l_delete(e);
cout<<"Do you want to delete more from the list? y/n"<<endl;
cin>>a3;}
while(a3=='y');
break;
case 5: list.display();
cout<<endl;
break;
default:
cout<<"Error in number"<<endl;
break;}
cout<<"Do you want to continue? y/n"<<endl;
cin>>c;}
while(c=='y');
}

#include<iostream.h>

class node{
public:
int data;
node* next;
node(int x){
data=x;
next=NULL;};

void display(){
cout<<data<<"  ";
};
};

class linked_list{
private:
node* first;
public:
linked_list(){
first=NULL;};

void insert_last(int d){
node* newnode=new node(d);
node* current=first ;
if(first==NULL)
first=newnode;
else{
while(current->next!=NULL)
current=current->next;
current->next=newnode;
}};

void insert_first(int z){
node* newnode= new node(z);
if(first==NULL)
first=newnode;
else{
newnode->next=first;
first=newnode;}
};

void display(){
node* current=first;
while(current!=NULL){
current->display();
current=current->next;}
};

void insert_mid(int d){
node* newnode=new node(d);
node* current=first;
node* temp;
while(current->next->data<d)
current=current->next;

temp=current->next;
current->next=newnode;
newnode->next=temp;
};

int l_delete(int x){
node* current=first;
if(first==NULL){
cout<<"List is empty"<<endl;
return -1;}
if(first->data==x)
first=first->next;
else{
while((current->next->data!=x)&&(current->next!=NULL))
current=current->next;}
if(current->next==NULL)
cout<<"error"<<endl;
else{
current->next=current->next->next;
delete current;}
return x;};
};



main(){
linked_list list;
int no, g, h, d, e;
char c, a0, a1, a2, a3;
do{
cout<<"Please choose the number of the option"<<endl<<endl;
cout<<"\t\t______________________ MENU _____________________"<<endl;
cout<<"\t\t1. Add new node to the end of the list"<<endl;
cout<<"\t\t2. Add new node to the beginning of the list"<<endl;
cout<<"\t\t3. Add new node in the middle of the list"<<endl;
cout<<"\t\t4. Delete a node from the list"<<endl;
cout<<"\t\t5. Display the list"<<endl;
cout<<"\t\t_________________________________________________"<<endl;
cin>>no;
switch(no){
case 1: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>g;
list.insert_last(g);
cout<<"Do you want to add more to the end of the list? y/n"<<endl;
cin>>a0;}
while(a0=='y');
break;
case 2: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>h;
list.insert_first(h);
cout<<"Do you want to add more to the beginning of the list? y/n"<<endl;
cin>>a1;}
while(a1=='y');
break;
case 3: do{
cout<<"Please enter the element you want to insert to the node:"<<endl;
cin>>d;
list.insert_mid(d);
cout<<"Do you want to add more to the mid of the list? y/n"<<endl;
cin>>a2;}
while(a2=='y');
break;
case 4: do{
cout<<"Please enter the value of the element you want to delete:"<<endl;
cin>>e;
list.l_delete(e);
cout<<"Do you want to delete more from the list? y/n"<<endl;
cin>>a3;}
while(a3=='y');
break;
case 5: list.display();
cout<<endl;
break;
default:
cout<<"Error in number"<<endl;
break;}
cout<<"Do you want to continue? y/n"<<endl;
cin>>c;}
while(c=='y');
}

Similar Threads

binary search trees in Java
LinkedList Search in Java

anifreak

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Apr 2008

Permalink

Jun 19th, 2008

Re: help with Sorting a Linked list is needed!

And if your code was indented AT ALL, some people might actually want to read it.

I mean, points++ for using code tags, but then you blew it by not indenting it.

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Jun 19th, 2008

Re: help with Sorting a Linked list is needed!

Well, I suppose this would solve your problem. You can merge the sort() into the insert().
Here's the code:

C++ Syntax (Toggle Plain Text)
#include <iostream>
#include <fstream>
using namespace std;
 
class List
{
	private:
		struct ListN
		{
			char item;
			ListN* next;
		};
		ListN* head;
		ListN* tail;
		int size;
 
	public:
		List();
		~List();
		void insert (char );
		void remove (int );
		void deleteAll ();
		void retrieve ();
		void countIte();
		void countRec();
		void display();
		void sort();
		void save();
};
 
 
List :: List()
{
	head = tail = NULL;
	size = 0;
}
 
List :: ~List()
{
	deleteAll ();
}
 
void List :: sort()
{
	ListN* curPtr;
	curPtr = head;
	char buffer;
	int i;
	int j;
 
	for (i=1; i<size; i++)
	{
		for(j=size-1, curPtr = head; j>=i; j--, curPtr = curPtr -> next)
		{
			if (curPtr->item > curPtr->next->item)
			{
				buffer = curPtr -> item;
				curPtr->item = curPtr->next->item;
				curPtr->next->item = buffer;
			}
		}
	}
 
	//alternate method for sorting
	/*if (size >= 2)
	{
		for (curPtr = head; curPtr->next != NULL; curPtr = curPtr -> next)
		{
			cout << "sorting " << curPtr-> item << endl;
			if (curPtr->item > curPtr->next->item)
			{
				buffer = curPtr -> item;
				curPtr->item = curPtr->next->item;
				curPtr->next->item = buffer;
			}
		}
	}*/
}
 
void List :: insert(char item)
{
	ListN* newPtr;
	ListN* curPtr;
	newPtr = new ListN;
	curPtr = head;
 
	newPtr -> next = NULL;
	newPtr -> item = item;
 
	if (size == 0)
	{
		head = newPtr;
		newPtr -> next = NULL;
	}
 
	else
	{
		curPtr = tail;
		curPtr->next = newPtr;
	}
 
	tail = newPtr;
	size++;
}
 
void List :: retrieve()
{
	ifstream read;
	char temp1;
	char check;
 
	read.open("Q2.txt");
	read >> temp1;
 
	insert(temp1);
	check = temp1;
 
	for (;;)
	{
		read >> temp1;
 
		if (temp1 == check)
			break;
		check = temp1;
		insert(temp1);
	}
	sort();
}
 
void List :: display()
{
	int i;
	ListN* curPtr;
	curPtr = head;
 
	sort();
	if (size == 0)
		cout << "No item in the List!!" << endl;
 
	else
	{
		cout << "\tThe list of record is :\t";
		for (i=1; i<=size; i++)
		{
			cout << curPtr -> item << " ";
			curPtr = curPtr -> next;
		}
	}
 
 
}
 
void List :: save()
{
	int i;
	ListN* curPtr;
	ofstream save;
 
	save.open("Q2.txt");
 
	curPtr = head;
	for( i=0; i<size; i++ )
	{
		save << curPtr -> item << endl;
		curPtr = curPtr -> next;
	}
}
 
void List :: remove(int index)
{
	int i;
	ListN* previous;
	ListN* curPtr;
	curPtr = head;
 
	if (index <= size && index >0)
	{
		if(index == 1)
		{
			head = head -> next;
			delete curPtr;
			curPtr->next = NULL;
		}
 
		for(i=1; i<index-1; i++)
			curPtr = curPtr -> next;
 
		previous = curPtr;
 
		curPtr = curPtr -> next;
 
		previous -> next = curPtr -> next;
 
		curPtr = NULL;
		size--;
	}
 
	else if (index<0 || index>size)
		cout << "The record number is out of range!!" << endl;
 
	previous = NULL;
 
}
 
void List :: deleteAll ()
{
	cout << size << endl;
	int i;
 
	for (i=size; i>0 ; i--)
	{
		if (i == 1)
		{
			head = NULL;
			size--;
		}
		else
		remove(i);
	}
}
 
void List :: countIte()
{
	int count;
	int i;
	ListN* curPtr;
 
	count = 0;
 
	for (i=0, curPtr = head; i<size; i++, curPtr = curPtr->next)
		count++;
 
	cout << "The total records is :\t\t" << count << endl;
}
 
void List :: countRec()
{
	ListN* curPtr;
	int count;
 
	count = 0;
 
	for(curPtr = head; curPtr != NULL; curPtr = curPtr->next, count++);
	{
	}
 
	cout << "The total records is :\t\t" << count << endl;
}
 
int main()
{
	List a;
	int choice;
	int index;
	char val;
 
	do
	{
		cout << "1	Insert a new item into the linked list." << endl;
		cout <<	"2	Remove an item from the linked list." << endl;
		cout <<	"3	Remove all items from the linked list." << endl;
		cout <<	"4	Get the item from a text file and added to the sorted linked list." << endl;
		cout <<	"5	Count the number of item iteratively." << endl;
		cout <<	"6	Count the number of item recursively." << endl;
		cout <<	"7	List the content of the linked list." << endl;
		cout << "8\tQuit." << endl << endl;
		cout << "\tYour Choice :\t";
		cin >> choice;
 
		cout << "\n\n\n" << endl;
 
		switch(choice)
		{
			case 1:
				cout << "Enter a value for insert :\t";
				cin >> val;
				a.insert(val);
				cout << "\n\n" << endl;
				break;
			case 2:
				cout << "Enter the index of record for deletion :\t";
				cin >> index;
				a.remove(index);
				cout << "\n\n" << endl;
				break;
			case 3:
				a.deleteAll();
				cout << "\n\n" << endl;
				break;
			case 4:
				a.retrieve();
				cout << "\n\n" << endl;
				break;
			case 5:
				a.countIte();
				cout << "\n\n" << endl;
				break;
			case 6:
				a.countRec();
				cout << "\n\n" << endl;
				break;
			case 7:
				a.display();
				cout << "\n\n" << endl;
				break;
 
			case 8:
				break;
		}
	}while(choice != 8);
 
	return 0;
}
#include <iostream>
#include <fstream>
using namespace std;

class List
{
	private:
		struct ListN
		{
			char item;
			ListN* next;
		};
		ListN* head;
		ListN* tail;
		int size;

	public:
		List();
		~List();
		void insert (char );
		void remove (int );
		void deleteAll ();
		void retrieve ();
		void countIte();
		void countRec();
		void display();
		void sort();
		void save();
};


List :: List()
{
	head = tail = NULL;
	size = 0;
}

List :: ~List()
{
	deleteAll ();
}

void List :: sort()
{
	ListN* curPtr;
	curPtr = head;
	char buffer;
	int i;
	int j;
 
	for (i=1; i<size; i++)
	{
		for(j=size-1, curPtr = head; j>=i; j--, curPtr = curPtr -> next)
		{
			if (curPtr->item > curPtr->next->item)
			{
				buffer = curPtr -> item;
				curPtr->item = curPtr->next->item;
				curPtr->next->item = buffer;
			}
		}
	}

	//alternate method for sorting
	/*if (size >= 2)
	{
		for (curPtr = head; curPtr->next != NULL; curPtr = curPtr -> next)
		{
			cout << "sorting " << curPtr-> item << endl;
			if (curPtr->item > curPtr->next->item)
			{
				buffer = curPtr -> item;
				curPtr->item = curPtr->next->item;
				curPtr->next->item = buffer;
			}
		}
	}*/
}

void List :: insert(char item)
{
	ListN* newPtr;
	ListN* curPtr;
	newPtr = new ListN;
	curPtr = head;

	newPtr -> next = NULL;
	newPtr -> item = item;
	
	if (size == 0)
	{
		head = newPtr;
		newPtr -> next = NULL;
	}

	else
	{
		curPtr = tail;
		curPtr->next = newPtr;
	}

	tail = newPtr;
	size++;
}

void List :: retrieve()
{
	ifstream read;
	char temp1;
	char check;

	read.open("Q2.txt");
	read >> temp1;

	insert(temp1);
	check = temp1;

	for (;;)
	{
		read >> temp1;
		
		if (temp1 == check)
			break;
		check = temp1;
		insert(temp1);
	}
	sort();
}

void List :: display()
{
	int i;
	ListN* curPtr;
	curPtr = head;

	sort();
	if (size == 0)
		cout << "No item in the List!!" << endl;
	
	else
	{
		cout << "\tThe list of record is :\t";
		for (i=1; i<=size; i++)
		{
			cout << curPtr -> item << " ";
			curPtr = curPtr -> next;
		}
	}

	
}

void List :: save()
{
	int i;
	ListN* curPtr;
	ofstream save;
	
	save.open("Q2.txt");

	curPtr = head;
	for( i=0; i<size; i++ )
	{
		save << curPtr -> item << endl;
		curPtr = curPtr -> next;
	}
}

void List :: remove(int index)
{
	int i;
	ListN* previous;
	ListN* curPtr;
	curPtr = head;

	if (index <= size && index >0)
	{
		if(index == 1)
		{
			head = head -> next;
			delete curPtr;
			curPtr->next = NULL;
		}
	
		for(i=1; i<index-1; i++)
			curPtr = curPtr -> next;

		previous = curPtr;

		curPtr = curPtr -> next;

		previous -> next = curPtr -> next;

		curPtr = NULL;
		size--;
	}
	
	else if (index<0 || index>size)
		cout << "The record number is out of range!!" << endl;

	previous = NULL;
	
}

void List :: deleteAll ()
{
	cout << size << endl;
	int i;

	for (i=size; i>0 ; i--)
	{
		if (i == 1)
		{
			head = NULL;
			size--;
		}
		else
		remove(i);
	}
}

void List :: countIte()
{
	int count;
	int i;
	ListN* curPtr;

	count = 0;

	for (i=0, curPtr = head; i<size; i++, curPtr = curPtr->next)
		count++;

	cout << "The total records is :\t\t" << count << endl;
}

void List :: countRec()
{
	ListN* curPtr;
	int count;

	count = 0;

	for(curPtr = head; curPtr != NULL; curPtr = curPtr->next, count++);
	{
	}

	cout << "The total records is :\t\t" << count << endl;
}

int main()
{
	List a;
	int choice;
	int index;
	char val;

	do
	{
		cout << "1	Insert a new item into the linked list." << endl;
		cout <<	"2	Remove an item from the linked list." << endl;
		cout <<	"3	Remove all items from the linked list." << endl;
		cout <<	"4	Get the item from a text file and added to the sorted linked list." << endl;
		cout <<	"5	Count the number of item iteratively." << endl;
		cout <<	"6	Count the number of item recursively." << endl;
		cout <<	"7	List the content of the linked list." << endl;
		cout << "8\tQuit." << endl << endl;
		cout << "\tYour Choice :\t";
		cin >> choice;

		cout << "\n\n\n" << endl;
		
		switch(choice)
		{
			case 1:
				cout << "Enter a value for insert :\t";
				cin >> val;
				a.insert(val);
				cout << "\n\n" << endl;
				break;
			case 2:
				cout << "Enter the index of record for deletion :\t";
				cin >> index;
				a.remove(index);
				cout << "\n\n" << endl;
				break;
			case 3:
				a.deleteAll();
				cout << "\n\n" << endl;
				break;
			case 4:
				a.retrieve();
				cout << "\n\n" << endl;
				break;
			case 5:
				a.countIte();
				cout << "\n\n" << endl;
				break;
			case 6:
				a.countRec();
				cout << "\n\n" << endl;
				break;
			case 7:
				a.display();
				cout << "\n\n" << endl;
				break;

			case 8:
				break;
		}
	}while(choice != 8);

	return 0;
}

raul15791

Reputation Points: 37

Solved Threads: 7

Junior Poster

Offline

102 posts
since Jun 2008

Permalink

Jun 20th, 2008

Re: help with Sorting a Linked list is needed!

Oh thank u so much!
there were some additional lines and some stuff that i didn't need, i fixed them and i got the program i wanted... thanx again raul!!!

anifreak

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Apr 2008

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: switch color of CListCtrl text

Next Thread in C++ Forum Timeline: What is C++ Good For?

DaniWeb Message

Cancel Changes

User Name
Password