Day27-【13003】短文，单链表应用代码举例

单链表的应用概览

查找单链表倒数第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】短文，什么是单链表、循环链表、双向链表、双向循环链表？它们的操作时间复杂度是多少？如何进行存储单元的计算？，中：单链表所占用的空间量与表中的结点个数成正比。