Операции обработки списков

Базовыми операциями при обработке списков являются операции (функции): car, cdr, cons и atom.

Операция car в качестве аргумента получает список (указатель на начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент). Например:

· если X - список (2,6,4,7), то car(X) - атом 2;

· если X - список ((1,2),6), то car(X) - список (1,2);

· если X - атом то car(X) не имеет смысла и в действительности не определено.

Операция cdr в качестве аргумента также получает список. Ее возвращаемым значением является остаток списка - указатель на список после удаления из него первого элемента. Например:

· если X - (2,6,4), то cdr(X) - (6,4);

· если X - ((1,2),6,5), то cdr(X) - (6,5);

· если список X содержит один элемент, то cdr(X) равно nil.

Операция cons имеет два аргумента: указатель на элемент списка и указатель на список. Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель на получившийся список. Например:

· если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7);

· если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).

Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое значение: true - если ее аргумент является атомом, или false - если ее аргумент является подсписком.

В программном примере 5.1 приведена реализация описанных операций как функций языка C++. Структура элемента списка, обрабатываемого функциями этого модуля, определена в нем как тип Item и полностью соответствует рис.5.1. Помимо описанных операций в модуле определены также функции выделения памяти для дескриптора данных - NewAtom и для элемента списка - NewNode. Реализация операций настолько проста, что не требует дополнительных пояснений.

{==== Программный пример 5.1 ====}

// Элементарные операции для работы со списками

typedef struct Item* lpt; // указатель на элемент списка

struct Item

{

char typeflg; // Char =0 - узел, иначе - код типа

void* down; // указатель на данные или на подсписок

lpt next; // указатель на текущем уровне

};

// *** создание дескриптора для атома

lpt NewAtom(void* d, char t)

{

lpt l = new Item;

l->typeflg = t; // тип данных атома

l->down = d; // указатель на данные

l->next = NULL;

return l;

}

// *** создание элемента списка для подсписка

lpt NewNode(lpt d)

{

lpt l = new Item;

l->typeflg = 0; // признак подсписка

l->down = (void*)d; // указатель на начало подсписка

l->next = NULL;

return l;

}

// *** проверка элемента списка: true - атом, false - подсписок

bool Atom(lpt l)

{

if(l->typeflg == 0) return false; // проверка поля типа

else return true;

}

// *** выборка 1-го элемента из списка

lpt Car(lpt l)

{

return (Item*)l->down; // выборка - указатель вниз

}

// *** исключение 1-го элемента из списка

lpt Cdr(lpt l)

{

return l->next; // выборка - указатель вправо

}

// *** добавление элемента в начало списка

lpt Cons(lpt l1, lpt l)

{

lpt l2 = new Item(*l1); // элемент списка для добавляемого

l2->next = l; // в начало списка

return l2; // возвращается новое начало списка

}

// *** добавление элемента в конец списка

lpt Append(lpt l1, lpt l)

{

lpt l2 = new Item(*l1); // элемент списка для добавляемого

// если список пустой, то он будет состоять из одного эл-та

if(l==NULL) return l2;

else // выход на последний эл-т списка

{

lpt l3 = l;

while(l3->next) l3 = l3->next;

l3->next = l2; // подключение нового эл-та к последнему

return l; // функция возвращает тот же указатель

}

}

В примере 5.1 в модуль базовых операций включена функция Append - добавления элемента в конец списка. На самом деле эта операция не является базовой, она может быть реализована с использованием описанных базовых операций, без обращения к внутренней структуре элемента списка, хотя, конечно, такая реализация будет менее быстродействующей. В программном примере 5.2 приведена реализация нескольких простых функций обработки списков, которые могут быть полезными при решении широкого спектра задач. В функциях этого модуля, однако, не используется внутренняя структура элемента списка.

{==== Программный пример 5.2 ====}

// Вторичные функции обработки списков

// *** добавление в конец списка l нового элемента x

lpt Append(lpt x, lpt l)

{ // если список пустой, то добавить x в начало пустого списка

if(l == NULL) return Cons(x,l);

/* если список непустой

- взять тот же список без 1-го эл-та - cdr(l);

- добавить в его конец эл-т x;

- добавить в начало 1-й эл-т списка */

else return Cons(Car(l), Append(x,Cdr(l)));

}

// *** Реверс списка l; список q - результирующий, при первом

// вызове он должен быть пустым

lpt ListRev(lpt l, lpt q)

{ // если входной список исчерпан, вернуть выходной список

if(l == NULL) return q;

/* иначе: - добавить 1-й эл-т вх.списка в начало вых.списка,

- реверсировать, имея вх. список без 1-го эл-та,

а вых.список - с добавленным эл-том */

else return ListRev(Cdr(l), Cons(Car(l), q));

}

// *** Превращение разветвленного списка l в линейный; список q -

// результирующий, при первом вызове он должен быть пустым

lpt FlatList(lpt l, lpt q)

{ // если входной список исчерпан, вернуть выходной список

if(l == NULL) return q;

/* если 1-й эл-т вх. списка - атом, то

- сделать "плоской" часть вх. списка без 1-го эл-та;

- добавить в ее начало 1-й эл-т */

else if(Atom(Car(l)))

return Cons(Car(l), FlatList(Cdr(l), q));

/* если 1-й эл-т вх. списка - подсписок, то

- сделать "плоской" часть вх.списка без 1-го эл-та;

- сделать "плоским" подсписок 1-го эл-та */

else return FlatList(Car(l), FlatList(Cdr(l), q));

}

// *** вставка в список l элемента x на место с номером m

// (здесь и далее нумерация эл-тов в списке начинается с 0)

lpt InsList(lpt x, lpt l, int m)

{ // если m=0, эл-т вставляется в начало списка

if(m == 0) return Cons(x,l);

// если список пустой, он и остается пустым

else if(l == NULL) return NULL;

/* - вставить эл-т x на место m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т */

else return Cons(Car(l), InsList(x, Cdr(l), m-1));

}

// *** удаление из списка l на месте с номером m

lpt DelList(lpt l, int m)

{ // если список пустой, он и остается пустым

if(l == NULL) return NULL;

// если m=0, эл-т удаляется из начала списка

else if(m == 0) return Cdr(l);

// - удалить эл-т x на месте m-1 в список без 1-го эл-та;

// - в начало полученного списка вставить 1-й эл-т

else return Cons(Car(l), DelList(Cdr(l), m-1));

}

// *** перестановка в списке l эл-тов в местах с номерами m и m+1

lpt ExchngList(lpt l, int m)

{ // если список пустой, он и остается пустым

if(l == NULL) return NULL;

else if(m = 0)

// если m=0, а следующего эл-та нет, список остается без изменений

if(Cdr(l) == NULL) return l;

/* если m=0 (обмен 0-го и 1-го эл-тов):

- берется список без двух 1-х эл-тов - cdr(cdr(l));

- в его начало добавляется 0-й эл-т;

- в начало полученного списка добавляется 1-й эл-т - car(cdr(l)) */

else return Cons(Car(Cdr(l)), Cons(Car(l), Cdr(Cdr(l))));

else return Cons(Car(l), ExchngList(Cdr(l), m-1));

}

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

Функция Append добавляет элемент x в конец списка l. Рассмотрим ее выполнение на примере вызова: Append(4,(1,2,3)).

Поскольку аргумент-список не пустой, выполняется ветвь else. Она содержит оператор:

Append:=cons(car(l),Append(x,cdr(l)));

Важно точно представить себе последовательность действий по выполнению этого оператора:

· car(l) = 1

· cdr(l) = (2,3);

· Append(4,(2,3))) - при этом рекурсивном вызове выполнение вновь пойдет по ветви else, в которой:

· car(l) = 2;

· cdr(l) = (3);

· Append(4,(3))) - выполнение вновь пойдет по ветви else, в которой:

· car(l) = 3;

· cdr(l) = nil;

· Append(4,nil) - в этом вызове список-аргумент пустой, поэтому выполнится Append:=cons(4,nil) и вызов вернет список: (4);

· cons(car(l), Append(x,cdr(l))) - значения аргументов функции

· cons для этого уровня вызовов: cons(3,(4)) = (3,4);

· на этом уровне Append возвращает список (3,4);

· cons(car(l), Append(x,cdr(l))) - на этом уровне: cons(2,(3,4)) = (2,3,4);

· на этом уровне Append возвращает список (2,3,4);

· cons(car(l), Append(x,cdr(l))) - на этом уровне: cons(1,(2,3,4)) = (1,2,3,4);

· на этом уровне Append возвращает список (1,2,3,4).

Функция ListRev выполняет инвертирование списка - изменяет порядок следования его элементов на противоположный. При обращении к функции ее второй аргумент должен иметь значение nil. Пример: ListRev(1,(2,3),4),nil).

Входной список не пустой, поэтому выполнение идет по ветви else, где:

ListRev:=ListRev(cdr(l),cons(car(l),q));

Последовательность действий:

* cdr(l) = ((2,3),4);

* car(l) = 1;

* cons(car(l),q) = (1) - список q при этом - пустой;

* рекурсивный вызов ListRev(((2,3),4), (1)):

* cdr(l) = (4);

* car(l) = (2,3);

* cons(car(l),q) = ((2,3),1) - список q - (1);

* рекурсивный вызов ListRev((4), ((2,3),1)):

* cdr(l) = nil;

* car(l) = 4;

* cons(car(l),q) = (4,(2,3),1);

* рекурсивный вызов ListRev(nil, (4,(2,3),1)):

* поскольку исходный список пустой, вызов возвращает список: (4,(2,3),1);

* вызов возвращает список: (4,(2,3),1);

* вызов возвращает список: (4,(2,3),1);

* вызов возвращает список: (4,(2,3),1).

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

Для упрощения примера мы ввели следующие ограничения:

· вся арифметика - целочисленная;

· программа не проверяет правильность исходной записи;

· в выражении не допускается унарный минус.

{==== Программный пример 5.3 ====}

// Калькулятор. Вычисление арифметических выражений

typedef int* iptr;

typedef char* cptr;

// цифровые символы

const char Digits[] = {'0','1','2','3','4','5','6','7','8','9'};

// знаки операций с высоким приоритетом

const char Prty[] = { '*', '/' };

std::string s; // исходная строка

int n; // номер текущего символа в исх. строке

// *** Создание атома для Int

void NewInt(lpt& lll, std::string& st)

{

iptr ip;

int cc;

if(st.size() >0)

{ /* если в st накоплено цифровое представление числа, оно

переводится в тип integer, для него создается атом и

записывается в конец списка */

ip = new int;

*ip = atoi(st.c_str());

lll = Append(NewAtom(ip, 'I'), lll);

st.clear(); // накопитель строки сбрасывается

}

}

// *** Создание атома для Char

void NewChar(char s1, lpt& lll)

{ /* выделяется память для 1 символа, в ней сохраняется

значение s1,для него создается атом, записывается в конец списка */

cptr cp;

cp = new char;

*cp = s1;

lll = Append(NewAtom(cp, 'C'), lll);

}

// *** Представление исходной строки в списочной форме

lpt Create_List()

{ // исходный список пустой, накопитель строки - пустой

lpt lll = NULL; // указатель на начало текущего списка

char s1; // текущий символ строки

std::string st; st.clear(); // накопитель строки-операнда

while(n <= s.size()) // цикл до конца исходной строки

{

s1 = s[n];

n++;

switch(s1)

{ /* начало скобочного подвыражения: для него создается новый список - Creat_Lst, который оформляется как подсписок - NewNode и добавляется в конец текущего списка – Append */

case '(': lll = Append(NewNode(Create_List()), lll);

break;

/* конец скобочного выражения - последнее число в

скобках добавляется в конец текущего списка и текущий

список сформирован - конец функции */

case ')': {

NewInt(lll, st);

return lll;

break;

}

default: { // цифра или знак операции

bool flag = false;

// цифры накапливаются в st

for(int i=0; i<10; i++)

if(s1 = Digits[i]) flag = true;

if(flag)

{

st.insert(st.size(), &s1, 1);

}

else // знак операции

{ // созд. атом для ранее накопленного числа

NewInt(lll, st);

// созд. атом для знака

NewChar(s1, lll);

}

}

} // end switch

} // end while

NewInt(lll, st); // созд. атом для ранее накопленного числа

return lll;

}

// *** Выделение в подсписки высокоприоритетных операций

lpt FormPrty(lpt l)

{

lpt op1, op, op2, // 1-й операнд, знак, 2-й операнд

l2 = NULL, // выходной список пустой

l3;

cptr cp;

op1 = Car(l); // выделение 1-го операнда

l = Cdr(l);

// если 1-й операнд - подсписок то - обработка подсписка

if(!Atom(op1)) op1 = FormPrty(op1);

while(l) // до опустошения исходного списка

{

op = Car(l); // выделение знака операции

l = Cdr(l);

op2 = Car(l); // выделение 2-го операнда

l = Cdr(l);

// если 2-й операнд – подсписок, то - обработка подсписка

if(!Atom(op2)) op2 = FormPrty(op2);

/* если знак операции приоритетный, то создается подспи-

сок: 1-й операнд, знак, 2-й операнд, этот подсписок

далее является 1-м операндом */

if((*(cptr)op->down) == Prty[0] ||

(*(cptr)op->down) == Prty[1])

{

op1 = Cons(op1, Cons(op2, NULL));

}

else /* если знак неприоритетный, 1-й операнд и знак

записываются в выходной список, 2-й операнд далее

является 1-м операндом */

{

l2 = Append(op, Append(op1, l2));

op1 = op2;

}

}

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

return Append(op1, l2);

}

// *** Вычисление выражения

int Eval(lpt l)

{

lpt op1, op, op2;

op1 = Car(l); // выделение 1-го операнда

l = Cdr(l);

// если 1-й операнд – подсписок, то вычислить его выражение

if(!Atom(op1)) *((iptr)op1->down) = Eval(op1);

while(l)

{

op = Car(l); // выделение знака операции

l = Cdr(l);

op2 = Car(l); // выделение 2-го операнда

l = Cdr(l);

// если 2-й операнд – подсписок, то вычислить его выражение

if(!Atom(op2)) *((iptr)op2->down) = Eval(op2);

switch(*((cptr)op->down)) // выполнение операции, результат - в op1

{

case '+': *((iptr)op1->down) += *((iptr)op2->down); break;

case '-': *((iptr)op1->down) -= *((iptr)op2->down); break;

case '*': *((iptr)op1->down) *= *((iptr)op2->down); break;

case '/': if(*((iptr)op2->down))

*((iptr)op1->down) /= *((iptr)op2->down); break;

}

}

return *((iptr)op1->down); // возврат последнего результата

}

// *** Главная программа

int main()

{ lpt l;

char ch[256];

printf("> "); scanf("%s", ch); // ввод исходной строки

s.assign(ch, strlen(ch));

l = Create_List(); // формирование списка

l = FormPrty(l); // выделение приоритетных операций

// вычисление и печать результата

printf("%s = %d", s.c_str(), Eval(l));

return 0;

}

Выполнение программы состоит во вводе строки, представляющей исходное выражение и последовательных обращений к трем функциям: Creat_Lst, FormPrty и Eval.

Функция Creat_Lst преобразует исходную строку в список. В функции поэлементно анализируются символы строки. Различаемые символы: левая круглая скобка, правая скобка, знаки операций и цифры. Цифровые символы накапливаются в промежуточной строке. Когда встречается символ-разделитель - правая скобка или знак операции, накопленная строка преобразуется в число, для него создается атом с типом 'I' и включается в конец списка. Для знака операции создается атом с типом 'C' и тоже включается в конец списка. Левая скобка приводит к рекурсивному вызову Creat_Lst. Этот вызов формирует список для подвыражения в скобках, формирование списка заканчивается при появлении правой скобки. Для сформированного таким образом списка создается узел, и он включается в основной список как подсписок. Так, например, для исходной строки:

5+12/2-6*(11-7)+4

функцией Creat_Lst будет сформирован такой список:

(5,+,12,/,2,-,6,*,(11,-,7),+,4)

Следующая функция - FormPrty - выделяет в отдельные подсписки операции умножения и деления, имеющие более высокий приоритет, и их операнды. Функция просматривает список и выделяет в нем последовательные тройки элементов "операнд - знак - операнд". Если один из операндов является подсписком, то он обрабатывается функцией FormPrty. Если знак является одним из приоритетных знаков, то из тройки формируется подсписок, который становится первым операндом для следующей тройки. Если знак не приоритетный, то второй операнд тройки становится первым для следующей тройки. Список нашего примера после обработки его функцией FormPrty превратится в:

(5,+,(12,/,2),-,(6,*,(11,-,7)),+,4)

Наконец, функция Eval выполняет вычисления. Она во многом похожа на функцию FormPrty: в ней также выделяются тройки "операнд1 - 0знак - операнд". Если один или оба операнда являются подсписками, то сначала вычисляются эти подсписки и заменяются на атомы - результаты вычисления. Если оба операнда - атомы, то над ними выполняется арифметика, задаваемая знаком операции. Поскольку в первую очередь вычисляются подсписки, то подвыражения, обозначенные скобками в исходной строке, и операции умножения и деления выполняются в первую очередь. Для нашего примера порядок вычислений будет таков:

12 / 2 = 6; 5 + 6 = 11; 11 - 7 = 4; 6 * 4 = 24;

24 + 4 = 28; 11 - 28 = -17

Дата добавления: 2014-01-07