C中双向链表中的const结构正在被修改

Question

我正在处理双向链表，遇到了一个我无法解决的问题。为了更好地说明它，在我说问题是什么之前，这是代码。

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;
}

ma​​in.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，它是我用来确保正确的内存使用的小实用程序

所以问题是间隔变量来自 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 正在执行的操作的影响。

Answer 1

如果您希望 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 来创建子列表。它不再需要对底层链接(下一个和上一个)进行任何修改。