Исходные задания.
Задания
Дана строка длиной n (где n 32). Вывести ее на экран в противоположном порядке. Для решения данной задачи используйте двусвязные списки. Пример: ввод: «мама» ; вывод: «амам».
Пусть заданы линейные списки: список элементов В=<К1,К2,К3,…,Кn> и список ключей V= (целые числа, делящиеся на 12). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В.
Контрольные вопросы
Дайте понятие последовательного списка.
В каких случаях список считается упорядоченным? Является ли упорядоченной следующая числовая последовательность: 7720560445?
Укажите различия между одномерным, двумерным массивом и структурой, как способами организации данных.
Как можно произвести сортировку списка по возрастанию?
Как можно определить объем памяти, необходимый для размещения списка?
В чем принципиальные отличия выполнения основных операций в однонаправленных и двунаправленных списках?
С какой целью в программах выполняется проверка на пустоту однонаправленного (двунаправленного) списка?
С какой целью в программах выполняется удаление однонаправленного (двунаправленного) списка по окончании работы с ним? Как изменится работа программы, если операцию удаления списка не выполнять?
Программа на языке программирования C++.
№ 1:
#include <iostream>
using namespace std;
struct Element
{
// Данные
char data;
// Адрес следующего элемента списка
Element * Next , *Prev;
};
// Двусвязный список
class List
{
// Адрес головного элемента списка
Element * Head;
// Адрес головного элемента списка
Element * Tail;
public:
// Конструктор
List();
//Деструктор
~List();
// Добавление элемента в список
// (Новый элемент становится последним)
void Add(char data);
// (Распечатка в обратном направлении)
void PrintBack();
};
List::List()
{
// Изначально список пуст
Head = Tail = NULL;
}
List::~List() //Деструктор класса List
{
while (Head!=NULL) //Пока по адресу есть хоть что-то
{
Element *temp=Head->Next; //Сразу запоминаем указатель на адрес следующего элемента структуры
delete Head; //Освобождаем память по месту начала списка
Head=temp; //Меняем адрес начала списка
}
}
void List::Add(char data)
{
// создание нового элемента
Element * temp = new Element;
// заполнение данными
temp->data = data;
// следующий элемент отсутствует
temp->Next = NULL;
temp->Prev=NULL;
// новый элемент становится последним элементом списка
// если он не первый добавленный
if(Head!=NULL){
temp->Prev=Tail;
Tail->Next=temp;
Tail = temp;
}
// новый элемент становится единственным
// если он первый добавленный
else{
Head=Tail=temp;
}
}
void List::PrintBack()
{
// запоминаем адрес головного элемента
Element * temp = Tail;
// Пока еще есть элементы
while(temp != 0)
{
// Выводим данные
cout << temp->data;
// Переходим на следующий элемент
temp = temp->Prev;
}
cout << “nn”;
}
int main()
{
setlocale(LC_ALL,”Russian”);
// Создаем объект класса List
List lst;
cout<<“Введите строку:n”;
char s[255];
// Вводим строку
cin.getline(s,255);
// Определяем длину строки
int len = strlen(s);
// Загоняем строку в список
for(int i = 0; i < len; i++)
lst.Add(s[i]);
// Распечатываем содержимое списка в обратном направлении
lst.PrintBack();
system(“pause”);
return 0;
}
Описание использованных алгоритмов.
№ 1:
В данной программе реализован класс для работы с двунаправленным списком.
Структура узла:
Информационное поле типа char.
Указатели на следующий и предыдущий элемент.
Поля класса:
Head – указатель на первый элемент списка.
Tail – указатель на последний элемент списка.
Методы класса:
Конструктор
Деструктор
Добавление элемента в список
Распечатка в обратном направлении
№ 2
В данной программе реализован класс для работы с однонаправленным списком.
Структура узла:
Информационное поле типа char.
Указатели на следующий элемент.
Поля класса:
Head – указатель на первый элемент списка.
Tail – указатель на последний элемент списка.
Методы класса:
Конструктор
Деструктор
Добавление элемента в список
Поиск и вывод в списке элементов из заданного параметром другого списка.
Скриншоты работы программы.
№ 1:
№ 2:
Ответы на контрольные вопросы.
1.Последовательный список – это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться.
Последовательный список F, состоящий из элементов D1,D2,…,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически (см.рис.12).
D1 D2 D3 … Dn
Рис.12. Изображение линейного списка.
Например, F1=< 2,3,1>,F2=< 7,7,7,2,1,12 >, F3=< >. Длина списков F1, F2, F3 равна соответственно 3,6,0
2. Список считается упорядоченным, если каждый следующий элемент больше(меньше) текущего относительно некоторой операции сравнения.
3. Структура данных зависит от цели их обработки и специфики отражаемых реальных объектов или событий. В дальнейшем под структурой данных будет пониматься совокупность элементов данных, между которыми указаны связи (отношения). Связи между элементами устанавливают порядок доступа к ним в процессе обработки. Элементы данных размещаются в ячейках памяти, имеющих адреса.
Так как структура данных указывает на способ их организации в памяти компьютера, поэтому, как правило, под структурой данных подразумевают структуру хранения данных. Известны следующие типовые структуры данных: линейные (одномерный массив, двумерный массив), и нелинейные (списочные структуры, древовидные и сетевые).
Линейные одномерные массивы
Данная структура предполагает размещение элементов данных в непрерывной последовательности ячеек памяти компьютера
Наиболее важными из однородных (линейных) структур данных являются очередь и стек. Очередь содержит элементы, выстроенные друг за другом в цепочку, у которой есть начало и конец. Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала.
Двумерные массивы
Он применяется в том случае, если длина строки или столбца известны. Как правило, при обработке двумерных массивов известны и номера строк и номера столбцов (матрицы). Тогда для поиска нужного элемента достаточно указать номер строки и номер столбца.
Нелинейные структуры
Списочные структуры
Довольно часто данные в компьютере располагаются не в последовательных ячейках, а в произвольных частях памяти. Для того, что бы задать связь между различными элементами данных применяют указатели. В такой структуре первая ячейка содержит адрес первого элемента данных, вторая элемент данных и адрес следующего элемента данных и т.д. Последняя ячейка содержит элемент данных и указатель конца списка.
4. Сортировку списка по возрастанию можно произвести методом пузырька. Ведь при этом методе требуется обращаться только к двум рядом стоящим элементам списка, что очень удобно для такой структуры.
Организация:
Пусть в списке N элементов. В цикле от 1 до N-1 выполним проход списка от начала до предпоследнего элемента. В случае когда текущий элемент больше следующего, меняем их местами.
5. Пусть имеется список из N элементов. Узлом является структура вида:
struct Element
{
int data;
Element * Next ;
};
Такая структура занимает в памяти 8 байт. Значит весь список 8*(N+1) байт, учитывая память выделенную под указатель первого элемента списка.
6. Двунаправленный список отличается от однонаправленного, лишь наличием указателя на предыдущий элемент, а значит появляется возможность прохода списка в обратном направлении. При добавлении нужно указывать предыдущий элемент. При удалении перенаправлять обе связи, а не одну, как в случае с однонаправленным список.
7. Проверка на пустоту выполняется обычно при добавлении и удалении элементов.
Удалить из пустого списка нельзя.
При добавлении в непустой список, полю next элемента после, которого добавляем, присваивается значение добавляемого узла. В пустом списке такого элемента не существует и такая операция вызовет ошибку.
8 . Удаление списка по окончании работы производится с целью освободить оперативную память от ненужного мусора, ведь список уже не используется. Если не определить специальные процедуры удаления, то программа попытается удалить список, но удалив первый элемент, она не получит адреса следующего, а значит мусор в памяти останется.
Выводы о проделанной работе.
При выполнении данной работы я научился создавать классы для работы с однонаправленными и двунаправленными списками. Разобрался с их организацией в памяти и основными операциями(Добавления, Удаления, Вывода на экран, Поиска).