汤科资源网

链表是一种常用的数据结构,它通过指针将一些列数据结点,连接成一个数据链,相对于数组,链表具有更好的动态性

数据域用来存储数据,指针域用来建立与下一个结点的联系

建立链表时无需预先知道数据总量的,可以随机的分配空间,可以高效的在链表中的任意位置实时插入或删除数据

链表的开销,主要是访问顺序性和组织链的空间损失

链表和数组的区别

数组: 随机访问元素效率高

需要分配一块连续的存储区域

删除和插入某个元素效率低

链表:无需一次性分配一块连续的存储区域,只需分配n块结点存储区域,通过指针建立关系

不需要一块连续的存储区域

删除和插入某个元素效率高

随机访问元素效率低

有关结构体的自身引用

结构体可以嵌套另外一个结构体的任何类型变量

结构体嵌套本结构体普通变量.本结构体的类型大小无法确定,类型本质:固定大小内存块别名

结构体嵌套结构体指针变量,指针变量的空间能确定,32位,4字节,64位,8字节

//静态链表
typedef struct Stu
{
	int id;
	char name[100];
	struct Stu *next;
}Stu;

void test()
{
	//初始化三个结构体变量
	Stu s1 = { 1,"yuri",NULL };
	Stu s2 = { 2,"yui",NULL };
	Stu s3 = { 3,"yri",NULL };
	s1.next = &s2;
	s2.next = &s3;
	s3.next = NULL;
	Stu *p = &s1;
	while (p != NULL)
	{
		printf("id=%d,name=%s\n", p->id, p->name);
		//结点往后移动一位
		p = p->next;
	}

}

//动态链表
typedef struct Stu
{
	int id;
	char name[100];
	struct Stu *next;
}Stu;

//动态分配3个结点
void test()
{
	Stu *s1 = (Stu*)malloc(sizeof(Stu));
	s1->id = 1;
	strcpy(s1->name, "yuri");

	Stu *s2 = (Stu*)malloc(sizeof(Stu));
	s1->id = 2;
	strcpy(s1->name, "yui");

	Stu *s3 = (Stu*)malloc(sizeof(Stu));
	s1->id = 3;
	strcpy(s1->name, "yri");

	//建立节点的关系
	s1->next = s2;
	s2->next = s3;
	s3->next = NULL;

	//遍历结点
	Stu *p = s1;
	while (p != NULL)
	{
		printf("id=%d,name=%s\n", p->id, p->name);
		//结点往后移动一位
		p = p->next;
	}

	//释放节点空间
	p = s1;
	Stu *tmp = NULL;
	while (p != NULL)
	{
		tmp = p;
		p = p->next;
		free(tmp);
		tmp = NULL;
	}
}