Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Проблемы с функцией сортировки односвязного списка по возрастанию. С++.

88K
14 января 2015 года
Andrey_Gers
2 / / 14.01.2015
Имеется односвязный список. Сделал функции создания и удаления элементов в списке. Проблемы с функцией сортировки односвязного списка по возрастанию.

Код:
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <locale.h>

using namespace std;

struct Node       //Структура являющаяся звеном списка
{
    int x;     //Значение x будет передаваться в список
    Node *Next; //Указатели на адреса следующего элемента списка
};

class List   //Создаем тип данных Список
{
    Node *Head, *Tail; //Указатели на адреса начала списка и его конца
public:
    List() :Head(NULL), Tail(NULL){}; //Инициализируем адреса как пустые
    ~List(); //Деструктор
    void Show(); //Функция отображения списка на экране
    void Add(int x); //Функция добавления элемента в список
    void Sort(int x); //Функция сортировки элементов в списке
    void Delete(int x); //Функция удаления элемента в списке
};

List::~List() //Деструктор
{
    while (Head) //Пока по адресу на начало списка что-то есть
    {
        Tail = Head->Next; //Резервная копия адреса следующего звена списка
        delete Head; //Очистка памяти от первого звена
        Head = Tail; //Смена адреса начала на адрес следующего элемента
    }
}

void List::Add(int x)
{
    Node *temp = new Node; //Выделение памяти под новый элемент структуры
    temp->Next = NULL;  //Указываем, что изначально по следующему адресу пусто
    temp->x = x;//Записываем значение в структуру

    if (Head != NULL) //Если список не пуст
    {
        Tail->Next = temp; //Указываем адрес следующего за хвостом элемента
        Tail = temp; //Меняем адрес хвоста
    }
    else //Если список пустой
    {
        Head = Tail = temp; //Голова=Хвост=тот элемент, что сейчас добавили
    }
}

void List::Show()
{
    if (Head == NULL)
        printf("List is NULL");
    //ВЫВОДИМ СПИСОК С НАЧАЛА
    Node *temp = Head; //Временно указываем на адрес первого элемента
    while (temp != NULL) //Пока не встретим пустое значение
    {
        cout << temp->x << " "; //Выводим каждое считанное значение на экран
        temp = temp->Next; //Смена адреса на адрес следующего элемента
    }
    cout << "n";
}

void List::Delete(int x)
{
    int number = 0;
    Node *temp = Head;
    Node *tempL = Head;
    Node *tempR = Head;
    while (number < x - 1) //Пока не встретим пустое значение
    {
        number++;
        temp = temp->Next; //Смена адреса на адрес следующего элемента
    }
    tempR = temp->Next;

    tempL->Next = tempR;
    cout << "Удалили(" << x << "): " << temp->x << endl;
    delete temp;

}


void List::Sort(int x)
{

}

int main()
{
    setlocale(LC_ALL, "Russian");
    List lst; //Объявляем переменную, тип которой есть список

    system("cls");
    printf("n Односвязный список. Функции: создание, удаление, сортировка.");
    printf("n Список возможных действий: ");
    printf("n 1 - Добавление элемента в список");
    printf("n 2 - Удаление элемента из списка");
    printf("n 3 - Сортировка элементов в списке");
    printf("n 4 - Вывод списка");
    printf("n 0 - Выходn");
    int choise = 228, buf;
    while (1)
    {
        printf("Выберите действие: ");
        scanf_s("%d", &choise);
        if (choise == 1)
            {
                printf("Введите элемент, который будет добавлен в список: ");
                scanf_s("%d", &buf);
                lst.Add(buf);
            }
        else if(choise == 2)
            {
                printf("Введите номер элемента списка, который хотите удалить: ");
                scanf_s("%d", &buf);
                lst.Delete(buf);
            }
        else if(choise == 3)
                lst.Sort(buf);
        else if(choise == 4)
            lst.Show();
        else if(choise == 0)
            exit(0);
        else
            printf("Неверный выбор. Повторите попыткуn");
    }
    system("PAUSE");
}
Подскажите пожалуйста какой код необходим в

 
Код:
void List::Sort(int x)
{

}
392
15 января 2015 года
cronya
421 / / 03.01.2009
Вопрос: Зачем односвязному списку конец хранить в памяти????
Должно быть так:

Код:
#include <iostream>

using std::cout;
using std::endl;
using std::system;

class List
{
public:
    int numer;
    List* next;
    List(){ numer = 0; next = NULL; }
    ~List(){};
}*head;

void Create();
void Out();
void Sort();

int main()
{
    Create();
    Out();
    Sort();
    cout << "Sort List: " << endl;
    Out();
    cout << endl;
    system("pause");
    return 0;
}

void Create()
{
    List* ptr = NULL, *tmp = NULL;
    for(int idx=0; idx<10; idx++)
    {
        ptr = new List();
        ptr->numer = idx;
        if( idx != 0 )
        {      
            ptr->next = head;
            head = ptr;
        }
        else
        {
            head = ptr;
            ptr->next = NULL;
        }
    }
}

void Out()
{
    List* ptr = head;
    while(ptr)
    {
        cout << ptr->numer;
        cout << "\t";
        ptr = ptr->next;
    }
}

void Sort()
{
    List* ptr = head, *tmp = NULL, *prev = NULL;
    bool flag = false; 
    do
    {
        flag = false;
        ptr = head;
        while(ptr->next)
        {
            if(ptr->numer > ptr->next->numer)
            {
                if(ptr == head)
                {
                    tmp = ptr;
                    ptr = tmp->next;
                    tmp->next = ptr->next;
                    ptr->next = tmp;
                    head = ptr;
                    flag = true;                   
                }
                else
                {
                    tmp = ptr;
                    ptr = tmp->next;
                    tmp->next = ptr->next;
                    ptr->next = tmp;
                    prev->next = ptr;
                    flag = true;
                }
            }
            prev = ptr;
            ptr = ptr->next;
        }
    }
    while(flag);
}
Результат:

 
Код:
9       8       7       6       5       4       3       2       1       0
Sort List:
0       1       2       3       4       5       6       7       8       9

Для продолжения нажмите любую клавишу . . .
392
15 января 2015 года
cronya
421 / / 03.01.2009
а вообще должно быть так по уму))

Код:
#include <iostream>
#include <clocale>
#include <conio.h>

using std::cout;
using std::cin;
using std::endl;
using std::system;

class Node
{
public:
    int numer;
    int pos;
    Node* next;
    Node(){numer = 0; pos = 0; next = NULL;}   
};

class List
{
private:
    Node* head;
    int Length;
public:
    List(){head = NULL; Length = 0;}
    ~List()
    {
        Node* ptr = head, *tmp = NULL;
        if(head)
        {
            while(ptr->next)
            {
                tmp = ptr;
                delete[] ptr;
                ptr = tmp;
            };
            delete[] ptr;
        }
       
    }
    void Show(bool flag);
    void Add();
    void Delete();
    void Sort();
    void Clean();  
    bool Checker(int buf); 
};

void menu();
void Numeric(Node* head);

int main()
{
    setlocale(0,"Russian");
    menu();
    cout<<endl;
    system("pause");
    return 0;
}

void menu()
{
    List point;
    int buf = 0;
    do
    {
        system("cls");
        cout<<"Меню:"<<endl;
        cout<<"Односвязный список. Функции: создание, удаление, сортировка."<<endl;
        cout<<"Список возможных действий:"<<endl;
        cout<<"1 - Добавление элемента в список"<<endl;
        cout<<"2 - Удаление элемента из списка"<<endl;
        cout<<"3 - Сортировка элементов в списке"<<endl;     
        cout<<"4 - Вывод списка"<<endl;
        cout<<"5 - Очистка списка"<<endl;
        cout<<"ESC - Выход"<<endl;    
        cout<<"Выберите действие:"<<endl;
        switch (_getch())
        {
        case 49:
            cout<<endl;
            cout<<"Добавление элемента в список."<<endl;
            point.Add();   
            break;
        case 50:
            cout<<endl;
            cout<<"Удаление элемента из списка."<<endl;
            point.Delete();
            break;
        case 51:
            cout<<endl;
            cout<<"Сортировка элементов в списке."<<endl;
            point.Sort();
            break;
        case 52:
            cout<<endl;
            cout<<"Вывод списка."<<endl;
            point.Show(false);
            break;
        case 53:
            cout<<endl;
            cout<<"Очистка списка."<<endl;
            point.Clean();         
            break;
        case 27://ESC button           
            exit(0);
            break;
        default:
            break;
        }
    }
    while(true);
}

void List::Add()
{
    int buf = -1;  
    cout<<"Введите цифру: ";
    cin.clear();
    cin.sync();
    cin >> buf;
    if(!Checker(buf))  
    {
        if(head == NULL)
        {
            Node* ptr = NULL;
            ptr = new Node;
            ptr->numer = buf;
            ptr->next = NULL;
            head = ptr;
        }
        else
        {
            Node* ptr = NULL;
            ptr = new Node;
            ptr->numer = buf;
            ptr->next = head;
            head = ptr;
        }
        Length++;
        cout<<"Цифра - "<<buf<<" добавлена"<<endl;       
    }  
    cout<<endl;
    system("pause");
}

void List::Delete()
{
    if(head)
    {
        Show(true);
        int temp = -1;
        cout<<"Выберите элемент, введя его номер позиции: ";
        cin.clear();
        cin.sync();
        cin >> temp;
        if(!Checker(temp))
        {
            if(temp > Length || temp == 0)
            {
                cout<<"Ввели неправильный номер элемента. Повторите ввод." << endl;
            }
            else
            {              
                Node* ptr = head, *tmp = NULL, *ToDel = NULL, *prev = NULL;
                int position = 0, Value = 0;
                while(ptr)
                {
                    if(ptr->pos == temp)
                    {
                        ToDel = ptr;
                        Length--;
                        position = ptr->pos;
                        Value = ptr->numer;
                        break;
                    }
                    else
                    {
                        prev = ptr;
                        ptr = ptr->next;
                    }
                };
                if(ToDel)
                {
                    if(ToDel == head)
                    {
                        tmp = ToDel->next;
                        delete[] ToDel;
                        head = tmp;
                    }
                    else
                    {
                        if(ToDel->next == NULL)
                        {
                            delete[] ToDel;
                            prev->next = NULL;
                        }
                        else
                        {
                            prev->next = ToDel->next;
                            delete[] ToDel;
                        }
                    }
                    cout<<"Элемента списка под номером {" << position <<") " << Value <<"} удален успешно."<<endl;
                }

            }
        }
        cout<<endl;
        system("pause");
    }
}

void List::Sort()
{  
    Node* ptr = head, *tmp = NULL, *prev = NULL;
    bool flag = false;
    if(head)
    {
        do
        {
            flag = false;
            ptr = head;
            while(ptr->next)
            {
                if(ptr->numer > ptr->next->numer)
                {
                    if(ptr == head)
                    {
                        tmp = ptr;
                        ptr = tmp->next;
                        tmp->next = ptr->next;
                        ptr->next = tmp;
                        head = ptr;
                        flag = true;                  
                    }
                    else
                    {
                        tmp = ptr;
                        ptr = tmp->next;
                        tmp->next = ptr->next;
                        ptr->next = tmp;
                        prev->next = ptr;
                        flag = true;
                    }
                }
                prev = ptr;
                ptr = ptr->next;
            }
        }
        while(flag);       
        cout<<"Список отсортирован."<<endl;
    }
    else
        cout<<"Список пуст. Сортировать нечего."<<endl;
    cout<<endl;
    system("pause");
}

void List::Show(bool flag)
{  
    cout<<"Текущий список:"<<endl;
    Node* ptr = head;
    if(!flag)
    {
        if(head == NULL)
        {
            cout<<"Список пуст."<<endl;
        }
        while(ptr)
        {      
            cout<<ptr->numer<<"\t";
            ptr=ptr->next;
        }
        cout<<endl;
        system("pause");
    }
    else
    {
        if(head == NULL)
        {
            cout<<"Список пуст."<<endl;
        }
        else
        {          
            Numeric(head);
            while(ptr)
            {
                cout<<ptr->pos<<") ";
                cout<<ptr->numer<<endl;
                ptr=ptr->next;
            }      
        }
    }
   

}

bool List::Checker(int buf)
{
    bool flag = false;
    if(buf == -1 || buf < 0)
    {
        cout<<"Введена не цифра. Повторите ввод." << endl;
        flag = true;           
    }
    else flag = false; 
   
    return flag;
}

void List::Clean()
{
    Node* ptr = head, *tmp = NULL;
    if(head)
    {
        while(ptr->next)
        {
            tmp = ptr->next;
            delete[] ptr;
            ptr = tmp;
        }
        delete[] ptr;
        head = NULL;
        Length = 0;
        cout<<"Список успешно очищен."<<endl;
    }
    else
    {
        cout<<"Список пуст. Нечего очищать."<<endl;
    }
    cout<<endl;
    system("pause");
}

void Numeric(Node* head)
{
    Node* ptr = head;
    int idx = 1;
    while(ptr)
    {
        ptr->pos = idx;
        idx++;
        ptr=ptr->next;
    }
}
исходник внутри
Прикрепленные файлы:
19 Кб
Загрузок: 316
88K
15 января 2015 года
Andrey_Gers
2 / / 14.01.2015
Спасибо огромное

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог