单向链表，双向链表，内核链表，栈，队列简单操作

2024-08-30 00:20
文章标签 简单 链表 操作 队列 双向 内核 单向

本文主要是介绍单向链表，双向链表，内核链表，栈，队列简单操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.单向链表

        1.1创建空节点

        link_t 为宏定义的链表节点结构体，typedef struct linknode{struct linknode pnext; DateType   data; }link_t;  其中DateType为宏定义的数据类型#define  int DateType；

link_t *CreateLinkNode(void)
{link_t *phead = NULL;phead = malloc(sizeof(link_t));if (phead == NULL){return NULL;}phead->pnext = NULL;return phead;
}

        1.2头插法插入节点

int HeadInsertLinkList(link_t *phead, DateType tmpdate)
{link_t *newnode = NULL;//申请空间newnode = malloc(sizeof(link_t));if (NULL == newnode){return -1;}//对两个成员赋值newnode->data = tmpdate;newnode->pnext = phead->pnext;//头结点指向新节点phead->pnext = newnode;return 0;
}

        1.3尾插法插入节点

//尾插法
int TailInsertLinkList(link_t *phead, DateType tmpdate)
{   link_t *ptemp = NULL;link_t *newlink = NULL;ptemp = phead;while (ptemp->pnext != NULL){ptemp = ptemp->pnext;}newlink = malloc(sizeof(link_t));if (newlink == NULL){return -1;}newlink->data = tmpdate;newlink->pnext = NULL;ptemp->pnext = newlink;return 0;
}

        1.4遍历链表

//打印链表内容
int ShowLinkList(link_t *phead)
{link_t *ptemp = NULL;ptemp = phead->pnext;while (ptemp != NULL){printf("%d ", ptemp->data);ptemp = ptemp->pnext;}printf("\n");return 0;
}

        1.5修改链表数据

//修改链表数据
int UpdateLinkList(link_t *phead, DateType olddate, DateType newdate)
{//遍历链表，查找数据link_t *ptemp = NULL;ptemp = phead->pnext;while (ptemp != NULL){if (ptemp->data == olddate){ptemp->data = newdate;break;}ptemp = ptemp->pnext;}return 0;
}

        1.6查找链表数据

//查找链表数据
link_t *FindLinkList(link_t *phead, DateType tmpdate)
{link_t *ptemp = NULL;ptemp = phead->pnext;while (ptemp != NULL){if (ptemp->data == tmpdate){break;}ptemp = ptemp->pnext;}return ptemp;
}

        1.7删除链表节点

        定义两个结构体指针，分别指向头节点和下一节点，遍历链表，同时两个指针同步向下走，直到需要删除的节点

//删除链表
int DeleteLinkList(link_t *phead, DateType tempdate)
{link_t *pfirst = NULL;link_t *psecend = NULL;int cnt = 0;pfirst = phead;psecend = phead->pnext;while (psecend != NULL){if (psecend->data == tempdate){pfirst->pnext = psecend->pnext;free(psecend);psecend = pfirst->pnext;cnt++;}else{pfirst = pfirst->pnext;psecend = psecend->pnext;}}return cnt;
}

        1.8销毁链表

//销毁链表
int DestoryLinkList(link_t **phead)
{link_t *pfirst = NULL;link_t *psecend = NULL;psecend = pfirst = (*phead);while (psecend != NULL){psecend = psecend->pnext;free(pfirst);pfirst = psecend;}(*phead) = NULL;return 0;
}

        1.9查找链表中间节点

        定义两个指针，一快，一慢，快指针走过的距离始终是慢指针走过距离的两倍，走到最后慢指针指向的节点为中间节点

link_t *FindMedleLinkList(link_t *phead)
{link_t *pfast = NULL;link_t *pslow = NULL;pfast = pslow = phead->pnext;while (pfast != NULL){pslow = pslow->pnext;pfast = pfast->pnext;if (pfast != NULL){pfast = pfast->pnext;}}return pslow;
}

        1.10找到单向链表倒数第K个节点

        同样定义两个指针， 一快，一慢，快指针先走k个距离，然后两只指针在同时向下走，最后慢指针指向的节点为第K个节点

//找到倒数第k个节点
link_t *FindNumKLinkList(link_t *phead, DateType tempdate)
{link_t *pfast = NULL;link_t *pslow = NULL;int i = 0;pfast = phead;pslow = phead;for (i = 0; i < tempdate; i++){pfast = pfast->pnext;if (pfast == NULL){return NULL;break;}}while (pfast != NULL){pfast = pfast->pnext;pslow = pslow->pnext;}return pslow;
}

       1.11倒置 

//链表倒置
int IvertLinkList(link_t *phead)
{link_t *ptemplink = NULL;link_t *pinvertlink = NULL;ptemplink = phead->pnext;phead->pnext = NULL;pinvertlink = ptemplink;while (ptemplink != NULL){ptemplink = ptemplink->pnext;pinvertlink->pnext = phead->pnext;phead->pnext = pinvertlink;pinvertlink = ptemplink;}return 0;
}

        1.12冒泡排序

//链表冒泡排序
int BubbleSortLinkList(link_t *phead)
{link_t *ptemplink1 = NULL;link_t *ptemplink2 = NULL;link_t *pend = NULL;DateType tempdate;if (phead->pnext == NULL || phead->pnext->pnext == NULL){return 0;}while (pend != phead->pnext->pnext){ptemplink1 = phead->pnext;ptemplink2 = phead->pnext->pnext;while (ptemplink2 != pend){if (ptemplink1->data > ptemplink2->data){   tempdate = ptemplink1->data;ptemplink1->data = ptemplink2->data;ptemplink2->data = tempdate;}ptemplink1 = ptemplink1->pnext;ptemplink2 = ptemplink2->pnext;}pend = ptemplink1;}return 0;
}

        1.13选择排序

//选择排序
int SelectLinkList(link_t *phead)
{link_t *pmin = NULL;link_t *ptemp = NULL;link_t *pswap = NULL;DateType tempdate = 0;if (phead->pnext == NULL || phead->pnext->pnext == NULL){return 0;}pswap = phead->pnext;while (pswap->pnext != NULL){pmin = pswap;ptemp = pswap->pnext;while (ptemp != NULL){if (ptemp->data > pmin->data){pmin = ptemp;}ptemp = ptemp->pnext;}if (pmin != pswap){tempdate = pmin->data;pmin->data = pswap->data;pswap->data = tempdate;}pswap = pswap->pnext;}return 0;
}

        1.14判断是否有环，以及环长为多少

        定义快慢指针， 循环向下走，当快慢指针相同时即为有环，并定义一个指向慢指针，即快慢指针的相遇点。若快指针走到NULL即该链表没有环。

        定义一个指针指向相遇点，从该点开始循环并计数cnt，当该指针回到该点时cnt的值为环长

        定义两个指针，一个指向相遇点，一个指向第一个有效节点即phead->pnext，两指针同时向下走，当两指针相遇时的节点即换入口位置

//判断链表是否有环
//实现方式：
//     快指针每次走2步，慢指针每次走1步
//     两者能够相遇即为有环
LinkNode *IsHasCircle(LinkNode *pHead, int *pcnt)
{LinkNode *pFast = NULL;LinkNode *pSlow = NULL;LinkNode *pTmpNode = NULL;LinkNode *pNode1 = NULL;LinkNode *pNode2 = NULL;int ret = 0;int cnt = 1;pSlow = pFast = pHead->pNext;while (1){pFast = pFast->pNext;if (NULL == pFast){ret = 0;break;}pFast = pFast->pNext;if (NULL == pFast){ret = 0;break;}pSlow = pSlow->pNext;if (pSlow == pFast){ret = 1;break;}}if (1 == ret){//获得环长pTmpNode = pSlow->pNext;while (pTmpNode != pSlow){cnt++;pTmpNode = pTmpNode->pNext;}*pcnt = cnt;//获得环入口位置pNode1 = pSlow;pNode2 = pHead->pNext;while (1){pNode1 = pNode1->pNext;pNode2 = pNode2->pNext;if (pNode1 == pNode2){return pNode1;}}}return NULL;
}

2.双向链表

        2.1创建头节点

//创建头节点
LinkNode *CreateDoubleLinkNode(void)
{LinkNode *phead = NULL;phead = malloc(sizeof(LinkNode));if (phead == NULL){return NULL;}phead->pPre = NULL;phead->pNext = NULL;return phead;
}

        2.2头插法插入

//头插法插入
int HeadInsertLinkNode(LinkNode *phead, DateType tempdate)
{LinkNode *NewNode = NULL;NewNode = malloc(sizeof(LinkNode));if (NewNode == NULL){return -1;}NewNode->date = tempdate;NewNode->pNext = phead->pNext;phead->pNext = NewNode;NewNode->pPre = phead;if (NewNode->pNext != NULL){NewNode->pNext->pPre = NewNode;}return 0;
}

        2.3尾插法插入

//尾插法插入
int TailInsertLinkNode(LinkNode *phead, DateType tempdate)
{LinkNode *NewNode = NULL;LinkNode *pTempNode = NULL;NewNode = malloc(sizeof(LinkNode));if (NewNode == NULL){return -1;}pTempNode = phead->pNext;if (pTempNode == NULL){HeadInsertLinkNode(phead, tempdate);}while (pTempNode->pNext != NULL){pTempNode = pTempNode->pNext;}NewNode->date = tempdate;NewNode->pNext = NULL;NewNode->pPre = pTempNode;pTempNode->pNext = NewNode;return 0;
}

        2.4遍历链表

//头插法插入
int HeadInsertLinkNode(LinkNode *phead, DateType tempdate)
{LinkNode *NewNode = NULL;NewNode = malloc(sizeof(LinkNode));if (NewNode == NULL){return -1;}NewNode->date = tempdate;NewNode->pNext = phead->pNext;phead->pNext = NewNode;NewNode->pPre = phead;if (NewNode->pNext != NULL){NewNode->pNext->pPre = NewNode;}return 0;
}

        2.5删除链表节点

//删除节点
int DeleteLinkNode(LinkNode *phead, DateType tempdate)
{LinkNode *pTempNode = NULL;LinkNode *pRetNode = NULL;pTempNode = phead->pNext;pRetNode = phead->pNext;while (pTempNode != NULL){pRetNode = pRetNode->pNext;if (pTempNode->date == tempdate && pTempNode->pNext != NULL){pTempNode->pPre->pNext = pTempNode->pNext;pTempNode->pNext->pPre = pTempNode->pPre; free(pTempNode);}else if (pTempNode->date == tempdate && pTempNode->pNext == NULL){pTempNode->pPre->pNext = NULL;free(pTempNode);}pTempNode = pRetNode;}return 0;
}

        2.6销毁链表

//销毁链表
int DestoryLinkNode(LinkNode **phead)
{LinkNode *pTempNode = NULL;if ((*phead)->pNext == NULL){free(*phead);*phead = NULL;return 0;}if ((*phead)->pNext->pNext == NULL){pTempNode = (*phead)->pNext;free(pTempNode);free(*phead);*phead = NULL;return 0;}else {pTempNode = (*phead)->pNext->pNext;while (pTempNode != NULL){free(pTempNode->pPre);if (pTempNode->pNext == NULL){break;}pTempNode = pTempNode->pNext;}free(pTempNode);free(*phead);*phead = NULL;}

3.内核链表

        3.1概念

        内核链表基于双向链表

        一种内核链表可以操作多种数据类型的对象

        数据包含节点，数据节点与链表节点相同类型不同，需要进行强制转换

        3.2示例

        其中list.h为内核链表宏定义文件

#include "list.h"
#include <stdio.h>
#include <stdlib.h>//定义数据类型结构
typedef struct data
{struct list_head node;char name[64];char sex[32];int age;double score;
}stu_t;int main(void)
{struct list_head head;struct list_head *pTmpNode = NULL;stu_t *pdata = NULL;INIT_LIST_HEAD(&head);    //初始化头节点stu_t tmp1 = {{NULL, NULL}, "zhangsan", "male", 16, 75.6};    //插入数据list_add(&tmp1.node, &head);                                  //头插法插入数据节点stu_t tmp2 = {{NULL, NULL}, "lisi", "fmale", 21, 33.3};list_add(&tmp2.node, &head);stu_t tmp3 = {{NULL, NULL}, "wanger", "male", 88, 49.8};list_add(&tmp3.node, &head);stu_t tmp4 = {{NULL, NULL}, "zhaoliu", "male", 55, 88.8};list_add_tail(&tmp4.node, &head);stu_t tmp5 = {{NULL, NULL}, "laoba", "fmale", 44, 92.1};list_add_tail(&tmp5.node, &head);list_for_each(pTmpNode, &head){pdata = (stu_t *)pTmpNode;        //强制类型转换，将链表节点转换为数据节点printf("name = %-10s sex = %-5s age = %-4d score = %-.2lf\n", pdata->name, pdata->sex, pdata->age, pdata->score);}return 0;
}

4.栈        

        4.1概念

        栈和队列只允许在固定位置插入和删除

        表可以在任何位置插入删除

    先进后出，后进先出 
    栈顶：允许入栈出栈的一端称为栈顶
    栈底：不允许入栈和出栈的一端称为栈底
    入栈（压栈）：将数据元素放入栈顶
    出栈（弹栈）：将数据元素从栈顶位置取出

        分类：空增栈， 空减栈，满增栈，满减栈，顺序栈，链式栈

        4.2创建空增栈

//创建空增栈
stack_t *CreateSeqstack(int MAXLEN)
{stack_t *pTmpStack = NULL;pTmpStack = malloc(sizeof(stack_t));if (pTmpStack == NULL){return NULL;}pTmpStack->tLen = MAXLEN;pTmpStack->Top = 0;pTmpStack->pData = malloc(sizeof(DataType) * MAXLEN);if (pTmpStack->pData == NULL){return NULL;}return pTmpStack;
}

        4.3判断栈是否为空，是否存满

//判断栈有没有满
int IsFullSeqstack(stack_t *pStack)
{return pStack->Top == pStack->tLen ? 1 : 0;
}//判断栈是不是空
int IsEmptySeqstack(stack_t *pStack)
{return 0 == pStack->Top ? 1 : 0;
}

        4.4压栈，出栈

//进栈
int EnterSeqstack(stack_t *pStack, DataType tmpdata)
{if (IsFullSeqstack){return -1;}pStack->pData[pStack->Top] = tmpdata;pStack->Top++;return 0;
}//出栈
DataType PopSeqstack(stack_t *pStack)
{if (IsEmptySeqstack){return -1;}pStack->Top--;return pStack->pData[pStack->Top];
}

        4.5销毁栈

//销毁栈
int DestorySeqstack(stack_t **pStack)
{(*pStack)->Top = 0;free((*pStack)->pData);free(*pStack);*pStack = NULL;return 0;
}

        4.6链式栈

#include "list.h"
#include <stdio.h>
#include <stdlib.h>typedef struct data
{struct list_head naode;int pData;
}data_t;int main(void)
{struct list_head head;int i = 0;struct list_head *pTmpNode = NULL;INIT_LIST_HEAD(&head);data_t D[5] = {{{NULL, NULL}, 1},{{NULL, NULL}, 2},{{NULL, NULL}, 3},{{NULL, NULL}, 4},{{NULL, NULL}, 5}};for (i = 0; i < 5; i++){list_add(&D[i].naode, &head);}while (!list_empty(&head)){pTmpNode = head.next;printf("%d ", list_entry(pTmpNode, data_t, naode)->pData);list_del(head.next);}printf("\n");return 0;
}

5.队列

        5.1队列

        先进先出

        栈和队列只允许在固定位置插入和删除

        表可以在任何位置插入删除

这篇关于单向链表，双向链表，内核链表，栈，队列简单操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1119265。

相关文章

使用Java填充Word模板的操作指南

使用Java填充Word模板的操作指南

《使用Java填充Word模板的操作指南》本文介绍了Java填充Word模板的实现方法,包括文本、列表和复选框的填充,首先通过Word域功能设置模板变量,然后使用poi-tl、aspose-words... 目录前言一、设置word模板普通字段列表字段复选框二、代码1. 引入POM2. 模板放入项目3.代码
阅读更多...
利用Python操作Word文档页码的实际应用

利用Python操作Word文档页码的实际应用

《利用Python操作Word文档页码的实际应用》在撰写长篇文档时,经常需要将文档分成多个节,每个节都需要单独的页码,下面：本文主要介绍利用Python操作Word文档页码的相关资料,文中通过代码... 目录需求：文档详情：要求：该程序的功能是：总结需求：一次性处理24个文档的页码。文档详情：1、每个
阅读更多...
Python内存管理机制之垃圾回收与引用计数操作全过程

Python内存管理机制之垃圾回收与引用计数操作全过程

《Python内存管理机制之垃圾回收与引用计数操作全过程》SQLAlchemy是Python中最流行的ORM（对象关系映射）框架之一,它提供了高效且灵活的数据库操作方式,本文将介绍如何使用SQLAlc... 目录安装核心概念连接数据库定义数据模型创建数据库表基本CRUD操作创建数据读取数据更新数据删除数据查
阅读更多...
Go语言中json操作的实现

Go语言中json操作的实现

《Go语言中json操作的实现》本文主要介绍了Go语言中的json操作的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录 一、jsOChina编程N 与 Go 类型对应关系️ 二、基本操作：编码与解码 三、结构体标签（Struc
阅读更多...
Python实现简单封装网络请求的示例详解

Python实现简单封装网络请求的示例详解

《Python实现简单封装网络请求的示例详解》这篇文章主要为大家详细介绍了Python实现简单封装网络请求的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录安装依赖核心功能说明1. 类与方法概览2.NetHelper类初始化参数3.ApiResponse类属性与方法使用实
阅读更多...
Java 字符串操作之contains 和 substring 方法最佳实践与常见问题

Java 字符串操作之contains 和 substring 方法最佳实践与常见问题

《Java字符串操作之contains和substring方法最佳实践与常见问题》本文给大家详细介绍Java字符串操作之contains和substring方法最佳实践与常见问题,本文结合实例... 目录一、contains 方法详解1. 方法定义与语法2. 底层实现原理3. 使用示例4. 注意事项二、su
阅读更多...
Java Stream流与使用操作指南

Java Stream流与使用操作指南

《JavaStream流与使用操作指南》Stream不是数据结构,而是一种高级的数据处理工具,允许你以声明式的方式处理数据集合,类似于SQL语句操作数据库,本文给大家介绍JavaStream流与使用... 目录一、什么是stream流二、创建stream流1.单列集合创建stream流2.双列集合创建str
阅读更多...
SpringBoot集成redisson实现延时队列教程

SpringBoot集成redisson实现延时队列教程

《SpringBoot集成redisson实现延时队列教程》文章介绍了使用Redisson实现延迟队列的完整步骤,包括依赖导入、Redis配置、工具类封装、业务枚举定义、执行器实现、Bean创建、消费... 目录1、先给项目导入Redisson依赖2、配置redis3、创建 RedissonConfig 配
阅读更多...
Python正则表达式匹配和替换的操作指南

Python正则表达式匹配和替换的操作指南

《Python正则表达式匹配和替换的操作指南》正则表达式是处理文本的强大工具,Python通过re模块提供了完整的正则表达式功能,本文将通过代码示例详细介绍Python中的正则匹配和替换操作,需要的朋... 目录基础语法导入re模块基本元字符常用匹配方法1. re.match() - 从字符串开头匹配2.
阅读更多...
Java实现在Word文档中添加文本水印和图片水印的操作指南

Java实现在Word文档中添加文本水印和图片水印的操作指南

《Java实现在Word文档中添加文本水印和图片水印的操作指南》在当今数字时代,文档的自动化处理与安全防护变得尤为重要,无论是为了保护版权、推广品牌,还是为了在文档中加入特定的标识,为Word文档添加... 目录引言Spire.Doc for Java：高效Word文档处理的利器代码实战：使用Java为Wo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2