2 семестр / Пояснения к классу List

Рисунок

Пояснение

Случай 1. Надо поменять местами первый элемент и второй.

сначала меняем значение current->next на элемент через один.

Потом для следующего от текущего меняем значение указателя next на current.

Перерисуем после этих манипуляций список в новой последовательности. Видим, что указатели current и current_next надо поменять местами.

Поменяли значения указателей через темп.

Обозначили новый h. Одна перестановка завершилась успешно.

Сдвинули указатели на 1 узел вперед.

2 случай. Надо поменять два элемента, которые не в начале. Для грамотной замены потребуется наличие указателя на предыдуший перед обмениваемой парой элемент. Назовем его temp.

Теперь задаем новые значения next для temp и current.

тут же обновляем значение для current_next

Переставим элементы согласно связям. Видим, что current и current_next надо их поменять.

Поменяли значения указателей (не полей структуры).

Если список не закончился, сдвинулись к следующей тройке элементов.

struct subjs

{

int info, math, phys;

};

struct listelem

{

string group;

char *name;

int year;

subjs marks;

listelem* next;

};

В дальнейших примерах урезана структура listelem.

Вообще, элементы списка можно представить структурой или классом, как принадлежащими классу list, так и вне его. В ЛР предлагаю смешать оба варианта представления данных, чтобы повторить полученные ранее знания.

! Обратите внимание, что поле group представлено типом string, в то время как поле name все еще в стиле Си (указателем на массив символов).

bool s_year(listelem* a, listelem* b)

{

return (a->year > b->year);

}

bool s_name(listelem* a, listelem* b)

{

return (strcmp(a->name,b->name)>0);

}

Для простого примера возьмем 2 функции, принимающие на вход 2 указателя типа listelem, но сравнивающиеся только по одному полю.

Первая функция будет возвращать значение true, если значение года у элемента a больше значения года элемента b.

Вторая функция сравнивает результат, полученной функцией strcmp с 0. Напомню, что strcmp возвращает 1, если первый аргумент расположен относительно алфавитного порядка раньше второго аргумента, возвращает 0, если две строки равны, и -1, если первый аргумент расположен дальше по алфавиту, чем второй.

Указатель на функцию, передаваемый в другую функцию в качестве параметра будет выглядеть так: bool (*funk_name_formal)(listelem*, listelem*). Имя со звездочкой обязательно заключается в круглые скобки, иначе звездочка по синтаксису будет относиться к bool.

void list::sort(bool (*f)(listelem*, listelem*))

{

if (h != NULL && h->next!= NULL)//(size() > 1)

{

listelem *temp,*current,*current_next;

bool flag = true;

while (flag)

{

flag = false;

current = h;

current_next = current->next;

if (f(current, current_next)) //если надо поменять местами 2 элемента в начале списка, меняем их связи

{

h = current_next;

current->next= current_next->next;

current_next->next = current;

//ставим указатели на нужные места

temp = current;

current = current_next;

current_next = temp;

flag = true;

}

while (current_next->next != NULL)

{

//сохраняем предыдущий элемент, остальные сдвигаем

temp = current;

current = current_next;

current_next = current_next->next;

//меняем 2 элемента не в начале списка

if (f(current, current_next))

{

temp->next = current_next;

current->next=current_next->next;

current_next->next = current;

//ставим указатели на нужные места

temp = current;

current = current_next;

current_next = temp;

flag = true;

}

}

}

}

}

Метод sort будет принадлежать классу list, на вход будет принимать только «правило сортировки». Можно из тех, что мы создали сами, можно перегрузку бинарных операторов (если помните, они тоже принимают на вход 2 параметра, а возвращают булево значение).

Как уже было сказано, тривиальные случаи, когда список куст или состоит из одного элемента – не рассматриваются. Их исключаем первым if.

Далее объявляем необходимые переменные.

Внешний цикл сортировки будет по флагу (true значит «была перестановка»). Внутри него пробегаемся по массиву, перемещая «бОльший» элемент в конец.

Первую пару элементов всегда сравниваем отдельно.

Далее в цикле сравниваем все остальные пары элементов, сдвигаясь каждый раз на один элемент вперед.

В main остается только вызвать метод к списку с выбранным условием.

bool s_group_name(listelem* a, listelem* b)

{

bool fl = a->group > b->group;

if (a->group == b->group)

fl = strcmp(a->name, b->name) > 0;

return fl;

}

В качестве бонуса еще одна предикативная функция. Она упорядочивает по группам. Если группы равны, то упорядочивает по ФИО. Как не трудно заметить, если ФИО тоже будут равны, то порядок этих элементов по этому условию не изменится.

Чтобы работать с русским шрифтом нормально, исходный текстовый файлик должен быть сохранен с кодировкой ANSI. Поменять кодировку можно через «Сохранить как».

Структура моего упрощенного файла такова, что данные ФИО будут считываться построчно, остальные привычно до «белого символа» (пробела, перехода на новую строку, знака табуляции и т.п.).

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

#include <locale>

в main прописать первой строчкой

setlocale(LC_CTYPE, "");

Подключаем библиотеку <locale> , а в мейн прописать первой строчкой setlocale(LC_CTYPE, "");

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

Также в main

ifstream inFile("..\\spisok3.txt");

if (!inFile)

{

cout << "Can't open \"spisok3.txt\" \n";

exit(1);

}

fromfile(w, n, inFile);

inFile.close();

Для работы с файлами объявляем потоковую переменную для входного файла. Кстати, две точки в имени файла подсказывают компилятору, что надо подняться на директорию выше, и уже там (или оттуда) искать файл с данными.

Не забываем подключить библиотеку #include <fstream>

После использования файл закрываем.

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

void fromfile(list& L, int& n, ifstream& in)

{

char buf[80];

int i = 0;

n = 0;

listelem* temp;

while (!in.eof())

{

temp = new listelem;

in >> temp->group;

in.ignore(1, '\n');

in.getline(buf, 80, '\n');

temp->name = new char[strlen(buf) + 1];

strcpy_s(temp->name, strlen(buf) + 1, buf);

in >> temp->year;

in >> temp->marks.info >> temp->marks.math >> temp->marks.phys;

if (temp->group != "")

{

L.push_back(temp);

n++;

}

delete temp;

i++;

}

}

На вход функции подается список L, переменная n, отвечающая за количество элементов в списке (она не обязательная, т.к. размер списка мы всегда можем получить из класса) и файловая переменная in.

Данные будут считываться в переменную temp последовательно группами, пока не будет достигнут конец файла. Естественно, name у нас типа char*, значит и загрузка его должна происходить по-особому. Для работ некоторых функций понадобится библиотека

#include <string>

Год и оценки будут считываться как простые переменные.

Если данные по группе были считаны корректно, то добавляем эти данные в список. Эта проверка у меня сделана только для последней пустой строки, не более.

Как только информация об элементе добавлена, освобождаем память из под временного.

Всю эту функцию можно реализовать как метод, передав на вход лишь входной поток.

friend ostream& operator<<(ostream& out, list& L)

{

listelem* current = L.h;

while (current != NULL)

{

out << setw(10) << current->group << "\t" << current->name << "\t"

<< current->year << "\t"

<< current->marks.info << " "

<< current->marks.math << " "

<< current->marks.phys << " "<<"\t"<< endl;

current = current->next;

}

return out;

}

Пробегаемся по списку с первого элемента, формируя выходной поток с нужной информацией.

Для задания ширины, занимаемой выходной переменной, используется библиотека

#include <iomanip>

Печатается весь список!

В main

cout << w;

ofstream outFile("..\\result.txt");

if (!outFile)

{

cout << "Can't open \"result.txt\" \n";

exit(1);

}

outFile << "Исходный список\n" << w;

outFile.close();

Перегрузку мы можем использовать как для консоли, так и для файла («в стиле С++»). Список w будет одинаково выводиться в оба потока.

int main(void)

{

setlocale(LC_CTYPE, "");

list w, res;

int n;

ifstream inFile("..\\spisok3.txt");

if (!inFile)

{

cout << "Can't open \"spisok3.txt\" \n";

exit(1);

}

fromfile(w, n, inFile);

inFile.close();

w.print();

cout << endl << "Перегрузка <<" << endl;

cout << w;

ofstream outFile("..\\result.txt");

if (!outFile)

{

cout << "Can't open \"result.txt\" \n";

exit(1);

}

outFile << "Исходный список\n" << w;

w.sort(s_year);

//cout << w;

outFile <<"Отсортирован по году\n"<< w;

outFile << "Новый список без троешников\n";

res.new_list(w, is_no3);

res.sort(s_name);

outFile << "Отсортирован по ФИО\n" << res;

res.sort(s_group_name);

outFile << "Отсортирован по группе и ФИО\n" << res;

outFile.close();

cout << "\nПосмотрите результаты в\"result.txt\" \n";

system("pause");

return 0;

}

w – исходный список.

res – результирующий список без троешников.

Пример выходного файла: