연결된 목록 정렬 문제

Question

버블 정렬을 사용하여 연결된 목록을 정렬하려고합니다. 노드 안의 값을 바꿀 수는 없습니다. 나는 도움없이 스스로 할 수있는 방법을 알아 내려고 그림을 그려 왔지만 머리가 아파지기 시작했으며 왜 이것이 효과가 없는지 알 수 없습니다.

void sort_ascending(struct node ** head){ 
    int x; 
    struct node*temp; 
    struct node*temp2; 
    x = length(*head)+1; //checks if more than one node is in the list 
    if(x < 2){ 
    printf("1 or less\n"); 
    //free(temp); 
    return; 
    } 
    printf("longer than 1\n"); 
    printf("%d %d\n", (*head)->val, (*head)->next->val); 
    if((*head)->val > (*head)->next->val){ 
    printf("needs to sort!\n"); 
    temp = (*head)->next->next; //sets temp to the node after the two nodes being swapped 
    printf("test1\n"); 
    temp2 = (*head); //sets temp2 to the node1 
    printf("test2\n"); 
    *head = (*head)->next; //changes head to point at node2 instead of node1 
    printf("test3\n"); 
    (*head)->next = temp2; //sets node2 to point to node1 
    (*head)->next->next = temp; //sets node2 to point back into the list 
    printf("test4\n"); 
    //free(temp); 
    } 
} 

지금은 두 노드를 정렬하려고합니다. 이 작업을 수행 한 후에 루프로 만들 것입니다. 웬일인지 처음 두 요소를 정렬하지도 않습니다.

은 여기 내 다른 기능 중 일부는 이해를 돕기 위해 다음과 같습니다

구조체 정의 :

struct node { 
int val; 
struct node *next; 

};

다른 기능 :

void push(struct node ** headRef, int data){ 
struct node* newNode = malloc(sizeof(struct node)); //alocates space on heap 
printf("pushed node\n"); 
newNode->val = data;//sets data value 
printf("%d\n", newNode->val); 
newNode->next = *headRef; // The '*' to dereferences back to the real head 
*headRef = newNode; // ditto 

};

void print(struct node * head, int length){ 
int x = 0; 
printf("tried to print\n"); 
//struct node*temp = head; 

//while(head->next != NULL){ 
while (x < length + 1){ 
    printf("ran loop\n"); 
    printf("%d\n", head->val); 
    printf("got number\n"); 
    head = head->next; 
    x++; 
} 
printf("done with loop\n"); 

}

int main(){ 
char ans; 
int num; 
struct node *head = NULL; 
do { 
    do { 
     printf("Enter a number: "); 
     scanf("%d", &num); 
     push(&head, num);//Can change to append for back 

     printf("Do you want another num (y or n): "); 
     scanf("%1s", &ans); 
    } while (ans == 'y'); 

    printf("Sort ascending or descending (a or d)? "); 
    scanf("%1s", &ans); 
    if(ans == 'a') sort_ascending(&head); 
    //else if(ans == 'd') sort_descending(&head); 

    print(head, length(head)); 

    printf("Do you want to do this again (y or n)? "); 
    scanf("%1s", &ans); 
    if (ans == 'y') clear(&head); 

} while (ans == 'y'); 


return 0; 

}

int length(struct node* head){ 
int length = 0; 
//struct node*temp = head; 
printf("tried to find length\n"); 
while (head->next != NULL){ 
    length++; 
    head = head->next; 
} 
printf("%d\n", length + 1); 
return length; 

}

Answer 1

자, 정리해 보자.

함수 길이 함수 인쇄가 너무 많은 인쇄 1.

int length(struct node* head){ 
    int length = 0; 
    while (head != NULL){ 
     ++length; 
     head = head->next; 
    } 
    return length; 
} 

으로 해제되어 있습니다.

void print(struct node * head, int length){ 
    int x; 
    for(x = 0; x < length; ++x){ 
     printf("%d\n", head->val); 
     head = head->next; 
    } 
} 

그리고 scanf가 메모리를 손상시키고 있습니다. "% 1s"을 (를) 가진 scanf는 적어도 두 개의 문자 (하나는 저장하고 후행 null 바이트)에 대한 포인터를 예상합니다. 따라서 두 개의 문자 (char ans[2];)를 제공하거나보다 나은 해결책은 한 문자를 문자로 읽는 것입니다. 궁금하면 내가 (같은 ++x를) ++ 앞에 당신의 후위 ++ (x++ 등) 변경 왜 C.

로 프로그래밍하는 경우 don't cast the return value of malloc, 말했듯이

char ans; 
scanf("%c", &ans); 

또한 : 나는 오전 C++ 프로그래머와 C++의 경우 성능상의 이유 때문에 접미어 ++를 postfix ++보다 선호하는 것이 좋습니다 (int 또는 포인터와 관련이 없지만 반복자와 같은 복잡한 유형의 경우).