Блог

Главная - Вопросы по программированию - C поворот связанного списка по выбору пользователя

C поворот связанного списка по выбору пользователя

#c #linked-list #rotation #singly-linked-list #function-definition

Вопрос:

Я написал программу, которая получает от номера пользователя связанный список и номер для того, чтобы повернуть каждый узел в направлении влево. и мне удалось сделать это только в одном случае, но не по кругу. и моя программа должна быть в состоянии перемещать узел левее, чем длина списка по кругу. кто-нибудь знает, как я могу исправить свою программу??. (функция, которую необходимо исправить, — это функция «RotateALinkedList»). я имею в виду, что если пользователь хочет переместить список 4 раза влево, первый узел будет начинаться с последнего узла.

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


typedef struct numbers_list
{
    int data;
    struct numbers_list* next;
}number;

void RotateALinkedList(number** head, int node); //the function that rotate the linked list
int CreateLinkedList(number** head, int iNumberofNode);
int attachToEnd(number** head, int k);
void PrintTheList(number* pNode);
void FreeAllocatedMemory(number** head);

int main(void)
{
    int list_len = 0;
    int data = 0;
    number* head = NULL;
    printf("How many nodes in list? ");
    scanf("%d", amp;list_len);
    getchar();
    CreateLinkedList(amp;head, list_len);
    printf("Choose a number k, and the list will be rotated k places to the left: ");
    scanf("%d", amp;data);
    getchar();
    if (data <= list_len)
    {
        RotateALinkedList(amp;head, data);
        PrintTheList(head);
    }
    else
    {
        printf("Please Enter Valid number of noden");
    }
    FreeAllocatedMemory(amp;head);
    getchar();
    return 0;
}

void RotateALinkedList(number** head, int node)
{
    int count = 0;
    number* p = *head;
    number* tempNode = NULL;
    for (count = 1; ((count < node) amp;amp; (p != NULL)); count  )
    {
        p = p->next;
    }
    if (p == NULL)
    {
        return;
    }
    else
    {
        tempNode = p;
    }
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = *head;
    *head = tempNode->next;
    tempNode->next = NULL;
}

int CreateLinkedList(number** head, int iNumberofNode)
{
    int data = 0;
    int iRetValue = -1;
    int count = 0;
    number* pNewNode = NULL;
    for (count = 0; count < iNumberofNode; count  )
    {
        printf("Enter number: ");
        scanf("%d", amp;data);
        getchar();
        if ((*head) == NULL)
        {
            pNewNode = (number*)malloc(sizeof(number));
            if (pNewNode != NULL)
            {
                pNewNode->data = data;
                pNewNode->next = NULL;
                *head = pNewNode;
                iRetValue = 0;
            }
        }
        else
        {
            iRetValue = attachToEnd(head, data);
        }
    }
    return iRetValue;
}

int attachToEnd(number** head, int k)
{
    int iRetValue = -1;
    number* pLastNode = NULL;
    number* pNewNode = NULL;
    pLastNode = *head;
    pNewNode = (number*)malloc(sizeof(number));
    if (pNewNode != NULL)
    {
        pNewNode->data = k;
        pNewNode->next = NULL;
        iRetValue = 0;
    }
    if (pLastNode == NULL)
    {
        *head = pNewNode;
    }
    else
    {
        while (pLastNode->next != NULL)
        {
            pLastNode = pLastNode->next;
        }
        pLastNode->next = pNewNode;
    }
    return iRetValue;
}

void PrintTheList(number* pNode)
{
    printf("the rotated list:n");
    while (pNode != NULL)
    {
        printf("%d  ", pNode->data);
        pNode = pNode->next;
    }
}

void FreeAllocatedMemory(number** head)
{
    number* ptempNode = NULL;
    number* pFirstNode = NULL;
    pFirstNode = *head;
    while (pFirstNode != NULL)
    {
        ptempNode = pFirstNode;
        pFirstNode = pFirstNode->next;
        free(ptempNode);
    }
    *head = NULL;
}

Комментарии:

1. Под поворотом вы подразумеваете перемещение конца списка в начало или наоборот?

2. Если вы можете вращать список до тех пор, пока вращение меньше длины списка, это довольно просто исправить. Просто сделайте: actual_rotation = user_asked_rotation % length_of_list тогда вам никогда не понадобится, чтобы фактическое вращение было больше длины списка. Пример: В вашем списке 8 пунктов. Пользователь запрашивает 100 оборотов. Поскольку 100%8 равно 4, вы просто поворачиваетесь 4 раза.

Ответ №1:

Для начала имя number псевдонима в этом объявлении typedef

 typedef struct numbers_list
{
    int data;
    struct numbers_list* next;
}number;

это сбивает с толку.

Вместо этого будет лучше определить две структуры

 struct Node
{
    int data;
    struct Node *next;
};

struct List
{
    size_t size;
    struct Node *head;
};

и определите в основном список, такой как

 struct List numbers = { .size = 0, .head = NULL };

Вы упростите свою задачу, если список будет содержать элемент данных, указывающий количество узлов в списке.

Функция CreateLinkedList должна выполнять одну задачу: создать список из массива, указанного пользователем. Он должен попросить пользователя ввести номера, которые будут сохранены в списке.

Я могу предложить следующее решение, показанное в демонстрационной программе ниже.

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

struct Node
{
    int data;
    struct Node *next;
};

struct List
{
    size_t size;
    struct Node *head;
};

void clear( struct List *list )
{
    while ( list->head )
    {
        struct Node *tmp = list->head;
        list->head = list->head->next;
        free( tmp );
    }
    
    list->size = 0;
}

size_t create( struct List *list, const int a[], size_t n )
{
    clear( list );
    
    for ( struct Node **current = amp;list->head; 
          n-- amp;amp; ( *current = malloc( sizeof( struct Node ) ) ) != NULL; )
    {
        ( *current )->data = *a  ;
        ( *current )->next = NULL;
        current = amp;( *current )->next;
          list->size;
    }
    
    return list->size;
}

FILE * display( const struct List *list, FILE *fp )
{
    fprintf( fp, "There is/are %zu items: ", list->size );
    for ( struct Node *current = list->head; current != NULL; current = current->next )
    {
        fprintf( fp, "%d -> ", current->data );
    }
    
    fputs( "null", fp );
    
    return fp;
}

void rotate( struct List *list, size_t n )
{
    if ( ( list->size != 0 ) amp;amp;  ( ( n %= list->size ) != 0 ) )
    {
        struct Node **current = amp;list->head;
        
        while ( n-- ) current = amp;( *current )->next;
        
        struct Node *tmp = list->head;
        
        list->head = *current;
        *current = NULL;
        
        struct Node *last = list->head;
        while ( last->next != NULL ) last = last->next;
        last->next = tmp;
    }
}

int main(void) 
{
    struct List numbers = { .size = 0, .head = NULL };
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    create( amp;numbers, a, sizeof( a ) / sizeof( *a ) );
    
    fputc( 'n', display( amp;numbers, stdout ) );
    
    rotate( amp;numbers, 1 );
    
    fputc( 'n', display( amp;numbers, stdout ) );
    
    rotate( amp;numbers, 2 );
    
    fputc( 'n', display( amp;numbers, stdout ) );
    
    rotate( amp;numbers, 3 );
    
    fputc( 'n', display( amp;numbers, stdout ) );
    
    rotate( amp;numbers, 4 );
    
    fputc( 'n', display( amp;numbers, stdout ) );
    
    clear( amp;numbers );
    
    return 0;
}

Вывод программы является

 There is/are 10 items: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
There is/are 10 items: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 0 -> null
There is/are 10 items: 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 0 -> 1 -> 2 -> null
There is/are 10 items: 6 -> 7 -> 8 -> 9 -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
There is/are 10 items: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
Метки: