uni/ws2019/ipi/uebungen/haseigel.cpp

#include<stdio.h>

// Ein Listenelement
struct IntListElem {
    IntListElem* next;  // Zeiger auf nächstes Element
    int value;          // Daten zu diesem Element  
} ;

// Eine Liste
struct IntList {
    int count;          // Anzahl Elemente in der Liste
    IntListElem* first; // Zeiger auf erstes Element der Liste
} ;


// Initialisiere eine Listenstruktur
void empty_list (IntList* l)
{
    l->first = 0;   // 0 ist keine gueltige Adresse: Liste ist leer
    l->count = 0;
}

// Fuege ein Element nach einem gegebenem ein
void insert_in_list (IntList* list, IntListElem* where, IntListElem* ins)
{
    if (where==0) // fuege am Anfang ein
    {
        ins->next = list->first;
        list->first = ins;
        list->count = list->count + 1;
    }
    else         // fuege nach where ein
    {
        ins->next = where->next;
        where->next = ins;
        list->count = list->count + 1;
    }
}

// Entferne ein Element nach einem gegebenem
// Liefere das entfernte Element zurueck
IntListElem* remove_from_list (IntList* list, IntListElem* where)
{
    IntListElem* p;  // das entfernte Element

    // where==0 dann entferne erstes Element
    if (where==0) 
    {
        p = list->first;
        if (p!=0)
        {
            list->first = p->next;
            list->count = list->count - 1;
        }
        return p;
    }

    // entferne Element nach where
    p = where->next;
    if (p!=0)
    {
        where->next = p->next;
        list->count = list->count - 1;
    }
    return p;
}

// creates a cyclic list with a linear part of k elements
// and a cyclic part of n elements
IntList* make_cyclic_list(int k, int n) {
    IntList* list = new IntList();
    empty_list(list);

    // create cyclic list of length n
    if (n > 0) {
        // create last element of list (its inserted first)
        IntListElem* last = new IntListElem();
        last->value = n+k;
        // insert the (now first, but later) last element into the list
        insert_in_list(list, 0, last);
            // now iterate over every other number
            for (int i = n+k-1; i > k; i--) {
            // and create a new list element
            IntListElem* elem = new IntListElem();
            // with the given number
            elem->value = i;
            // and add it to the list in the very beginning
            insert_in_list(list, 0, elem);
        }
        // make the last element reference the first one
        last->next = list->first;
    }
    IntListElem* firstCyclic = list->first;
    // add a linear part
    for (int i = k; i > 0; i--) {
        // create new list element
        IntListElem* elem = new IntListElem();
        // with given value
        elem->value = i;
        // and insert in the very beginning
        insert_in_list(list, 0, elem);
        // if it is the (first inserted, but later) last element of the linear
        // part, make it point to the first cyclic element
        if (i == k) {
            elem->next = firstCyclic;
        }
    }
    return list;
}

// Hase-Igel Algorithmus zum Finden eines Zyklus in einer Liste
int hase_igel(IntList* list) {
    // create igel, that goes on by one
    IntListElem* igel = list->first;
    // create hase that always skips one element
    IntListElem* hase = list->first;
    // count the number of steps needed
    int n = 0;
    // this is the first occurence of a cycle
    int first = 0;
    // move forward with igel and hase until we hit the end of the list
    while (igel != 0 && hase != 0) {
        // increment igel and hase
        igel = igel->next;
        hase = hase->next->next;
        // increment the step counter
        n++;
        // if igel and hase point to the same element, there
        // has to be a cycle
        if (igel == hase) {
            // save the first occurence
            if (first == 0) {
                first = n;
            // if we find the second one, return the difference
            } else {
                return n - first;
            }
        }
    }
    // if there is an end, there can't be a cycle
    return 0;
}

int main() {
    IntList* list = make_cyclic_list(10, 0);
    printf("Laenge des Zyklus: %d\n", hase_igel(list));
}