文章目录
- 单链表的应用概览
- 查找单链表倒数第k个结点
- 查找单链表的中间结点
- 将单链表逆置
- 第二章真题检测
单链表的应用概览
查找单链表倒数第k个结点
本节给出单链表的4个应用示例。单链表结点的定义与本章第三节中的定义相同。为了方便，重新写出来。
#define TRUE 1
#define FALSE 0
#define ERROR -1
单链表中每个元素的类型是ELEMType，单链表中结点及链表的定义如下。
typedef int ELEMTYPE;
typedef struct node { //单链表结点
ELEMTYPE data; //数据域
struct node *next; //指针域
} LinkNode;
typedef LinkNode *LinkList; //单链表
typedef int Position; //位置
为了展示单链表的应用，需要先创建一个单链表。
单链表中各元素的值从键盘读入。
定义单链表的头指针LinkListhead=NULL，然后调用本章第三节中的initList(&head)进行初始化。
接下来，调用createMyList(&head)创建单链表。
在createMyList中，先从键盘上输入元素个数，然后依次读入相应个数的整数值，使用这些值构造一个带头结点的单链表。
相应的实现如下。
int createMyList(LinkList * head) {
// 构造一个带头结点的单链表
int i, counter, k;
printf("请输入单链表元素个数: ");
scanf("%d", &counter);
if (counter > 0) {
printf("请输入构成链表的%d个整数: ", counter);
for (i = 0; i < counter; i++) {
scanf("%d", &k);
if (insertList(head, i, k) == FALSE) return FALSE;
}
}
display(head);
return TRUE;
}
在程序运行后，从键盘输入的单链表元素个数保存在变量counter中。
只有当counter大于0时，才依次读入单链表各元素的值。
读入的值使用本章第三节实现的insertList()函数插入到单链表的表尾。
也可以将待输入的数据预先保存在一个一维数组中，假设数组是a，数组元素个数是na，
则在完成初始化后，调用createMyListFromArray(head,a,na)来构建单链表。
createMyListFromArray的实现如下。
int createMyListFromArray(LinkList * head, int * a, int n) {
// 读取数组中元素的值,构造一个带头结点的单链表
int i;
if (n > 0) {
for (i = 0; i < n; i++) {
if (insertList(head, i, a[i]) == FALSE) return FALSE;
}
}
return TRUE;
}
我们已经知道，在单链表中，每个结点含有的指针只有— 个，它指向当前结点的后继结点。
当要访问单链表中正数第K个结点时，从头指针开始，沿指针的方向依次后移k-1次，就可以定位到要访间的结点。
为了统一 ，如果单链表中有头结点，则将头结点也一 起编号。
如果要查找单链表中倒数第k (k≥1) 个结点，则没有这么简单。因为不能从表尾向表头进行遍历，所以不能直接从表尾向表头直接数K个结点。
至少有两个办法可以实现这个操作。
如果知道单链表的长度，那么查找倒数第K个结点就很容易了。
假设单链表中含有n个结点，则倒数第K个结点即第n-k+l个结点。
如果单链表头结点的数据域中保存了单链表的长度，则可以很方便地找到这个值。
如果没有保存，则需要遍历一 遍单链表，并对结点个数进行计数，从而得到单链表的长度。
当不知道单链表的长度时，还可以使用下面介绍的方法来查找单链表倒数第k个结点。
使用两个指针front和rear , 均从表头开始向表尾方向移动。
初始时，先令front前进K步，当个 “排头兵＇。
这样front和rear指向的位置相距k个结点。
然后两个指针同步前进。
当front到达表尾时，rear即指向倒数第k个结点。
在这个过程中，可能会出现几种例外情况，需要加以特殊处理。
一种例外是，给定的单链表是空表。
对于空表，不能进行相应的查找。所以程序需要判定给定的单链表是不是空表。
另一种例外是，给定的k值不合理。
程序中需要判定k值是不是不大于表长的一个正整数。
程序的实现如下。
LinkNode * findKth(LinkList * head, int k) {
// 查找倒数第k个结点
LinkNode * front, * rear;
int i, flag = 1;
if (k <= 0) {
printf("k必须大于零!");
return NULL;
}
if (*head == NULL) {
printf("链表错误\n");
return NULL;
}
front = *head;
rear = *head;
for (i = 0; i < k; i++) {
if (front!= NULL) front = front->next;
else {
flag = 0;
break;
}
}
if (!flag) {
printf("k值大于表长!");
return NULL;
}
while (front!= NULL) {
front = front->next;
rear = rear->next;
}
return rear;
}
查找单链表的中间结点
单链表的长度是任意的，所以中间结点并不能确定是其中的第几个结点，具体的值要依单链表的长度而定。
而且，当单链表结点个数是偶数时，会有两个中间结点，这里只求前一个结点。
不能简单地调用上面给出的findKth函数，但实现思想是类似的。
仍然使用两个指针，并从表头开始同步地向表尾方向移动，一个指针每次走两步，另一个指针每次走一步。
- 这个之前学习过
这样，当“排头兵”指针到达表尾时，后面的指针即指向链表的中间结点。
与findKth函数中一样，两个指针分别是front和rear。
程序的实现如下。
LinkNode * findMiddle(LinkList * head) {
// 查找中间结点, 返回指向中间结点的指针
LinkNode * front, * rear;
if (*head == NULL) {
printf("链表错误\n");
return NULL;
}
front = *head;
rear = *head;
while (front!= NULL) {
// 当前指针front没有移动到最后一个结点之前, 继续循环
front = front->next;
if (front!= NULL) {
front = front->next;
rear = rear->next;
}
else {
break;
}
}
return rear;
}
将单链表逆置
假设单链表中含有头结点。
原单链表的头结点保留，仍为逆置后新单链表的头结点。
所以，对于头指针head，先不进行处理。
从第一个数据结点开始，依次让每个结点的指针域反向，由指向其后继结点转为指向其前驱结点。
为了使处理过程中单链表的链接不中断，使用三个指针分别指向相邻的三个结点，
如图2-24所示。
第一个数据结点需要特殊处理，因为它将是逆置后单链表的表尾结点，next域必须置为NULL
对于单链表中的其他结点，让middle所指结点的next域指向left所指结点，即left所指结点的原后继(middle所指)变为它的新前驱。
然后，三个指针依次后移一个位置。
当所有结点中的next域都转向后，再将head所指的头结点链接在表头处。
程序的实现如下。
int reverse(LinkList * head) {
// 将单链表逆置
LinkNode * left, * middle, * right;
if (*head == NULL) {
printf("链表错误\n");
return FALSE;
}
left = (*head)->next;
if (left!= NULL) middle = left->next;
left->next = NULL;
while (middle!= NULL) {
right = middle->next;
middle->next = left;
left = middle;
middle = right;
}
(*head)->next = left;
return TRUE;
}
第二章真题检测
1、链表
B、D
2、顺序表
A、E
3、F是两者共有
支持顺序存取，链表和顺序表都支持，这个是最基本的存取嘛
4、C是链表独有
链表所需空间与元素个数成正比
来自AI：
链表中每个元素都存储在一个独立的节点中，每个节点除了存储元素本身的数据外，还需要额外的空间来存储指针（用于指向下一个节点或前一个节点和下一个节点 ）。随着元素个数的增加，节点的数量也相应增加，由于每个节点都有数据部分和指针部分，所以整体占用的空间也随之增加，呈现出与元素个数成正比的关系。
若要存储整数 1、2、3，需要创建 3 个节点：
- 第一个节点存储 1，同时有一个指针指向第二个节点；
- 第二个节点存储 2，同时有一个指针指向第三个节点；
- 第三个节点存储 3，由于它是最后一个节点，其指针指向
NULL。每增加一个元素，就要新增一个节点，也就增加了存储数据和指针的空间。比如再增加一个元素 4，就需要再创建一个节点来存储 4，并将其与前一个节点通过指针连接起来。所以，元素个数越多，创建的节点就越多，占用的空间也就越大，二者成正比关系。
见，Day27-【13003】短文，什么是单链表、循环链表、双向链表、双向循环链表？它们的操作时间复杂度是多少？如何进行存储单元的计算？，中：单链表所占用的空间量与表中的结点个数成正比。
