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

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将各种数据写入Excel表格的操作示例

使用Java将各种数据写入Excel表格的操作示例

《使用Java将各种数据写入Excel表格的操作示例》在数据处理与管理领域,Excel凭借其强大的功能和广泛的应用,成为了数据存储与展示的重要工具,在Java开发过程中,常常需要将不同类型的数据,本文... 目录前言安装免费Java库1. 写入文本、或数值到 Excel单元格2. 写入数组到 Excel表格
阅读更多...
Python中pywin32 常用窗口操作的实现

Python中pywin32 常用窗口操作的实现

《Python中pywin32常用窗口操作的实现》本文主要介绍了Python中pywin32常用窗口操作的实现,pywin32主要的作用是供Python开发者快速调用WindowsAPI的一个... 目录获取窗口句柄获取最前端窗口句柄获取指定坐标处的窗口根据窗口的完整标题匹配获取句柄根据窗口的类别匹配获取句
阅读更多...
Python位移操作和位运算的实现示例

Python位移操作和位运算的实现示例

《Python位移操作和位运算的实现示例》本文主要介绍了Python位移操作和位运算的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 位移操作1.1 左移操作 (<<)1.2 右移操作 (>>)注意事项：2. 位运算2.1
阅读更多...
快速修复一个Panic的Linux内核的技巧

快速修复一个Panic的Linux内核的技巧

《快速修复一个Panic的Linux内核的技巧》Linux系统中运行了不当的mkinitcpio操作导致内核文件不能正常工作，重启的时候，内核启动中止于Panic状态，该怎么解决这个问题呢？下面我们就... 感谢China编程(www.chinasem.cn)网友 鸢一雨音 的投稿写这篇文章是有原因的。为了配置完
阅读更多...
Python ZIP文件操作技巧详解

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技
阅读更多...
Java中字符串转时间与时间转字符串的操作详解

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间（一）使用预定义格式（二）自定义格式二、时间转字符串（一）使用预定义格式（二）自
阅读更多...
Java的栈与队列实现代码解析

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念（Stack）栈的实现代码队列（Queue）模拟实现队列(双链表实现)循环队列（循环数组
阅读更多...
Redis消息队列实现异步秒杀功能

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结
阅读更多...
Java字符串操作技巧之语法、示例与应用场景分析

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字
阅读更多...
Linux内核参数配置与验证详细指南

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数（sysctl）的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置（重启失效）3.2 永久设置（重启仍生效
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2