注:我想避免向StackOverflow社区寻求帮助,因为我知道并支持这种问题不会因案例而异并且多次seen and reseen会增加任何价值。那就是说可以随意投票,但是我非常需要帮助:是我正在尝试的5小时,明天我要考试!
在C中,我必须编写一个BubbleSort函数,该函数交换节点而不是值] LinkedList,但是我无法完成它。这是代码(如您所见,顺序不正确):
#include <stdio.h>
#include <malloc.h> // malloc, free
#include <stddef.h> // NULL
// defining 'int' as data_t
typedef int data_t;
typedef struct node_s {
data_t data;
struct node_s* next;
} node_t;
node_t** list_new() {
node_t** list = malloc(sizeof **list);
if (!list) return NULL;
*list = NULL;
return list;
}
void list_delete(node_t** list) {
node_t *node, *next;
for (node = *list; node; node = next) {
next = node->next;
free(node);
}
}
node_t* list_push_front(node_t** list, data_t data) {
node_t* node = malloc(sizeof(node_t));
if (!node) return NULL;
node->data = data;
node->next = *list;
return *list = node;
}
// IS EASY TO SWAP THE VALUES
/*
void swap(data_t* a, data_t* b) {
data_t c = *a;
*a = *b;
*b = c;
}
void simple_bubble_sort(node_t** list) {
for(node_t* i = *list; i; i = i->next)
for(node_t* j = *list; j->next; j = j->next)
if(j->data > j->next->data)
swap(&(j->data), &(j->next->data));
}
*/
// MUCH LESS EASY TO SWAP THE NODES
void swap_node(node_t** prev_node_A, node_t** node_A, node_t** node_B) {
node_t *last_node = (*node_B)->next;
node_t *first_node = *node_A;
node_t *second_node = *node_B;
if (prev_node_A) {
(*prev_node_A)->next = second_node;
(*prev_node_A)->next->next = first_node;
(*prev_node_A)->next->next->next = last_node;
} else {
(*node_A) = second_node;
(*node_A)->next = first_node;
(*node_A)->next->next = last_node;
}
}
void simple_bubble_sort(node_t** list) {
for(node_t* i = *list; i->next; i = i->next)
for (node_t *j = *list; j->next->next; j = j->next) {
if (j == *list) {
if (j->data > j->next->data) {
*list = j->next;
swap_node(NULL, &j, &(j->next));
}
}
else {
if (j->next->data > j->next->next->data)
swap_node(&j, &(j->next), &(j->next->next));
}
//printf("%i,%i | %i, %i, %i, %i \n", i->data, j->data, (*list)->data, (*list)->next->data, (*list)->next->next->data, (*list)->next->next->next->data);
//system("pause");
}
}
int main() {
// Create List
node_t** list = list_new();
if (!list)
goto memory_allocation_failure;
// Add values to List
for(int i=0; i<10; i++)
if (!list_push_front(list, i))
goto memory_allocation_failure;
// Print List
for (node_t* node = *list; node != NULL; node = node->next)
printf("%i\n", node->data);
// Swap Test
//swap_node(NULL, &(*list), &((*list)->next));
//swap_node(&(*list), &((*list)->next), &((*list)->next->next));
// Sort List
printf("-- Bubble Sort --\n");
simple_bubble_sort(list);
// Print List
for (node_t* node = *list; node != NULL; node = node->next)
printf("%i\n", node->data);
// Delete List
list_delete(list);
return 0;
// Error Handler
memory_allocation_failure:
printf("Memory Allocation Failure");
return 1;
}
谢谢,马可。
swap
。 void swap( node_t **current )
{
node_t *tmp = ( *current )->next->next;
( *current )->next->next = *current;
*current = ( *current )->next;
( *current )->next->next = tmp;
}
这是函数simple_bubble_sort
void simple_bubble_sort( node_t **head ) { if ( *head ) { for ( node_t **first = head, *sorted = NULL, *last = sorted; ( *first )->next != last; last = sorted ) { sorted = ( *first )->next; for ( node_t **current = first; ( *current )->next != last; current = &( *current )->next ) { if ( ( *current )->next->data < ( *current )->data ) { swap( current ); sorted = ( *current )->next; } } } } }
调查他们。