链表节点插入时的小技巧

    今天再次学习了一下数据结构关于链表的操作，嘿嘿。
     链表的节点包含三个数值，* next：指针指向下一个的节点，value：链表的值，name[]：链表的名字，改名字指向该节点所分配的地址。

struct A{
     struct A * next;//无论是指向int char等任何类型都只占4个字节的空间
     int value;//占4个字节的空间
     char name[0];//空字符串数组，不占内存空间
       }

现在测试一下：

main()
{     struct A text;
      printf("the text size is:%d\n",sizeof(text));
      system("pause");

}
显示：the text size is：8

上面的所有就是为了说明一个问题：char name[] 是不占内存空间的。那么这样做有什么好处呢，那么就假设他是指针类型的吧。

struct A{
      struct A * next;//无论是指向int char等等任何类型都只占占4个字节的空间
       int value;//占4个字节的空间
       char * name;//占4个字节的空间
       }

由上面可以知道，如果是指针类型的，则占用了4个字节的内存空间，再往下看：

1、char name[]的情况：
     现在假设要在一条链表里面插入一个新的节点，而且这个节点的value值所占的内存空间为9，加上后面“\n“所占的一个字节，就需要分配10+sizeof(A)个字节的内存空间：

struct A *p = (struct A*)malloc(sizeof(struct A)+10);

那么name[]的第一个元素就会指向分配地址的首地址。

2、char *p的情况：   
同样是在一条链表里面插入一个新的节点，需要分配10+sizeof(A)个字节的内存空间：
   

    //声明一个A的节点空间，并且将*p指向该节点。
    struct A *p = (struct A*)malloc(sizeof(struct A));

    //为节点开辟一个新的空间存储value值，指针name指向该空间的首地址。
    struct ->name = (char *)malloc(10*(sizeof(char)));

  
    根据上述几个过程可以得出：
    1、用数组（char name[]）做为链表的结构体类型，它所占的内存空间比指针（char *name）小。
    2、如果是数组（char name[]）的话，则只需一次动态分配内存地址空间即可。指针（char *p）则需要两次分配。
    3、一般在操作系统里面，我们希望分配的内存是一块连续的区域，第一种方法很好的做到了这一点。第二种方法由于是两次动态分配，很难分配在一个连续的内存空间。而且很大程度上浪费了内存(比如出现内碎片和外碎片的情况)。   

评论

1 楼 deepfuture 2010-11-16  

char name[0];//空字符串数组，不占内存空间这种用法比较经典