I pass in a linked list of size 10 to sort_nodes, alongside an int stating so. However when I use quicksort, my program "stops", and it does not seem to execute the second print nodes function. For some reason, my CLion compiler is giving me an "unable to disassemble function" error so I have been unsuccessful even using the debugger.
int main(void){
node_ptr *head;
int num_of_nodes = load_nodes(head); // returns the number of items loaded, in this case it is going to be 10
print_all_nodes(head);
sort_nodes(head,num_of_nodes);
print_all_nodes(head); // check that the items have been sorted correctly
}
void insert_node(node_ptr *head_ptr, node_ptr insertion){
if (*head_ptr != NULL){ // if the header has a pointer
printf("Inserting new item at head\n");
insertion->next = *head_ptr;
}
else{
printf("Head is null so assigning head to new pointer\n");
}
*head_ptr = insertion;
}
int compare_strings(const void *p1, const void *p2){
competitor *competitor1, *competitor2;
node1= (node *) p1;
node2 = (node *) c2;
return strcmp(node1->some_string,node2 ->some_string);
}
void delete_linked_list(node_ptr *head_ptr){
node_ptr current_temp_ptr = *head_ptr;
node_ptr next_temp_ptr = NULL;
while (current_temp_ptr != NULL){
next_temp_ptr = current_temp_ptr->next;
free(current_temp_ptr);
current_temp_ptr = next_temp_ptr;
}
head_ptr = NULL;
}
void sort_nodes(node_ptr *head_ptr, const int num_of_nodes){
printf("Num of nodes: %d\n",num_of_nodes); // expected 10 got 10;
node_ptr nodes[num_of_nodes]; // array used for sorting
node_ptr temp_ptr = *head_ptr;
printf("temp pointer set up\n");
for (int i=0; i<num_of_nodes; i ){
temp_ptr = temp_ptr->next; // get next (first) node
nodes[i] = temp_ptr;
}
delete_linked_list(head_ptr);
printf("Num of nodes: %d",num_of_nodes); //expected 10, got 10
qsort(&nodes,num_of_nodes, sizeof(node), compare_strings);
printf("Num of nodes= %d", num_of_nodes); // expected 10, got -2145129072
for (int i=0; i<num_of_nodes; i ){
insert_node(head_ptr,nodes[i]);
}
}
Sorry for any typos I've had to change names to make the problem more general
CodePudding user response：
At least these issues
Wrong type
p1, p2 are pointers to a nodes_ptr, not a pointer to node. Recall that p1, p2 are pointers to the elements of the array and the array was nodes_ptr nodes[num_of_nodes].
int compare_strings(const void *p1, const void *p2){
// competitor *competitor1, *competitor2;
// node1= (node *) p1;
// node2 = (node *) c2;
const nodes_ptr *node1 = (const nodes_ptr *) p1;
const nodes_ptr *node2 = (const nodes_ptr *) p2;
// return strcmp(node1->some_string,node2 ->some_string);
return strcmp((*node1)->some_string, (*node2)->some_string);
}
Wrong element size and & not needed
Rather than size to the type of an element sizeof(node) (and use the wrong type as OP did), size to an array element sizeof nodes[0]. Easier to code right.
nodes_ptr nodes[num_of_nodes]; // array used for sorting
....
// Drop v wrong size
// qsort(&nodes,num_of_nodes, sizeof(node), compare_strings);
qsort(nodes, num_of_nodes, sizeof nodes[0], compare_strings);
CodePudding user response：
I could try to explain what is (apparently) wrong with your partial code, but without a proper minimal complete example I wouldn't be able to top what Chux has already pointed out. However, what I can do is explain how this is done using as simple a code example as I possibly can. For this example, our structure will be trivial:
typedef struct node node;
struct node
{
int data;
node *next;
};
Wes, we're going for a simple linked list of numbers. They're easy to understand and easy to sort. Some utility functions appear below, and the names, and code, are nothing if not self-evident.
Utility Functions
First is a simple loader. Obviously you'll be using your own mechanics for building your linked list.
node *load_nodes(size_t n_nodes)
{
node *head = NULL;
for (size_t i=0; i<n_nodes; i)
{
node *p = malloc(sizeof *p);
p->data = 1 rand() % 100;
p->next = head;
head = p;
}
return head;
}
From there we need something that deletes a linked list as well:
void delete_nodes(node *head)
{
while (head)
{
node *tmp = head;
head = tmp->next;
free(tmp);
}
}
Next, something that prints a linked list of our nodes. Again, yours will obviously depend on your node type:
void print_nodes(const node *head)
{
for (; head; head = head->next)
printf("%d ", head->data);
fputc('\n', stdout);
}
Comparator for qsort
We're building an array of pointers that will be sorted. That means each address passed to the comparator will be an offset address within that pointer array. Therefore, the arguments are actually pointer-to-pointer-to-node. All qsort comparators require the same basic logic:
- if
ais "less" thanb, return less than zero - if
ais "greater" thanb, return greater than zero - otherwise, they're equivalent. return zero
Given that, our comparator can be written as follows, without risk of over/underflow.
int cmp_node_ptr(const void *a, const void *b)
{
const node * const *lhs = a;
const node * const *rhs = b;
return (*lhs)->data < (*rhs)->data ? -1 : (*rhs)->data < (*lhs)->data;
}
The Array Build, Sort, and List Re-chain
Finally, the moment you've been waiting for: the actual sort operation. Given a linked list, we do the following:
- Build the array, resizing exponentially as required, and storing the pointers from our terminated linked list into the pointer array. The dynamic resize allows you to never fret about calculating the list length (though in real-world practice the length, and probably the head and tail) are trio-managed for performance and flexibility).
- Then we run
qsortagainst the array using the length we calculated while building it, and the comparator we just discussed previously. - Once that is done, we walk the array, rebuilding the linked list
- Then, delete the pointer array. it is no longer needed.
- Finally return the new list head as our function result:
node *sort_nodes(node *head)
{
node **arr = NULL;
size_t capacity = 0;
size_t len = 0;
for (; head; head = head->next)
{
if (len == capacity)
{
size_t new_capacity = (capacity ? 2 * capacity : 1);
void *tmp = realloc(arr, new_capacity * sizeof *arr);
if (tmp == NULL)
{
perror("Failed to allocate pointer array for sorting");
exit(EXIT_FAILURE);
}
arr = tmp;
capacity = new_capacity;
}
arr[len ] = head;
}
if (len > 0)
{
// sort the pointer sequence using our comparator
qsort(arr, len, sizeof *arr, cmp_node_ptr);
// reusing our passed-in head pointer
node **pp = &head;
for (size_t i=0; i<len; i)
{
*pp = arr[i]; // save pointer at *pp
pp = &(*pp)->next; // adjust pp to the next pointer storage location
}
*pp = NULL; // important. terminates the linked list
free(arr);
}
return head;
}
To prove all this madness works, we have simple driver program:
int main()
{
srand((unsigned)time(NULL));
node *head = load_nodes(30);
print_nodes(head);
head = sort_nodes(head);
print_nodes(head);
delete_nodes(head);
return EXIT_SUCCESS;
}
That's it. The final program in its entirety appears below, along with a sample output run.
Code
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct node node;
struct node
{
int data;
node *next;
};
node *load_nodes(size_t n_nodes)
{
node *head = NULL;
for (size_t i=0; i<n_nodes; i)
{
node *p = malloc(sizeof *p);
p->data = 1 rand() % 100;
p->next = head;
head = p;
}
return head;
}
void delete_nodes(node *head)
{
while (head)
{
node *tmp = head;
head = tmp->next;
free(tmp);
}
}
void print_nodes(const node *head)
{
for (; head; head = head->next)
printf("%d ", head->data);
fputc('\n', stdout);
}
int cmp_node_ptr(const void *a, const void *b)
{
const node * const *lhs = a;
const node * const *rhs = b;
return (*lhs)->data < (*rhs)->data ? -1 : (*rhs)->data < (*lhs)->data;
}
node *sort_nodes(node *head)
{
node **arr = NULL;
size_t capacity = 0;
size_t len = 0;
for (; head; head = head->next)
{
if (len == capacity)
{
size_t new_capacity = (capacity ? 2 * capacity : 1);
void *tmp = realloc(arr, new_capacity * sizeof *arr);
if (tmp == NULL)
{
perror("Failed to allocate pointer array for sorting");
exit(EXIT_FAILURE);
}
arr = tmp;
capacity = new_capacity;
}
arr[len ] = head;
}
if (len > 0)
{
// sort the pointer sequence using our comparator
qsort(arr, len, sizeof *arr, cmp_node_ptr);
// reusing our passed-in head pointer
node **pp = &head;
for (size_t i=0; i<len; i)
{
*pp = arr[i]; // save pointer at *pp
pp = &(*pp)->next; // adjust pp to the next pointer storage location
}
*pp = NULL; // important. terminates the linked list
free(arr);
}
return head;
}
int main()
{
srand((unsigned)time(NULL));
node *head = load_nodes(30);
print_nodes(head);
head = sort_nodes(head);
print_nodes(head);
delete_nodes(head);
return EXIT_SUCCESS;
}
Output
60 39 73 62 91 31 17 89 12 43 93 16 20 22 74 48 58 97 42 72 67 80 93 58 15 63 59 88 97 56
12 15 16 17 20 22 31 39 42 43 48 56 58 58 59 60 62 63 67 72 73 74 80 88 89 91 93 93 97 97
Summary
This is just one way to do this. You can adjust this code by doing the following:
- Change your node type as needed.
- Change the comparator to match the node type.
- Change
load_nodesto mach your build requirements, - Change
print_nodesto match your output requirements.
The rest will require little/no changes.