Материал: Larin_Anton_AiSD_21_2

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра МО ЭВМ

отчет

по лабораторной работе №2

по дисциплине «АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ»

Тема: Иерархические списки

Санкт-Петербург

2019

Цель работы.

Научится работать с иерархическими списками, изучить способ их реализации, решить с их помощью рекурсивную задачу

Основные теоретические положения.

Рассмотрим для начала работы обычных линейных однонаправленных списков

Список - некоторый упорядоченный набор элементов любой природы.

Линейный однонаправленный (односвязный) список - список, каждый элемент которого хранит помимо значения указатель на следующий элемент. В последнем элементе указатель на следующий элемент равен NULL (константа нулевого указателя).

Иерархические списки отличаются от линейных тем, что элементы такого списка могут представлять из себя как значения(атомы), так и другие иерархические списки. Из данного определения очевидно что обработка подобных списков наиболее удобна при помощи рекурсивных алгоритмов.

Представлять иерархические списки в программе удобнее в виде структуры из двух указателей – элемент(атом/список) и на другую структуру списка

Например иерархический список вида (1 (2 3) 4) будет иметь следующее представление

Задание

Вар.13

Вычислить глубину (число уровней вложения) иерархического списка как максимальное число одновременно открытых левых скобок в сокращённой скобочной записи списка; принять, что глубина пустого списка и глубина атомарного S-выражения равны нулю; например, глубина списка (a (b ( ) c) d) равна двум

Реализация

В основной функции main последовательно происходит:

Вызов функций parseArgs, которая обрабатывает аргумента командной строки;

Затем, если требуется, открытие файлов на вход и выход;

Вызов функции read_lisp для считывания данных из потока ввода (либо автоматический сгенерированных функцией awtoInput) в переменную типа lisp

Иерархический список посылается в рекурсивную функцию maxDepth, которая вычесляет глубину его вложенности

Результат выводится в консоли или в файл.

Программа поддерживает настройку при помощи параметров из командной строки. Получить информацию от них можно аргументом «-h»

Они следуюшие:

-h help

-A [N] Автоматическое тестирование на списках глубины 0 — N-1 (N=1 по умолчанию; игнорирует параметры -i и -r при вводе)

-r Дает выбор перезапустить программу после исполнения. Не совместимо с «-i/-A»

-i [file] Ввод из файла file, вместо стандартного потока stdin («in» по умолчанию)

-o [file] Вывод в файл file вместо стандартного потока stdout («out по умолчанию»)

Работа рекурсивной функции maxDepth:

Данная функция получает на вход иерархический список.

Если списак пуст либо является атомом — его глубина 0;

Иначе при помощи стандартного алгорится поиска максимума происходит вычисление глубины всех подсписков(либо атомов) данного списка. Возвращяется наибольшая глубина подсписка +1(с учетом тек.)

Тесты.

0.

Input:

1

Inter=results:

Depth:

0

1.

Input:

( 1 )

Inter=results:

( 1 )

1

Depth:

1

2.

Input:

( ( 1 ) ( 1 ) )

Inter=results:

( ( 1 ) ( 1 ) )

( 1 )

1

( 1 )

1

2

Depth:

2

3.

Input:

( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) )

Inter=results:

( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) )

( ( 1 ) ( 1 ) )

( 1 )

1

( 1 )

1

2

( ( 1 ) ( 1 ) )

( 1 )

1

( 1 )

1

2

( ( 1 ) ( 1 ) )

( 1 )

1

( 1 )

1

2

3

Depth:

3

4.

Input:

( ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) )

Depth:

4

5.

Input:

( ( ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ) ( ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ) ( ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ) ( ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ) ( ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ( ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ( ( 1 ) ( 1 ) ) ) ) )

Depth:

5

Выводы.

В результате работы была написана полностью рабочая программа решающая поставленную задачу при использовании изученных теоретических материалов. Программа было протестирована, результаты совпадают с контрольными из примеров в условии;

Приложение(листинг программы)

l_mod1_.cpp

#include <iostream>

#include <fstream>

#include <cstdlib>

#include <vector>

#include <sstream>

//#include "l_mod1_.h"

#include "l_intrfc_.h"

#define DEFAULT_IFILE_NAME "in"

#define DEFAULT_OFILE_NAME "out"

#define printStr(str) cout<<(str)

using namespace std;

istream *inFile = NULL;

bool readFromFile= false;

ostream *outFile = NULL;

bool printToFile= false;

bool repeat= false;

bool awto = false;

int awtoLim = 0;

void help(){

cout<<"-h\t\thelp\n";

cout<<"-A [N]\t\tAuto testing with 0 to N vector length (ignores -i and -r)\n";

cout<<"-r\t\tchose to repeat input after compliton. Incompatable with \"-i\"!\n";

cout<<"-i [file]\t input from file (\""<<DEFAULT_IFILE_NAME<<"\" by default)\n";

cout<<"-o [file]\t output to file (\""<<DEFAULT_OFILE_NAME<<"\" by default)\n";

}

void setIFile(istream* istr){

//cin.rdbuf()

cin.rdbuf((*istr).rdbuf());

//inFile=istr;

}

void setOFile(ostream* ostr){

cout.rdbuf((*ostr).rdbuf());

//outFile=ostr;

}

int parseArgs(int argc, char** argv, string &iFileName, string &oFileName); //Parses arguments. Returns 1 if program is to be closed

using namespace h_list;

int maxDepth(const lisp s, int recLvl = 0); // Ищет максимальную глубину вложений иерархического списка

string genHL(int lvl);//Get generated string Hierarch-List of depth lvl

int awtoInput(lisp &s1);//Auto testing

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

string iFileName;

string oFileName;

ofstream oFile;

ifstream iFile;

if(parseArgs(argc,argv,iFileName,oFileName))return 0;

if (printToFile){

oFile.open(oFileName,ios::out);

if(!oFile){

printStr("Cannot open file: "+oFileName+"\n");

return 1;

}

setOFile(&oFile);

}

if (readFromFile){

iFile.open(iFileName);

if(!iFile){

printStr("Cannot open file: "+iFileName+"\n");

return 1;

}

setIFile(&iFile);

}

//Variables

lisp s1;

int _depth; //Result container

do {

//Input

if (awto) {

awto = !awtoInput(s1);

} else {

cout << "Enter hierarchical list(bound wihh brackets. Any standalone symbol is interpritet as an atom):"

<< endl;

read_lisp(s1);

}

//Echo

cout << "Input: " << endl;

write_lisp(s1);

cout << endl;

//Process and print

cout << "Inter=results:\n";

_depth = maxDepth(s1);

cout << "Depth: \n" << _depth << endl;

//Checks

if(repeat)

{

printStr("\nRepeat? [1-Yes|0-No]\n");

cin.clear();

int t=0;

cin >> t;

repeat = t;

}

cout<<endl;

} while (repeat || awto);

return 0;

}

int parseArgs(int argc, char** argv, string &iFileName, string &oFileName){

//Run through all arguments looking for matches. Wrong keys are ignored. Wrong values leads to an undefined behaviou.

int i=1;

while(i<argc){

//if(argc>1){

if(!((string)argv[i]).compare("-h")){

help();

return 1;

} else if(!((string)argv[i]).compare("-i")){

readFromFile=true;

if(i!=argc-1 && argv[i+1][0]!='-'){

iFileName=(string)argv[i+1];

i++;

} else iFileName = DEFAULT_IFILE_NAME;

i++;

} else if(!((string)argv[i]).compare("-o")){

printToFile=true;

if(i!=argc-1 && argv[i+1][0]!='-'){

oFileName=(string)argv[i+1];

i++;

} else oFileName = DEFAULT_OFILE_NAME;

i++;

} else if(!((string)argv[i]).compare("-r")){

repeat=true;

i++;

}

else if(!((string)argv[i]).compare("-A")){

awto=true;

if(i!=argc-1 && argv[i+1][0]!='-'){

awtoLim=atoi(argv[i+1]);

i++;

} else awtoLim = 1;

i++;

} else i++;

}

if(awto && (readFromFile||repeat)){

printStr("Warning! -A is incompatable with -r and -i. These are ignored!\n");

readFromFile=repeat=false;

}

if((readFromFile||printToFile)&&repeat){

repeat=false;

printStr("Warning! -i and -o are incompatable with -r. -r is ignored!\n");

}

return 0;

}

int maxDepth(const lisp s, int recLvl)

{

int depth;// for temporary depth containing

if(isNull(s)||isAtom(s)){return 0;} // null and atom elements has zero depth

else

{

lisp l = s; //Initial node

for(int i = 0;i<recLvl;i++)cout<<"\t"; //Inter-result

write_lisp(l);

cout<<endl;

int _maxDepth=maxDepth(l->node.pair.hd,recLvl+1); //Look for max child element depth

while(!isNull(l->node.pair.tl)) //Hence running through all sub-elements

{

l=l->node.pair.tl; //Take next node

depth=maxDepth(l->node.pair.hd,recLvl+1); //Take depth of current element

_maxDepth=depth>_maxDepth?depth:_maxDepth; //Default max algo

}

for(int i = 0;i<recLvl;i++)cout<<"\t";cout<<_maxDepth+1<<endl; //Inter-result

return _maxDepth+1;//Current depth is max child depth + self(another 1)

}

}

string genHL(int lvl){

if(lvl)

{

string s = "( ";

for(int i = 0;i<lvl; i++){

s+=genHL(lvl-1);

s+=" ";

}

s+=" )";

return s;

}else{

return ((string)"1");

}

}

int awtoInput(lisp &s1){

static int n = 0;

string strg = genHL(n);

istringstream strst(strg);

cin.rdbuf(strst.rdbuf());

read_lisp(s1);

n++;

if(n>awtoLim)return 1;

else return 0;

}

l_impl_.cpp

#include <iostream>

#include <cstdlib>

#include "l_intrfc_.h"

//#include "l_mod1_.h"

#ifndef INS

#define INS cin

#endif

using namespace std;

#ifndef PRINT(str)

#define PRINT(str) (cout << str)

#endif

namespace h_list

{

//....................................

lisp head (const lisp s)

{// PreCondition: not null (s)

if (s != NULL) if (!isAtom(s)) return s->node.pair.hd;

else { cerr << "Error: Head(atom) \n"; exit(1); }