Const структура в двусвязном списке изменяется в C - PullRequest
Новая
       4

Const структура в двусвязном списке изменяется в C

0 голосов
/ 12 декабря 2010

Я имею дело с двусвязными списками, и возникла проблема, с которой я не работаю.Чтобы проиллюстрировать это лучше, вот код, прежде чем я скажу, в чем проблема.

Dblist.h 

# Ifndef CGI_DBLIST_H
# Define CGI_DBLIST_H
# Include "malloc.h"
/ * Structure represantative an element of the list. * /

typedef struct elem
{
     int value;
     struct elem * prev;
     struct elem * next;
} Elem;

/ * Structure access to the list. * /

typedef struct
{
     elem * first;
     elem * last;
} dblist;

# ifdef __cplusplus
extern "C" {
# Endif
    void Init (dblist * l);                    /* Initialize the list  */
    void pushback (dblist * s, int val);       /* Add a value at end   */
    void PushFront (dblist * l, int val);      /* Add a value at start */
    int PopBack (dblist * l);                  /* Remove value at end  */
    int PopFront (dblist * l);                 /* Remove value at start */
    void View (dblist l);                      /* Display whole list   */
    void ViewReverse (dblist l);               /* Display all reversed */
    void Clear (dblist * l);                   /* discard list         */
    dblist getInterval (dblist const * s);

  #ifdef __cplusplus
  }
  #endif

  #endif /* CGI_DBLIST_H */

Dblist.c 

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

#include "dblist.h"
#include "malloc.h"

void Init (dblist * l)
{
   l-> first = NULL;
   l-> last = NULL;
}

void pushback (dblist * s, int val)
{
   elem * n = malloc (sizeof (elem));
   if (! n) exit (EXIT_FAILURE);
   n-> value = val;
   n-> prev = l-> last;
   n-> next = NULL;
   if (s-> last) s-> last-> next = n;
   else s-> first = n;
   l-> last = n;
}

void PushFront(dblist *l, int val)
{
   elem *n = malloc(sizeof(elem));
   if(!n) exit(EXIT_FAILURE);
   n->value = val;
   n->next = l->first;
   n->prev = NULL;
   if(l->first) l->first->prev = n;
   else l->last = n;
   l->first = n;
}

int PopBack(dblist *l)
{
   int val;
   elem *tmp = l->last;
   if(!tmp) return -1;
   val = tmp->value;
   l->last = tmp->prev;
   if(l->last) l->last->next = NULL;
   else l->first = NULL;
   free(tmp);
   return val;
}

int popFront(dblist*  l)
{
   int val;
   elem *tmp = l->first;
   if(!tmp) return -1;
   val = tmp->value;
   l->first = tmp->next;
   //if(l->first)l->first->prev = NULL;
   //else l->last = NULL;
   //free(tmp);
   return val;
}

dblist getInterval (dblist const * s) 
{
   dblist* intervals = NULL;
   memmove(&intervals, &l, sizeof(l));
   if(intervals->first)intervals->first->prev = NULL;
   else intervals->last = NULL;

   return *intervals;
}

void View (dblist l)
{
    elem *pelem = l.first;
    while (Pelem)
    {
       printf ("% d \ n", pelem-> value);
       pelem = pelem-> next;
     }
}

void ViewReverse (dblist l)
{
    elem* test = l.last;

    while (test)
    {
       printf("% d \ n", test-> value);
       test = test-> prev;
    }
}

void Clear (dblist * l)
{
   elem *tmp;
   elem *pelem = l->first;
   while(pelem)
   {
      tmp = pelem;
      pelem = pelem->next;
      free(tmp);
   }
   l->first = NULL;
   l->last = NULL;
}

main.c 

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

 #include "dblist.h"

 int main ()
 {
    dblist pdbListe * = malloc (sizeof (dblist));
    dblist interval;

    Init (pdbListe);
    printf ("Pushin In The gains list\n");
    PushFront (pdbListe, 10);
    Pushback (pdbListe, 20);
    Pushback (pdbListe, 40);
    PushFront (pdbListe, 23);
    PushFront (pdbListe, 70);
    PushFront (pdbListe, 54);

    printf ("Viewing the list:\n");
    View (pdbListe *);
    puts ("--------------");

    printf ("poping front capital gains from The Stack:\n");
    printf ("% d\n", PopFront (pdbListe));
    printf ("% d\n", PopFront (pdbListe));
    / / Printf ("% d\n", PopBack (pdbListe));
    puts ("--------------");

    printf ("Viewing the list after pop front:\n");
    View (pdbListe *);
    puts ("--------------");
    printf ("this is pdbListe:% p\n", pdbListe);
    printf ("this is interval:% p\n", & interval);

    interval = getInterval (pdbListe);
    printf ("Viewing the interval\n");
    ViewReverse (interval);
    printf ("first element is:% d\n", interval.first-> value);
    printf ("last element is:% d\n", interval.last-> value);
    puts ("--------------");

    printf ("Reverse Viewing the list after pop front:\n");
    ViewReverse (pdbListe *); // ISSUE HERE: it should print 6 elements not 4
    puts ("--------------");

    printf ("this is pdbListe:% p\n", pdbListe);
    printf ("this is interval:% p\n", & interval);
    printf ("sizeof pdbListe% d\n", sizeof (pdbListe));
    printf ("sizeof interval% d\n", sizeof (interval));

    printf ("Pushing back a value in The List:\n");
    Pushback (pdbListe, 30);

    printf ("Viewing the list after push back:\n");
    View (pdbListe *);
    puts ("--------------");

    printf ("In The Front popping list:\n");
    printf ("% d\n", PopFront (pdbListe));
    printf ("% d\n", PopFront (pdbListe));
    puts ("--------------");

    printf ("Viewing the list after pop front:\n");
    View (pdbListe *);
    puts ("--------------");
    printf ("Clearing the list\n");
    Clear (pdbListe);

    printf ("Freeing the list\n");
    free (pdbListe);

    system ("PAUSE");
    return 0;
}

Меня не волнует malloc.h, это небольшая утилита, которую я использую для обеспеченияправильная память usgae

Таким образом, проблема заключается в том, что переменная интервала исходит из getInterval(const dblist *), я хочу, чтобы она содержала только часть исходного списка, когда применено popBack или popFront.

Проблема в том, что если я внесу изменения в getInterval, это повлияет на значения pdbListe.Например, попробуйте изменить getInterval следующим образом (попробуйте прокомментировать эти строки, как показано ниже): 

dblist getInterval(const dblist* l) {
   dblist* intervals = NULL;
   memmove(&intervals, &l, sizeof(l));
   //if(intervals->first)intervals->first->prev = NULL;
   //else intervals->last = NULL;

   return *intervals;
}

Отсюда видно, что не только результат, возвращаемый getInterval (в данном случаепеременная-интервал в main.c), но также и переменная pdbListe, которая по сути никогда не должна изменяться!

Что я могу сделать, чтобы обойти это?Я хочу, чтобы pdbListe оставался таковым и никогда не зависел от того, что делает getInterval.

1 Ответ

0 голосов
/ 12 декабря 2010

Если вы хотите, чтобы getRange возвращал подсписок, в то время как исходный список остается неизменным, вам нужно изменить способ завершения (размещения конечных точек) вашего списка. Вам нужно прекратить использовать NULL в качестве маркера конца и вместо этого использовать сравнение с указателями первого / последнего элемента. Например: 

void printList(dblist *list) {
  for (elem *e = list->first; e != list->last; e = e->next) {
    printf("%d ", e->value);
  }
}

Обратите внимание на e != list->last, а не e != NULL.

Таким образом, вы можете создать подсписок, создав список dblist с новыми начальными / конечными точками. Он больше не требует каких-либо изменений для базовых ссылок (next и prev).

...