写一个C程序来创建一个链表的副本

Question

我想写一个copy_list函数，它创建一个链表(函数结果)，其中包含与copy_list的单个参数引用的链表相同的数据的新节点。但是我的copy_list函数不起作用。它进入无限循环，While循环不会停止。

我的结构

typedef struct name_node_s {
  char name[11];
  struct name_node_s *restp;
}name_node_t;
typedef struct {
  name_node_t *headp;
  int size;
}name_list_t;

My copy_list函数:

name_node_t *copy_list(name_node_t *head){
    name_node_t *current = head;
    name_node_t *newList = NULL;
    name_node_t *tail = NULL;
    while (current != NULL){
        if (newList == NULL) {
            newList = malloc(sizeof(name_node_t));
            strcpy(newList->name, current->name);
            newList->restp = NULL;
            tail = newList;
        }
        else {
            tail->restp = malloc(sizeof(name_node_t));
            tail = tail->restp;
            strcpy(tail->name, current->name);
            tail->restp = NULL;
        }
        current = current->restp;
    }
    return(newList);
}

剩余代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct name_node_s {
  char name[11];
  struct name_node_s *restp;
}name_node_t;
typedef struct {
  name_node_t *headp;
  int size;
}name_list_t;
name_node_t* presidents(void);
void insertAfter(name_node_t* mynode,name_node_t* newNode);
//void delete_last(name_node_t** headRef);
//void ListDelete(name_list_t* listP, char pname[]);
void lastDelete(name_list_t* listP);
void place_first(name_node_t **headRef, char pname[]);
name_node_t *copy_list(name_node_t *head);
int main(void)
{
  name_list_t list;
  name_list_t list_two;
  //name_node_t *np, *qp;
  list.headp = presidents();
  name_node_t *new_node;
  new_node = malloc(sizeof(name_node_t));
  strcpy(new_node->name, "Eisenhower");
  insertAfter(list.headp->restp, new_node);
  lastDelete(&list);
  place_first(&list.headp, "Mustafa");
  printf("%s %s %s %s", list.headp->name, list.headp->restp->name, list.headp->restp->restp->name, list.headp->restp->restp->restp->name);
  list_two.headp = copy_list(list.headp);
  printf("%s %s %s %s", list_two.headp->name, list.headp->restp->name, list.headp->restp->restp->name, list.headp->restp->restp->restp->name);
  return(0);
}
name_node_t* presidents(void)
{
  name_node_t* head = NULL;
  name_node_t* second = NULL;
  name_node_t* third = NULL;
  head = malloc(sizeof(name_node_t));
  second = malloc(sizeof(name_node_t));
  third = malloc (sizeof(name_node_t));
  strcpy(head->name, "Washington");
  head->restp = second;
  strcpy(second->name, "Roosevelt");
  second->restp = third;
  strcpy(third->name, "Kennedy");
  third->restp = NULL;
  return(head);
}
void insertAfter(name_node_t* mynode,name_node_t* newNode)
{
    newNode->restp = mynode->restp;
    mynode->restp = newNode;
}
void ListDelete(name_list_t* listP, char pname[]){
    name_node_t *to_freep, *cur_nodep;
    if(strcmp(listP->headp->name, pname)){
        to_freep = listP->headp;
        listP->headp = to_freep->restp;
        --(listP->size);
    }
    else {
        for (cur_nodep = listP->headp;
            cur_nodep->restp != NULL && !strcmp(cur_nodep->restp->name, pname);
            cur_nodep = cur_nodep->restp) {
                if( cur_nodep->restp != NULL && strcmp(cur_nodep->restp->name, pname)) {
                    to_freep = cur_nodep->restp;
                    cur_nodep->restp = to_freep->restp;
                    free(to_freep);
                    --(listP->size);
                }
            }
        }
    }
void lastDelete(name_list_t* listP){
    name_node_t *to_freep, *cur_nodep;
    for (cur_nodep = listP->headp;
            cur_nodep->restp != NULL;
            cur_nodep = cur_nodep->restp) {}
    to_freep = cur_nodep;
    cur_nodep->restp = to_freep->restp;
    free(to_freep);
    --(listP->size);
}
void place_first(name_node_t **headRef, char pname[]) {
    name_node_t *newNode = malloc(sizeof(name_node_t));
    strcpy(newNode->name, pname);
    newNode->restp = *headRef;
    *headRef = newNode;
}
/*name_node_t *copy_list(name_node_t *head) {
    name_node_t *current = head;
    name_node_t *newList = NULL;
    name_node_t **lastPtr;
    lastPtr = &newList;
    while (current != NULL) {
        printf("**");
        place_first(lastPtr, current->name);
        lastPtr = &((*lastPtr)->restp);
        current = current->restp;
    }
    return(newList);
}*/
/*name_node_t *copy_list(name_node_t *head) {
    if (head == NULL)
        return NULL;
    else {
        name_node_t *newList = malloc(sizeof(name_list_t));
        strcpy(newList->name, head->name);
        newList->restp = copy_list(head->restp);
        return(newList);
    }
}*/
/name_node_t *copy_list(name_node_t *head){
    name_node_t *current = head;
    name_node_t *newList = NULL;
    name_node_t *tail = NULL;
    while (current != NULL){
        if (newList == NULL) {
            newList = malloc(sizeof(name_node_t));
            strcpy(newList->name, current->name);
            newList->restp = NULL;
            tail = newList;
        }
        else {
            tail->restp = malloc(sizeof(name_node_t));
            tail = tail->restp;
            strcpy(tail->name, current->name);
            tail->restp = NULL;
        }
        current = current->restp;
    }
    return(newList);
}

Answer 1

在lastDelete()中，这个循环:

for (cur_nodep = listP->headp;
            cur_nodep->restp != NULL;
            cur_nodep = cur_nodep->restp) {}

…在列表中的最后一个节点处停止。之后，您永远不会在倒数第二个元素中将restp设置为NULL。您只工作在最后一个，因为to_freep和cur_nodep指向相同的元素。

Answer 2

这可能更容易递归，因为单链表是递归结构:

• NULL的拷贝就是NULL。
• name_node_t的副本是一个新的malloc 'd name_node_t，具有与原件相同的name和原件restp的副本作为其restp。

Answer 3

我写c++已经很久了。:

看起来不像在copy_list中有任何东西应该使它进入无限循环。

逻辑有:while (current!=null) current = current->next;

也许copy_list在一个错误的列表中传递?(即列表的最后一个元素没有restp == null)。

您正在呼叫:
insertAfter(…);
lastDelete(…),
…

copy_list(…);

所以问题可能是在insertAfter或lastDelete…还是…

检查lastDelete:

 name_node_t *to_freep, *cur_nodep;
 for (cur_nodep = listP->headp;
        cur_nodep->restp != NULL;
        cur_nodep = cur_nodep->restp) {}
 to_freep = cur_nodep;
 cur_nodep->restp = to_freep->restp;
 free(to_freep);   //what if listP->headp was null? i.e. list had size 0?
--(listP->size);

很多问题

1. 如果传递给你一个0个元素的列表怎么办?
2. 如果你传递了一个只有一个元素的列表怎么办?
3. 在释放"to_freep"之后的任何情况下，在"to_freep"之前的节点没有将其restp设置为null。因此，最后第二个节点现在指向一个已删除的节点!这意味着列表永远不会终止。

一个更好的lastDelete:(只是一个算法，不记得语法了…)

if (head == null) return; //do nothing
if (head->next == null) 
{
  listP->head = null;
  listP->size = 0;
  return;
}
node* prev = head;
head = head->next;
while (head->next != null)
{
   prev = head;
   head = head->next;
}
//now prev points to a 2nd last node
//head points to last node
free(head);
prev->restp = null;