Lineárně zřetězený seznam v C – C / C++ – Fórum – Programujte.com

zdravím, mám zadání na zápočet ale nějak s s tím nevím rad (spíš jakým způsobem to mám dělat) :
 

Výstup je (bez úprav na schématu úpravy barevně): 1 3 5 7 9 11

Po úpravách (na schématu barevně) je výstup: 1 2 3 5 9 11. Co ukazuje modrá barva?

Prvek 7 není dostupný (takže logicky neexistuje – odpad - garbage).

Poučení: program musí fungovat i pro mezní (či „odlehlé“) situace, např. zde když je seznam prázdný.

Domácí cvičení: kromě uvedené úlohy „vypiš“ naprogramujte i funkce „vlož“ a „zruš“ (prvek nemusí v seznamu být) – viz schematicky výše. Dále naprogramuje funkci „najdi“ (prvek rovněž nemusí v seznamu být).

Problémy pro DCV:

1. Funkce „vlož“: Hodnotu je třeba dát na správné místo (tj. i jako první či poslední prvek seznamu); jak se zachovat, když už prvek v seznamu je. Jsou 2 možnosti: dát tam prvek znovu nebo oznámit tuto skutečnost a už nic neukládat. Vyberte si některou (v databázi nemůže být duplicitní primární klíč). Pokud se rozhodnete ukládat prvky opakovaně, pak doplňte systém o funkci „najdivše“, která oznámí, kolikrát je prvek v seznamu uveden.

2. Funkce„zruš“: co když zamýšlený rušený prvek v seznamu vůbec není?

3. Jaký předpokládat výstup v případě funkce „najdi“?

Řešení: buď je volný seznam veden skutečně jako seznam s indexy pro následníky, nebo je možno použít setřásacích algoritmů kdy se platné informace přesouvají „nahoru“. V obou případech je algoritmus dvoufázový, kdy v první fázi je nutno nějak „označit“ platné (nepatné jsou totiž nedostupné. Je nutno použít “g-bit“.

Hlavní program pak může postupně vyvolávat výše zmíněné funkce podle zadání obsluhy.

Připojen obrázek.

přiznám se že sem vůbec nepochopil to zadání ....

nemáš náhodu někde originál ????

#3 Jerry

on to v podstatě originál je

https://ulozto.cz/!OILKmc1wK93T/priklad-na-zapocet-doc

já jen nevím jestli to mám řešit jako pole s 3 hodnotama (index vektoru, hodnota, ukazatel) nebo jak by to bylo nejlepší. pro info: když zobrazím tu původní tab. a budu chtít přidat další číslo aby se mi zařadilo dle velikosti (hodnota) a aby se změnily kazatele (index vektoru je přiřazuje postupně, jako primární klíč)

to co chceš je oboustraně zřetězený sekvenční binární strom. je to dost práce no    

typedef struct t_treeItem
{
	int value;
	bool endElement;
	t_treeItem *fwLink = NULL;
	t_treeItem *bwLink = NULL;
	t_treeItem *self = NULL;

} treeItem;






	treeItem *item = NULL;

	// dulezite globalni RIDICI promenne 
	treeItem *firstItem = NULL;
	treeItem *lastItem = NULL;



	{

		// funkce pridani prvku do sekvencniho binarniho stromu - bud na prvni misto pokud 
		//  je strom prazdny nebo na posledni misto pokud neni prazdny


		
		// pridani prveho prvku do sekvencniho binarniho stromu
		if (firstItem == NULL ) {

			item = new treeItem();
			item->value = 0; // zadana hodnota uzivatelem / nejaka

			item->fwLink = NULL;
			item->bwLink = NULL;
			item->self = item;
		
			firstItem = item;   
			lastItem = item;

		} else  // pridani noveho prvku za posledni prvek sekvencniho binarniho stromu. 
		{

			item = new treeItem();
			item->value = 0; // zadana hodnota nejaka

			// zalinkujeme novy prvek sekvencniho binarniho stromu 
			item->fwLink = NULL;
			item->bwLink = lastItem->self;  // spojeni na predchoziho
			item->self = item;

			// vytvorime spojeni v retezci posledniho prvku na prave vytvoreny item
			lastItem->fwLink = item;

			// firstItem = item;    // nemeni se zde leda ze bychom mazali prvni prvek
			lastItem = item;  // meni se pokazde kdyz pridavame za posledni prvek seznamu

		}

			// podobne napr odebrani prvku 
			/*
			// pokud mazes prvni prvek  t.j. firstItem == item pak 
			item->fwLink->bwlink = NULL; 
			firstItem = item->fwLink->self;
			delete( item );

			// pokud mazes prvek item ktery je jiny nez prvni a posledni t.j. item != lastItem AND  item != firstItem;
			item->fwLink->bwlink = item->bwLink; nebo taky item->bwLink->self; coz je to same
			item->bwLink->fwlink = item->fwLink; nebo taky item->fwLink->self; coz je to same 
            delete( item );
			
			// pokud mazes posledni prvek  t.j. lastItem == item pak
			item->bwLink->fwlink = NULL;
			lastItem = item->bwLink->self;
			delete( item );


			//stejnym zpusobem se pak udela vlozeni prvku kdekoliv ve uprostred strome t.j. musim vedet
			// ZA jaky item vkladam nebo PRED jaky vkladam 
			{
			item = new treeItem();
			item->value = 0; // zadana hodnota nejaka

			// zalinkujeme novy prvek sekvencniho binarniho stromu NEKAM ... pozor poradi prikazu je dulezite 
			item->fwLink = ten_za_ktery_vkladam->fwLink;
			item->bwLink = ten_za_ktery_vkladam->self; 
			ten_za_ktery_vkladam->fwLink->bwLink = item;  nebo taky  ten_pred_ktery_vkladam->bwLink = item; coz je to same
			ten_za_ktery_vkladam->fwLink = item;


			item->self = item;

			// vytvorime spojeni v retezci posledniho prvku na prave vytvoreny item
			lastItem->fwLink = item;

			// firstItem  nemeni se 
			// lastItem  nemeni se 
			}
			
			*/

	}// 

#5 Jerry
díky za odpověď, no to je dobra pomsta od učitele :-) snad se s tím nějak poperu. Když se na to tak teď dívám tak jsem z toho takovej zmatenej :-/

#5 Jerry
ale když se tak dívám na internet...nešlo by to jako Jednosměrně zřetězený seznam? to by asi bylo jednodušší ne?

#7 Honza
to šlo ale objem práce je přibližně stejnej  protože potebuješ naprogramovat

stejnej počet obslužných funkcí takže je to fuk.

ale všechno co potřebuješ už tam máš napsaný .... vytvoření, vložení, mazání

pokud to chceš udělat jednosměrný stačí vynechat  t_treeItem *bwLink = NULL; a k němu příslušné řádky

obslužného kodu
 

#1 Honza
kde že to studiješ ? ČVUT ? VUT ? ZCU ?

#1 Honza
já sem se teď koukal eště jednou na to zadání a máš tam aj mazat položky... takže bych nechal oboustranně zřetězenej protože se to pak dělá výrazně líp a o těch pár řádků navíc se to už neposere... jinak budeš muset dohledávat předchozí prvek

budeš muset napsat eště funkci Hledej - tu sem tam nenapsal - na hledání prvku v tom seznamu co vrátí pointer na t_treeItem kde ta hodnota je to je jenom jednoduchej enumerátor  n2co ve smyslu:

while ( enum->MoveNext() )  {

          if ( enum->GetPtr()->Value == hledanahodnota ) {

             ..........

            return enum->GetPtr();

          }

}

To zadání psal úplněj debil.

#11 gna
#10 Jerry

zadání psal jeden docent do přednáší v Třebíči, jinak já studuji EPI to je polytechnika v Kunovicích. Blbý je že dálkově tak těch přednášek není tolik a samostudium je na pytel když ti nemá kdo poradit když se zasekneš.

no problém bych viděl v tom, že on to po tobě asi u ústního zkoušení bude chtít ..... což je blbý....

takže to asi budeš muset nacvakat sám ... ale jak řikám všechno to důležitý už tam máš stačí to jenom rozhodit do jednotlivých funkcí např. InitBT (detekuje zda už strom existuje zalozi novy firstitem atd) deleteBT (smaze strom) Append a Add( pridaji polozku na konec nebo na zacatek pokud strom je prazdny),Insert ( vlozi int hodnotu za nejakou existujici hodnotu) IndexOf (vrati pointer na existujici prvek nebo NULL pokud prvek neexistuje - to je ten enumerator a prohledava se cely strom od zacatku), Delete(smaze existujici prvek dany hodnotu int pokud existuje), DeleteFirst (smaze prvni pokud to jde), DeleteLast(smaze posledni pokud to jde) , FindALL je stejný jako IndexOf ale zrusis tu podminku If, Sort (setridi seznam A-Z nebo Z-A styl)

kdybys na to hodil bobek a chtěl to risknout tak uěláme výměnu já tobě semestrálku a ty mě tohle:

https://www.alza.cz/dvd-r-medium-verbatim-d54961.htm?catid=18848915

jinak si mužeš stěžovat (možná to budeš muset dát písemně doporučeným dopisem) na napřiměřenost ulohy pokud si např. v prvním semestru prvního rocniku protože tohle je na prvaky moc. Pokud si treba ve 3 a vyšším semestru a už si absolvoval 2 semestry výuky programování pak už asi stížnost bude braná jako neoprávněná.

Jinak k tomu bodu 4 tvé ulohy .... no .. GarbageCollector s tim nema nic společnýho protože v NativeC/C++ neni a kdyby byl tak GC je tak agresivni, že k odstranení "odpadu" dochází téměř ihned a navic je možné použít příkaz System::GC::Collect (viz google) a vyčištění si vynutit ale ten je jen v jazyce C++/CLI a C# (resp. ve všech co podporujou CLI/CLR) pro .NET což se tě netýká. Navíc je to spojené s memory managementem windows a do toho se vůbec ani nedá nějak hlouběji zasahovat - microsoft to nepovolil.

jenom k tý poznámce na konci_

Poznámky:

Předpokládejte, že prvky v seznamu (tabulce) jsou řazeny vzestupně. Je to přirozené[1]?

[1] Tabulky bývají setříděné.

tabulku lze setřídit ... ale někdo ten kod musi napsat... přehazuje se jak pointer tak i hodnota Value, takze je to slozitejsi

#13 Jerry
díky za poznámky, jelikož už nějaké základy za sebou mám tak to budu muset nějak zvládnout. kdyby se nedařilo tak se ozvu s tou tvoji nabídkou :-) 

#4 Honza
Přečetl jsem si zadání a je to podle mne pouze jednoduchý jednosměrný spojový seznam, akorát je implementovaný nad polem - místo ukazatelů se používají indexy. A tím jak je to nad polem, tak je (pro pokročilé) ještě potřeba nějaké správy uvolněných položek (což se opět dá udělat jednodušše spojovým seznamem). Rozhodně podle zadání není potřeba žádný binární strom (zadání se jmenuje lineární zřetězený seznam).

každopádně to zadání psal totální mamlas   

#15 Staon
ale v tom případě to musí být pole záznamů a ne jenom pole což je ve výsledku to samý :) jako SBT

#17 Jerry
Naprosto s vámi souhlasím, že zadání psal nějaký mamlas :-)

Aha, prošel jsem si váš kód pořádně a to co popisujete, není strom, ale obousměrně zřetězený spojový (lineární) seznam. Nevím, kde jste vzal název sekvenční binární strom. Binární strom je hierarchická struktura, kde každý uzel má až dva potomky. A protože je vždy hierarchický, slovo sekvenční k tomu už nedává moc smysl.

Je pravda, že z hlediska teorie grafů je možné seznam považovat za speciálním případ stromu. Ale v zadání neřeší grafy, tak bych mu s tím hlavu nezatěžoval a používal standardní terminologii v oboru.

Ve výsledku je jedno, jestli seznam implementujete alokováním na haldě, nebo nad polem záznamů (jak jste správně poznamenal). Podstatné je, že v zadání mají jednosměrně zřetězený seznam, zatímco vy mu jako radu dáváte obousměrně zřetězený. Předpokládám, že jejich učitel zaprvé nechtěl, aby se ztratili v příliš mnoha propojkách (představit si jak přepojit uzel v obousměrném seznamu není úplně jednoduché), zadruhé asi chtěl, aby si sami na vlastní kůži vyzkoušeli, jak jednosměrně zřetězený seznam zkomplikuje operace delete a insert.

#18 Staon
stanislav dvořák, dekompozice a rekurzivní algoritmy, grada 1992, isbn 80-85424-76-2, strana 393-393., je to forma nevyváženého tedy non-AVL binárního stromu, taky se tomu dá říkat lineární zřetězený seznam viz Jan Rychlík, programovací techniky, koop, 1993, isbn 80-85828-05-7, strana 28, každý uzel - node - má 2 linky a to fwLink a bwLink, ale sou vánoce opravdu se nechci handrkovat vo kravinu    mě osobně je to úplně jedno jak se tomu bude řikat,  já sem sem na forum přišel protože sem potrřeboval pomoct s SQL   a tak sem si řek že na oplátku zase pomůžu já někomu abych nevypadal jak vyžírka když mi někdo na moji otázku odpověděl, jinak ten celej program neni až tak dlouhej, vychází cca na 600 řádků t.j 10 stran A4 když se to vytiskne, sem zvědavej co ten nebožák student splodí   

Vánocééééééééééé Vánocééééééééééé Vánocééééééééééé Vánocééééééééééé

oléééééééééééé   Vánocééééééééééé

dostanu dáréék bude kaprrrrrr   wou wou   

#19 Jerry
Bez urážky, ale navést úplného začátečníka na chybný termín není "handrkování vo kravinu". Dokážete si představit, jak mu teď lezou oči z důlků, pokud dal na vaši radu a zagooglil na téma "binární stromy"? :-) Proto jsem psal svůj první příspěvek, že žádné stromy nepotřebuje a ať kouká na spojový seznam.

Zkusil jsem zjistit, jestli mi někde něco neuniklo, ale hledání tohoto termínu mě odkázalo pouze na jeden váš příspěvek na jiném fóru. Autor termín zřejmě použil pro popis kritického krajního případu, kdy binární vyhledávací strom zdegeneruje na lineární seznam a tedy na sekvenční prohledávání. Rozhodně to není název datové struktury, a pokud si do budoucna chcete ušetřit další handrkování vo kraviny, tak ten termín přestaňte používat. Je velmi zavádějící a oficiální termíny koneckonců slouží k tomu, abychom se mezi sebou dokázali domluvit.

Jinak přeji hezké Vánoce.

#1 Honza
řešení ? hotový příklad ? že by ? a zdarma ? v kapitalismu ? v Kalouskově kapitalismu ? není možná :))))

https://uloz.to/!wybTcOhmXzwM/consoleapplication1-zip

#20 Staon

Staone .... bez urážky :))))))))))) nedivim se že česká ekonomika je v prdeli a máme nejnižší platy v EU :)

..........ineární spojový seznam neboli v angličtině LinkedList (přeloženo do češtiny SPOJOVY SEZNAM) nebo také jinak řečeno sekvenční binární strom nebo také sekvenční non-AVL tree má 2 formy a to jednostranně zřetězený (vžitý název v .NET List a to s nebo bez [Int32] indexeru) a nebo oboustraně zřetězený (vžitý název v .NET je LinkedList) viz zde 

http://www.stoimen.com/blog/2012/06/22/computer-algorithms-binary-search-tree-data-structure/.

v české literatuře to asi nenajdeš 

pěkně si to užij :)

#22 Jerry
Je to tam zminene akorat jako Worst-Case-Scenario pro nebalancovany binarni strom. Nicmene spojovy seznam nemusi byt serazeny, tak jako je ten nejhorsi pripad binarniho stromu (ten proste serazeny byt musi). Takze vynucovat nejaky nepouzivany pojem pro neco, co to ani neni, je opravdu tezke mateni zacatecnika.

V clanku se taky zminuje neefektivita sekvencniho hledani, nicmene se tam vubec nezminuje problem fenomenu zvaneho Cache Prediction - pokud se data nevlezou do cache procesoru, a je potreba nacist data mimo tento blok, tak se nacita jiny blok. Coz muze trvat az tisice strojovych cyklu. Zatimco sekvencni prochazeni bloku pameti je predvidatelne.

---

Taktez podle popisu na 100% neni pozadovan obousmerny spojovy seznam. Dokonce nepotrebuje ani tri polozky te struktury (jak si autor mysli/myslel), jelikoz ji urcuje pozice v poli (a tudiz nemusi byt nikde ulozena). Staci tedy jen hodnota a pozice dalsiho prvku.

Delat tam garbage collection je taky picovina, proste to budou propojene vsechny prvky a pokud se nejaky smaze, tak se zaradi na konec. Kdyz uz se tam beztak pracuje s pojmem pocet prvku, tak to tak pujde tak jak tak. (+ bude potrebovat nejakou "kontejnerovou" strukturu)

stěžoval sis že to máš těžký co ?

koukni sem

http://programujte.com/forum/vlakno/31789-linearni-spojovy-seznam-problem/