字符指针和字符数组_指向二维数组的指针

C语言自定义数据类型（四）用指针处理链表 　　C语言自定义数据类型系列文章： 　　C语言自定义数据类型（一）定义和使用结构体变量 　　C语言自定义数据类型（二）使用结构体数组 　　C语言自定义数据类型（三）结构体指针 　　C语言自定义数据类型（四）用指针处理链表 　　C语言自定义数据类型（五）共用体类型 　　C语言自定义数据类型（六）使用枚举类型 　　目录 　　一、什么是链表 　　1.1引入 　　1.2定义 　　二、建立简单的静态链表 　　2.1举例说明 　　三、建立动态链表 　　3.1举例说明 　　四、输出链表 　　4.1举例说明 　　一、什么是链表 　　1.1引入 　　链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。由前面的介绍中已知：用数组存放数据时，必须事先定义固定的数组长度(即素个数)。如果有的班级有 100 人，而有的班级只有 30 人，若用同一个数组先后存放不同班级的学生数据，则必须定义长度为 100 的数组。如果事先难以确定一个班的最多人数，则必须把数组定得足够大，以便能存放任何班级的学生数据，显然这将会浪费内存。链表则没有这种缺点，它根据需要开辟内存单。 　　
　　链表有一个 “ 头指针 ” 变量，图中以 head 表示，它存放一个地址，该地址指向一个素。链表中每一个素称为 “ 结点 ”，每个结点都应包括两个部分：(1)用户需要用的实际数据；(2)下一个结点的地址。可以看出， head 指向第 1 个素，第 1 个素又指向第 2 个素……直到最后一个素，该素不再指向其他素，它称为 “ 表尾 ”，它的地址部分放一个 “ NULL ” (表示 “ 空地址 ”)，链表到此结束。 　　可以看到链表中各素在内存中的地址可以是不连续的。要找某一素，必须先找到上一个素，根据它提供的下一素地址才能找到下一个素。如果不提供 “ 头指针 ”(head)，则整个链表都无法访问。链表如同一条铁链一样，一环扣一环，中间是不能断开的。 　　1.2定义 　　前面介绍了结构体变量，用它去建立链表是最合适的。一个结构体变量包含若干成员，这些成员可以是数值类型、字符类型、数组类型，也可以是指针类型。用指针类型成员来存放下一个结点的地址。 　　例如，可以设计这样一个结构体类型： 　　其中，成员 num 和 score 用来存放结点中的有用数据(用户需要用到的数据)。相当于上图结点中的A，B，C，D。next 是指针类型的成员，它指向 struct Student 类型数据(就是 next 所在的结构体类型)。一个指针类型的成员既可以指向其他类型的结构体数据，也可以指向自己所在的结构体类型的数据。现在，next 是 struct Student 类型中的一个成员，它又指向 struct Student 类型的数据。用这种方法就可以建立链表。 　　
　　图中每一个结点都属于struct Student 类型，它的成员 next 用来存放下一结点的地址，程序设计人员可以不必知道各结点的具体地址，只要保证将下一个结点的地址放到前一结点的成员 next 中即可。 　　注意：上面只是定义了一个 struct Student 类型，并未实际分配存储空间，只有定义了变量才分配存储单。 　　二、建立简单的静态链表 　　2.1举例说明 　　下面通过一个例子来说明怎样建立和输出一个简单链表。 　　举例：建立一个如 1.2 所示的简单链表，它由 3 个学生数据的结点组成,要求输出各结点中的数据。 　　解题思路：声明一个结构体类型，其成员包括num(学号)，score(成绩)和next(指针变量)。将第 1 个结点的起始地址赋给头指针 head，将第 2 个结点的起始地址赋给第 1 个结点的 next 成员，将第 3 个结点的起始地址赋给第 ⒉个结点的 next 成员。第 3 个结点的 next 成员赋予 NULL。这就形成了链表。 　　运行结果： 　　
　　程序分析： 　　为了建立链表，使 head 指向  a结点，a.next 指向 b 结点，b.next 指向 c 结点，这就构成链表关系。“ c.next = NULL ” 的作用是使 c.next 不指向任何有用的存储单。 　　在输出链表时要借助 p，先使 p 指向 a 结点，然后输出 a 结点中的数据，“ p = p->next ” 是为输出下一个结点作准备。p->next 的值是 b 结点的地址，因此执行 “p = p>next” 后 p 就指向 b 结点，所以在下一次循环时输出的是 b 结点中的数据。 　　本例是比较简单的，所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为 “ 静态链表 ”。 　　三、建立动态链表 　　所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。 　　3.1举例说明 　　写一函数建立一个有 3 名学生数据的单向动态链表。 　　解题思路：先考虑实现此要求的算法。在用程序处理时要用到动态内存分配的知识和有关函数(malloc，calloc，realloc 和 free 函数)。 　　①定义 3 个指针变量：head，p1 和 p2，它们都是用来指向 struct Student 类型数据的。先用 malloc 函数开辟第 1 个结点，并使 p1 和 p2 指向它。然后从键盘读入一个学生的数据给 p1 所指的第 1 个结点。在此约定学号不会为零，如果输入的学号为0，则表示建立链表的过程完成，该结点不应连接到链表中。先使 head 的值为 NULL (即等于0)，这是链表为 “空” 时的情况(即 head 不指向任何结点，即链表中无结点)，当建立第 1 个结点就使 head 指向该结点。 　　
　　②如果输入的 p1->num 不等于0，则输入的是第 1 个结点数据(n=1)，令 head = p1，即把 p1 的值赋给 head，也就是使 head 也指向新开辟的结点。p1 所指向的新开辟的结点就成为链表中第 1 个结点。然后再开辟另一个结点并使 p1 指向它，接着输人该结点的数据。 　　
　　③如果输入的 p1->num ≠ 0，则应链入第 2 个结点(n=2)，由于 n ≠ 1，则将 p1 的值赋给 p2->next，此时 p2 指向第1个结点，因此执行“ p2->next = p1” 就将新结点的地址赋给第 1 个结点的 next 成员，使第 1 个结点的 next 成员指向第 2 个结点。接着使 p2 = p1，也就是使 p2 指向刚才建立的结点。 　　
　　④接着再开辟 1 个结点并使 p1 指向它，并输入该结点的数据。在第 3 次循环中，由于 n = 3(n≠1)，又将 p1 的值赋给 p2->next，也就是将第 3 个结点连接到第 2 个结点之后，并使 p2 = p1，使 p2 指向最后一个结点。 　　
　　⑤再开辟一个新结点，并使 p1 指向它，输入该结点的数据。由于p1->num 的值为0，不再执行循环,此新结点不应被连接到链表中。此时将 NULL 赋给 p2->next。建立链表过程至此结束，p1 最后所指的结点未链入链表中，第 3 个结点的 next 成员的值为 NULL，它不指向任何结点。虽然 p1 指向新开辟的结点，但从链表中无法找到该结点。 　　
　　运行结果： 　　
　　程序分析： 　　（1）调用 create 函数后，先后输入所有学生的数据，若输入“0 0”，表示结束。函数的返回值是所建立的链表的第 1 个结点的地址(请查看 return 语句)，在主函数中把它赋给指针变量 pt。为了验证各结点中的数据，在 main 函数中输出了第 1 个结点中的信息。 　　（2）第 3 行令 LEN 代表 struct Student 类型数据的长度，sizeof 是 “ 求字节数运算符 ”。 　　（3）第 10 行定义一个 create 函数，它是指针类型，即此函数带回一个指针值，它指向一个 struct Student 类型数据。实际上此creat函数带回一个链表起始地址。 　　（4）第 15 行 malloc(LEN) 的作用是开辟一个长度为 LEN 的内存区，LEN 已定义为 sizeof( struct Student )，即结构体 struct Student 的长度。malloc 带回的是不指向任何类型数据的指针(void *类型)。而 p1，p2是指向 struct Student 类型数据的指针变量，可以用强制类型转换的方法使指针的基类型改变为 struct Student 类型，在 malloc(LEN) 之前加了 “( struct Student* )”，它的作用是使 malloc 返回的指针转换为 struct Student 类型数据的指针。注意括号中的 “ * ” 号不可省略，否则变成转换成 struct Student 类型了，而不是指针类型了。 　　（5）create 函数最后一行 return 后面的参数是 head( head 已定义为指针变量，指向  struct Student 类型数据)。因此函数返回的是 head 的值，也就是链表中第 1 个结点的起始地址。 　　（6）n 是结点个数。 　　（7）这个算法的思路是让 p1 指向新开辟的结点，p2 指向链表中最后一个结点，把 p1 所指的结点连接在 p2 所指的结点后面，用 “ p2->next = p1”来实现。 　　四、输出链表 　　将链表中各结点的数据依次输出。这个问题比较容易处理。 　　4.1举例说明 　　举例：编写一个输出链表的函数 print。 　　解题思路：从例 3.1 已经初步了解输出链表的方法。首先要知道链表第 1 个结点的地址，也就是要知道 head 的值。然后设一个指针变量 p，先指向第 1 个结点，输出 p 所指的结点,然后使 p 后移一个结点，再输出，直到链表的尾结点。 　　运行结果： 　　
　　说明: 　　链表是一个比较深入的内容，初学者有一定难度，计算机专业人员是应该掌握的，非专业的初学者对此有一定了解即可，在以后需要用到时再进一步学习。 　　对链表中结点的删除和结点的插入等操作，在此不作详细介绍，如读者有需要或感兴趣，可以自己完成。如果想详细了解，可参考严蔚敏《数据结构》一书。 　　结构体和指针的应用领域很宽广，除了单向链表之外，还有环形链表和双向链表。此外还有队列、树、栈、图等数据结构。有关这些问题的算法可以学习 “ 数据结构 ” 课程。