2

リンクリストを並べ替えるアルゴリズムの書き方に頭を悩ませようとしていますが、うまくいくものを思いつくのに苦労しています。文字列に名前を含むリンクリストと、何int時間も必要です。リストと時間の合計を表示した後、キュー内の時間の昇順でリストを並べ替える必要があります。ご覧のとおり、リストとそのすべての機能がクラスオブジェクトに格納されています。新鮮なアイデアを思いつくことを期待して、持っていたもののすべての機能をクリアしましたが、何も思い浮かびません。最初は、並べ替えられたリストを持つ2番目のリンクリストを作成しようとしていましたが、同じリスト内で並べ替えることができるかどうか疑問に思い始めました。これが投稿時の私のコードです。

#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"

いつものように助けることができる人に感謝します

4

3 に答える 3

1

整数配列をソートするように、連結リストをソートしてみてください。ノードを交換する代わりに、ノード内のコンテンツを交換します。

于 2012-10-17T05:45:06.347 に答える
1

効率を気にしない場合は、任意の並べ替えアルゴリズムを使用できます。リンクされたリストと配列の違いは、並べ替え中に 2 つの要素の位置を交換するスワップ操作が、リストのリンクを介して実行する必要があるため、非常に遅くなることです。

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 に答える