5 Replies - 231 Views - Last Post: 29 January 2013 - 08:35 AM Rate Topic: -----

#1 fyr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 23-January 13

snippet concerning circular lists

Posted 28 January 2013 - 01:12 PM

Hi. Can anyone explain me why do I need the following snippet in main:

// ???? 
        if(element == NULL)
           element = clist_next(clist_head(&list));
        else 
           element = clist_next(element);



void clist_init(CList* list, void (*destroy)(void* data)) {

    list->size = 0;
    list->head = NULL; 
    list->destroy = destroy;
}

// insert a node after the current 
int clist_ins_next(CList* list, CListElmt* element, const void* data) {
    // create a new element
    CListElmt* new_element;
    if((new_element = malloc(sizeof(CListElmt))) == NULL)
        return -1;
    // set the data to the new element
    new_element->data = (void*) data;
    // insert when the list is empty
    if(clist_size(list) == 0)
    {    
      // keep a reference to itself
      new_element->next = new_element;
      list->head = new_element;
    }
    // insert when the list is not empty
    else {
      new_element->next = element->next;
      element->next = new_element;
    }            
    // update the size of the list
    list->size++;
    return 0;
}




int main(void) {
    CList list;
    CListElmt* element;
    int* data;
    int i;

    clist_init(&list, free);
    element = clist_head(&list);
    for (i = 0; i <= 9; i++) {
        if ((data = malloc(sizeof (int))) == NULL)
            return EXIT_FAILURE;
        *data = i;
        if (clist_ins_next(&list, element, data) < 0)
            return EXIT_FAILURE;

        // ???? 
        if(element == NULL)
           element = clist_next(clist_head(&list));
        else 
           element = clist_next(element); 
    }
    print_list(&list);
    return EXIT_SUCCESS;
}



Is This A Good Question/Topic? 0
  • +

Replies To: snippet concerning circular lists

#2 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 651
  • View blog
  • Posts: 2,232
  • Joined: 31-December 10

Re: snippet concerning circular lists

Posted 28 January 2013 - 01:41 PM

What do you think it's there for? This sounds suspiciously like a homework problem, and we don't do people's homework, nor is this a code writing service.

*EDIT*: here's a little tip, think about what type of data structure this is supposed to be.

Also, IMO, the part you are talking about should be in one of the CList functions and not in main.

This post has been edited by vividexstance: 28 January 2013 - 01:44 PM

Was This Post Helpful? 0
  • +
  • -

#3 fyr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 23-January 13

Re: snippet concerning circular lists

Posted 28 January 2013 - 01:48 PM

Quote

What do you think it's there for?


I don't know. This is a code from Mastering Algorithms in C. I teach myself. Here's the whole code for the circular list I'm studying:

/*****************************************************************************
*                                                                            *
*  ------------------------------- clist.h --------------------------------  *
*                                                                            *
*****************************************************************************/

#ifndef CLIST_H
#define CLIST_H

#include <stdlib.h>

/*****************************************************************************
*                                                                            *
*  Define a structure for circular list elements.                            *
*                                                                            *
*****************************************************************************/

typedef struct CListElmt_ {

void               *data;
struct CListElmt_  *next;

} CListElmt;

/*****************************************************************************
*                                                                            *
*  Define a structure for circular lists.                                    *
*                                                                            *
*****************************************************************************/

typedef struct CList_ {

int                size;

int                (*match)(const void *key1, const void *key2);
void               (*destroy)(void *data);

CListElmt          *head;

} CList;

/*****************************************************************************
*                                                                            *
*  --------------------------- Public Interface ---------------------------  *
*                                                                            *
*****************************************************************************/

void clist_init(CList *list, void (*destroy)(void *data));

void clist_destroy(CList *list);

int clist_ins_next(CList *list, CListElmt *element, const void *data);

int clist_rem_next(CList *list, CListElmt *element, void **data);

#define clist_size(list) ((list)->size)

#define clist_head(list) ((list)->head)

#define clist_data(element) ((element)->data)

#define clist_next(element) ((element)->next)

#endif



#include <stdlib.h>

#include "clist.h"

// initialize all the members of the list

void clist_init(CList* list, void (*destroy)(void* data)) {

    list->size = 0;
    list->head = NULL; 
    list->destroy = destroy;
}

// insert a node after the current 
int clist_ins_next(CList* list, CListElmt* element, const void* data) {
    // create a new element
    CListElmt* new_element;
    if((new_element = malloc(sizeof(CListElmt))) == NULL)
        return -1;
    // set the data to the new element
    new_element->data = (void*) data;
    // insert when the list is empty
    if(clist_size(list) == 0)
    {    
      // keep a reference to itself
      new_element->next = new_element;
      list->head = new_element;
    }
    // insert when the list is not empty
    else {
      new_element->next = element->next;
      element->next = new_element;
    }            
    // update the size of the list
    list->size++;
    return 0;
}

// remove an element after the current
int clist_rem_next(CList *list, CListElmt *element, void **data) {
    //keep a reference of the element to be removed
    CListElmt* old_element;

    // can't remove if the list is empty
    if (clist_size(list) == 0)
        return -1;

    // retrieve the data from the element to be removed
    *data = element->data;
    // verify if the element is the last one remaining in the list
    if (element->next == element) {
        old_element = element->next;
        list->head = NULL;
    }// remove element other than the last one
    else {

        old_element = element->next;
        element->next = element->next->next;
        // ensure the cyclic property of the list
        if (old_element == clist_head(list))
            list->head = old_element->next;
    }
    free(old_element);
    // update the list size
    list->size--;
    return 0;
}



#include <stdio.h>
#include <stdlib.h>

#include "clist.h"

typedef enum boolean_ {
    false, true
} boolean;

static void print_list(CList* list) {
    CListElmt* element;
    int* data;
    int i = 0;
    int size;

    // print the size of the list 
    printf("list size is %d\n", clist_size(list));
    size = clist_size(list);
    element = clist_head(list);
    while (i < size) {
        data = clist_data(element);
        printf("list[%03d] = %03d\n", i, *data);
        element = clist_next(element);
        i++;
    }
}

int main(void) {
    CList list;
    CListElmt* element;
    int* data;
    int i;

    clist_init(&list, free);
    element = clist_head(&list);
    for (i = 0; i <= 9; i++) {
        if ((data = malloc(sizeof (int))) == NULL)
            return EXIT_FAILURE;
        *data = i;
        if (clist_ins_next(&list, element, data) < 0)
            return EXIT_FAILURE;

        // ???? 
        if(element == NULL)
           element = clist_next(clist_head(&list));
        else 
           element = clist_next(element); 
    }
    print_list(&list);
    return EXIT_SUCCESS;
}



If you doubt me, you can find the code at page 85 in a PDF reader.
Was This Post Helpful? 0
  • +
  • -

#4 fyr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 23-January 13

Re: snippet concerning circular lists

Posted 28 January 2013 - 01:56 PM

to be precise, I didn't understand this part:

// ???? 
        if(element == NULL)
           element = clist_next(clist_head(&list));



because I can't understand which part of the circular linked list would be NULL. After all, the last node is linked to the head. Therefore, it seems he is skipping the head. But, why? does that mean the head is NULL then? what guarantees me that the head is NULL if I already inserted nodes with the insertion function? I can't understand this paradox.
Was This Post Helpful? 0
  • +
  • -

#5 fyr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 23-January 13

Re: snippet concerning circular lists

Posted 28 January 2013 - 02:17 PM

I understood. I need the snippet because of this line of code in main:

element = clist_head(&list);


Was This Post Helpful? 0
  • +
  • -

#6 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 651
  • View blog
  • Posts: 2,232
  • Joined: 31-December 10

Re: snippet concerning circular lists

Posted 29 January 2013 - 08:35 AM

if(element == NULL)
    element = clist_next(clist_head(&list));


I didn't look through all that code, but it appears to me that that line is the part makes the list circular. Once you reach the end of the list, element should be NULL, then the assignment makes element point to the head of the list.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1