Sorting a Linked List

[tlove65219]

Can someone help me point to the next node, so that my output will show the two sorted nodes. Right now it is only displaying one.

#include <iostream>
using namespace std;

// Specification file for the ShoppingList class
#ifndef SHOPPINGLIST_H
#define SHOPPINGLIST_H

class ShoppingList
{
private:
	// Declare a structure for the list
	struct ListNode
	{
		char name [25];
		double price;
		int priority;
		struct ListNode *next;
	};

	ListNode *head;

public: 
	// Constructor
	ShoppingList()
	{ head = NULL; }

	// Destructor
	~ShoppingList();

	// Linked list operations
	void appendNode(char Name[],double Price,int Priority);
	void deleteNode(char Name[],double Price,int Priority);
	void sortNode(char Name[],double Price,int Priority);
	void displayList() const;
};
#endif

void ShoppingList::appendNode(char Name[], double Price, int Priority)
{
	ListNode *newNode;	// To point to a new node
	ListNode *nodePtr;	// To move through the list

	// Allocate a new node and store item there.
	newNode = new ListNode;
	newNode->priority = Priority;
	strcpy_s( newNode->name, Name );
	newNode->price = Price;
	newNode->next = NULL;

	// If there are no nodes in the list make newNode the first node.
	if (!head)
		head = newNode;
	else
	{
		// Initialize nodePtr to head of list.
		nodePtr = head;

		// Find the last node in the list.
		while (nodePtr->next)
			nodePtr = nodePtr->next;

		// Insert newNode as the last node.
		nodePtr->next = newNode;
	}
}

void ShoppingList::displayList() const
{
	ListNode *nodePtr;	//To move through list

	//Position nodePtr at the head of the list.
	nodePtr = head;

	//While nodePtr points to a node, traverse the list.
	while (nodePtr)
	{
		//Display the value in this node.
		cout << nodePtr->name << endl;
		cout << nodePtr->price << endl;
		cout << nodePtr->priority << endl;


		// Move to the next node.
		nodePtr = nodePtr->next;
	}
}

void ShoppingList::deleteNode(char Name[], double Price, int Priority)
{
	ListNode *nodePtr;		// To traverse the list
	ListNode *previousNode;	// To point to the previous node
	
	// If the list is empty, do nothing.
	if (!head)
		return;

	// Determine if the first node is the one.
	if (head->priority == Priority)
	{
		nodePtr = head->next;
		delete head;
		head = nodePtr;
	}
	else
	{
		//Initialize nodePtr to head of the list
		nodePtr = head;

		// Skip all nodes whose item member is not equal to num.
		while (nodePtr != NULL && nodePtr->priority != Priority)
		{
			previousNode = nodePtr;
			nodePtr = nodePtr->next;
		}

		// If nodePtr is not at the end of th list, link the previous node
		// to the node after nodePtr, then delete nodePtr.
		if (nodePtr)
		{
			previousNode->next = nodePtr->next;
			delete nodePtr;
		}
	}
}

void ShoppingList::sortNode(char Name[], double Price, int Priority)
{
	ListNode *nodePtr;
	nodePtr = head;

	for (bool didSwap = true;
		didSwap;)
	{
		didSwap = false;
		for (head = nodePtr;
			head->next != NULL;
			head = head->next)
		{
			if (head->priority > head->next->priority)
			{
				nodePtr->priority = head->priority;
				head->priority = head->next->priority;
				head->next->priority = nodePtr->priority;
				didSwap = true;
			}
		}
	}
}

ShoppingList::~ShoppingList()
{
	ListNode *nodePtr;
	ListNode *nextNode;

	nodePtr = head;

	while (nodePtr != NULL)
	{
		nextNode = nodePtr->next;

		delete nodePtr;

		nodePtr = nextNode;
	}
}

int main()

{
	double budget;
	ShoppingList list;
	cout << "Enter your budget: $";
	cin >> budget;

	// Build the list.
	list.appendNode("Computer",599.99,1);
	list.appendNode("Ipad",499.99,3);
	list.appendNode("HD T.V.",329.99,2);
	
	//Display the list.
	cout << "Here are the items on the shopping list:\n";
	list.displayList();
	cout << endl;

	//Sort the list.
	list.sortNode("Computer",599.99,1);
	list.sortNode("Ipad",499.99,3);
	list.sortNode("HD T.V.",329.99,2);

	//Displat the sorted list.
	cout << "Here are the sorted items on the shopping list:\n";
	list.displayList();
	cout << endl;
	return 0;
}

[PanGalactic]

Please edit your post and put the source inside code tags. It will make your post a lot more legible and folks here will be more likely to look at it.

[tlove65219]

I added code tags. Can you check it out for me now?

[PanGalactic]

Do you really need to use a fixed-length char[] for ShoppingList::ListNode::name? Can you use std::string instead?

[D80DSL3A]

It looks like your appendNode() (starting at line 37) is intended for getting the node data, but it's incomplete. The 3rd parameter (item) is handled OK - it is assigned to priority on line 44: newNode->priority = item;

The same needs to be done for the other 2 data members of ListNode - name and price. There are parameters in the function header for these but no labels for variable names to be used in the function. Presently:
void ShoppingList::appendNode(char, double, int item)
Make this: void ShoppingList::appendNode(char Name[], double Price, int item)
then assign these within the function following line 43:

strcpy( newNode->name, Name );
newNode->price = Price;

You are prompting for this data in main() on lines 170, 171 and 172. Add some code there to actually get the data, then call appendNode() to add a node with this data.

Line 178 might display the data but line174 will prevent it from ever executing (why return early?) as this ends the program. I haven't looked for any other problems. Good luck!

[tlove65219]

I changed it and now I am getting an error that says: error C2511: 'void ShoppingList::sortNode(char [],double,int)' : overloaded member function not found in 'ShoppingList'

[D80DSL3A]

Did you also change the function header for sortNode() on line 120? I'm looking at what is now your old code so I can't tell.

I'm kinda new to using linked lists. I'm working on a similar project myself, just to see if I can make it work.
Looking further at your sortNode()...
I thought sorting was done by making new pointer assignments (rearranging the node order) instead of copying the data from node to node.
Doesn't this defeat a principal advantage in using a linked list?

Why would sortNode() take any arguments at all? None are being used. You are sorting by existing values of priority.
Also, by using head as the loop variable in the for loop (line 129) you lose its value. I thought this variable (head) was reserved to keep a pointer to the head (1st node) in the list.

[tlove65219]

I put my new code up.. I'm not sure what you are referring to tho. This is my first time ever doing a linked list.

[tlove65219]

How should I change the function header for the sortNode()

[tlove65219]

I added this to the main function but when I ran the program. Only one item showed. I was wondering how could I change it so that the items would sort.
//Sort the list.
	list.sortNode("Computer",599.99,1);
	list.sortNode("Ipad",499.99,3);
	list.sortNode("HD T.V.",329.99,2);

[tlove65219]

Everything is running. I just need to know how to make the other nodes appear after I sort the nodes.