Сортировка узлов в СВЯЗАННОМ СПИСКЕ по алфавиту путем сравнения строк, хранящихся в каждом узле. (Программа C)

ProgramBox

Сортировка узлов в СВЯЗАННОМ СПИСКЕ по алфавиту путем сравнения строк, хранящихся в каждом узле. (Программа C)

Post author:admin
Запись опубликована:4 февраля, 2023
Post category:Вопросы по программированию

Вопрос:

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STR_LEN 80

//STRUCT
typedef struct link_node
{
char node_str[MAX_STR_LEN];
struct link_node *next;
} link;

// FUNCTION CALLS
link *Nodes_Create(int num);
int compare_node(link *n1, link *n2);
link *add_node(link *list, link *node);
void display_list(link *head);

//MAIN
int main() {
    int num, i;
    link *Head;
    link *Rest;
    link *Temp;

    printf("how many users? ");
    scanf("%d", amp;num);
    getchar(); //DEBUGGING

    Head = Nodes_Create(num);
    display_list(Head);

    //COMPARE
    Rest = Head;
    for(i = 0; i < num - 1; i  ) {
        if(compare_node(Rest, Rest->next) == -1) {  //for example: 28->17->08->54
            printf("nTRUE");
            Temp = Rest->next;
            Rest->next = Rest; //NOT WORKING!!!
            Rest = Temp;
        }
        else printf("nFALSE");
        Rest = Rest->next;
    }

    return 0;
}
//FUNCTION FOR CREATING NODES
link *Nodes_Create(int num) {
    link *Temp = NULL;
    link *Head = NULL;
    link *Rest = NULL;
    char userName[MAX_STR_LEN];
    int i;

    for(i = 0; i < num; i  ) {
        //ALLOCATE MEMORY FOR TEMP NODE
        Temp = (link*)malloc(sizeof(link));
        //GET STRING IN TEMP->node_str
        printf("Enter the user name for user N%d: ", i   1);
        fgets(userName, MAX_STR_LEN, stdin);
        strcpy(Temp->node_str, userName);
        Temp->next = NULL;

        //CREATING NODES
        if (Head == NULL) {
            Head = Temp;
        }
        else {
            Rest = Head;
            while(Rest->next != NULL) {
                Rest = Rest->next;
            }
            Rest->next = Temp;
        }
    }
    return Head;
}
//FUNCTION FOR COMPARING NODES
int compare_node(link *n1, link *n2) {
    link* Temp;

    if(n1->node_str[0] > n2->node_str[0])
        return -1;
    else if(n1->node_str[0] == n2->node_str[0])
        return 0;
    else
        return 1;
}
//FUNCTION FOR ADDING NODES
link *add_node(link *list, link *node) {

}
//FUNCTION FOR DISPLAYING NODES
void display_list(link *head) {
    link *rest = head;

    while(rest != NULL){
        printf("%s", rest->node_str);
        rest = rest->next;
    }
}

Здравствуйте, это мой код для домашнего задания, которое у меня есть в курсе compe160, но я не могу понять, как расположить строки в алфавитном порядке в моем связанном списке, поэтому, если у меня есть 4 входа: Майк, Боб, Энн, Джейкоб. Я бы хотел, чтобы это было организовано следующим образом: Энн, Боб, Джейкоб, Майк. проблема здесь в разделе //COMPARE моего кода в main() все остальное работает нормально.

Temp = Rest-> next;
Rest-> next = Rest;
Rest = Temp;

Приведенный выше код не работает, и я не понимаю почему, если кто-нибудь объяснит мне это, я был бы очень благодарен. Заранее спасибо. Кроме того, я впервые публикую здесь, и я не знаю, как правильно это сделать: DD

1. c #, c и c — три очень разных языка. Пожалуйста, не спамите несвязанные теги

2. Возьмите лист бумаги и нарисуйте поле для temp и поле для rest. Теперь выполните каждую из ваших операций по очереди. Куда сейчас указывают Rest и Temp? Куда указывают их следующие указатели?

3. Я нажал рекомендуемые теги:// буду иметь в виду в следующий раз

4. они указывают на одно и то же …? Rest будет указывать на (Rest-> next)-> next; Temp указывает на то же самое, что я думаю. Я не очень хорош в этом, только начал учиться. @Botje

Ответ №1:

Давайте начнем с рисования связанного списка:

 prev -> c1=Rest -> c2 -> Tail

Здесь Rest указывает на c1 , и вы определили это c1 и c2 находитесь в неправильном порядке. Это означает, что мы хотим установить prev->next = c2 , c2->next = c1 , и c1->next = Tail .

Игнорируя prev на мгновение, последние два легко сделать:

 link* Tail = c2->next;
c2->next = c1; /* We now have c2 -> c1 -> c2 -> ... */
c1->next = Tail; /* c2 -> c1 -> tail */
Rest = c2; /* so Rest = Rest->next points to c1 -> Tail */

В вашем текущем коде нет prev , поэтому мы не можем исправить эту ссылку.
Хуже того, может случиться так, что самые первые две ячейки списка нужно поменять местами, поэтому нам также нужно обновить ваш Head указатель.

Для этого есть общий трюк, который включает в себя сохранение указателя на указатель на связанный список: на первой итерации, link** prev = amp;Head , и для каждой итерации после этого prev = amp;Rest->next;

Теперь мы можем добавить следующее к блоку выше:

 *prev = c2;

и все будет работать во всех случаях.