☰

» »

enojno povezan seznam -izpis nazaj

enojno povezan seznam -izpis nazaj

nastjaz ::

Zdravo!

Ima kdo kakšno idejo kako sprogramirat pri enojno povezanem seznamu izpis nazaj s prostorsko omejitvijo O(1),časovna O(n)?
Uporabi se kazalec na začetek in pomožni kazalec?

Lp

Genetic ::

Hja, z rekurzijo?

izpis_nazaj(Seznam s)
if (s.next != null) izpis_nazaj(s.next);
izpis(s.elt);

ragezor ::

tega se ne da brez da bi si ob prvem prehodu skozi list shranil elemente ali pointerje in jih potem izpisal v obratnem vrstnem redu.

rekurzija drzi vse v spominu.

Andrejpan ::

Kako točno si predstavljaš, da bi povezan seznam imel O(1) prostora?

technolog ::

Ne podatkovna struktura sama, ampak algoritem za iteriranje po njej, Andrej.

Kar se tiče pa originalnega vprašanja, je pa odgovor trivialen, le seznam mora bit v pravo smer povezan. Drugače se pa res ne da.

Zgodovina sprememb…

illion ::

če je to neko teoretično vprašanje, ki ti ga zastav profesor, potem je geneticov odgovor najbrž najboljši:)
v praksi pa ne, vsaj pri velikih seznamih..

Andrejpan ::

Naj si bo algoritem iteracija ali rekurzija, še vedno moreš vsak element obiskati, kar pomeni O(n) časa in prostora.

AndrejO ::

Bah, ste hecni. Govora je o povezanem seznamu.

Postopek je sledeč:

1) Začasen kazalec naj kaže na naslednji element (zacasni = trenutni->naslednji).
2) Naslednji element trenutnega naj kaže na predhodnega (trenutni->naslednji = predhodni)
3) Premakneš se na naslednji element (predhodni = trenutni, trenutni = zacasni)
4) Ponavljaj 1-3, dokler ne prideš do konca seznama.

Voila. Seznam obrnjen v časovni O(n), in prostorski O(1).

nastjaz ::

Dopolnite podatkovno strukturo enojno povezan seznam s funkcijo, ki obrne vrstni
red elementov v seznamu, pri čemer je lahko dodatna prostorska zahtevnost
konstantna, torej O(1).

To je originalno navodilo naloge, je pa naloga z izpita, torej bi se naj dalo =)

AndrejO bom implementirala v C++.
Hvala

Genetic ::

Eno je izpis nazaj, kjer sem predvideval, da se struktura seznama ne spremeni, drugo pa je obrniti vrstni red elementov v seznamu, tu se pa spremeni struktura in sicer tako, kot je AndrejO opisal.

nastjaz ::

Ampak kako je AndrejO uporabil predhodni?Če je enojni seznam imam samo začetek in naslednji.Povezave nazaj ni?
Kolikor se mi sveti bi AndrejO rad sproti obračal seznam ali?

Vesoljc ::

nastjaz je izjavil:

Ampak kako je AndrejO uporabil predhodni?Če je enojni seznam imam samo začetek in naslednji.Povezave nazaj ni?
Kolikor se mi sveti bi AndrejO rad sproti obračal seznam ali?


ja, sproti obraca. narisi si par korakov, bo prec jasno.
Abnormal behavior of abnormal brain makes me normal...

Utk ::

Mislim da nekdo ne loči obračanje podatkovne strukture od obračanja izpisa iz začetne strukture.

AndrejO ::

Utk je izjavil:

Mislim da nekdo ne loči obračanje podatkovne strukture od obračanja izpisa iz začetne strukture.

Nerelevantno.

Če ne želiš imeti na koncu izpisa "obrnjenega" seznama, ga pač še enkrat obrneš. To ne bo spremenilo ne časovne, ne prostorske kompleksnosti O za algoritem.

Za vajo izračunaj veliki O za O(n) + O(n) ter O(1) + O(1).

AndrejO ::

nastjaz je izjavil:

Ampak kako je AndrejO uporabil predhodni?Če je enojni seznam imam samo začetek in naslednji.Povezave nazaj ni?
Kolikor se mi sveti bi AndrejO rad sproti obračal seznam ali?

Da, pogruntal si. V O(n) obrneš seznam. Ko si ga obrnil ga lahko v naslednjih O(n) izpišeš - kar je seveda izpis elementov provtnega v obratnem vrstnem redu. Če Utk-ju ni všeč, da imaš na koncu "narobe" seznam, ga z istim postopkom še enkrat obrneš.

O(n) + O(n) + O(n) = ?

technolog ::

Če spreminjaš podatkovno strukturo (prepišeš podatke), se šteje, kot da si porabil tudi vsaj O(n) prostora.

To potem ni več algoritem s prostorsko zahtevnostjo O(1).

Moj odgovor je še vedno edini pravilen: Po enojno povezanem seznamu lahko iteriraš nazaj pod temi pogoji, samo če je seznam od zadaj naprej povezan.

Zgodovina sprememb…

AndrejO ::

technolog je izjavil:

Če spreminjaš podatkovno strukturo (prepišeš podatke), se šteje, kot da si porabil tudi vsaj O(n) prostora.

Če ne izdelaš kopije, potem se nič ne šteje, da si porabil O(n) prostora, ker ga nisi. Algoritem za svoje delo porabi natančno 2x velikost kazalca bytov, kar je maksimalna količina pomnilnika, ki ga potrebuje. Torej O(1).

technolog ::

Če rabiš staro, nespremenjeno podatkovno strukturo še za naprej, potem nimaš izbire, kopijo moraš naredit.

Mavrik ::

Ne. Saj ti je lepo povedal, da lahko spet v linearnem času popraviš strukturo nazaj.
The truth is rarely pure and never simple.

AndrejO ::

technolog je izjavil:

Če rabiš staro, nespremenjeno podatkovno strukturo še za naprej, potem nimaš izbire, kopijo moraš naredit.


Heh, se ne daš. :P

OK, ne bom te zafrkaval in ti bom raje pojasnil, kje nimaš znanja, kje si površen in kje imaš (skoraj) prav.

Pri algoritmih je ključno, da razumeš podatkovno strukturo in njeno obnašanje, hkrati pa razumeš tudi kako se računa najmanj z O in Ω. Tvoja napaka je, da si morda pozabil ali pa še nisi vprašal te kategorije teoretičnih vprašanj, kjer se vprašanje ukvarja z razumevanjem teh osnovnih pojmov. Tukaj nisi pokazal znanja. Pri velikem O se šteje dejanska poraba pomnilnika in to je to. Še več, nalogi dodajaš nove pogoje, ki seveda spremenijo rešitev. To je trma, ne pa znanje. Trma pa definicij ne spreminja.

Površen si, ker ne prve, ne druge naloge nisi pozorno prebral. Nobena od njiju namreč niti ne namiguje, da algoritem ne sme manipulirati podatkov. Naloga bi takšen pogoj lahko imela, vendar pa je kot vedno potrebno izluščiti jedro. To, da si ti v glavi predstavljaš, da izpis običajno ne pomeni spreminjanja izvornih podatkov, še ne pomeni, da naloga to omejitev postavlja. To je torej tvoja površnost.

Skoraj imaš prav, ko praviš, da potrebuješ kopijo, če želiš obdržati original. Zgoraj sem že opisal kako imaš lahko na koncu znova originalno vsebino, pa boš še vedno opravil delo v O(n) in porabil O(1) prostora. Kar bi moral pravilno zapisati, je, da je O(n) minimum v primeru, ko originala ne smeš ali ne moreš spremeniti. Običajno zato, ker se nahaja v pomnilniku, v katerega ne smeš ali ne moreš pisati (razmišljaj npr. o tračnih enotah ali pa dnevniških zapisih na bliskovnem(bliskovitem?) pomnilniku). Znova si površen, vendar pa si imel pri zadnjem komentarju skoraj prav. Jaz pa sem obljubil, da te več ne bom zafrkaval.

Zgodovina sprememb…

  • spremenil: AndrejO ()

technolog ::

Pa res. Sem spregledal odgovor.

Jap, če lahko po pomnilniku pišeš, potem se pa res da. Lep trik.

Spura ::

ragezor je izjavil:

tega se ne da brez da bi si ob prvem prehodu skozi list shranil elemente ali pointerje in jih potem izpisal v obratnem vrstnem redu.

rekurzija drzi vse v spominu.

Rekurzija drzi tocno isto v spominu kot tvoj seznam pointerjev.

Zgodovina sprememb…

  • spremenil: Spura ()

Spura ::

V praksi (ne kot odgovor na nalogo) imajo vse resitve pomanjkljivosti. Vecinoma folk ne rabi izpisa v obratno smer ampak iteracijo v obratno smer. To prepisovanje pointerjev je najslabsa varianta mozna, ce bi dejansko delal tako podatkovno strukturo.

ragezor ::

Spura je izjavil:


Rekurzija drzi tocno isto v spominu kot tvoj seznam pointerjev.


Vem, hotel sem samo izpostaviti, da rekurzija drzi vse elemente v spominu, ker na prvi pogled ni ocitno.

Drugace pa se sam nebi spomnil prepisovanja pointerjev. Razen ce bi mogoce reseval nalogo pri podatkovnih strukturah :P

Ponavadi, ko uporabljas katero podatkovno strukturo si omejen z njeno implementacijo in je ne mores spreminjati.

Randomness ::

Evo, še delujoč proof-of-concept: 
#include <stdio.h>
#include <stdlib.h>

struct list {
	int v;
	struct list *next;
};

static struct list *create();
static void destroy(struct list* l);
static struct list *revert(struct list* l);
static void print(struct list* l);

int main() {
	struct list *l;

	l = create();
	printf("naprej:"); print(l);
	l = revert(l);
	printf("nazaj :"); print(l);
	l = revert(l);
	printf("naprej:"); print(l);
	destroy(l);

	return 0;
}

struct list *create() {
	struct list *h, *l;
	int i;

	h = l = malloc(sizeof(struct list));
	l->v = 0;

	for (i = 1; i < 10; i++) {
		l->next = malloc(sizeof(struct list));
		l = l->next;
		l->v = i;
	}
	l->next = NULL;

	return h;
}

void destroy(struct list* l) {
	struct list *n;

	for (n = l->next; l != NULL; l = n, n = n ? n->next : NULL) {
		free(l);
	}
}

struct list *revert(struct list* l) {
	struct list *p, *n;

	for (p = l, l = l->next, p->next = NULL, n = l->next;
		 l != NULL; p = l, l = n, n = n ? n->next : NULL) {
		l->next = p;
	}

	return p;
}

void print(struct list* l) {
	while (l) {
		printf(" %d", l->v);
		l = l->next;
	}
	printf("\n");
}

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[C++] enosmerno povezan seznam

Oddelek: Programiranje		63644 (1528) 3p
»

Za programerske teoretike

Oddelek: Programiranje		478525 (5327) Jerry000
»

Časovna zahtevnost

Oddelek: Programiranje		222854 (2398) technolog
»

[C] kazalčni seznam

Oddelek: Programiranje		122863 (2677) MrBrdo
»

Programiranje v C++

Oddelek: Programiranje		352478 (1336) krneki0001

Več podobnih tem