Zadanie z laboratorium programowania na Informatyce UW.
Zadanie 15 (termin wysylania rozwiazan: 21 maja 2008, godz. 23:59)
(Permutowanie napisu)
Napisz program, ktory wczyta z wejscia ciag znakow zakonczony koncem
wiersza oraz niepusty ciag liczb calkowitych zakonczony liczba zero,
ktorej nie uznajemy za czesc ciagu.
Nie znamy maksymalnej dlugosci zadnego z ciagow, wiec bedziemy je
przechowywac w strukturach listowych. Po listach bedziemy sie
poruszali cyklicznie - po liscie liczb w jednym kierunku a po
liscie znakow w dwoch kierunkach. Oznacza to, ze program bedzie sie
poslugiwal dwukierunkowa lista cykliczna znakow oraz jednokierunkowa
lista cykliczna liczb.
Po utworzeniu obu list, program powinien wypisac zawartosc ciagu
znakow, w kolejnosci wyznaczonej przez ciag liczb, rozpoczynajac
od pierwszego znaku i pierwszej liczby, zgodnie z nastepujacym
przepisem:
* wypisujemy aktualny znak
* usuwamy go z listy
* niech k bedzie aktualna liczba na liscie liczb
- jesli k jest wieksze od zera, to przesuwamy sie o k znakow do
przodu (wzgledem usunietego znaku) na liscie cyklicznej znakow
- jesli k jest mniejsze od zera, to przesuwamy sie o k znakow do
tylu (wzgledem usunietego znaku)
* zmieniamy k na nastepna liczbe (uwzgledniajac cyklicznosc listy)
Np. dla danych:
alamakota
3 -2 0
program powinien wypisac:
amlkataoa
A oto rozwiązanie:
#include
#include
#include
//Struktura dla znakow zasugerowana w zadaniu
typedef struct znak_el{
char znak;
struct znak_el * nastepny;
struct znak_el * poprzedni;
};
struct liczba_el {
int liczba;
struct liczba_el* nastepny;
};
int main (int argc, char *argv[])
{
//Inicjujemy
int liczba,kierunek,wynik,skok;
char znak;
struct znak_el *teraz_znak=NULL;
struct znak_el *start_znak=NULL;
struct znak_el *tmp_znak=NULL;
struct liczba_el *teraz_liczba=NULL;
struct liczba_el *start_liczba=NULL;
struct liczba_el *tmp_liczba=NULL;
wynik=scanf("%c",&znak);
if((znak!='r')&&(znak!='n')&&(wynik!=EOF))//jesli nie bylo znakow w pierwszym wierszu.
{
//pierwszy element ciagu znakow
start_znak=malloc(sizeof(struct znak_el));
start_znak->nastepny=start_znak;
start_znak->poprzedni=start_znak;
start_znak->znak=znak;
wynik=scanf("%c",&znak);
teraz_znak=start_znak;
while((znak!='r')&&(znak!='n')&&(wynik!=EOF)) //wesole atrakcjie dla koncow znakow w roznych systemach.
{
teraz_znak->nastepny=malloc(sizeof(struct liczba_el));
teraz_znak->nastepny->poprzedni=teraz_znak;
teraz_znak->nastepny->nastepny=start_znak;
teraz_znak=teraz_znak->nastepny;
teraz_znak->znak=znak;
wynik=scanf("%c",&znak);
}
start_znak->poprzedni=teraz_znak; //Zapetlamy koncowke
//znaki powinny byc wczytane.
//wczytujemy liczby
wynik=scanf("%d",&liczba);
if((wynik!=EOF)&&(liczba!=0)) //Jesli sa liczby
{
start_liczba=malloc(sizeof(struct liczba_el));
start_liczba->nastepny=start_liczba;
start_liczba->liczba=liczba;
wynik=scanf("%d",&liczba);
teraz_liczba=start_liczba;
while((liczba!=0)&&(wynik!=EOF)) //dopoki....
{
teraz_liczba->nastepny=malloc(sizeof(struct liczba_el));
teraz_liczba->nastepny->nastepny=start_liczba;
teraz_liczba=teraz_liczba->nastepny;
teraz_liczba->liczba=liczba;
wynik=scanf("%d",&liczba);
}
teraz_znak=start_znak;
teraz_liczba=start_liczba;
//OK. Powinno byc wczytane, Trzeba wypisac.
//I teraz trzeba wypisac!!
while(teraz_znak->nastepny!=teraz_znak) //Jesli jest wiecej niz jeden znak w liscie
{
//dopoku nie zostal jeden znak na liscie.
//wypisujemy,
printf("%c",teraz_znak->znak);
//usuwamy
tmp_znak=teraz_znak;
teraz_znak->poprzedni->nastepny=teraz_znak->nastepny;
teraz_znak->nastepny->poprzedni=teraz_znak->poprzedni;
//ustalamy wlasnosci skoku
if(teraz_liczba->liczba>0)
{
kierunek=1;
skok=teraz_liczba->liczba;
}
else
{
kierunek=-1;
skok=teraz_liczba->liczba*-1;
}
teraz_liczba=teraz_liczba->nastepny;
//teraz wlasciwy skok.
while(skok>0)
{
if(kierunek==1)
{
//skok do przodu
teraz_znak=teraz_znak->nastepny;
}
else
{
//skok do tylu
teraz_znak=teraz_znak->poprzedni;
}
skok+=-1;
}
//przesunieto nastepny znak do wypisania.
//faktyczne usuwanie znaku.
free(tmp_znak);
}
//dobrze. W tej chwili powinien zostac jeden znak w liscie.
printf("%cn",teraz_znak->znak);
free(teraz_znak);
//no dobrze, ale tez byloby milo po sobie posprzatac. zostaly nam liczby..
while(teraz_liczba->nastepny!=start_liczba)
{
tmp_liczba=teraz_liczba;
teraz_liczba=teraz_liczba->nastepny;
free(tmp_liczba);
}
}
else
{
//Szwindel. Nie bylo liczb.
return 2;
}
}
else
{
//Szwindel. Nie bylo znakow.
return 1;
}
return 0;
}