/* c201.c *********************************************************************}
{* Téma: Jednosměrný lineární seznam
**
** Návrh a referenční implementace: Petr Přikryl, říjen 1994
** Úpravy: Andrea Němcová listopad 1996
** Petr Přikryl, listopad 1997
** Přepracované zadání: Petr Přikryl, březen 1998
** Přepis do jazyka C: Martin Tuček, říjen 2004
** Úpravy: Bohuslav Křena, říjen 2009
**
** Implementujte abstraktní datový typ jednosměrný lineární seznam.
** Užitečným obsahem prvku seznamu je celé číslo typu int.
** Seznam bude jako datová abstrakce reprezentován proměnnou typu tList.
** Definici konstant a typů naleznete v hlavičkovém souboru c201.h.
**
** Vaším úkolem je implementovat následující operace, které spolu s výše
** uvedenou datovou částí abstrakce tvoří abstraktní datový typ tList:
**
** InitList ...... inicializace seznamu před prvním použitím,
** DisposeList ... zrušení všech prvků seznamu,
** InsertFirst ... vložení prvku na začátek seznamu,
** First ......... nastavení aktivity na první prvek,
** CopyFirst ..... vrací hodnotu prvního prvku,
** DeleteFirst ... zruší první prvek seznamu,
** PostDelete .... ruší prvek za aktivním prvkem,
** PostInsert .... vloží nový prvek za aktivní prvek seznamu,
** Copy .......... vrací hodnotu aktivního prvku,
** Actualize ..... přepíše obsah aktivního prvku novou hodnotou,
** Succ .......... posune aktivitu na další prvek seznamu,
** Active ........ zjišťuje aktivitu seznamu.
**
** Při implementaci funckí nevolejte žádnou z funkcí implementovaných v rámci
** tohoto příkladu, není-li u funkce explicitně uvedeno něco jiného.
**
** Nemusíte ošetřovat situaci, kdy místo legálního ukazatele na seznam
** předá někdo jako parametr hodnotu NULL.
**
** Svou implementaci vhodně komentujte!
**
** Terminologická poznámka: Jazyk C nepoužívá pojem procedura.
** Proto zde používáme pojem funkce i pro operace, které by byly
** v algoritmickém jazyce Pascalovského typu implemenovány jako
** procedury (v jazyce C procedurám odpovídají funkce vracející typ void).
**/
#include "c201.h"
int solved;
int errflg;
void Error() {
/*
** Vytiskne upozornění na to, že došlo k chybě.
** Tuto funkci budete volat v rámci některých dále implementovaných operací.
**/
printf ("*ERROR* Chyba při práci se seznamem.\n");
errflg = TRUE; /* globální proměnná -- příznak chyby */
}
/*
** Provede inicializaci seznamu L před jeho prvním použitím (tzn. žádná
** z následujících funkcí nebude volána nad neinicializovaným seznamem).
** Tato inicializace se nikdy nebude provádět nad již inicializovaným
** seznamem, a proto tuto možnost neošetřujte. Vždy předpokládejte,
** že neinicializované proměnné mají nedefinovanou hodnotu.
**/
void InitList (tList *L) {
L->Act = NULL;
L->First = NULL;
}
/*
** Zruší všechny prvky seznamu L a uvede seznam L do stavu, v jakém se nacházel
** po inicializaci. Všechny prvky seznamu L budou korektně uvolněny voláním
** operace free.
*/
void DisposeList (tList *L) {
tElemPtr pom; // pomocny ukazatel
while ((pom = L->First) != NULL) {
// zacatek seznamu nasmerujeme na nasledujici prvek
L->First = pom->ptr;
// uvolnit prvek z pameti
free(pom);
}
// prazdny seznam nemuze mit aktivni polozku
L->Act = NULL;
}
/*
** Vloží prvek s hodnotou val na začátek seznamu L.
** V případě, že není dostatek paměti pro nový prvek při operaci malloc,
** volá funkci Error().
*/
void InsertFirst (tList *L, int val) {
// alokovat pamet pro novy prvek
struct tElem *elPtr;
if ((elPtr = malloc(sizeof(struct tElem))) == NULL) {
Error();
return;
}
// naplnit daty a vsunout na zacatek seznamu
elPtr->data = val;
elPtr->ptr = L->First;
L->First = elPtr;
}
/*
** Nastaví aktivitu seznamu L na jeho první prvek.
** Funkci implementujte jako jediný příkaz, aniž byste testovali,
** zda je seznam L prázdný.
*/
void First (tList *L) {
L->Act = L->First;
}
/*
** Vrátí hodnotu prvního prvku seznamu L.
** Pokud je seznam L prázdný, volá funkci Error().
*/
void CopyFirst (tList *L, int *val) {
if (L->First == NULL)
Error();
else
*val = L->First->data;
}
/*
** Ruší první prvek seznamu L. Pokud byl rušený prvek aktivní, aktivita seznamu
** se ztrácí. Pokud byl seznam L prázdný, nic se neděje!
*/
void DeleteFirst (tList *L) {
// zrusit pripadnou aktivitu
if (L->Act == L->First)
L->Act = NULL;
// odstranit prvni prvek
if (L->First != NULL) {
tElemPtr pom = L->First;
L->First = pom->ptr;
free(pom);
}
}
/*
** Ruší prvek seznamu L za aktivním prvkem. Pokud není seznam L aktivní
** nebo pokud je aktivní poslední prvek seznamu L, nic se neděje!
*/
void PostDelete (tList *L) {
//preskocit neaktivni seznam nebo seznam s aktivnim poslednim prvkem
if (L->Act == NULL || L->Act->ptr == NULL)
return;
tElemPtr pom = L->Act->ptr; // ukazatel na odstranovany prvek
// odstranit prvek z vazby seznamu
L->Act->ptr = pom->ptr;
// uvolnit prvek z pameti
free(pom);
}
/*
** Vloží prvek s hodnotou val za aktivní prvek seznamu L.
** Pokud nebyl seznam L aktivní, nic se neděje!
** V případě, že není dostatek paměti pro nový prvek při operaci malloc,
** volá funkci Error().
*/
void PostInsert (tList *L, int val) {
// pokud neni seznam aktivni, nedelat nic
if (L->Act == NULL)
return;
// alokovat pamet pro novy prvek
struct tElem *elPtr;
if ((elPtr = malloc(sizeof(struct tElem))) == NULL) {
Error();
return;
}
// naplnit daty a vsunout za aktivni prvek
elPtr->data = val;
elPtr->ptr = L->Act->ptr;
L->Act->ptr = elPtr;
}
/*
** Vrátí hodnotu aktivního prvku seznamu L.
** Pokud seznam není aktivní, volá se funkce Error().
*/
void Copy (tList *L, int *val) {
if (L->Act == NULL)
Error();
else
*val = L->Act->data;
}
/*
** Přepíše data aktivního prvku seznamu L.
** Pokud seznam L není aktivní, nedělá nic!
*/
void Actualize (tList *L, int val) {
if (L->Act != NULL)
L->Act->data = val;
}
/*
** Posune aktivitu na následující prvek seznamu L.
** Všimněte si, že touto operací se může aktivní seznam stát neaktivním.
** Pokud seznam L není aktivní, nedělá nic!
*/
void Succ (tList *L) {
if (L->Act != NULL)
L->Act = L->Act->ptr;
}
/*
** Je-li seznam L aktivní, vrací True. V opačném případě vrací false.
** Tuto funkci implementujte jako jediný příkaz return.
*/
int Active (tList *L) {
return L->Act != NULL;
}
/* Konec c201.c */