2 Replies - 982 Views - Last Post: 18 April 2009 - 06:20 AM Rate Topic: -----

#1 M3L  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 10-March 09

Sorting Structure

Posted 17 April 2009 - 05:42 PM

Hey guys!

This is my first post here.

I am having a problem on one of my functions i am trying to create. this is the description i am suppose to use:

"Use a node pointer to point to the linked list from LinkList. And use
Node * link in private section to build a new sorted list, with Nodes information copied
from the linked list in LinkList. SortList results a linked list with IDs in ascending
order."

the sortlist function i've created is similar to bubble sort.

i am just not sure how to use the structure in the sort function.

#include <iostream>
#include <string>
#include <fstream>
#include <math.h>
#include <cstdlib>

using namespace std;

struct Node
{
 	char name[30];
	long ID;
	Node *next;
	Node();
	Node(char newName[], long &newID);
	
};

Node::Node()
{
	next = NULL;
}

Node::Node(char newName[], long &newID)
{
 	strcpy(name, newName);
	ID = newID;
} 	 		

class LIST
{
 	private:
			  Node *link;
		  
	public:
		   LIST();
		   void OpenFile(ifstream &infile, char fname[25]);
		   void ReadFile (ifstream &infile);
		   Node* NodeBuild (char name[], long &nID);
		   void LinkList(Node *next);
		   void SortList();
		   void ShowList();
};
 
LIST::LIST()
{
	link = NULL;
}

void LIST::ReadFile(ifstream& infile)
{
	
 	char temp[30];
	char name_temp[30];
	long temp_ID;
	
	infile.getline(temp,30,' ');
	strcpy(name_temp, temp);

	infile.getline(temp,30);
	temp_ID = atol(temp); 
	
	Node *tempnode; 
	   
	tempnode = NodeBuild(name_temp, temp_ID);
	cout<<tempnode->name<<'\t'<<tempnode->ID<<endl;	
}

Node* LIST::NodeBuild (char newName[], long &newID)
{
 	Node *newInfo = new Node(newName, newID);	   
	 
	return newInfo;
}

void LIST::OpenFile(ifstream& infile, char fname[25])
{
	infile.open(fname);
}

void LIST::LinkList(Node* tempnode)
{
	if (link == NULL)
	   	   link = tempnode;
	else
	  { 
			 tempnode->next;
			 link=tempnode;}
			 	   
}

//void LIST::SortList(){
//	Node *x;
//	Node *y;
//	
//	Node tmp;
//	
//	for(x = link; x; x = x->next)
//	{
//		for(y = link; y->next; y = y->next)
//		{
//			if(y->ID > y->next->ID)
//			{
//				Node temp;
//			   
//				strcpy(temp.name, y->next->name);
//			   // temp = link;
//				
//			   
//				strcpy(y->next->name,y->name);
//			  
//				
//			   
//				strcpy(y->name,temp.name);
//			  
//				
//			}
//		}
//	}
//	 cout<<x<<'\t'<<y<<endl;
//}

			  
int main()
{
	LIST newList;
 	ifstream inFile;
 	
 	newList.OpenFile(inFile, "a9.txt");						 
	
	while (inFile.good())
	{
		newList.ReadFile(inFile);
	}
	 
//	newList.SortList(); 
 	system("pause");
	return 0;
}




Thank you!

Attached File(s)

  • Attached File  a9.txt (156bytes)
    Number of downloads: 29


Is This A Good Question/Topic? 0
  • +

Replies To: Sorting Structure

#2 trixt.er  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 419
  • Joined: 28-September 08

Re: Sorting Structure

Posted 17 April 2009 - 07:40 PM

Well that depends on what kind of a sort you wish to implement.
Selection sort 0(n^2)
Insertion sort 0(n^2) <--- Really easy to use when constructing list.
Bubble sort 0(n^2)
Heap sort 0(n log n)

or you can try...

Merge sort 0(n log n) <---- The merge sort is fast and fairly easy to program. I alreadly have one if you need it but it is designed to work for the stl's list and needs to be modified for your own defined list. The merge sort partially uses the selection sort.

So how do you want to sort the list?
Was This Post Helpful? 0
  • +
  • -

#3 M3L  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 10-March 09

Re: Sorting Structure

Posted 18 April 2009 - 06:20 AM

View Posttrixt.er, on 17 Apr, 2009 - 06:40 PM, said:

So how do you want to sort the list?



The bubble sort would do just fine. ive done bubble sort before however i was not using pointers. in this particular way, i would need to use the pointers and im not familiar with it.



void LIST::SortList(){
	Node *x;
	Node *y;
	
	Node temp;
	
	for(x = link; x; x = x->next)
	{
		for(y = link; y->next; y = y->next)
		{
			if(y->ID > y->next->ID)
			{
				Node temp;
			   
				strcpy(temp.name, y->next->name);
			   // temp = link;
				
			   
				strcpy(y->next->name,y->name);
			  
				
			   
				strcpy(y->name,temp.name);
			  
				
		   }
		}
	}
}



Thank you!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1