1

二重リンク リストを使用するプログラムに取り組んでいます。ノードの挿入、ノードの削除、ノードからの値の取得、リストの表示、リストのサイズの出力、リストが空かどうかの通知、およびすべてのノードの削除を行う機能は既に取得しています。

私が問題を抱えているのは、値を昇順にソートし、特定の値がどのノードにあるかを見つけることです.

明日ヘルプラボに行く予定ですが、その前に誰か助けてくれるかどうか見てみようと思っていました.

sort() についてどうすればよいかわかりません。find() はある程度機能していますが、値のノードを検索するように依頼すると、入力した値が返されます。

編集: deleteAll() が正しく動作するようになりました!

#include <iostream>
#include <limits>

using namespace std;

struct node
{
int data; //data
struct node *next; //link to next node
struct node *back; //link to previous node
};

class LinkedList //class LinkedList
{
struct node *root;
struct node *end;

int size;
public:

LinkedList() : root(NULL), size(0){}

bool isEmpty() const { return (root == NULL); }
void create();    //cleate list
void insert();    //insertion
void remove();    //deletion
void display();   //display list
void sort();     //sort list
void find();      //find a values' node
void deleteAll(); //delete all values
void retreive();  //retrive node
void getSize();      //return the number of nodes
};

//Creating a new list
void LinkedList::create()
{
struct node *nxt_node;
struct node *prev_node;

int value;
int n;
int i;

root = nxt_node = NULL;

cout << "How many nodes will the list have?: ";
cin >> n;

cout << "Enter the numbers to create the list: ";

for(i = 1; i <= n; i++)
{
    cin >> value;
    nxt_node = new node;
    nxt_node->data = value;
    nxt_node->next = NULL;
    nxt_node->back = NULL;

    if(root == NULL)
    {
        root = nxt_node;
    }
    else
    {
        prev_node->next = nxt_node;
        nxt_node->back = prev_node;
    }
    prev_node = nxt_node;
}
end = nxt_node;

size = n;

cout << endl;
cout << "The list has been created!" << endl;
cout << endl;
display();
}

//Displaying the list
void LinkedList::display()
{
if(isEmpty())
{
    cout << "The list is empty!" << endl;
    return;
}
else
{
    struct node *tmp = root;

    cout << "The list is: ";

    cout << "root -> ";
    while(tmp != NULL)
    {
        cout << tmp->data << " -> ";
        tmp = tmp->next;
    }
    cout << "end";
    cout << endl << endl;
}
}

//Instert a node anywhere
void LinkedList::insert()
{
int pos;
int dat;

struct node *ptr_b;
struct node *ptr_f;
struct node *tmp;

cout << "At what node do you want to insert the new data?: " << endl;
cout << "(If the node is not found the data will be added to the beginning)" << endl;
cout << "Node: ";
cin >> pos;

cout << endl;
cout << "Enter the data to be inserted: ";
cin >> dat;

ptr_b = root;
tmp = new node;
tmp->data = dat;

while(ptr_b->next != NULL && ptr_b->data != pos)
{
    ptr_b = ptr_b->next;
}
if(ptr_b->next == NULL && ptr_b->data != pos) //insertion to front
{
    root->back = tmp;
    tmp->next = root;
    tmp->back = NULL;
    root = tmp;
}
else if(ptr_b->next == NULL && ptr_b->data == pos) //insertion at the end
{
    ptr_b->next = tmp;
    tmp->next = NULL;
    tmp->back = ptr_b;
    end = tmp;
}
else // insertion between two nodes
{
    ptr_f = ptr_b->next;
    tmp->next = ptr_b->next;
    tmp->back = ptr_b;
    ptr_b->next = tmp;
    ptr_f->back = tmp;
}
size++;
cout << "The new data has been inserted!" << endl << endl;
display();
}

//remove any node
void LinkedList::remove()
{
int loc;
int dat;

struct node *ptr_b;
struct node *ptr_f;
struct node *tmp;

cout << "Enter the node to delete: ";
cin >> loc;

tmp = root;

if(loc < size && loc > 0) //return the value at loc
{
    int ind = 0;

    while(++ind < loc && tmp->next != NULL)
    {
        tmp = tmp->next;
    }
}
if(tmp->next == NULL && tmp->data != loc) //Data not found
{
    cout << "Node not found!" << endl << endl;
    return;
}
else if(tmp->next == NULL && tmp->data == loc) //Delete from the end of the list
{
    ptr_b = tmp->back;
    dat = tmp->data;
    ptr_b->next = NULL;
    end = ptr_b;
}
else //Delete between two nodes or first node
{
    dat = tmp->data;

    if(root == tmp) //delete the first node
    {
        root = tmp->next;
        ptr_f = root;
        ptr_f->back = NULL;
    }
    else //deletion between two nodes
    {
        dat = tmp->data;
        ptr_b = tmp->back;
        ptr_b->next = tmp->next;
        ptr_f = ptr_b->next;
        ptr_f->back = ptr_b;
    }
}
delete tmp;

size--;
cout << endl;
cout << "The node has been deleted!" << endl << endl;
display();
}

//retrieve a nodes data value
void LinkedList::retreive()
{
int loc;

//if the list is empty, say so
if(isEmpty())
{
    cout << "The List is empty!";
    return;
}
else
{
    //If the list is not empty
    cout << "What nodes' value do you want to retrieve?: ";
    cin >> loc;

    if(loc < size && loc > 0) //return the value at loc
    {
        struct node *tmp = root;

        int ind = 0;

        while(++ind < loc && tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        cout << "The nodes value is: " << tmp->data << endl;
        cout << endl;
    }
    else //if the node is out of range
    {
        cout << "Invailid location!" << endl;
    }
}
}

//sort the list in acending order
void LinkedList::sort()
{
cout << "The list has been sorted!" << endl;
}

//delete all the values
void LinkedList::deleteAll()
{
struct node *tmp;

for(int i = 1; i < size; i++)
{
    while(root != NULL)
    {
        tmp = root;

        root = tmp->next;

        delete tmp;
    }
}
display();
}

//find a values' node
void LinkedList::find()
{
int value;

//if the list is empty, say so
if(isEmpty())
{
    cout << "The List is empty!";
    return;
}
else
{
    //If the list is not empty
    cout << "What values' node do you want to find?: ";
    cin >> value;

    struct node *tmp = root;

    int ind = 0;

    while(++ind < value && tmp->data != value)
    {
        tmp = tmp->next;
    }

    if(tmp->next == NULL && tmp->data != value) //Data not found
    {
        cout << "Value not found!" << endl << endl;
        return;
    }
    else
    {
        cout << "The value is at node: " << tmp->data << endl;
        cout << endl;
    }
}
}

void LinkedList::getSize()
{
cout << "The list has " << size << " nodes" << endl << endl;
}

int main()
{
LinkedList list;

list.create(); //create a new list
int choice;
while(1)
{
    cout << "What would you like to do? (1-7): " << endl;
    cout << "1. Insert a number" << endl;
    cout << "2. Delete a node" << endl;
    cout << "3. Delete ALL values" << endl;
    cout << "4. Retrieve a nodes' value" << endl;
    cout << "5. Retrives a values' node" << endl;
    cout << "6. Return the size of the list" << endl;
    cout << "7. Exit the program" << endl;
    cout << endl;

    cout << "Enter your choice (1-7): ";
    cin >> choice;
    cout << endl;

    switch(choice)
    {
        case 1: //insertion
            list.insert();
            break;
        case 2: //deletion
            list.remove();
            break;
       case 3: //delete all the values
            list.deleteAll();
            break;
        case 4: //retrieve a nodes' value
            list.retreive();
            break;
        case 5: //retrieve a values' node
            list.find();
            break;
        case 6: //returns the lists size
            list.getSize();
            break;
        case 7: //Exit the program
            exit(0);
            break;
        default:
            cout << "Please enter a vaild choice (1-7)!" << endl;
            break;
    }
}
return 0;
}

どんな助けでも大歓迎です。両方のことを手伝いたくない場合は理解しています。完了に近づいているもの (find()) を取得するだけで素晴らしいでしょう!

ありがとう。

4

1 に答える 1

1

deleteAll の場合、for ループは 1 からではなく 0 から開始する必要があります (またはサイズ + 1 に移動します)。サイズ 1 のリストを考えてみてください。コードは実行されません。これが、リンク リストに 1 つのノードが残っている理由です。コードも再考する必要があります。for ループではなく、while ループでしょうか。

struct node *tmp;
while (root != NULL)
{
    tmp = root;
    root = root->next;
    root->back = NULL;    //Is this even necessary? You're deleting ALL nodes.
    delete tmp;
}
display();

find 関数に関しては、void (何も返さない) を返すように設定しました。ノード値を出力していますが、ノードを返していないためです。find が何を返すか (ノードまたは null) を考える必要があります。

リストを並べ替えるには、QuickSort を検索することをお勧めします。これは特殊なケースであるため、QuickSort を node->value でソートするように調整する必要があります。ソートするときは、値を交換するときにノードが正しい前のノードと次のノードを指していることを確認する必要があります。エラーが発生した場合は引き続きコードを投稿してください。試したことと機能していないことをお知らせください。正しい方向に導くお手伝いをさせていただきます。

于 2011-11-01T01:47:10.410 に答える