9 8 7 6 5 4 3 2 1 0
Sort List:
0 1 2 3 4 5 6 7 8 9
Для продолжения нажмите любую клавишу . . .
Проблемы с функцией сортировки односвязного списка по возрастанию. С++.
Имеется односвязный список. Сделал функции создания и удаления элементов в списке. Проблемы с функцией сортировки односвязного списка по возрастанию.
Подскажите пожалуйста какой код необходим в
Код:
#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");
}
#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)
{
}
{
}
Вопрос: Зачем односвязному списку конец хранить в памяти????
Должно быть так:
Результат:
Должно быть так:
Код:
#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);
}
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);
}
Код:
а вообще должно быть так по уму))
исходник внутри
Код:
#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;
}
}
#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;
}
}
Спасибо огромное