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

C语言数据结构-单链表

backend 2025/5/24 13:23:41

单链表

头文件：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.xdnf.cn/news/8555.html

相关文章：

  • 解锁内心的冲突：神经症冲突的理解与解决之道
  • 半导体B2B分销中台有哪些应用场景
  • 安装NBU软件及配置方法
  • 谈谈对dubbo的广播机制的理解
  • 促销活动期间，确保邮件不被标记为垃圾邮件
  • 第六十六篇 探秘Java JVM内存模型：从城市基建到程序世界的精妙映射
  • mysql8.4.3配置主从复制
  • 鸿蒙进阶——Framework之Want 隐式匹配机制概述
  • ch11题目参考思路
  • linux移植lvgl
  • 经典密码学和现代密码学的结构及其主要区别（1）维吉尼亚密码—附py代码
  • 模拟交易新维度：如何通过自营交易考试实现策略收益双提升？
  • PTA L1系列题解（C语言）（L1_105 -- L1_112）
  • OCC导入进度显示
  • Makefile快速入门
  • 直播预告 | 共探“数字化转型新引擎”，蓝卓工业互联网+AI对话夜等你来
  • 数字计数--数位dp
  • C 语言学习笔记（指针4）
  • golang 垃圾收集机制
  • 防火墙NAT地址组NAT策略安全策略
  • 50 python Matplotlib之Seaborn
  • Python爬虫实战：研究Cola框架相关技术
  • 开发工具整理
  • Python初始Flask框架
  • 敦煌网测评从环境搭建到风控应对，精细化运营打造安全测评体系
  • 【自定义类型-结构体】--结构体类型，结构体变量的创建和初始化，结构体内存对齐，结构体传参，结构体实现位段
  • ComfyUI Chroma解锁文生图新维度；OpenMathReasoning数学推理数据集，首个专注数学推理的高质量数据集
  • 深入探索 CSS 中的伪类：从基础到实战​
  • 文件目录名称无效？数据恢复全流程与常见问题解析
  • CMA/CNAS认证电子签章审计追踪 质检 LIMS 系统应用要点