데이터를 스와핑하지 않고 링크 된 목록의 노드 스왑

Question

어떻게 데이터를 복사하지 않고 포인터를 사용할 수 있습니까? 거품 정렬 함수를 작성하고 싶지만 막혔습니다. 값 대신 노드 주소를 바꿀 수있는 방법이 필요합니다. 나는 도시의 이름 및 온도를 가진 파일이 있습니다

• 라스 베이거스, 25
• 뉴욕, 33
• 시카고, 23
• 휴스턴, 39

을 내가 필요 온도에 따라 분류하고 다른 파일에 쓰십시오.

UPDATE : 좋아, 지금은 내가 theoratical 부분을 이해 생각 :

// p is my node 
// p-prev -> p -> p-next -> p-next-next 
prev->next = p->next; 
p->next = p->next->next; 
prev->next->next = p; 

이 내가 노드를 교체하기 위해해야 ​​할 일이지만, 구문 내가 그것을 작동하게 couldnt한다. 싱글 링크드리스트에 두 개의 노드를 교환하기 위해

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

struct node { 
    char name[128]; 
    int id; 
    struct node *next; 
}*head; 

void readFile() { 
    char fnamer[128] = ""; 
    printf("\nEnter the file name to read (delimiter: ,): \n"); 
    scanf("%s",&fnamer); 
    FILE *inf = fopen(fnamer, "r"); 

    char buffer[1024]; 
    memset(buffer, 0, 1024); 
    while(fgets(buffer, 1024, inf)){ 
     struct node *temp = malloc(sizeof(struct node)); 
     temp->next = NULL; 

     if(sscanf(buffer, "%19[^,], %d", temp->name, &temp->id) != 2){ 
      free(temp); 
      break; 
     } 

     if(!head){ 
      head = temp; 
     } else{ 
      temp->next = head; 
      head = temp; 
     } 
    } 

    fclose(inf); 
} 

int main(void) { 
    // Read a linked list from file 
    readFile(); 

    //Bubble sort in linked list 
    struct node *loop1 = head; 
    while(loop1){ 
     struct node *loop2 = loop1->next; 
     while(loop2){ 
      if(loop1->id > loop2->id){ 

       // Swap next pointers 
       // This is not working 
       struct node *temp = loop1->next; 
       loop1->next = loop2->next; 
       loop2->next = temp; 

      } 
      loop2 = loop2->next; 
     } 
     loop1 = loop1->next; 
    } 

    // Print the sorted linked list to file: 
    char foutname[100]=""; 
    printf("\nPlease Enter the file name to write the result: \n"); 
    scanf("%s",&foutname); 

    FILE *outf; 
    outf = fopen(foutname, "w+"); 

    loop1 = head; 
    while(loop1){ 
     printf("%s %d\n", loop1->name, loop1->id); 
     fprintf(outf, "%s %d\n", loop1->name, loop1->id); 
     loop1 = loop1->next; 
    } 
    fclose(outf); 
    return 0; 
} 

Answer 1

next 링크를 교체해야 링크 체인이 다시 정렬됩니다. 당신이 node1 및 node2 교환 할 경우, 다음과 같이 변경해야합니다 링크 체인은 다음과 같습니다 더 이상 스왑이없는 경우

//change the link chain from 
node0 -> node1 -> node2 -> node3 
//to 
node0 -> node2 -> node1 -> node3 

우리는 while 루프와 루프 나누기 안에이 넣어. 번호 비교를 제한하여이 기능을 개선 할 수 있습니다. 각 루프 후에 마지막 요소를 정렬해야합니다.

typedef 키워드를 사용하면 어디서나 struct을 반복 할 필요가 없습니다.

typedef struct node_t 
{ 
    char name[20]; 
    int id; 
    struct node_t *next; 
} node; 

void bubblesort(node **list) 
{ 
    if(!(*list)) return; 
    node *previous_node = NULL; 
    node *sort_up_to = NULL; 
    while(1) 
    { 
     previous_node = NULL; 
     node *ptr = *list; 
     node *last_change = NULL; 
     while(ptr->next) 
     { 
      //the rest of the list is sorted? 
      if(sort_up_to && ptr == sort_up_to) break; 

      node *next = ptr->next; 
      if(ptr->id > next->id) 
      { 
       if(previous_node == NULL) 
        *list = next; 
       else 
        previous_node->next = next; 
       ptr->next = next->next; 
       next->next = ptr; 
       last_change = next; 
      } 

      previous_node = ptr; 
      ptr = next; 
     } 

     //list is all sorted? 
     if(!last_change) break; 

     sort_up_to = last_change; 
    } 
} 

int main(void) 
{ 
    node* head = NULL; 

    FILE *fin = fopen("test.txt", "r"); 
    if(!fin) 
     return 0; 

    node temp; 
    while(fscanf(fin, "%19[^,], %d\n", temp.name, &temp.id) == 2) 
    { 
     node *n = malloc(sizeof(node)); 
     n->next = NULL; 
     strcpy(n->name, temp.name); 
     n->id = temp.id; 
     if(head) 
      n->next = head; 
     head = n; 
    } 
    fclose(fin); 

    bubblesort(&head); 

    for(node* n = head; n != NULL; n = n->next) 
     printf("%s %d\n", n->name, n->id); 

    return 0; 
} 

Answer 2

당신은 헤드 노드를 교환 예를 들어 다음과 같은 기능

void swap(struct node **current) 
{ 
    struct node *tmp = (*current)->next->next; 
    (*current)->next->next = *current; 
    *current = (*current)->next; 
    (*current)->next->next = tmp; 
} 

을 사용할 수 있으며 다음 노드 당신은

같은 함수를 호출 할 수 있습니다

swap(&head); 

또한이 참조에 내 대답을 참조하십시오. Bubble sort in c linked list 여기에는 단일 연결 목록에 대한 버블 정렬 알고리즘을 작성하는 방법이 나와 있습니다.