Двусвязный список: сортировка узлов в порядке возрастания - PullRequest
Новая
       13

Двусвязный список: сортировка узлов в порядке возрастания

1 голос
/ 01 ноября 2011

Я работаю над программой, использующей двусвязные списки. Я уже получил функциональность для вставки узлов, удаления узлов, извлечения значения из узла, отображения списка, вывода размера списка, сообщения о том, является ли список пустым, и удаления всех узлов.

У меня проблемы с сортировкой значений в порядке возрастания и определением, в каком узле находится определенное значение.

Я собираюсь завтра в лабораторию помощи. Я просто подумал, что увижу, сможет ли кто-нибудь помочь до этого.

Понятия не имею, что делать с 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 ()), было бы здорово!

Спасибо.

1 Ответ

1 голос
/ 01 ноября 2011

Для deleteAll цикл for должен начинаться с 0, а не с 1 (или перейти к размеру +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();

Что касается функции поиска, вы установили ее для возврата void (ничего). Он печатает значение узла, потому что вы указываете это, но не возвращаете узел. Вам нужно подумать о том, что должен вернуть find (узел или ноль).

Я бы предложил поискать QuickSort для сортировки вашего списка. Поскольку это специализированный случай, вам придется настроить QuickSort для сортировки по значению node->, а при сортировке вы должны будете убедиться, что ваши узлы указывают на правильный предыдущий и следующий узлы, когда вы меняете значения. Продолжайте публиковать свой код, когда вы столкнетесь с большим количеством ошибок, и, пожалуйста, обязательно сообщите нам, что вы пробовали, а что не работает, мы будем рады помочь вам в правильном направлении.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...