当前位置： 首页 > article >正文

C语言数据结构-单向链表

article 2025/8/14 13:14:04

头文件：link.h

#ifndef __LINK_H__
#define __LINK_H__

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

/*节点数据类型*/
typedef struct node
{
    DataType data;              //数据域
    struct node *pNext;         //指针域
}LinkNode;

/* 标签数据类型 */
typedef struct list
{
    LinkNode *pHead;           //链表头节点指针
    int cLen;                  //当前链表节点个数
}LinkList;

#endif

源文件：link.c

#include "link.h"

创建一个新节点：
LinkList *createLinkList()
{
    LinkList *pList = NULL;

    pList = malloc(sizeof(LinkList));
    if (NULL == pList)
    {
        perror("fail to malloc");
        return NULL;
    }
    pList->pHead = NULL;
    pList->cLen = 0;

    return pList;
}

头插：
int insertHeadLinkList(LinkList *pList, DataType data)
{
    LinkNode * pInsertNode = malloc(sizeof(LinkNode));
    if (NULL == pInsertNode)
    {
        perror("fail to malloc");
        return -1;
    }
    pInsertNode->data = data;

    pInsertNode->pNext = pList->pHead;
    pList->pHead = pInsertNode;
    pList->cLen++;

    return 0;
}

遍历：

void showLinkList(LinkList *pList)
{
    LinkNode *pTmpNode = pList->pHead;

    while (pTmpNode != NULL)
    {
        printf("%d ", pTmpNode->data);
        pTmpNode = pTmpNode->pNext;
    }
    printf("\n");

}

判空：

int isEmptyLinkList(LinkList *pList)
{
    return pList->cLen == 0;
}

尾插：
int insertTailLinkList(LinkList *pList, DataType data)
{
    LinkNode *pInsertNode = malloc(sizeof(LinkNode));
    if (NULL == pInsertNode)
    {
        perror("fail to malloc");
        return -1;
    }
    pInsertNode->data = data;
    pInsertNode->pNext = NULL;

    if (isEmptyLinkList(pList))
    {
        pList->pHead = pInsertNode;
    }
    else
    {
        LinkNode *pTmpNode = pList->pHead;
        while (pTmpNode->pNext != NULL)
        {
            pTmpNode = pTmpNode->pNext;
        }
        pTmpNode->pNext = pInsertNode;
    }
    pList->cLen++;

    return 0;
}

头删:

int deleteHeadLinkList(LinkList *pList)
{
    if (isEmptyLinkList(pList))
    {
        return 0;
    }

    LinkNode *pFreeNode = pList->pHead;
    pList->pHead = pFreeNode->pNext;
    free(pFreeNode);
    pList->cLen--;

    return 0;
}

尾删：

int deleteTailLinkList(LinkList *pList)
{
    if (isEmptyLinkList(pList))
    {
        return 0;
    }
    else if (1 == pList->cLen)
    {
        deleteHeadLinkList(pList);
    }
    else
    {
        LinkNode *pTmpNode = pList->pHead;
        while (pTmpNode->pNext->pNext != NULL)
        {
            pTmpNode = pTmpNode->pNext;
        }
        free(pTmpNode->pNext);
        pTmpNode->pNext = NULL;
        pList->cLen--;
    }

    return 0;
}

查找单链表的某个节点：

LinkNode *findLinkList(LinkList *pList, DataType findData)
{
    LinkNode *pTmpNode = pList->pHead;

    while (pTmpNode != NULL)
    {
        if (pTmpNode->data == findData)
        {
            return pTmpNode;
        }
        pTmpNode = pTmpNode->pNext;
    }

    return NULL;
}

单链表倒置：

int reverseLinkList(LinkList *pList, DataType oldData, DataType newData)
{
    LinkNode *pTmpNode = NULL;
    while ((pTmpNode = findLinkList(pList, oldData)) != NULL)
    {
        pTmpNode->data = newData;
    }
    
    return 0;
}

销毁链表：

void destroyLinkList(LinkList **ppList)
{
    while ((*ppList)->pHead != NULL)
    {
        deleteHeadLinkList(*ppList);
    }
    free(*ppList);
    *ppList = NULL;

}

查找中间节点：
LinkNode *findMidLinkNode(LinkList *pList)
{
    LinkNode *pFast = pList->pHead;
    LinkNode *pSlow = pFast;

    while (pFast != NULL)
    {
        pFast = pFast->pNext;
        if (NULL == pFast)
        {
            break;
        }
        pFast = pFast->pNext;
        pSlow = pSlow->pNext;
    }

    return pSlow;
}

查找最后一个节点：

LinkNode *findLastKNode(LinkList *pList, int K)
{
    LinkNode *pFast = pList->pHead;
    LinkNode *pSlow = pFast;
    int i = 0;
    for (; i < K; i++)
    {
        pFast = pFast->pNext;
    }
    while (pFast != NULL)
    {
        pFast = pFast->pNext;
        pSlow = pSlow->pNext;
    }

    return pSlow;
}

删除某个节点：

int deletePointNode(LinkList *pList, DataType deleteData)
{
    LinkNode *pPreNode = pList->pHead;
    LinkNode *pFreeNode = pList->pHead;

    while (pFreeNode != NULL)
    {
        if (pFreeNode->data == deleteData)
        {
            if (pPreNode == pFreeNode)
            {
                pList->pHead = pFreeNode->pNext;
                free(pFreeNode);
                pPreNode = pList->pHead;
                pFreeNode = pList->pHead;
            }
            else
            {
                pPreNode->pNext = pFreeNode->pNext;
                free(pFreeNode);
                pFreeNode = pPreNode->pNext;
            }
            pList->cLen--;
        }
        else
        {
            pPreNode = pFreeNode;
            pFreeNode = pFreeNode->pNext;
        }
    }

    return 1;
}

单链表反转：

void invertLinkList(LinkList *pList)
{
    LinkNode *pTmpNode = pList->pHead;
    LinkNode *pInsertNode = NULL;
    
    pList->pHead = NULL;
    while (pTmpNode != NULL)
    {
        pInsertNode = pTmpNode;
        pTmpNode = pTmpNode->pNext;
        
        pInsertNode->pNext = pList->pHead;
        pList->pHead = pInsertNode;
    }
    
    return ;
}

链表排序：

void sortLinkList(LinkList *pList)
{
    //链表为空或只有一个节点不需要排序
    if (isEmptyLinkList(pList) || 1 == pList->cLen)
    {
        return ;
    }
    //保存第二个节点并且从第一个节点后断开
    LinkNode *pInsertNode = NULL;
    LinkNode *pTmpNode = pList->pHead->pNext;
    pList->pHead->pNext = NULL;

    while (pTmpNode != NULL)
    {
        //找到要插入的节点
        pInsertNode = pTmpNode;
        pTmpNode = pTmpNode->pNext;

        //判断是否需要头插
        if (pInsertNode->data < pList->pHead->data)
        {
            //头插
            pInsertNode->pNext = pList->pHead;
            pList->pHead = pInsertNode;
        }
        else
        {
            //寻找插入位置
            LinkNode *p = pList->pHead;
            while (p->pNext != NULL && p->pNext->data < pInsertNode->data)
            {
                p = p->pNext;
            }
            //节点插入
            pInsertNode->pNext = p->pNext;
            p->pNext = pInsertNode;
        }
    }
}

判断链表是否有环：

int isLoopLinkList(LinkList *pList)
{
    LinkNode *pFast = pList->pHead;
    LinkNode *pSlow = pList->pHead;

    while (pFast != NULL)
    {
        pFast = pFast->pNext;
        if (NULL == pFast)
        {
            return 0;
        }
        if (pSlow == pFast)
        {
            return 1;
        }
        pFast = pFast->pNext;
        pSlow = pSlow->pNext;
        if (pFast == pSlow)
        {
            return 1;
        }
    }
}
int main(int argc, const char *argv[])
{
    LinkList *pList = NULL;
    LinkNode *pTmpNode = NULL;

    pList = createLinkList();

//    insertHeadLinkList(pList, 1);
    insertHeadLinkList(pList, 2);
    insertHeadLinkList(pList, 3);
    insertHeadLinkList(pList, 4);

    insertTailLinkList(pList, 5);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);


    showLinkList(pList);
#if 0
    deleteHeadLinkList(pList);

    deleteTailLinkList(pList);

    showLinkList(pList);

    pTmpNode = findLinkList(pList, 3);
    if (pTmpNode != NULL)
    {
        printf("find %d\n", pTmpNode->data);
    }
    else
    {
        printf("not find\n");
    }

    reverseLinkList(pList, 3, 10);
    showLinkList(pList);
#endif
    
    pTmpNode = findMidLinkNode(pList);
    printf("mid node = %d\n", pTmpNode->data);

    pTmpNode = findLastKNode(pList, 3);
    printf("last K node = %d\n", pTmpNode->data);
#if 0    
    deletePointNode(pList, 3);
    showLinkList(pList);
    
    invertLinkList(pList);
    showLinkList(pList);

    sortLinkList(pList);
    showLinkList(pList);

//    destroyLinkList(&pList);
#endif

    //构造环形链表
    pTmpNode = pList->pHead;
    while (pTmpNode->pNext != NULL)
    {
        pTmpNode = pTmpNode->pNext;
    }
    pTmpNode->pNext = pList->pHead->pNext->pNext->pNext->pNext;

    if (isLoopLinkList(pList))
    {
        printf("is loop link.\n");
    }
    else
    {
        printf("is not loop link.\n");
    }

    return 0;
}
 

http://www.lryc.cn/news/2387873.html

相关文章：

  • 小样本分类新突破：QPT技术详解
  • Excel常用公式全解析（1）：从基础计算到高级应用
  • C++ STL 容器：List 深度解析与实践指南
  • 每天掌握一个Linux命令 - ab（Apache Benchmark）
  • 与 PyCharm 官方沟通解决开发环境问题记录（进展：官方已推出2个新的修复版本）
  • Python的分布式网络爬虫系统实现
  • Vue快速上手(业务、技术、报错)
  • taro + vue3 实现小程序sse长连接实时对话
  • 使用MATLAB求解微分方程：从基础到实践
  • 基于MATLAB的大规模MIMO信道仿真
  • 如何在 Windows 和 Mac 上擦拭和清洁希捷外置硬盘
  • Vue 3.0 中状态管理Vuex 与 Pinia 的区别
  • 第三届黄河流域网安技能挑战赛复现
  • pyｔｈｏｎ 生成复杂表格，自动分页等功能
  • 2025年高防IP与游戏盾深度对比：如何选择最佳防护方案？
  • 在 Vue + Vite 项目中，直接使用相对路径或绝对路径引用本地图片资源时，图片无法正确显示。
  • 判断手机屏幕上的横向滑动（左滑和右滑）
  • 用户有一个Django模型没有设置主键，现在需要设置主键。
  • 【文献阅读】EndoChat: Grounded Multimodal Large Language Model for Endoscopic Surgery
  • React JSX语法介绍（JS XML）（一种JS语法扩展，允许在JS代码中编写类似HTML的标记语言）Babel编译
  • 【R语言编程绘图-箱线图】
  • 【elasticsearch 7 或8 的安装及配置SSL 操作指引】
  • GitHub 趋势日报 (2025年05月23日)
  • MongoDB索引：原理、实践与优化指南
  • SQL实战之索引优化(单表、双表、三表、索引失效)
  • [7-1] ADC模数转换器 江协科技学习笔记（14个知识点）
  • SSM整合：Spring+SpringMVC+MyBatis完美融合实战指南
  • Spring Boot分页查询进阶：整合Spring Data REST实现高效数据导航
  • 阿里云 Serverless 助力海牙湾构建弹性、高效、智能的 AI 数字化平台
  • 升级node@22后运行npm install报错 distutils not found