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

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。

相关文章

Linux内核的调试（TODO）

Linux内核的调试（TODO）

（TODO）
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu2289（简单二分）

hdu2289（简单二分）

虽说是简单二分，但是我还是wa死了  题意：已知圆台的体积，求高度 首先要知道圆台体积怎么求：设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
内核启动时减少log的方式

内核启动时减少log的方式

内核引导选项 内核引导选项大体上可以分为两类：一类与设备无关、另一类与设备有关。与设备有关的引导选项多如牛毛，需要你自己阅读内核中的相应驱动程序源码以获取其能够接受的引导选项。比如，如果你想知道可以向 AHA1542 SCSI 驱动程序传递哪些引导选项，那么就查看 drivers/scsi/aha1542.c 文件，一般在前面 100 行注释里就可以找到所接受的引导选项说明。大多数选项是通过"_
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
uva 10387 Billiard（简单几何）

uva 10387 Billiard（简单几何）

题意是一个球从矩形的中点出发，告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间，求小球出发时的角度和小球的速度。 简单的几何问题，小球每与竖边碰撞一次，向右扩展一个相同的矩形；每与横边碰撞一次，向上扩展一个相同的矩形。 可以发现，扩展矩形的路径和在当前矩形中的每一段路径相同，当小球回到出发点时，一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直
阅读更多...
poj 1113 凸包+简单几何计算

poj 1113 凸包+简单几何计算

题意： 给N个平面上的点，现在要在离点外L米处建城墙，使得城墙把所有点都包含进去且城墙的长度最短。 解析： 韬哥出的某次训练赛上A出的第一道计算几何，算是大水题吧。 用convexhull算法把凸包求出来，然后加加减减就A了。 计算见下图： 好久没玩画图了啊好开心。 代码： #include <iostream>#include <cstdio>#inclu
阅读更多...
uva 10130 简单背包

uva 10130 简单背包

题意： 背包和 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2