Question
I am trying to implement something like this to sort my linked list in descending order (I think), cause I am storing the list in
I am trying to implement something like this to sort my linked list in descending order (I think), cause I am storing the list in a queue and when I delete them I want to print them as they dequeue and they should print in ascending order. My problem is implementing this sort into my existing code which uses a few header files and template classes. I get really confused when using template classes.... I guess I am trying to create a sorting function or functions that can be implemented into a linkedlist header file and called from the priority queue(main) header file.I needed to show an implementation using both a heap and a linked list. I got the heap implementation working. Here is heap header file showing how I am reordering the data in the heap:
#ifndef HEAP_H
#define HEAP_H
template
void swapHeapDown(T& one, T& two, int& count);
template
void swapHeapUp(T& one, T& two, int& count);
template
struct Heap
{
void ReheapDown(int root, int bottom);
void ReheapUp(int root, int bottom);
T* element;
int enqueCount;
int dequeCount;
};
template
void swapHeapDown(T& first, T& second, int& count)
{
T temp;
count++;
temp = first;
count++;
first = second;
count++;
second = temp;
}
template
void swapHeapUp(T& first, T& second, int& count)
{
T temp;
count++;
temp = first;
count++;
first = second;
count++;
second = temp;
}
template
void Heap
{
int parent;
if (bottom > root)
{
parent = (bottom - 1) / 2;
enqueCount++;
if (element[parent] > element[bottom])
{
swapHeapUp(element[parent], element[bottom], enqueCount);
ReheapUp(root, parent);
}
}
}
template
void Heap
{
int minChild;
int rightChild;
int leftChild;
leftChild = root * 2 + 1;
rightChild = root * 2 + 2;
if (leftChild <= bottom)
{
if(leftChild == bottom)
{
minChild = leftChild;
}
else
{
dequeCount++;
if (element[leftChild] >= element[rightChild])
{
minChild = rightChild;
}
else
{
minChild = leftChild;
}
}
dequeCount++;
if (element[root] > element[minChild])
{
swapHeapUp(element[root], element[minChild], dequeCount);
ReheapDown(minChild, bottom);
}
}
}
#endif
Here is snippet from my main header file: Showing where I am calling the heap ordering functions and where I need to implement a linkedlist ordering call function.
//**************************************************************************************
// Dequeue
//
//
//**************************************************************************************
template
void PriorityQueue
{
if (length == 0)
{
throw EmptyPQ();
}
else
{
item = items.element[0];
items.element[0] = items.element[length - 1];
length--;
items.ReheapDown(0, length - 1);
}
}
//**************************************************************************************
// Enqueue
//
//
//**************************************************************************************
template
void PriorityQueue
{
if (length == maxItems)
{
throw FullPQ();
}
else
{
length++;
items.element[length - 1] = newItem;
items.ReheapUp(0, length - 1);
}
}
//**************************************************************************************
// AddToQueueList
//
//
//**************************************************************************************
template
void PriorityQueue
{
if (ListLength == maxItems)
{
cout << " Queue is Full! ";
system("pause");
}
else
{
NodeType* newNode;
newNode = new NodeType;
newNode->info = newItem;
newNode->next = NULL;
if (rear == NULL)
{
front = newNode;
}
else
{
rear->next = newNode;
}
rear = newNode;
ListLength++;
}
}
//**************************************************************************************
// RemoveFromQueueList
//
//
//**************************************************************************************
template
void PriorityQueue
{
if (ListLength == 0)
{
cout << " Queue is empty! ";
//system("pause");
}
else
{
NodeType* tempPtr;
tempPtr = front;
item = front->info;
front = front->next;
if (front == NULL)
{
rear = NULL;
}
delete tempPtr;
ListLength--;
cout << item << " ";
//system("pause");
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started