정렬 된 순서로 포인터에 문제가 발생했습니다.

Question

char *를 LinkedList에 추가하여 linkedList가 항상 사전 순으로 정렬되도록하는 방법을 만들고 있습니다.

// Adds a new item to the beginning of a list, returning the new 
// item (ie the head of the new list *) 
ListItem* add_item(ListItem *p_head, char *s) { 
    // Allocate some memory for the size of our structure. 
    ListItem *p_new_item = malloc(sizeof(ListItem)); 
    p_new_item->p_next = p_head;  // We are the new tail. 
    p_new_item->s = s;  // Set data pointer. 
    return p_new_item; 
} 

지금 여기에 내가 ', 내 코드입니다 : 나는 또한 목록의 시작 부분에 항목을 추가하는 방법을 주어졌다

// Define our list item as 'struct ListItem', and also 
// typedef it under the same name. 
typedef struct ListItem { 
    char *s; 
    struct ListItem *p_next; 
} ListItem; 

: 나는 LinkedItem 구조체를 정의하는 코드를 주어졌다 더 후 설명 할 것이다 : A와 B의 올바른 정렬 된 순서는 A, 그 다음 B, 거짓 otherwise- 평등 경우 지금

ListItem* addSortedItem(ListItem *p_head, char *s){   
    if(p_head==NULL)//if the list is empty, we add to the beginning 
     return add_item(p_head,s); 
    ListItem* p_new_item = malloc(sizeof(ListItem)); 
    ListItem *p_current_item = p_head; //makes a pointer to the head of the list 


    while (p_current_item) { // Loop while the current pointer is not NULL 
     printf("entering while loop with current=%s\n",p_current_item->s); 
     // now we want to look at the value contained and compare it to the value input  
     if(aThenB(s,p_current_item->s)!=TRUE){ 
      // if A goes after B, we want to go on to look at the next element 
      p_current_item=p_current_item->p_next; 
     } else if (aThenB(s,p_current_item->s)==TRUE) {printf("entered elseif\n");  
      p_head=add_item(p_current_item,s); 
      return p_head;   
     } else {printf("WHY DID WE EVER REACH THE ELSE!?"); return p_head;} 
    } 
} 

, aThenB (StringA, StringB)가 true를 돌려주는 것은 옵션, 나는 단순히 천국도 이거 작동하지 않아. l :

내 테스트 데이터 (0에서 10까지의 숫자 인 "sheep i")는 하나의 요소 만 반환하거나 임의로 요소를 건너 뛸 때 발생합니다. 주문 입력. 더 많은 코드를 포함 할 수 있지만 약간 지저분합니다.

필자의 문제점은 포인터를 완전히 이해하지 못하고 어떻게 동작하는지에 기인한다고 생각합니다. p_head가 항상 머리를 가리키고, p_current가 목록을 통해 이동하고 있음을 보장하고자합니다. 하지만 p_current가 마지막 요소에 도달하면 seg faults가 발생하므로 어디서 잘못 될지 잘 모르겠습니다.() main 메소드에 다음 블록에서 호출 addSortedItem : 처음에는

// The empty list is represented by a pointer to NULL. 
    ListItem *p_head = NULL; 
    ListItem *p_head2=NULL; 
    // Now add some items onto the beginning of the list. 
    int i; 
    for (i=0; i<NO_ITEMS; i++) { 

    // Allocate some memory for our string, and use snprintf to 
    // create a formatted string (see GNU API docs) much like printf 
    // but instead writing to memory rather than the screen. 
    char* s = malloc(MAX_DATA_CHARS); 
    snprintf(s, (size_t) MAX_DATA_CHARS, "sheep %d", i); 
    p_head = addSortedItem(p_head, s); 
    } 

Answer 1

링크 된 목록의 중간 또는 끝에 새 요소를 추가 할 때 오류가 있습니다.당신의 addStoredItem 기능에 당신은 currentItem로 인 newItem에서 포인터를 만들하지만 당신은 링크 된 목록 addStoredItem

item1-->item2-->item4-->item5 

를 호출을 befor 인 newItem

초기 연결리스트로 이전 요소에서 링크를 가지고 고려하지 않는다 위해 addStoredItem를 호출 afetr 당신이 adde을 볼 수 항목 3

item1-->item2-->item4-->item5 
       ^
       | 
       item3 

그래서 추가 D 서브 연결리스트의 머리에 새 항목이 item4에서 시작하지만 당신은 우리가 링크를 완료하기 위해 이전 항목에 대한 포인터를 유지해야한다는 항목 3 에 항목 2에서 링크를하지 않습니다 .

add_item() 기능은 머리에 항목을 추가 할 수

같은 일이 당신은

item1-->item2-->item4-->item5 NULL 
           ^
           | 
           item6 

가 item6 별도의 머리로 추가 한 연결리스트의 마지막에 항목을 추가하려고하면 및

그래서 당신의 addStoredItem() 기능 수 (신규) item6에 item5 (이전)로부터 링크가 없습니다 이

ListItem* addSortedItem(ListItem *p_head, char *s){   
    if(p_head==NULL)//if the list is empty, we add to the beginning 
     return add_item(p_head,s); 
    struct ListItem* p_new_item = malloc(sizeof(ListItem)); 
    ListItem *p_current_item = p_head; //makes a pointer to the head of the list 
    ListItem *p_prev_item = NULL; //FIXED 

    while (p_current_item) { // Loop while the current pointer is not NULL 
     printf("entering while loop with current=%s\n",p_current_item->s); 
     // now we want to look at the value contained and compare it to the value input  
     if(aThenB(s,p_current_item->s)!=TRUE){ 
      // if A goes after B, we want to go on to look at the next element 
      p_prev_item = p_current_item; //FIXED 
      p_current_item=p_current_item->p_next; 
     } else if (aThenB(s,p_current_item->s)==TRUE) {printf("entered elseif\n");  
      break;   
     } else {printf("WHY DID WE EVER REACH THE ELSE!?"); return p_head;} 
    } 

    if (p_prev_item!=NULL) //FIXED 
     p_prev_item->p_next=add_item(p_current_item,s); //FIXED 
    else //FIXED 
     p_head=add_item(p_current_item,s);//FIXED 
    return p_head; //FIXED 
} 

처럼 고정 고정 라인 //FIXED

Answer 2

는

편집 :-) 제대로 반환하려면 코드를 얻는 방법에 어떤 도움을 주셔서 감사합니다 p_head은 NULL이므로 addSortedItem 함수를 입력하면 목록을 만들고 첫 번째 문자열을 추가합니다. 그 괜찮아요.
하지만 두 번째 항목 ("양 1"인 경우)을 추가 할 때 while (p_current_item) 루프를 입력하십시오. aThenB에 대한 전화는 FALSE을 반환하고 다음 요소 인 .. NULL으로갑니다! 사실,이 시간에, p_head는 다음과 같습니다

p_head { 
s = "sheep 0", 
p_next = NULL 
} 

귀하의 while 조건이 사실이 아니다 당신이 당신의 기능을 종료, 아무것도 첨가하지 않았다.
당신은 당신의 첫번째 if 등의 조건을 추가 할 수 있습니다

if (p_current_item->next == NULL) 
    p_current_item->next = addSortedItem(NULL, s); 
else 
    p_current_item = p_current_item->next; 

또한, p_head=add_item(p_current_item,s);가 잘못되었다는 말. 목록은 같은 것입니다 가정 : 당신이 "양 3"을 추가하는 경우

"sheep 1" -> "sheep 2" -> "sheep 4" -> "sheep 5" 

을, 당신이 얻을 것이다 :

"sheep 1" -> "sheep 2" -> "sheep 3" -> "sheep 4" -> "sheep 5" 
         ^
          | 
          p_head 

당신은 더 이상 "양 0"을 추가 할 수 없습니다. addSortedItem의 반환 값을 새 값으로 반환하지 마십시오. p_head

Answer 3

지원 재료로 표시됩니다 :

#define FALSE 0 
#define TRUE 1 
#define aThenB(a,b) (strcmp(a,b) <=0 ? TRUE : FALSE) 

모든 특별한 경우를 피할 수 에 함수의 서명을 수정하여 포인터를 받아 바늘.

void addSortedItem(ListItem **pp_head, char *s){   
    ListItem *p_new_item ; 

    for (  ;*pp_head; pp_head = &(*pp_head)->p_next) {  
     if (aThenB(s,(*pp_head)->s)==FALSE) break; 
    } 

    p_new_item = malloc(sizeof *p_new_item); 
    p_new_item->s = s; 

    p_new_item->p_next = *pp_head; 
    *pp_head = p_new_item; 
} 

호출자는 수행해야합니다

ListItem *root = NULL; 
addSortedItem(&root, "sheep#0");