C 링크 된 목록의 버블 정렬

Question

입력 파일에서 링크 된 목록으로 읽어야합니다. 파일의 일부는 다음과 같습니다

NameA, 25
NameB, 33
NameC라는 이름의 23
, 39

그리고 내가 수 (버블 정렬)으로 정렬하고 서로를 쓸 필요가 후 파일.

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

struct node{ 
    char name[20]; 
    int number; 
    struct node *next; 
    struct node *prev; 
}*head; 

int main(void) { 

    struct node *temp; 
    temp = malloc(sizeof(struct node)); 
    temp->next = NULL; 
    head = temp; 

    FILE *ifp; 
    char fnamer[100] = ""; 
    char line[128]; 
// printf("\n\nPlease Enter the Full Path of the file: \n"); 
// scanf("%s",&fnamer); 

    ifp = fopen("mintaadatok.txt", "r"); 
    if (ifp == NULL) { 
     printf("\n%s\" File NOT FOUND!", fnamer); 
     exit(1); 
    } 

    int c = 0; 

    char buffer[1024]; 
    memset(buffer, 0, 1024); 
    while (c < 15) { 
     fgets(buffer, 1024, ifp); 
     sscanf(buffer, "%19[^,], %d", temp->name, &temp->number); 
     printf("%d %s %d\n", c, temp->name, temp->number); 
     temp->next = malloc(sizeof(struct node)); 
     temp = temp->next; 
     temp->next = NULL; 
     c++; 
    } 

    int i,step; 
    for (temp = head; temp; temp = temp->next) { 
     printf("%s", temp->name); 
     printf("%d\n", temp->number); 
     for(step=0;step<10-1;++step) 
      for(i=0;i<10-step-1;++i) 
      { 
       temp->next = malloc(sizeof(struct node)); 
       if(temp->number>temp->next) 
       { 
        temp=temp->number; 
        temp->number=temp->next; 
        temp->next=temp; 
       } 
      } 
    } 
    printf("In ascending order: "); 
} 

당신이 날이 데이터를 정렬하는 데 도움이 있습니다 : 여기

내가 가진 무엇인가? 는

Answer 1

while(c<10) 
{ 
    fgets(buffer, 1024, ifp); 
    sscanf(buffer, "%19[^,], %d", temp->name, &temp->id); 
    ... 
} 

파일을 읽을 수 행이 더 이상 없을 때 중지됩니다 while(fgets(buffer, 1024, ifp)){...}이를 사용하는 4 개 항목,하지 (10) 파일을 읽을 수있는 더 좋은 방법을 가지고 나타납니다. main을 종료하자마자 메모리가 해제되기 때문에 여기서는 중요하지 않지만 실용적인 응용 프로그램에서는 코드를 다른 기능으로 실행하고 메모리를 확보해야합니다.

malloc을 추가로 호출했기 때문에 연결된 목록이 완전히 올바르지 않습니다.이 메모리를 해제 할 수 없습니다.

버블 정렬을 사용하여 연결된 목록을 정렬하는 것은 쉬운 일이 아닙니다. 더 좋은 방법은 파일을 node의 배열로 읽어 들이고 realloc을 사용하는 것입니다. 그런 다음 배열에 버블 정렬을 사용하십시오. 또는 연결된 목록을 배열로 변환 할 수 있습니다 (무의미 함)

그렇지 않으면 연결된 목록에서 버블 정렬을 사용하여 두 개의 루프를 만들어 목록을 탐색 한 다음 각 노드의 값을 비교하고 변경할 수 있습니다.

예제는 아래 목록의 선두에있는 항목을 (리스트가 정렬되고 있기 때문에이 문제가되지 않습니다) 삽입 및 버블 정렬 실행합니다.

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

int main(void) 
{ 
    FILE *ifp = fopen("mintaadatok.txt", "r"); 
    if (!ifp) 
    { 
     printf("file error\n"); 
     return 0; 
    } 

    char buffer[1024]; 
    memset(buffer, 0, 1024); 
    while(fgets(buffer, 1024, ifp)) 
    { 
     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; 
     } 
    } 

    //bubble sort here: 
    struct node *loop1 = head; 
    while(loop1) 
    { 
     int swapped = 0; 
     struct node *loop2 = loop1->next; 
     while(loop2) 
     { 
      if(loop1->id > loop2->id) 
      { 
       //swap the values for `name` and `id` 
       //but don't change the `next` pointers 
       char name[20]; 
       strcpy(name, loop1->name); 
       strcpy(loop1->name, loop2->name); 
       strcpy(loop2->name, name); 

       int id = loop1->id; 
       loop1->id = loop2->id; 
       loop2->id = id; 
       swapped = 1; 
      } 

      loop2 = loop2->next; 
     } 

     //if there were no swaps then list is already sorted 
     if (!swapped) 
      break; 

     loop1 = loop1->next; 
    } 

    //print the list: 
    loop1 = head; 
    while(loop1) 
    { 
     printf("%s %d\n", loop1->name, loop1->id); 
     loop1 = loop1->next; 
    } 

    return 0; 
} 

Answer 2

우리 초보자가 서로 도움이 될 것입니다을 :)

나는 모든 코드를 살펴 보지 않았습니다. 그러나 때문에 그래서 마지막 노드는 데이터 멤버 next 제외하고 불확정 값으로 데이터 멤버를해야합니다이 루프

while (c < 15) { 
    fgets(buffer, 1024, ifp); 
    sscanf(buffer, "%19[^,], %d", temp->name, &temp->number); 
    printf("%d %s %d\n", c, temp->name, temp->number); 
    temp->next = malloc(sizeof(struct node)); 
    temp = temp->next; 
    temp->next = NULL; 
    c++; 
} 

의 노드 할당의 잘못된 순서로 예를 들어 분명히 잘못된 것입니다.

단일 링크 된 목록에 대한 버블 정렬 기능을 작성하는 방법.

단일 링크 목록에 대한 버블 정렬 기능을 작성하는 것은 당신과 나 같은 초보자에게는 쉬운 작업이 아닙니다. 예를 들어 목록의 노드에 대해 스왑 함수를 올바르게 작성해야합니다.

여기 있습니다.

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

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

int push_back(struct node **head, const char *name, int id) 
{ 
    struct node *tmp = malloc(sizeof(struct node)); 
    int success = tmp != NULL; 

    if (success) 
    { 
     while (*head != NULL) head = &(*head)->next; 

     strcpy(tmp->name, name); 
     tmp->id = id; 
     tmp->next = NULL; 

     *head = tmp; 
    } 

    return success; 
} 

void display(struct node **head) 
{ 
    for (struct node *current = *head; current != NULL; current = current->next) 
    { 
     printf("{ %s, %d } ", current->name, current->id); 
    } 
} 

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


void bubble_sort(struct node **head, int cmp(const void *, const void *)) 
{ 
    if (*head != NULL) 
    { 
     for (struct node *last = NULL, *swapped = NULL; (*head)->next != last; last = swapped) 
     { 
      swapped = (*head)->next; 

      for (struct node **first = head; (*first)->next != last; first = &(*first)->next) 
      { 
       if (cmp((*first)->next, *first) < 0) 
       { 
        swap(first); 
        swapped = (*first)->next; 
       } 
      } 
     } 
    } 
} 

int cmp_id(const void *a, const void *b) 
{ 
    const struct node *left = a; 
    const struct node *right = b; 

    return (right->id < left->id) - (left->id < right->id); 
} 

int cmp_name(const void *a, const void *b) 
{ 
    const struct node *left = a; 
    const struct node *right = b; 

    return strcmp(left->name, right->name); 
} 

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

    push_back(&head, "NameA", 25); 
    push_back(&head, "NameB", 33); 
    push_back(&head, "NameC", 23); 
    push_back(&head, "NameD", 39);  

    display(&head); 
    putchar('\n'); 

    bubble_sort(&head, cmp_id); 

    display(&head); 
    putchar('\n'); 

    bubble_sort(&head, cmp_name); 

    display(&head); 
    putchar('\n'); 

    return 0; 
} 

프로그램 출력 먼저리스트 ID에 의해 분류되고있는 프로그램의 예시적인

{ NameA, 25 } { NameB, 33 } { NameC, 23 } { NameD, 39 } 
{ NameC, 23 } { NameA, 25 } { NameB, 33 } { NameD, 39 } 
{ NameA, 25 } { NameB, 33 } { NameC, 23 } { NameD, 39 } 

인 명칭으로하고.

이제는 사용한 파일의 데이터에서 목록을 올바르게 작성해야합니다.

Answer 3

연결된 목록을 정렬하려면 먼저 머리 포인터가 필요하고 두 개의 포인터가 필요하며 구현은 버블 정렬과 동일하지만 약간의 차이는 있지만 링크 된 목록 요소는 색인으로 직접 액세스 할 수 없습니다. 버블 정렬에서 배열을 할 때와 마찬가지로 값을 비교하기 위해 다음 두 포인터를 사용해야합니다.

pptr=head; //for the previou element 
    ptr=head->next;//for the next element 

    if(pptr->value > ptr->value) //comparing the value in linked list 

두 개의 포인터를 늘리는 것을 잊지 마십시오.