/* c206.c **********************************************************}
{* Téma: Dvousměrně vázaný lineární seznam
**
** Návrh a referenční implementace: Bohuslav Křena, říjen 2001
** Přepracované do jazyka C: Martin Tuček, říjen 2004
** Úpravy: Bohuslav Křena, říjen 2008
**
** Implementujte abstraktní datový typ dvousměrně vázaný lineární seznam.
** Užitečným obsahem prvku seznamu je hodnota typu int.
** Seznam bude jako datová abstrakce reprezentován proměnnou
** typu tDLList (DL znamená Double-Linked a slouží pro odlišení
** jmen konstant, typů a funkcí od jmen u jednosměrně vázaného lineárního
** seznamu). Definici konstant a typů naleznete v hlavičkovém souboru c206.h.
**
** Vaším úkolem je implementovat následující operace, které spolu
** s výše uvedenou datovou částí abstrakce tvoří abstraktní datový typ
** obousměrně vázaný lineární seznam:
**
** DLInitList ...... inicializace seznamu před prvním použitím,
** DLDisposeList ... zrušení všech prvků seznamu,
** DLInsertFirst ... vložení prvku na začátek seznamu,
** DLInsertLast .... vložení prvku na konec seznamu,
** DLFirst ......... nastavení aktivity na první prvek,
** DLLast .......... nastavení aktivity na poslední prvek,
** DLCopyFirst ..... vrací hodnotu prvního prvku,
** DLCopyLast ...... vrací hodnotu posledního prvku,
** DLDeleteFirst ... zruší první prvek seznamu,
** DLDeleteLast .... zruší poslední prvek seznamu,
** DLPostDelete .... ruší prvek za aktivním prvkem,
** DLPreDelete ..... ruší prvek před aktivním prvkem,
** DLPostInsert .... vloží nový prvek za aktivní prvek seznamu,
** DLPreInsert ..... vloží nový prvek před aktivní prvek seznamu,
** DLCopy .......... vrací hodnotu aktivního prvku,
** DLActualize ..... přepíše obsah aktivního prvku novou hodnotou,
** DLSucc .......... posune aktivitu na další prvek seznamu,
** DLPred .......... posune aktivitu na předchozí prvek seznamu,
** DLActive ........ zjišťuje aktivitu seznamu.
**
** Při implementaci jednotlivých 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 "c206.h"
int solved;
int errflg;
void DLError() {
/*
** 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 ošetření chyby */
return;
}
/*
** 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 DLInitList (tDLList *L) {
L->Act = NULL;
L->First = NULL;
L->Last = NULL;
}
/*
** Zruší všechny prvky seznamu L a uvede seznam do stavu, v jakém
** se nacházel po inicializaci. Rušené prvky seznamu budou korektně
** uvolněny voláním operace free.
**/
void DLDisposeList (tDLList *L) {
tDLElemPtr pom; // pomocny ukazatel
// pri ruseni prvku neprinasi obousmernost seznamu zadnou vyhodu
while ((pom = L->First) != NULL) {
L->First = pom->rptr;
free(pom);
}
// je potreba dodatecne uklidit ukazatel na konec a aktivnost
L->Last = NULL;
L->Act = NULL;
}
/*
** Vloží nový prvek na začátek seznamu L.
** V případě, že není dostatek paměti pro nový prvek při operaci malloc,
** volá funkci DLError().
**/
void DLInsertFirst (tDLList *L, int val) {
// alokace noveho prvku
struct tDLElem *elPtr;
if ((elPtr = malloc(sizeof(struct tDLElem))) == NULL) {
DLError();
return;
}
// naplnit daty
elPtr->data = val;
elPtr->lptr = NULL;
elPtr->rptr = NULL;
// pokud jde o prvni vkladany prvek, musi na nej smerovat i konec
if (L->First == NULL)
L->Last = elPtr;
// provazat s pocatkem seznamu (elem nebo NULL)
elPtr->rptr = L->First;
// pokud je vpravo soused, provazat jej s nove pridanym
if (elPtr->rptr != NULL)
elPtr->rptr->lptr = elPtr;
// nasmerovat pocatek na novy prvek
L->First = elPtr;
}
/*
** Vloží nový prvek na konec seznamu L (symetrická operace k DLInsertFirst).
** V případě, že není dostatek paměti pro nový prvek při operaci malloc,
** volá funkci DLError().
**/
void DLInsertLast(tDLList *L, int val) {
// alokace noveho prvku
struct tDLElem *elPtr;
if ((elPtr = malloc(sizeof(struct tDLElem))) == NULL) {
DLError();
return;
}
// naplnit daty
elPtr->data = val;
elPtr->rptr = NULL;
elPtr->lptr = NULL;
// pokud jde o prvni vkladany prvek, musi na nej smerovat i zacatek
if (L->First == NULL)
L->First = elPtr;
// provazat s koncem seznamu (elem nebo NULL)
elPtr->lptr = L->Last;
// pokud je vlevo soused, provazat jej s nove pridanym
if (elPtr->lptr != NULL)
elPtr->lptr->rptr = elPtr;
// nasmerovat konec seznamu na novy prvek
L->Last = elPtr;
}
/*
** Nastaví aktivitu na první prvek seznamu L.
** Funkci implementujte jako jediný příkaz (nepočítáme-li return),
** aniž byste testovali, zda je seznam L prázdný.
**/
void DLFirst (tDLList *L) {
L->Act = L->First;
}
/*
** Nastaví aktivitu na poslední prvek seznamu L.
** Funkci implementujte jako jediný příkaz (nepočítáme-li return),
** aniž byste testovali, zda je seznam L prázdný.
**/
void DLLast (tDLList *L) {
L->Act = L->Last;
}
/*
** Vrátí hodnotu prvního prvku seznamu L.
** Pokud je seznam L prázdný, volá funkci DLError().
**/
void DLCopyFirst (tDLList *L, int *val) {
// pri spravne implementaci staci pro zjisteni prazdnosti
// overit jeden konec
if (L->First == NULL) {
DLError();
return;
}
*val = L->First->data;
}
/*
** Vrátí hodnotu posledního prvku seznamu L.
** Pokud je seznam L prázdný, volá funkci DLError().
**/
void DLCopyLast (tDLList *L, int *val) {
// nelze nad prazdnym seznamem
if (L->First == NULL) {
DLError();
return;
}
*val = L->Last->data;
}
/*
** Zruší první prvek seznamu L. Pokud byl první prvek aktivní, aktivita
** se ztrácí. Pokud byl seznam L prázdný, nic se neděje.
**/
void DLDeleteFirst (tDLList *L) {
// nelze nad prazdnym seznamem, ale nejde o chybu
if (L->First == NULL)
return;
// pokud jde o jediny prvek v seznamu, odkotvit od nej konec
if (L->First == L->Last)
L->Last = NULL;
// odstranit pripadnou aktivitu
if (L->Act == L->First)
L->Act = NULL;
tDLElemPtr pom = L->First;
// nasmerovat zacatek na 2. prvek nebo NULL (pokud se maze posledni)
L->First = pom->rptr;
// odstranit prvek
free(pom);
// pokud existuje, nasmerovat novy 1. prvek na NULL
if (L->First != NULL)
L->First->lptr = NULL;
}
/*
** Zruší poslední prvek seznamu L. Pokud byl poslední prvek aktivní,
** aktivita seznamu se ztrácí. Pokud byl seznam L prázdný, nic se neděje.
**/
void DLDeleteLast (tDLList *L) {
// nelze nad prazdnym seznamem, ale nejde o chybu
if (L->First == NULL)
return;
// pokud jde o jediny prvek v seznamu, odkotvit od nej zacatek
if (L->First == L->Last)
L->First = NULL;
// odstranit pripadnou aktivitu
if (L->Act == L->Last)
L->Act = NULL;
tDLElemPtr pom = L->Last;
// nasmerovat konec na predposledni prvek nebo NULL (pokud se maze posledni)
L->Last = pom->lptr;
// smazat prvek (pres pravy ukazatel ted uz posledniho)
free(pom);
// pokud existuje, nasmerovat novy posledni prvek na NULL
if (L->Last != NULL)
L->Last->rptr = NULL;
}
/*
** Zruší prvek seznamu L za aktivním prvkem.
** Pokud je seznam L neaktivní nebo pokud je aktivní prvek
** posledním prvkem seznamu, nic se neděje.
**/
void DLPostDelete (tDLList *L) {
// pokud neni co rusit, skoncime bez chyby
if (L->Act == NULL || L->Act == L->Last)
return;
// pomocny uk. na odstranovany prvek
tDLElemPtr pom = L->Act->rptr;
// pokud je za rusenym prvkem dalsi, provazat jej s aktivnim
if (pom->rptr != NULL) {
L->Act->rptr = pom->rptr;
pom->rptr->lptr = L->Act;
}
// jinak bude z aktivniho posledni
else {
L->Act->rptr = NULL;
L->Last = L->Act;
}
free(pom);
}
/*
** Zruší prvek před aktivním prvkem seznamu L .
** Pokud je seznam L neaktivní nebo pokud je aktivní prvek
** prvním prvkem seznamu, nic se neděje.
**/
void DLPreDelete (tDLList *L) {
// pokud neni co rusit, skoncime bez chyby
if (L->Act == NULL || L->Act == L->First)
return;
// pomocny uk. na odstranovany prvek
tDLElemPtr pom = L->Act->lptr;
// pokud je pred rusenym prvkem dalsi, provazat jej s aktivnim
if (pom->lptr != NULL) {
L->Act->lptr = pom->lptr;
pom->lptr->rptr = L->Act;
}
// jinak bude z aktivniho prvni
else {
L->Act->lptr = NULL;
L->First = L->Act;
}
free(pom);
}
/*
** Vloží prvek 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 DLError().
**/
void DLPostInsert (tDLList *L, int val) {
// nelze nad nedaktivnim seznamem
if (L->Act == NULL)
return;
// alokace noveho prvku
struct tDLElem *elPtr;
if ((elPtr = malloc(sizeof(struct tDLElem))) == NULL) {
DLError();
return;
}
// naplnit daty
elPtr->data = val;
elPtr->rptr = NULL;
elPtr->lptr = NULL;
// pokud je za aktivnim nejaky dalsi, provazat jej s pridavanym
if (L->Act->rptr != NULL) {
L->Act->rptr->lptr = elPtr;
elPtr->rptr = L->Act->rptr;
}
// jinak na nove pridavany nasmerovat konec
else
L->Last = elPtr;
// provazat pravou stranu aktivniho a levou noveho
L->Act->rptr = elPtr;
elPtr->lptr = L->Act;
}
/*
** Vloží prvek před 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 DLError().
**/
void DLPreInsert (tDLList *L, int val) {
// nelze nad neaktivnim seznamem
if (L->Act == NULL)
return;
// alokace noveho prvku
struct tDLElem *elPtr;
if ((elPtr = malloc(sizeof(struct tDLElem))) == NULL) {
DLError();
return;
}
// naplnit daty
elPtr->data = val;
elPtr->rptr = NULL;
elPtr->lptr = NULL;
// pokud je pred aktivnim nejaky dalsi, provazat jej s pridavanym
if (L->Act->lptr != NULL) {
L->Act->lptr->rptr = elPtr;
elPtr->lptr = L->Act->lptr;
}
// jinak na nove pridavany nasmerovat zacatek
else
L->First = elPtr;
// provazat pravou stranu aktivniho a levou noveho
L->Act->lptr = elPtr;
elPtr->rptr = L->Act;
}
/*
** Vrátí hodnotu aktivního prvku seznamu L.
** Pokud seznam L není aktivní, volá funkci DLError ().
**/
void DLCopy (tDLList *L, int *val) {
if (L->Act == NULL)
DLError();
else
*val = L->Act->data;
}
/*
** Přepíše obsah aktivního prvku seznamu L.
** Pokud seznam L není aktivní, nedělá nic.
**/
void DLActualize (tDLList *L, int val) {
if (L->Act != NULL)
L->Act->data = val;
}
/*
** Posune aktivitu na následující prvek seznamu L.
** Není-li seznam aktivní, nedělá nic.
** Všimněte si, že při aktivitě na posledním prvku se seznam stane neaktivním.
**/
void DLSucc (tDLList *L) {
if (L->Act != NULL)
L->Act = L->Act->rptr;
}
/*
** Posune aktivitu na předchozí prvek seznamu L.
** Není-li seznam aktivní, nedělá nic.
** Všimněte si, že při aktivitě na prvním prvku se seznam stane neaktivním.
**/
void DLPred (tDLList *L) {
if (L->Act != NULL)
L->Act = L->Act->lptr;
}
/*
** Je-li seznam aktivní, vrací true. V opačném případě vrací false.
** Funkci implementujte jako jediný příkaz.
**/
int DLActive (tDLList *L) {
return L->Act != NULL;
}
/* Konec c206.c*/