37.2° Blog

1.定义

typedef int ElemType;
typedef struct LinkNode
{
    ElemType data;
    struct LinkNode* next;
}LinkNode, *LinkList;

2.初始化单链表（带头结点）

bool initList(LinkList& L)
{
    L = (LinkNode*)malloc(sizeof(LinkNode));
    if (L == NULL)
        return false;
    L->next = NULL;
    return true;
}

3.判断链表为空

bool emptyList(LinkList L)
{
    return (L->next == NULL);
}

4. 创建单链表

4.1 头插法建立单链表

算法思想

• 先将插入结点的指针域修改为L的后继
• 再将头结点L的后继更新为 pNode

代码

void headInsertCreateList(LinkList& L, int arr[], int arrLength)
{
    // 初始化单链表，带头结点
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = NULL; 
    LinkNode* pNode = NULL;
    // 将每个元素加入链表中
    for (int idx = 0; idx < arrLength; idx++)
    {
        pNode = (LinkNode*)malloc(sizeof(LinkNode));
        pNode->data = arr[idx];
        // step1：先将插入结点指针域修改为L的后继
        pNode->next = L->next;
        // step2：再将头结点L的后继更新为pNode
        L->next = pNode;
    }
}

4.2 尾插法建立单链表

算法思想

• 先将插入结点的指针域改为tail指针的指针域
• 尾指针后继改为pNode
• 更新尾指针

代码

void tailInsertCreateList(LinkList& L, int arr[], int arrLength)
{
    // 初始化单链表，带头结点
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = NULL;
    LinkNode* tail = L;     // 表尾结点指针
    LinkNode* pNode = NULL;
    for (int i = 0; i < arrLength; i++)
    {
        pNode = (LinkNode*)malloc(sizeof(LinkNode));
        pNode->data = arr[i];
        // step1：先将插入结点的指针域改为tail指针的指针域
        pNode->next = tail->next;
        // step2：尾指针后继改为pNode
        tail->next = pNode;
        // step3：更新尾指针
        tail = pNode;
    }
}

5.链表递归

问题

L为带头结点的单链表，使用递归求解： （1）求单链表中的最大整数 （2）求链表中的结点数 （3）求链表中所有元素的平均值

算法思想

带头结点的链表，递归时，需要将头结点和其他数据结点分开，因为头结点不存数据。

注意递归的终止条件，

代码

求链表中的最大值

int getListMaxValue(LinkNode* pNode)
{
    if (pNode == NULL)
        return INT_MIN;
    // 递归求解L后面的最大值
    ElemType tmp = getListMaxValue(pNode->next);
    return tmp > pNode ->data ? tmp : pNode ->data;
}

求链表的结点数量

int getListNodes(LinkNode* pNode)
{
    if (pNode == NULL)
        return 0;
    // pNode 后子表长度 + 当前结点数
    return getListNodes(pNode->next) + 1;
}

求链表的元素之和

int getListElemSum(LinkNode* pNode)
{
    if (pNode == NULL)
        return 0;
    // L 当前结点元素 + L后结点元素之和
    return pNode->data + getListElemSum(pNode->next);
}

求链表元素的平均值

float getListElemAverage(LinkList L)
{
    LinkNode* pNode = L->next;
    int sum = getListElemSum(pNode);
    int nodes = getListNodes(pNode);
    return (float)sum / nodes;
}

6.链表插入

6.1 按位序插入

问题

在第i个位置插入元素e

算法思想

• 一个只有头结点的空链表，链中存在0个数据结点，因此就可以将头结点是为单链表中第0个数据结点。
• 使用计数器，每访问一个结点，计数器就增加一。
• 适用于结点编号的场景。

注意边界条件

代码

bool insertElemList(LinkList& L, int i, ElemType elem)
{
    if (i < 1)
        return false;
    // 当前扫描到的结点
    LinkNode* curNode = L;
    // 当前curNode是第几个结点
    int idxCurNode = 0;
    while (curNode != NULL && idxCurNode < i - 1)
    {
        curNode = curNode->next;
        idxCurNode++;
    }
    // i值不合法
    if (curNode == NULL)
        return false;
    LinkNode* tmp = (LinkNode*)malloc(sizeof(LinkNode));
    tmp->data = elem;
    // 将结点tmp连接到curNode之后
    tmp->next = curNode->next;
    curNode->next = tmp;
    return true;
}

6.2 后插操作

问题

在pNode结点之后插入元素elem

算法思想

注意不要断链

代码

bool nextInsertElemList(LinkNode* pNode, ElemType elem)
{
    if (pNode == NULL)
        return false;
    LinkNode* tmp = (LinkNode*)malloc(sizeof(LinkNode));
    if (tmp == NULL)
        return false;
    tmp->data = elem;
    // 将tmp结点插入pNode之后
    tmp->next = pNode->next;
    pNode->next = tmp;
    return true;
}

6.3 前插操作

问题

在pNode结点之前插入元素elem

算法思想

pNode后面插入一个结点tmp，将pNode结点的数据复制到tmp结点，新数据放入pNode结点

代码

bool priorInsertElemList(LinkNode* pNode, ElemType elem)
{
    if (pNode == NULL)
        return false;
    LinkNode* tmp = (LinkNode*)malloc(sizeof(LinkNode));
    if (tmp == NULL)
        return false;
    // 将pNode的元素复制到tmp中
    tmp->data = pNode->data;
    // 新元素复制到pNode中
    pNode->data = elem;
    // 将tmp插入pNode之后，实现前插操作
    tmp->next = pNode->next;
    pNode->next = tmp;
    return true;
}

7.链表删除

7.1 按位序删除

问题

删除单链表中第i个结点

算法思想

• 寻找链表中的第 i-1 个结点（删除结点的前一个）
• 删除第i个结点

代码

bool deleteElemList(LinkList& L, int i, ElemType& elem)
{
    if (i < 1)
        return false;
    // 当前扫描到的结点
    LinkNode* curNode = L;
    // 当前curNode是第几个结点
    int idxCurNode = 0;
    while (curNode != NULL && idxCurNode < i - 1)
    {
        curNode = curNode->next;
        idxCurNode++;
    }
    // 索引i不合法
    if (curNode == NULL)
        return false;
    // 第i-1个结点之后无其他结点
    if (curNode->next == NULL)
        return false;
    // 暂存要删除的结点
    LinkNode* tmp = curNode->next;
    elem = tmp->data;
    // 将删除的结点从链表中断开
    curNode->next = tmp->next;
    // 释放内存
    free(tmp);
    return true;
}

7.2 删除指定结点

问题

删除指定结点

算法思想

• 取出该结点的后继，
• 将后继的值赋予自身；
• 删除后继结点；
• 时间复杂度为O(1)

代码

bool deleteListNode(LinkNode* pNode)
{
    if (pNode == NULL)
        return NULL;
    // pNode后继结点
    LinkNode* nextNode = pNode->next;
    // 将pNode的后继结点的值复制到pNode中
    pNode->data = nextNode->data;
    // 将pNode的后继从链断开
    pNode->next = nextNode->next;
    // 释放空间
    free(nextNode);
    return false;
}

8.链表查找

8.1 按位查找

问题

按位查找，返回第i个元素（带头结点）

算法思想

• 注意终止条件
• 使用计数器标记访问过结点的数量

代码

LinkNode* getElemList(LinkList L, int i)
{
    if (i < 1)
        return false;
    // 当前扫描到的结点
    LinkNode* pNode = L;
    // 当前curNode是第几个结点
    int idxNode = 0;
    while (pNode != NULL && idxNode < i)
    {
        pNode = pNode->next;
        idxNode++;
    }
    return pNode;
}

8.2 按值查找

问题

按值查找

算法思想

• 注意区分终止条件

代码

LinkNode* localElemList(LinkList L, ElemType elem)
{
    LinkNode* pNode = L->next;
    // 从第一个结点开始查找数据域为elem的结点
    while (pNode != NULL && pNode->data != elem)
    {
        pNode = pNode->next;
    }
    return pNode;
}

8.3 查找倒数第m个结点

问题

设计高效算法查找带头结点单链表倒数第m个位置（m为正整数）的结点，并输出该结点的值

算法思想

• 先搜索距离第一个数据结点m个位置的元素，即用指针pCur指向第m+1个数据结点；
• 然后用pNode指向第一个结点，此时两个指针之间相距m个元素；
• 后移两个指针，当pCur指向空结点时，pNode指向距离空结点m个位置的结点；
• 此时，pNode结点即为倒数第m个结点。

代码

LinkNode* getRevElem(LinkList L, int m)
{
    // 指向头结点
    LinkNode* pCur = L;
    // 头结点为第0个结点
    int nodeNum = 0;
    // 依次访问结点，查找第m个结点
    while (pCur != NULL)
    {
        // 结点编号加一
        nodeNum++;
        // 找到第m个结点
        if (nodeNum == m)
        {
            // 指向第m个结点
            pCur = pCur->next;
            // 停止查找
            break;
        }
        pCur = pCur->next;
    }
    // 指向第m+1个元素
    pCur = pCur->next;
    LinkNode* pNode = L->next;
    // 将pCur移动到表末尾空结点
    while (pCur != NULL)
    {
        pNode = pNode->next;
        pCur = pCur->next;
    }
    return pNode;
}

9.其他

9.1 合并链表

问题

已知单链表La和Lb的元素按值非递减排列 合并La，Lb后的新链表Lc也按非递减排列

算法思想

• 注意和顺序表的区分

代码

void mergeList(LinkList La, LinkList Lb, LinkList& Lc)
{
    LinkNode* paNode = La->next;
    LinkNode* pbNode = Lb->next;
    // 用La的头结点作为Lc的头结点
    /*LinkNode* pcNode = La;
    Lc = pcNode;*/
    LinkNode* pcNode = Lc;
    while (paNode != NULL && pbNode != NULL)
    {
        if (paNode->data <= pbNode->data)
        {
            pcNode->next = paNode;
            pcNode = pcNode->next;
            paNode = paNode->next;
        }
        else
        {
            pcNode->next = pbNode;
            pcNode = pcNode->next;
            pbNode = pbNode->next;
        }
    }
    pcNode->next = paNode ? paNode : pbNode;
}

测试代码

// 链表合并
printf("链表合并\n");
int arr1[] = {8,7,6,5,4,3,2,1};
int arr1Length = 8;
LinkList Lc, Ld, Le;
headInsertCreateList(Lc, arr1, arr1Length);
headInsertCreateList(Ld, arr1, arr1Length);
initList(Le);
printList(Lc);
printList(Ld);
printList(Le);
mergeList(Lc,Ld, Le);
printList(Le);

9.2 链表逆置

问题

链表逆置

算法思想

• 将头结点取下，从第一个结点开始；
• 依次插到头结点后面（头插法建立单链表）
• 直到最后一个结点为止

代码

void reverseList(LinkList& L)
{
    // 工作指针，先指向链表头结点
    LinkNode* pNode = L->next;
    // pNode的后继，防止断链
    LinkNode* nextNode;
    // 将L的头结点置为NULL，准备用头插法
    L->next = NULL;
    // 依次取下头节点，使用头插法插入
    while (pNode != NULL)
    {
        // 暂存pNode结点
        nextNode = pNode->next;
        // 将pNode结点插入到头节点之后
        pNode->next = L->next;
        L->next = pNode;
        // 更新pNode结点
        pNode = nextNode;
    }
}