Например, формула
(а+b/с)*(d-e*f)
постфиксную (ПОЛИЗ - польская инверсная запись): abc/+def*-*.
Рассмотрим пример использования динамических структур данных(стек). По введенной формуле необходимо построить cc ПОЛИЗ. (При записи формулы используются только операции +, —, *, / и буквы - операнды.)
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <windows.h>
#define ZNAK (c=='*' || c=='/')
char buf[256];
char *rus(char *t)
{CharToOem(t,buf);
return buf;
}
struct Info
{char i;
};
struct LIFO{
//char d;//
Info d;
LIFO *next;
};
LIFO * first(Info d); //Формирование 1 элемента очереди
void add(LIFO **top, Info d);
Info del(LIFO **top);
//--.------...----------...--..-.....-----.-....--
void main()
{ char s[50], sl[80], c;
Info d;
int er, i, l, k=0;
LIFO *st=NULL;
puts(rus("Введите инфиксную запись формулы, операндами в которой"));
puts(rus("являются буквы, а знаками - символы +, -, *, /"));
gets(s) ;
l=strlen(s);
d.i='(';
st=first(d); // заносим '(o в стек и
for(i=0; i<l; i++) // просматриваем выражение слева направо
if(isalpha(s[i]))
sl[k++]=s[i]; // операнд заносим т выходной массив
else if(s[i] == '('){d.i='('; add(&st, d);} // '(' кладется а стек
else if(s[i]==')')
while((c=del(&st).i)!= '(')
sl[k++]=c;// извлекаем из стека все до ближай-
// шей'(', которую тоже удаляем из стека
else switch(s[i]) /* : когда в записи формулы встречается знак операции - не скобка и не операнд - то с вершины стека из-извлекаются (до ближайшей скобки, которая сохраняется в стеке) знаки операций, старшинство которых больше или равно старшинству данной операции, и они заносятся в выходной массив, после чего рассматриваемый знак заносится в стек.*/
{
case '+' : case '-':
while((st->d).i!='(')
sl[k++]=del(&st).i;
d.i=s[i];
add(&st, d); break;
case '*':case '/':
while((st->d).i!='(')
{ if(!ZNAK)break;
sl[k++]=del(&st).i; }
d.i=s[i];
add(&st, d); break;
default:printf(rus("Неверный символ s[%d]: %с !"), i+1, s[i]);
exit(1);}
// в заключение выполняются такие же действия, как если бы встре-
// тилась закрывающая скобка
while((c=del(&st).i) !='(') sl[k++]=c;
sl[k]='\0';
puts(rus("\n\t\tПОЛИЗ:\n\n\t")) ; puts(sl) ;
}
// Начальное формирование очереди
LIFO *first(Info d)
{LIFO *pv = new LIFO;
pv->d = d;
pv->next = 0;
return pv;
} //.-.---.----------------------------------------
// Добавление в конец
void add(LIFO **top, Info d)
{LIFO *pv = new LIFO;
pv->d = d;
pv->next = *top;
*top = pv;
} //--.-------------------------.------------..---.-
// Выборка
Info del(LIFO **top)
{Info temp = (*top)->d;
LIFO *pv = *top;
*top = (*top)->next;
delete pv;
return temp;}
Кольцевой список отличается от линейного тем, что в односвязном варианте элементом, следующим за последним, считается первый элемент списка; в двусвязном варианте элементом, следующим за последним, считается первый, а элементом, предшествующим первому, считается последний. Графически кольцевой список можно представить следующим образом (рис. 9.2):
Линейный двусвязный список отличается от односвязного только тем, что в данном случае элемент связан не только со следующим элементом, но и с предыдущим. И первый, и последний элементы списка содержат признак конца списка. Извлечение и добавление элементов может происходить в любом месте списка.
Описание простейшего элемента:
struct Node{
тип d; // тип данных информационного поля
Node *next;
Node *prev;
};
Над списками можно выполнять следующие операции:
- начальное формирование списка (создание первого элемента);
- добавление элемента в конец списка;
- чтение элемента с заданным ключом;
- вставка элемента в заданное место списка (до или после элемента с заданным ключом);
- удаление элемента с заданным ключом;
- упорядочивание списка по ключу.
Программа, которая формирует список из фамилий и например группы крови(целое число 1 2 3 или 4), добавляет запись в список, удаляет запись из списка и выводит список на экран. Указатель на начало списка обозначен рbеg, на конец списка — pend, вспомогательные указатели — pv и pkey
Указатели, которые могут измениться (например, при удалении из списка последнего элемента указатель на конец списка требуется скорректировать), передаются по адресу
#include <iostream.h>
#include <conio.h>
#include<string.h>
struct info
{char fam[20];
int gr;
};
struct LIST
{
info d;
LIST *next;
LIST *prev;
} ;
// ... - ... ---.---- .---- ----- -..--...-.--...-
void vvod(info &d);
LIST * first(info d); //// Формирование первого элемента
void add(LIST **pend, info d); // Добавление в конец списка
LIST * find(LIST * const pbeg, char *key); // Поиск элемента по ключу
bool remove(LIST **pbeg, LIST **pend, char *key); // Удаление элемента
LIST * insert(LIST * const pbeg, LIST **pend, char *key, info d); // Вставка элемента
void sort(LIST **pbeg, LIST **pend);
void vyvod(LIST *pbeg);
//-. ... -. .--..--.-.---..----.------. -----.--
int main()
{char fam[20];
info d;
int i;
vvod(d);
LIST *pbeg = first(d); // Формирование первого элемента списка
LIST *pend = pbeg ; // Список заканчивается едва начавшись
// Добавление в конец списка четырех элементов 2 3 4 и 5
for (i = 0 ;i<3;i++)
{
vvod(d);
add(&pend,d);
}
// Вставка элемента 200 после элемента 2
vyvod(pbeg);
cout <<" posle Fam ";
cin>>fam;
vvod(d);
insert(pbeg ,&pend, fam, d);
vyvod(pbeg);
// Удаление элемента 5
cout <<" Fam dla delet ";
cin>>fam;
if(!remove (&pbeg, &pend ,fam)) cout<< "не найден" ;
vyvod(pbeg);
cout<<"do sort"<<endl;
for(i=0;i<2;i++)
{vyvod(pbeg);
if(!i){ cout<<"posle sort"<<endl;
sort(&pbeg,&pend);}}
cout<<"fam for find\n";
cin>>fam;
LIST *pv=pbeg;
do{
if(pv=find(pv,fam))
{cout << pv->d.fam<<' '<<pv->d.gr<<endl;
pv=pv->next;}
}while(pv);
return 0;
}
// ... -- ---. ---- -..-..-- ---.. --..---... --
void vvod(info &d)
{cout <<"Fam"<<endl;
cin>>d.fam;
cout<<"G r"<<endl;
cin>>d.gr;
}
void vyvod(LIST *pbeg)
{LIST *pv = pbeg;
while (pv){ // вывод списка на экран
cout << pv->d.fam<<' '<<pv->d.gr<<endl;
pv = pv->next;
}}
// Формирование первого элемента
LIST * first(info d)
{
LIST *pv= new LIST;
pv->d = d ;
pv->next = 0;
pv->prev = 0;
return pv;
}
//..-...-.....-...------ ---- --- --..----. --
// Добавление в конец списка
void add(LIST **pend, info d)
{
LIST *pv = new LIST;
pv->d = d;
pv->next= 0;
pv->prev = *pend;
(*pend)->next = pv;
*pend = pv;
} //-...----...----....--.---..-...-..--.......-----
// Поиск элемента по ключу
LIST * find(LIST * const pbeg, char *key)
{ LIST *pv = pbeg;
while (pv){
if(!strcmp(pv->d.fam,key))break;
pv = pv->next;
} return pv;
}
//..-----.-.....---..--.....--....------.-....----
// Удаление элемента
bool remove(LIST **pbeg, LIST **pend, char *key){
if(LIST *pkey = find(*pbeg, key)){ // 1
if (pkey == *pbeg)
{ // 2
*pbeg = (*pbeg)->next;
(*pbeg)->prev =0;
}
else if (pkey == *pend)
{ // 3
*pend = (*pend)->prev;
(*pend)->next =0;
}
else
{ // 4
(pkey->prev)->next = pkey->next;
(pkey->next)->prev = pkey->prev;
}
delete pkey;
return true; //5
}
return false; // 6
}
//..-----...------....------.......--I--......---.
// Вставка элемента
LIST * insert(LIST * const pbeg, LIST **pend, char *key, info d)
{ if(LIST *pkey = find(pbeg, key)){
LIST *pv = new LIST;
pv->d = d;
// 1 - установление связи нового узла с последующим:
pv->next = pkey->next;
// 2 - установление связи нового узла с предыдущим:
pv->prev = pkey;
// 3 - установление связи предыдущего узла с новым-
pkey->next = pv;
// 4 - установление связи последующего узла с новым
if( pkey!= *pend) (pv->next)->prev = pv;
// Обновление указателя на конец списка
// если узел вставляется в конец
else *pend = pv;
return pv;
} return 0;
}
//---------------
void sort(LIST **pbeg, LIST **pend)
{bool f;
LIST *pv,*pt,*pk=*pbeg;
while(pk)
{ pv=new LIST;
pv->d =pk->d;
pt = *pbeg;
f=true;
while (pt!=pk){ // просмотр списка
if ((pv->d).gr < (pt->d).gr ){ // занести перед текущим элементом (pt)
f=false;
pv->next = pt;
if (pt == *pbeg){ // в начало списка
pv->prev = 0; *pbeg = pv;}
else{ // в середину списка
(pt->prev)->next = pv;
pv->prev = pt->prev;}
pt->prev = pv;
//запоминаем указатель на следующий элемент
pt=pk->next;
//удаляем элемент pk
if(pk==*pend)//если он стоит в конце
{(pk->prev)->next=0;
*pend=pk->prev;}
else //если он стоит в середине
{(pk->prev)->next= pk->next;
(pk->next)->prev=pk->prev;
}
delete pk;
pk=pt;
break;
} pt = pt->next;
}
if(f) pk=pk->next;
}
}
Рассмотрим подробнее функцию удаления элемента из списка remove Ее параметрами являются указатели на начало и конец списка и ключ элемента, подлежащего удалению В строке 1 выделяется память под локальный указатель pkey, которому присваивается результат выполнения функции нахождения элемента по ключу find Эта функция возвращает указатель на элемент в случае успешного поиска и 0, если элемента с таким ключом в списке нет. Если pkey получает ненулевое значение, условие в операторе i f становится истинным (элемент существует), и управление передается оператору 2, если нет — выполняется возврат из функции со значением false (оператор 6).
Удаление из списка происходит по-разному в зависимости от того, находится элемент в начале списка, в середине или в конце В операторе 2 проверяется, находится ли удаляемый элемент в начале списка — в этом случае следует скорректировать указатель pbeg на начало списка так, чтобы он указывал на следующий элемент в списке, адрес которого находится в поле next первого элемента Новый начальный элемент списка должен иметь в своем поле указателя на предыдущий элемент значение О
Если удаляемый элемент находится в конце списка (оператор 3), требуется сместить указатель pend конца списка на предыдущий элемент, адрес которого можно получить из поля prev последнего элемента Кроме того, нужно обнулить для нового последнего элемента указатель на следующий элемент Если удаление происходит из середины списка, то единственное, что надо сделать, — обеспечить двустороннюю связь предыдущего и последующего элементов После корректировки указателей память из-под элемента освобождается, и функция возвращает значение true
Работа функции вставки элемента в список проиллюстрирована на рис 3 2 Номера около стрелок соответствуют номерам операторов в комментариях.
Сортировка связанного списка заключается в изменении связей между элементами Алгоритм состоит в том, что исходный список просматривается, и каждый элемент вставляется в новый список на место, определяемое значением его ключа
Ниже приведена функция формирована упорядоченного списка (предполагается, что первый элемент существует):
void add_sort(Node **pbeg, Node **pend, int d)
{ Node *pv = new Node; // добавляемый элемент
pv->d = d;
Node * pt = *pbeg;
while (pt){ // просмотр списка
1f (d < pt->d){ // занести перед текущим элементом (pt)
pv->next = pt;
if (pt == *pbeg){ // в начало списка
pv->prev = О; *pbeg = pv;}
e1se{ // в середину списка
(pt->prev)->next = pv;
pv->prev = pt->prev;}
pt->prev = pv:
return;
} pt = pt->next:
}
pv->next = 0; // в конец списка
pv->prev = *pend:
(*pend)->next = pv;
*pend = pv;
}
Бинарное дерево — это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева.
Приведем пример бинарного дерева . Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потомками. Высота дерева определяется количеством уровней, на которых располагаются его узлы.
Если дерево организовано таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева — больше, оно называется деревом поиска. Одинаковые ключи не допускаются. В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле. Такой поиск гораздо эффективнее поиска по списку, поскольку время поиска определяется высотой дерева, а она пропорциональна двоичному логарифму количества узлов.
Рассмотрим работу с бинарным деревом (в котором у каждого узла может быть только два приемника - левый и правый сын). Необходимо уметь:
построить дерево;
выполнить поиск элемента с указанным значением в узле;
удалить заданный элемент;
обойти все элементы дерева (например, чтобы над каждым из них провести некоторую операцию).
Обычно бинарное дерево строится сразу упорядоченным, т.е. узел левого сына имеет значение меньшее, чем значение родителя, а узел правого сына - большее. Например, если приходят числа 17, 18, 6, 5, 9, 23, 12, 7, 8, то построенное по ним дерево будет выглядеть так (рис. 15.6).
Для того, чтобы вставить новый элемент в дерево, надо найти для него место. Для этого, начиная с корня, будем сравнивать значения узлов (Y) со значением нового элемента (NEW). Если NEW < Y, то пойдем по левой ветви; в противном случае - по правой. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это означает, что место под новый элемент найдено.
Путь поиска места для числа 11 покажем жирной линией.
При удалении узла из дерева возможны три ситуации:
а) исключаемый узел - лист (в этом случае надо просто удалить ссылку на данный узел);
б) из исключаемого узла выходит только одна ветвь;
в) из исключаемого узла выходят две ветви (в таком случае на место удаляемого узла надо поставить либо самый правый узел левой ветви, либо самый левый узел правой ветви для сохранения упорядоченности дерева).
Например, построенное ранее дерево после удаления узла 6 может стать таким (рис. 15.8).
Рассмотрим задачу обхода дерева. Существуют три способа обхода, которые естественно следуют из самой структуры дерева.
Обход слева направо: A, R, В (сначала посещаем левое поддерево, затем - корень и, наконец, правое поддерево).(5 6 7 8 9 11 12 17 18 23)
Обход сверху вниз: R, А, В (посещаем корень до поддеревьев).(17 6 5 9 7 8 12 11 18 23)
Обход снизу вверх: А, В, R (посещаем корень после поддеревьев). (5 8 7 11 12 9 6 17 23 18 )
Интересно проследить результаты этих трех обходов на примере записи формул в виде дерева.