VPF::Односвязный список. Проблема с сортировкой.

AndreyGers

Дата 14.1.2015, 22:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 29.11.2014

Репутация: нет
Всего: нет

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

Код


#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)
{


}

feodorv

Дата 15.1.2015, 06:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(AndreyGers @ 14.1.2015, 22:31

)

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;
}

Уже здесь неправильно. Во-первых, не отслеживаются Head и Tail (а если Вы удаляете какого-то из них? Или даже оба, если в списке один-единственный элемент.) Во-вторых tempL никак не меняется в цикле, как указывал на Head до, так и указывает после smile

Цитата(AndreyGers @ 14.1.2015, 22:31

)

Подскажите пожалуйста какой код необходим в

Здесь по-разному можно действовать. Например, скопировав Head и Tail во временнные переменные, а им присвоив 0, далее отщеплять от старого (на который сейчас ссылаются временные переменные) списка по одному элементу и добавлять его в нужное (согласно сортировке) место нового списка (который Head и Tail).

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »