リンクリスト

Question

のコピーを作成するためのCプログラムを書く私は、単一の引数が参照するリンクリストとして同じデータを含む新しいノードとリンクリストを作成するcopy_list機能（関数結果）を書きたいですcopy_list.But私の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; 

マイ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

、このループ：

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

...は、リスト内の最後のノードで停止します。その後、restpを最後の要素のNULLに設定することはありません。最後のものはto_freepで、cur_nodepは同じ要素を指しています。

Answer 2

重リンクリストは、再帰的な構造であるため、これは、再帰的に行うことが容易になることがあります。

• A NULLのコピーはNULLにすぎません。
• name_node_tのコピーがたてmallocある「元のrestpそのrestpなどのオリジナルとコピーと同じnameでname_node_tはd。 lastDelete()で

Answer 3

私はC++を書いたので、それは長い時間がかかりました。まだ：それは無限ループに行かせるべきでcopy_listに何があるかのように

見えません。

ロジックがあります。 while (current!=null) current = current->next;

おそらくcopy_listが悪いリストで渡されていますか？ （すなわち、最後の要素がrestp == nullを持たないリスト）。メインで

あなたが呼んでいる：
insertAfter（...）;
lastDelete（....）;
... copy_list（....）;

だから問題はinsertAfterになる可能性やlastDelete ...か...

チェックlastDelete：あなたが渡されている場合は何の問題

1. の

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

   充実しています0要素のリスト？

2. 1要素のリストを渡すとどうなりますか？いずれの場合においても
3. あなたの後の自由「to_freep」、前に「to_freep」へのノードは、それがnullに設定RESTPだありません。したがって、2番目の最後のノードは、削除されたノードを指します。つまり、リストは決して終了しません。

良く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;