0

I have a question regarding appending and casting new elements in a singly linked list in C. I did some research before deciding to ask, and found some answers to a similar question, which solve to some extent my doubt, but I still haven't understood completely why some castings are necessary to please the compiler.

I'm using gcc in Ubuntu 12.04 LTS:

$ gcc --version
gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3
Copyright (C) 2011 Free Software Foundation, Inc.

So I implemented the following code:

 1  #include <stdio.h>
 2  #include <stdlib.h>
 3  
 4  typedef struct {
 5      struct node* next;
 6      int data;
 7  } node;
 8  
 9  node* appendElement(node* head, int data);
10  node* removeElement(node* head, int data);  
11  
12  int main(int argc, char** args){
13      //main code             
14      return 0;   
15  }
16  
17  node* appendElement(node* head, int data){
18      node* newElement;
19      if(head == NULL){
20          if((newElement = malloc(sizeof(node))) != NULL){
21              newElement->data = data;
22              newElement->next = NULL;
23              return newElement;
24          }
25          else{
26              fprintf(stderr, "Error");   
27              return NULL;
28          }
29      }
30      else{
31          node* n = head;
32          while(n->next != NULL){
33              n = (node*)n->next;
34          }
35          if((newElement = malloc(sizeof(node))) != NULL){
36              newElement->data = data;
37              newElement->next = NULL;
38              n->next = (void*)newElement;
39              return head;
40          }
41          else{
42              fprintf(stderr, "Error");   
43              return NULL;
44          }
45      }
46  }
47  
48  node* removeElement(node* head, int data){
49      node* aux;
50      if(head == NULL){
51          printf("Empty list, nothing to remove.\n");
52          return NULL;
53      }
54      else if(head->data == data){            
55              aux = (node*)head->next;
56              free(head);
57              return aux;
58          }
59          else{   
60              node* n = head;         
61              while(n->next != NULL){
62                  aux = (node*)n->next;
63                  if(aux->data == data){
64                      n->next = aux->next;
65                      free(aux);                  
66                      return head;
67                  }
68                  n = (node*)n->next;
69              }
70              printf("Can't find %d in list.\n", data);
71              return head;    
72          }
73  }

From the answers I read one could change: 

4  typedef struct {
5      struct node* next;
6      int data;
7  } node;

into:

4  typedef struct _node {
5      struct _node* next;
6      int data;
7  } node;

in order to avoid the explicit casting in the following lines:

33  n = (node*)n->next;
38  n->next = (void*)newElement;
62  aux = (node*)n->next;
68  n = (node*)n->next;

As one would expect, it works. I understand that the compiler "doesn't like" to work with undefined structures. (And also that the argument of malloc can be newElement.)

My question is: what if one doesn't want to change the structure declaration? Why are those castings necessary to make the compiler happy? I believe even without those castings the program still works.

Particularly, the casting to void* I had to implement in line 38 doesn't convince me at all. I know that void* is a generic pointer and thus every pointer can be downcasted without issues, that's why I used it.

Maybe my understanding of structure declaration and typedef is not as good as I thought. Thanks for your time.

EDIT: Corrected some code for more clarity.

4

2 回答 2

0

Your structure is badly defined:

typedef  struct  {
    struct node* next;
    int data;
} node;

The second line declares next as a pointer to an unknown structure named node. It is unknown because you have not yet declared it. Change struct node* next to struct junk* next and the compilation will yield the same result. The compiler can continue beyond this point because it doesn't need to know how big a 'node' is, all it needs is to know this is a pointer.

It is normal to define that sort of thing as:

struct node {
    struct node* next;
    int data;
};
typedef struct node node;

This works because by the time the compiler comes to make the assignments you refer to, it knows what a struct node is. In your version you never define what a struct node is. Note that I used the same name in the typedef as in the struct, namely 'node'. This is ok because typedefs and structs are different namespaces (and hence can overlap).

于 2013-07-04T02:27:33.223 回答
0

Declared struct like following is fine.

#include<stdio.h>
typedef struct node
{
    int data;
    struct node *next;
}node;

int main()
{
    node n1, *pn1, *pn2;
    pn1 = &n1;
    pn2 = (node *)malloc(sizeof(node));
    pn1->data = 1;
    pn1->next = NULL;
    pn2->data = 2;
    pn2->next = pn1;
    printf("%d\n", pn2->data);
    printf("%d\n", pn2->next->data);
    return 0;
}

I test it in MS cl compiler and it works fine. You can be free from casting pointer.

于 2013-07-04T03:57:41.080 回答