0

I have a linked list, and I want to sort them by names (for example the names "Bx", "Tx", "Ax" would become : "Ax", "Bx", "Tx")... I need to switch the names if the one in the node's right has a "smaller name"..

this is what I wrote:

typedef struct data
{
char *name;
}data;

typedef struct Node 
{
data NodeData;
struct Node *next;
struct Node *prev;
}Node;

void Sorting(Node *head)
{
 Node *temp = head;
 Node *temp2 = (Node*)malloc(sizeof(Node));
 while (temp != NULL)
 {
       if (1 == (strcmp(temp -> NodeData.name, temp -> next -> NodeData.name))) 
       {
              strcpy (temp2 -> NodeData.name, temp -> NodeData.name);
              strcpy (temp -> NodeData.name, temp -> next -> NodeData.name);
              strcpy (temp -> next -> NodeData.name, temp2 -> NodeData.name);
       } 

       temp = temp -> next;

 }

}

I'm getting an runtime - error on the part where I need to swarp betwen the node's name(the strcpy lines): An access violation (segmentation fault)...

4

3 回答 3

1

I don't think you should be sorting the list by exchanging the data values, instead you should swap the nodes themselves. Note that this requires you to return the pointer to the new first node of the list.

EDIT: Passing a pointer to the head of the list also works, if you're into doubly-indirect pointers. It can make the code simpler too.

于 2012-05-20T20:05:29.370 回答
0

temp2 is char* here

char *temp2;

but Node here

strcpy (temp2 -> NodeData.name, temp -> NodeData.name);

So yes, on this line, you behave as if temp2 was a structure or union, but it is not.

于 2012-05-20T19:51:52.193 回答
0 
if (1 == (strcmp(temp -> NodeData.name, temp -> next -> NodeData.name))) {...}

When this line is executed, there is no guarantee that temp->next is not NULL. If it is NULL, temp->next->NodeData.Name would be rather painfull.

Also, as has been said, testing strcmp()s result against 1 is not right. strcmp can resutning any value equal to zero, < zero or > zero.

Also, as has been said, strcpy() is not right; the strings could have different allocated sizes, or could live in non-writable memory (string constants) . Swapping the pointers will suffice.

UPDATE:

void Sorting(Node *head)
{
 Node *temp ;

                /* since the compare dereferences temp->next you'll have to verify that it is not NULL */
 for (temp = head; temp && temp->next; temp = temp->next)  
 {
       if (strcmp(temp->NodeData.name, temp->next->NodeData.name) > 0 )  
       {
                /* no need for a whole node, since you only copy a pointer */
              char *cp;
              cp = temp->NodeData.name;
              temp->NodeData.name = temp->next->NodeData.name;
              temp->next->NodeData.name = cp;
       } 

 }

}

BTW: bubble sorting a linked list is really ugly. Linked lists are easyer and more elagantly sorted by mergesort.

于 2012-05-20T21:01:55.163 回答