2

I'm trying to wrap my head around how to write an algorithm to sort a linked list, but I'm having a hard time coming up with something that will work. What we need to do have a linked list that contains a name in a string, and an int for hours. After displaying the list and the sum of the hours, we then have to sort the list in ascending order by the hours in a queue. I have the list and all it's functioned stored in a class object, as you will see. I cleared the whole function of what I had in hopes of coming up with a fresh idea but nothing is coming to mind. I initially was going to create a second linked list that had the sorted list, but then I began to wonder if it was possible to sort it within the same list. Here is my code as of posting.

#include   <iostream>
#include   <ctime>
using namespace std;

// OrderedLL class
template<class T>
class   OrderedLL
{
private: 
struct NODE
{
    string  sName;
    int sHours;
    NODE    *next;
};
NODE    *list;
NODE    *rear;

public:
// Constructor
OrderedLL () { list = rear =  NULL;}

// Insert item x -------------------------------------
void    Insert(string x, int y)
{
    NODE *r;
    // Create a new node
    r = new(NODE); r->sName = x; r->sHours = y;
    r->next = NULL;
    // Inserts the item into the list
    r->next = list;
    list = r;
}

// Display the linked list --------------------------
void display()
{ NODE *p = list;
while( p != NULL)
    { cout << p->sName << "/" << p->sHours << "-->"; p = p->next;}
cout << "NULL\n";
}

// Delete x from the linked list --------------------
void DeleteNode(T x)
{
NODE *p = list, *r = list;
while( p->info != x) {r=p; p=p->next; }
if( p == list)
    { // delete the first node
    list = p->next; delete(p);
    }
    else
    { r->next = p->next; delete(p);}
}

// Sort by hours ------------------------------------
void    sortHours()
{
NODE    *p, *q;



}

// Display the total hours --------------------------
friend  T   totHours(OrderedLL  LL)
{
    NODE    *p;
    int total = 0;  

    p = LL.list;
    while(p != NULL)
    {
        total += p->sHours;
        p = p->next;
    }
    cout << "Total spending time = " << total << endl;
}





}; // end of OrderedLL class

int main(void)
{
    // Declare variables
time_t          a;
OrderedLL<int>      unsortedLL;
OrderedLL<int>      sortedLL;
int         inHours;
string          inName;




// Displays the current time and date
time(&a);
cout << "Today is " << ctime(&a) << endl;

// Asks the user to enter a name and hours 5 times, inserting each entry
// into the queue
for(int i = 0; i < 5; i++)
{
    cout << "Enter name and Time: ";
    cin >> inName >> inHours;
    unsortedLL.Insert(inName, inHours);
}

// Displays the unsorted list
cout << "\nWaiting List-->";
unsortedLL.display();
totHours(unsortedLL);

// Calls for the function to sort the list into a queue by hours
unsortedLL.sortHours();

unsortedLL.display();
return 0;

} // End of "main"

As always thanks to anyone who can help

4

3 回答 3

1

Try sorting the linked-list like you are sorting an integer array. Instead of swapping the nodes, swap the contents inside the nodes.

于 2012-10-17T05:45:06.347 回答
1

如果您不关心效率，则可以使用任何排序算法。链表和数组的不同之处在于交换操作，即在排序时交换两个元素的位置，会慢很多，因为它必须遍历链表的链接。

O(n²)冒泡排序很容易用链表实现，因为它只与它的邻居交换一个元素。

如果您关心效率，您可以考虑实现合并排序算法，即使它有点复杂。

于 2012-10-17T06:38:30.617 回答
0

你应该像这样插入

void Insert(string x, int y)
{
    NODE *r;NODE *temp;
    // Create a new node
    r = new NODE; r->sName = x; r->sHours = y;r->next = NULL;
    if(list==null)//check if list is empty
    {
    list=r;//insert the node r in the list
    }
    else
    {
    temp=list;
    while(temp->next!=null)temp=temp->next;//reach to the end of the list
    temp->next=r;//insert it at the end of the list
    }
}

不需要后指针..只需检查是否list->next是null，如果是，你在最后

你的sorthour功能应该是

void sortHours()
{

    for(NODE* n=list;n->next!=null;n=n->next)//get each of the node in list 1 by 1 except the last one i.e. n
    {

        for(NODE* n1=n->next;n1!=null;n1=n1->next)//compare the list n node with all the nodes that follow it i.e.n1
        {

            if(n->sHours > n1->sHours)//if one of the node is the less than n
            {
                //swap n and n1
                node temp=*n;
                n->age=n1->age;
                n->name=n1->name;
                n1->age=temp.age;
                n1->name=temp.name;
            }

        }

    }
}
于 2012-10-17T06:15:39.683 回答