今天再次学习了一下数据结构关于链表的操作,嘿嘿。
链表的节点包含三个数值,* 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、一般在操作系统里面,我们希望分配的内存是一块连续的区域,第一种方法很好的做到了这一点。第二种方法由于是两次动态分配,很难分配在一个连续的内存空间。而且很大程度上浪费了内存(比如出现内碎片和外碎片的情况)。