Listy cykliczne i listy dwukierunkowe

Przyjmując następującą definicję elementu listy dwukierunkowej rozwiąż podane zadania.

struct elem

{

int dane;

elem *nast;

elem *poprz;

};

Zad 1 Zaimplementuj podstawowe operacje na listach dwukierunkowych:

• dodawanie elementu na początek listy

void insert(int x, elem *&lista)

• dodawanie elementu pomiędzy elementy a

i−1

, a

i

void insert(int x, int i, elem *&lista)

• usunięcie pierwszego elementu

int remove(elem *&lista)

• usunięcie i-tego elementu listy

int remove(int i,elem *&lista)

Zad 2 Lista dwukierunkowa może zostać „odwrócona” na dwa sposoby. Można pozmieniać wskaź-

niki we wszystkich elementach tak, aby dostać odwrotny porządek lub można pozostawić strukturę

listy bez zmian i parami pozamieniać dane elementów listy. Zaimplementuj te dwa sposoby.

void reverse(elem *&lista)
Zad 3 Napisz funkcję zmieniającą kierunek wskaźników (pole „nast”) w jednokierunkowej liście

cyklicznej. (Wskaźnik czoło będzie wskazywał na ten sam element).

void redirect(elem *w)
Zad 4 Napisz funkcję przekształcającą podaną listę jednokierunkową w listę cykliczną.
Zad 5 Załóżmy, że pole „dane” jest typu znakowego i może przechowywać znaki: ’+’, ’-’ (dwuar-

gumentowy), ’*’, ’/’, ’a’ - ’z’. Wówczas lista może reprezentować wyrażenie arytmetyczne w zapisie

przedrostkowym (w notacji polskiej).

Napisz funkcję, która wypisze w notacji tradycyjnej (w zapisie wrostkowym) wyrażenie arytme-

tyczne zapisane w liście w notacji polskiej.

string print(elem *lista)

Napisz funkcję sprawdzającą, czy lista reprezentuje poprawnie skonstruowane wyrażenie w takiej

beznawiasowej notacji.

bool accepts(elem *lista)

1