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

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。

相关文章

python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型，3步搞定一个应
阅读更多...
redis群集简单部署过程

redis群集简单部署过程

《redis群集简单部署过程》文章介绍了Redis,一个高性能的键值存储系统,其支持多种数据结构和命令,它还讨论了Redis的服务器端架构、数据存储和获取、协议和命令、高可用性方案、缓存机制以及监控和... 目录Redis介绍1. 基本概念2. 服务器端3. 存储和获取数据4. 协议和命令5. 高可用性6.
阅读更多...
轻松上手MYSQL之JSON函数实现高效数据查询与操作

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》：本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE
阅读更多...
JAVA调用Deepseek的api完成基本对话简单代码示例

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》：本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先，从DeepSeek平台获取API密钥，用于身份验证。添加HTTP客户端依赖使用Jav
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
使用C++实现单链表的操作与实践

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...
Python利用自带模块实现屏幕像素高效操作

Python利用自带模块实现屏幕像素高效操作

《Python利用自带模块实现屏幕像素高效操作》这篇文章主要为大家详细介绍了Python如何利用自带模块实现屏幕像素高效操作,文中的示例代码讲解详,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、获取屏幕放缩比例2、获取屏幕指定坐标处像素颜色3、一个简单的使用案例4、总结1、获取屏幕放缩比例from
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2