Программирование символьных списков

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

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

// базовый класс Dlink, содержащий основные методы обработки записей списка

#ifndef DLINK

#define DLINK

class Dlink {

protected:

Dlink* next; // адрес следующей записи

Dlink* prev; // адрес предыдущей записи

public:

Dlink(); // инициализация ссылок

Dlink* append(Dlink*); // добавить новую запись

Dlink* incr(); // получить адрес следующей записи

Dlink* decr(); // получить адрес предыдущей записи

void excluse(); // исключить запись

Dlink* after(Dlink*); // вставить запись после текущей

Dlink* before(Dlink*); // вставить запись перед текущей

Dlink* tohead(void); // адрес начала списка

Dlink* tohead(int); // сдвиг в направлении начала списка

Dlink* totail(void); // адрес конца списка

Dlink* totail(int); // сдвиг в направлении конца списка

}; // Dlink

#endif

Исходный код методов класса Dlink специфицируется в файле dlink.ccи имеет следующий вид:

#include <stdio.h>

#include "dlink.h"

// init linked references

Dlink::Dlink() {

next=prev=NULL;

}

// инициализация адресов записей

Dlink* Dlink::incr() {

return(next);

}

// получить адрес предыдущей записи

Dlink* Dlink::decr() {

return(prev);

}

// добавить новую запись

Dlink* Dlink::append(Dlink* p) {

p->next=this;

if(this!= NULL)

prev = p;

return(p);

}

// исключить следующую запись

void Dlink::excluse() {

if(next!= NULL)

next->prev=prev;

if(prev!= NULL)

prev->next=next;

return;

}

// вставить запись после текущей

Dlink* Dlink::after(Dlink* p) {

p->next = next;

p->prev = this;

if(next!= NULL)

next->prev = p;

next = p;

return(p->next);

}

// вставить запись перед текущей

Dlink* Dlink::before(Dlink* p) {

p->next = this;

p->prev = prev;

if(prev!= NULL)

prev->next = p;

prev = p;

return(p->prev);

}

// получить адрес начала списка

Dlink* Dlink::tohead() {

Dlink* p = this;

Dlink* q = NULL;

while(p!= NULL) {

q = p;

p = p->prev;

} // while

return(q);

}

// перейти на n записей в направлении начала списка

Dlink* Dlink::tohead(int n) {

Dlink* p = this;

Dlink* q = this;

int i = 0;

while(p!= NULL) {

q = p;

if(i == n)

break;

p = p->prev;

i++;

}

return(q);

}

// получить адрес конца списка

Dlink* Dlink::totail() {

Dlink* p = this;

Dlink* q = NULL;

while(p!= NULL) {

q = p;

p = p->next;

} // while

return(q);

}

// перейти на n записей в направлении конца списка

Dlink* Dlink::totail(int n) {

Dlink* p = this;

Dlink* q = this;

int i = 0;

while(p!= NULL) {

q = p;

if(i == n)

break;

p = p->next;

i++;

} // while

return(q);

}

Компоненты базового класса Dlink могут наследоваться в различных производных классах. В данном случае методы класса Dlink будут наследоваться в производном классе двусвязного списка SymLink.

// Случайная перестановка строки символов

#include < stdio.h>

#include <stdlib.h>

#include "dlink.h"

// Класс элемент списка символов, производный от базового

// класса двусвязного списка

class SymLink: public Dlink {

private:

unsigned char sym; // код символа

public:

// инициализации кода символа и базовых адресов

SymLink(unsigned char c): Dlink(), sym(c) {};

// перегрузка базового метода incr

SymLink* incr() {return((SymLink*) Dlink::incr());};

// перегрузка базового метода deer

SymLink* deer() {return((SymLink*) Dlink::deer());};

SymLink* seek(int); // смещение указателя на заданное число элементов списка

int print(); // печать элементов списка

}; // SymLink

// метод сдвига к началу или к концу списка на n элементов

// в зависимости от знака аргумента

SymLink* SymLink::seek(int n) {

if(n > 0) // сдвиг к хвосту списка от текущего адреса базовы м методом totail

return((SymLink*) Dlink::totail(n));

if(n < 0) // сдвиг к началу списка от текущего адреса

return((SymLink*) Dlink::tohead(abs(n))); // базовым методом tohead

return(this); // нулевой сдвиг

} // Symlink::seek

// Печать и подсчет элементов от начала до конца списка

int SymLink::print() {

SymLink* p = this; // текущий адрес символа списка

SymLink* q; // адрес следующего символа списка

int n= 0; // счетчик символов

while(p!= NULL){ // цикл просмотра до конца списка

putchar(p->sym); // печать текущего символа списка

q = p->incr();// получить адрес следующего символа списка

p = q; // перейти к следующему символу списка

n++;// увеличить счетчик числа символов

}// while

return(n); // возврат числа напечатанных символов

} // SymLink::print

// основная функция

int main(int argc, char* argv[]) {

unsigned seed =0; // зерно псевдо-случайной последовательности

int count = 0; // счетчик случайных перестановок символов списка

int length; // длина списка символов

int ch; // код входного символа

unsigned pos; // смещение символа от начала списка

int side; // индекс сторожевого символа списка

SymLink* watch[2]; // адреса сторожевых символов в начале и конце списка

SymLink* head; // адрес начала списка символов

SymLink* tail; // адрес конца списка символов

SymLink* p, q; // текущие адреса символов списка

// массив адресов методов вставки символов

Dlink* (Dlink::* insert[])(Dlink*) = {&Dlink::after, SDlink::before};

if(argc >1) // получить зерно случайной последовательности символов

seed = atoi(argv[1]); // из аргумента командной строки вызова программы

// распределить сторожевые символы в начале и конце списка

watch[0] = head = new SymLink('\n'); // адресовать LF в начале списка

watch[1] = tail = new SymLink('\n'); / / адресовать LF в конце списка

tail ->before(head); // связка 2 сторожевых символов в пустой список

// распределить список символов из строки стандартного ввода

while((ch = getchar())!= '\n') { // ввод символа до LF

q = new SymLink(ch); // распределить элемент списка

tail->before(q); //вставить символ в конец списка перед концевым сторожем

} // while

// вывод исходного списка символов и подсчет его длины

if((length = head->print () - 1) < 2)

count = length; // блокировать обработку пустого списка

// случайное перемешивание символов в списке

srand(seed); // установить зерно псевдо-случайной последовательности

while(count < length) { // цикл перемешивания

side = rand() % 2; // случайный выбор начала или конца списка

while((pos = rand() % length) == 0); // случайный выбор символа в списке

printf("%*c\n", pos, '^'); // индикация выбора символа

q = head->seek(pos); // адресация выбранного символа

q->excluse(); // исключить выбранный символ из списка

(watch[side]->*insert[side])(q); // вставить его в начало или конец списка

head->print();// печать списка после перестановки символа

count++; // увеличить счетчик перестановок символов

} // while

// удалить список символов

р = tail;// адресовать конец списка

while(р!= NULL) { // цикл удаления списка от конца к началу

q = p->decr(); // фиксировать адрес предыдущего символа списка

p->excluse(); // исключить символ списка по текущему адресу

delete р; // освободить память исключенного символа списка

р = q; // адресовать предыдущий символ списка

} // while

return(length+1);// завершение программы возвратом длины списка

} // main

Варианты заданий для шестой лабораторной работы

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

Разработать объектно-ориентированную программу (ООП), которая в заданной строке символов переставляет каждый символ с максимальным кодом непосредственно перед ближайшим к нему символом с минимальным кодом без изменения взаимного расположения остальных символов. Исходная символьная строка должна передаваться программе через поток стандартного ввода. Результирующая символьная строка должна отображаться через поток стандартного вывода. В обеих строках все символы с максимальным и минимальным кодом должны указывать знаки ^. Разработка программы должна быть основана на использовании абстрактной структуры двунаправленного связанного списка с реализацией операций просмотра, удаления и вставки его элементов с использованием механизма наследования, который определяет базовый класс элемента абстрактного списка и использует производный класс элемента списка символов.

L01

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

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

L02

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

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

L03

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

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

L04

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

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

L05

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

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

L06

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

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

L07

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

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

L08

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

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

L09

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

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

L10

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

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

L11

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

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

L12

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

Разработать ООП для разделения любой заданной символьной строки на группы символов, коды которых заканчиваются одной цифрой в системе счисления по основанию 10. Входная символьная строка должны передаваться программе через поток стандартного ввода. Результат группировки символов должен отображаться строкой потока стандартного вывода, где все символы каждой группы расположены рядом, а под начальным символом каждой группы указана крайняя правая цифра его кода. Разработка программы должна быть основана на использовании абстрактной структуры двунаправленного связанного списка с реализацией операций просмотра, удаления и вставки его элементов с использованием механизма наследования, который определяет базовый класс элемента абстрактного списка и использует производный класс элемента списка символов.

L13

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

Разработать ООП для разделения любой заданной символьной строки на группы символов, коды которых заканчиваются одной цифрой в системе счисления по основанию 16. Входная символьная строка должны передаваться программе через поток стандартного ввода. Результат группировки символов должен отображаться строкой потока стандартного вывода, где все символы каждой группы расположены рядом, а под начальным символом каждой группы указана крайняя правая цифра его кода. Разработка программы должна быть основана на использовании абстрактной структуры двунаправленного связанного списка с реализацией операций просмотра, удаления и вставки его элементов с использованием механизма наследования, который определяет базовый класс элемента абстрактного списка и использует производный класс элемента списка символов.

L14

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

Разработать ООП для разделения любой заданной символьной строки на группы символов, коды которых заканчиваются одной цифрой в системе счисления по основанию 8. Входная символьная строка должны передаваться программе через поток стандартного ввода. Результат группировки символов должен отображаться строкой потока стандартного вывода, где все символы каждой группы расположены рядом, а под начальным символом каждой группы указана крайняя правая цифра его кода. Разработка программы должна быть основана на использовании абстрактной структуры двунаправленного связанного списка с реализацией операций просмотра, удаления и вставки его элементов с использованием механизма наследования, который определяет базовый класс элемента абстрактного списка и использует производный класс элемента списка символов.

L15

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

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

L16

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

Разработать ООП для разделения любой заданной символьной строки на группы символов, коды которых начинаются одинаковой цифрой в системе счисления по основанию 10. Входная символьная строка должны передаваться программе через поток стандартного ввода. Результат группировки символов должен отображаться строкой потока стандартного вывода, где все символы каждой группы расположены рядом, а под начальным символом каждой группы указана первая цифра его кода. Разработка программы должна быть основана на использовании абстрактной структуры двунаправленного связанного списка с реализацией операций просмотра, удаления и вставки его элементов с использованием механизма наследования, который определяет базовый класс элемента абстрактного списка и использует производный класс элемента списка символов.

L17

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

Разработать ООП для разделения любой заданной символьной строки на группы символов, коды которых начинаются одинаковой цифрой в системе счисления по основанию 16. Входная символьная строка должны передаваться программе через поток стандартного ввода. Результат группировки символов должен отображаться строкой потока стандартного вывода, где все символы каждой группы расположены рядом, а под начальным символом каждой группы указана первая цифра его кода. Разработка программы должна быть основана на использовании абстрактной структуры двунаправленного связанного списка с реализацией операций просмотра, удаления и вставки его элементов с использованием механизма наследования, который определяет базовый класс элемента абстрактного списка и использует производный класс элемента списка символов.

L18

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

Разработать ООП для разделения любой заданной символьной строки на группы символов, коды которых начинаются с одинаковой цифры системы счисления по основанию 8. Входная символьная строка должны передаваться программе через поток стандартного ввода. Результат группировки символов должен отображаться строкой потока стандартного вывода, где все символы одной группы расположены рядом, а под начальным символом каждой группы указана первая цифра его кода. Разработка программы должна быть основана на использовании абстрактной структуры двунаправленного связанного списка с реализацией операций просмотра, удаления и вставки его элементов с использованием механизма наследования, который определяет базовый класс элемента абстрактного списка и использует производный класс элемента списка символов.

L19

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

Разработать ООП для разделения любой заданной символьной строки на латинские буквы, десятичные цифры и знаки пунктуации. Заданная входная символьная строка должна передаваться программе через поток стандартного ввода. Результаты классифицирования ее символов должна отображать строка потока стандартного вывода, где все символы одного класса расположены рядом друг с другом. При этом первый символ каждого класса должен быть указан знаком ^. При разработке программы следует использовать абстрактную структуру двунаправленного связанного списка с реализацией операций просмотра, удаления и вставки его элементов с использованием механизма наследования, который определяет базовый класс элемента абстрактного списка и использует производный класс элемента списка символов.

L20

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