11.7用指针处理链表 11.7.1链表概述 链表是一种常见的重要的数据结构。它是动态地进 行存储分配的一种结构。我们知道,用数组存放数据 时
１1．７ 用指针处理链表 １1．７．1链表概述 链表是一种常见的重要的数据结构。它是动态地进 行存储分配的一种结构。我们知道，用数组存放数据 时
必须事先定义固定的长度(即元素个数)。比如,有的 班级有100人,而有的班只有30人,如果要用同 个数组先后存放不同班级的学生数据,则必须定义 长度为100的数组。如果事先难以确定一个班的最多 人数,则必须把数组定得足够大,以能存放任何班级 的学生数据。显然这将会浪费内存。链表则没有这种 缺点,它根据需要开辟内存单元。图10.11表示 最简单的一种链表(单向链表)的结构。链表有一个 “头指针”变量,图中以head表示,它存放一个 地址
必须事先定义固定的长度（即元素个数）。比如，有的 班级有１００人，而有的班只有３０人，如果要用同 一个数组先后存放不同班级的学生数据，则必须定义 长度为100的数组。如果事先难以确定一个班的最多 人数，则必须把数组定得足够大，以能存放任何班级 的学生数据。显然这将会浪费内存。链表则没有这种 缺点，它根据需要开辟内存单元。图１０．１１表示 最简单的一种链表（单向链表）的结构。链表有一个 “头指针”变量，图中以ｈｅａｄ表示，它存放一个 地址
该地址指向一个元素。链表中每一个元素称为“结点” 每个结点都应包括两个部分:一为用户需要用的实际 数据,二为下一个结点的地址。课以看出,head指向 第一个元素;第一个元素又指向第二个元素;… 直到最后一个元素,该元素不再指向其它元素,它称 为‘表尾”,它的地址部分放一个”NULL”(表 示“空地址”)。链表到此结束。 可以看到:链表中各元素在内存中可以不是连续存 放的。要找某一元素,必须先找到上一个元素,根据 它提供的下一元素地址才能找到下一个元素
该地址指向一个元素。链表中每一个元素称为“结点” ， 每个结点都应包括两个部分：一为用户需要用的实际 数据，二为下一个结点的地址。课以看出，head指向 第一个元素；第一个元素又指向第二个元素；……， 直到最后一个元素，该元素不再指向其它元素，它称 为‘表尾”，它的地址部分放一个”ＮＵＬＬ”（表 示“空地址”）。链表到此结束。 可以看到：链表中各元素在内存中可以不是连续存 放的。要找某一元素，必须先找到上一个元素，根据 它提供的下一元素地址才能找到下一个元素
如果不提供“头指针”(head),则整个链表都无法访 问。链表如同一条铁链一样,一环扣一环,中间是不 能断开的。打个通俗的比方:幼儿园的老师带领孩子 出来散步,老师牵着第一个小孩的手,第一个小孩的 另一只手牵着第二个孩子,…,这就是一个“链” 最后一个孩子有一只手空着,他是“链尾”。要找这 个队伍,必须先找到老师,然后顺序找到每一个孩子 可以看到,这种链表的数据结构,必须利用指针变 量才能实现
如果不提供“头指针”（head），则整个链表都无法访 问。链表如同一条铁链一样，一环扣一环，中间是不 能断开的。打个通俗的比方：幼儿园的老师带领孩子 出来散步，老师牵着第一个小孩的手，第一个小孩的 另一只手牵着第二个孩子，……，这就是一个“链” ， 最后一个孩子有一只手空着，他是“链尾”。要找这 个队伍，必须先找到老师，然后顺序找到每一个孩子。 可以看到，这种链表的数据结构，必须利用指针变 量才能实现
即:一个结点中应包含一个指针变量,用它存放下一 结点的地址 前面介绍了结构体变量,它包含若干成员。这些成 员可以是数值类型、字符类型、数组类型,也可以是 指针类型。这个指针类型可以是指向其它结构体类型 数据,也可以指向它所在的结构体类型。例如: st t student Li n t num
。即：一个结点中应包含一个指针变量，用它存放下一 结点的地址。 前面介绍了结构体变量，它包含若干成员。这些成 员可以是数值类型、字符类型、数组类型，也可以是 指针类型。这个指针类型可以是指向其它结构体类型 数据，也可以指向它所在的结构体类型。例如： sｔｒｕｃｔ sｔｕｄｅｎｔ ｛ｉｎｔ ｎｕｍ;