丹东电信网站备案,wordpress 重新生成,2017淘宝客网站怎么做,关键词代做排名推广大家好#xff01;今天我们来学习数据结构中的双链表。#xff08;我们这里讲解的是带头#xff08;哨兵位#xff09;双向循环链表哦~#xff09; 目录
1.双链表的概念
2. 双链表的逻辑结构
3. 双链表的定义
4. 双链表的接口实现
4.1 动态申请一个新结点
4.2 双链表… 大家好今天我们来学习数据结构中的双链表。我们这里讲解的是带头哨兵位双向循环链表哦~ 目录
1.双链表的概念
2. 双链表的逻辑结构
3. 双链表的定义
4. 双链表的接口实现
4.1 动态申请一个新结点
4.2 双链表的初始化
4.3 打印双链表
4.4 尾插数据
4.5 尾删数据
4.6 头插数据
4.7 头删数据
4.8 获得双链表的长度
4.9 查找指定数据
4.10 在指定位置之前插入数据
4.11 删除指定位置
4.12 销毁双链表
5. 双链表的完整代码
5.1 List.h
5.2 List.c
5.3 Test.c
6. 顺序表和链表的区别
7. 总结 1.双链表的概念
双链表也叫双向链表是链表的一种它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。所以从双链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。 2. 双链表的逻辑结构
我们这里以带头双向循环链表为例它的逻辑结构如下
3. 双链表的定义 typedef int LTDataType;
typedef struct ListNode
{LTDataType data; //存储的数据struct ListNode* prev; //存放前一个结点的地址struct ListNode* next; //存放后一个结点的地址
}LTNode; 使用结构体创建一个双链表。
用SLTDataType替换int方便对不同类型的数据进行修改。
用SLTNode替换struct SListNode方便简洁。
data是结点的数据域*prev用来存放前一个结点的地址前驱*next用来存放后一个结点的地址后继。 4. 双链表的接口实现
双链表的所有接口函数一览 //动态申请一个新结点
LTNode* BuyLTNode(LTDataType x);
//双链表的初始化
LTNode* LTInit();
//打印双链表
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//获得双链表的长度
int LTSize(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之前插入x
void LTInsert(LTNode* pos,LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
//销毁双链表
void LTDestroy(LTNode* phead); 这些接口函数主要实现了单链表的增删改查等功能接下来我们一一实现这些函数
4.1 动态申请一个新结点
我们每次给链表插入数据时都需要动态开辟空间申请结点。所以我们将这个过程封装成函数方便后续使用。
我们使用malloc()函数动态开辟一块空间表示新结点newnodemalloc函数返回一个void*类型的指针指向分配的内存块的起始位置。如果内存分配失败则返回一个空指针NULL。
所以我们要判断newnode是否为空指针NULL如果newnode是空指针则用perror()函数打印相关错误并用exit(-1)退出程序。
如果newnode不为空我们就用newnode的data赋值。又因为这是新开辟的结点我们暂时将newnode的prev和newnode的next指向空。 //动态申请一个新结点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode (LTNode *)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc failed);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
} 4.2 双链表的初始化
双链表的初始化就是给双链表创建一个头结点。因为头结点哨兵位不存储有效数据所以我们将头结点的data赋值为-1,同时让头结点的prev和next都指向自己最后返回头结点的地址。 //双链表的初始化
LTNode* LTInit()
{LTNode* phead BuyLTNode(-1);phead-next phead;phead-prev phead;return phead;
} 4.3 打印双链表
遍历双链表依次打印双链表的元素。
我们定义一个结构体类型的指针cur让cur一开始指向头结点的下一个结点也就是哨兵位后面的一个结点。当cur不为空时输出cur指向的结点的值cur-data然后让cur指向下一个结点curcur-next依次进行直到cur为头结点时停止因为最后一个结点的next指针指向头结点。 //打印双链表
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(phead);while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
} 4.4 尾插数据
尾插就是创建一个新结点newnode然后将newnode插入到尾结点tail的后面让tail的next指向newnode,让newnode的prev指向tail让newnode的next指向头结点phead头结点phead的prev指向newnode。建立这样的连接后尾插就完成了
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyLTNode(x);tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
} 4.5 尾删数据
尾删我们需要定义一个tailPrev存储尾结点tail的前一个结点也就是tail-prev再free掉tail让tailPrev的next指向头结点phead让头结点phead的prev指向tailPrev。
这里要注意的是如果链表为空phead-nextphead我们就不能进行尾删所以我们要用assert()进行断言。
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next! phead); //链表为空的情况LTNode* tail phead-prev;LTNode* tailPrev tail-prev;free(tail);tailPrev-next phead;phead-prev tailPrev;
} 4.6 头插数据
所谓头插就是在双链表的头结点哨兵位后面的一个结点前插入数据。我们调用BuyLTNode()函数创建一个新结点newnode让newnode的next指向头结点phead的next头结点phead的next的prev指向newnode让头结点phead的next指向newnodenewnode的prev指向phead。
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyLTNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;
} 4.7 头删数据
头删就是将头结点哨兵位后面的那一个结点删除。这里我们可以用first存储头结点哨兵位后面的第一个结点用second存储哨兵位后面的第二个结点。然后free掉first。将头结点phead的next指向second而second的prev指向头结点。
这里也要注意如果链表为空phead-nextphead我们就不能进行头删所以我们要用assert()进行断言。
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead); //链表为空的情况LTNode* first phead-next;LTNode* second phead-next-next;free(first);phead-next second;second-prev phead;
} 4.8 获得双链表的长度
要获得双链表的长度我们就使用cur从头结点哨兵位的后一个结点开始遍历直到cur等于头结点phead时停止。 //获得双链表的长度
int LTSize(LTNode* phead)
{assert(phead);int size 0;LTNode* cur phead-next;while (cur ! phead){size;cur cur-next;}return size;
} 4.9 查找指定数据
定义一个结构体指针cur让cur首先指向头结点哨兵位的下一个结点然后遍历双链表如果找到了指定数据cur-datax)就直接返回cur。否则让cur指向cur-next直到cur为头结点时停止。如果没有提前退出完整完成了整个循环也就是没有找到指定数据就返回空指针NULL。 //查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x)return cur;cur cur-next;}return NULL;
} 4.10 在指定位置之前插入数据
我们调用BuyLTNode()函数创建一个新结点newnode定义一个结构体指针posPrev用来保存pos位置的前一个位置让posPrev的next指向newnodenewnode的prev指向posPrev让newnode的next指向pospos的prev指向newnode。
既然我们要在指定位置之前插入数据那么这个指定位置必须是存在的所以我们要使用assert()断言。
//在pos位置之前插入x
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev pos-prev;LTNode* newnode BuyLTNode(x);posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;
} 4.11 删除指定位置
我们要删除指定位置可以定义一个结构体指针posPrev保存要删除位置的前一个位置定义一个结构体指针posNext保存要删除位置的后一个位置。然后free掉pos让posPrev的next指向posNext让posNext的prev指向posPrev。
既然要删除指定位置那么这个指定位置也必须是存在的这里也同样要用assert()断言。
//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev pos-prev;LTNode* posNext pos-next;free(pos);posPrev-next posNext;posNext-prev posPrev;
} 4.12 销毁双链表
我们先让cur指向头结点哨兵位的下一个结点然后遍历双链表定义一个结构体指针next用来保存遍历时每一个结点的后面一个结点依次free每个结点然后让cur指向next直到cur指向头结点时停止。
最后将头结点哨兵位phead释放。 //销毁双链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);
}5. 双链表的完整代码
5.1 List.h #pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int LTDataType;
typedef struct ListNode
{LTDataType data; //存储的数据struct ListNode* prev; //指向前一个结点的指针struct ListNode* next; //指向后一个结点的指针
}LTNode;//动态申请一个新结点
LTNode* BuyLTNode(LTDataType x);
//双链表的初始化
LTNode* LTInit();
//打印双链表
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//获得双链表的长度
int LTSize(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之前插入x
void LTInsert(LTNode* pos,LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
//销毁双链表
void LTDestroy(LTNode* phead);5.2 List.c #define _CRT_SECURE_NO_WARNINGS 1
#includeList.h//动态申请一个新结点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode (LTNode *)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc failed);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}//双链表的初始化
LTNode* LTInit()
{LTNode* phead BuyLTNode(-1);phead-next phead;phead-prev phead;return phead;
}//打印双链表
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(phead);while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyLTNode(x);tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next! phead); //链表为空的情况LTNode* tail phead-prev;LTNode* tailPrev tail-prev;free(tail);tailPrev-next phead;phead-prev tailPrev;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyLTNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead); //链表为空的情况LTNode* first phead-next;LTNode* second phead-next-next;free(first);phead-next second;second-prev phead;
}//获得双链表的长度
int LTSize(LTNode* phead)
{assert(phead);int size 0;LTNode* cur phead-next;while (cur ! phead){size;cur cur-next;}return size;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x)return cur;cur cur-next;}return NULL;
}//在pos位置之前插入x
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev pos-prev;LTNode* newnode BuyLTNode(x);posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;
}//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev pos-prev;LTNode* posNext pos-next;free(pos);posPrev-next posNext;posNext-prev posPrev;
}//销毁双链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);
}5.3 Test.c #define _CRT_SECURE_NO_WARNINGS 1
#includeList.hvoid TestList()
{LTNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPushFront(plist, 10);LTPushBack(plist, 10);LTPrint(plist);LTPopBack(plist);LTPopFront(plist);LTPrint(plist);LTPushFront(plist, 10);LTPushFront(plist, 20);LTPushFront(plist, 30);LTPushFront(plist, 40);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTDestroy(plist);plist NULL;
} 6. 顺序表和链表的区别
存储器层次结构
顺序表
优点下标随机访问cpu高速缓存命中率高
缺点头部和中间插入删除效率低扩容有一定程度性能消耗可能存在一定程度的空间浪费。 链表
优点可以任意位置插入删除复杂度O(1)能够按需申请释放。
缺点不支持下标随机访问。
7. 总结
到这里我们就用C语言实现了数据结构中的双链表。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处可以在评论区留言。如果喜欢我的文章可以点赞收藏哦
文章转载自： http://www.morning.lcplz.cn.gov.cn.lcplz.cn http://www.morning.lsnbx.cn.gov.cn.lsnbx.cn http://www.morning.lgtzd.cn.gov.cn.lgtzd.cn http://www.morning.rbylq.cn.gov.cn.rbylq.cn http://www.morning.hbkkc.cn.gov.cn.hbkkc.cn http://www.morning.mzcrs.cn.gov.cn.mzcrs.cn http://www.morning.pwzzk.cn.gov.cn.pwzzk.cn http://www.morning.qfkdt.cn.gov.cn.qfkdt.cn http://www.morning.xqgfy.cn.gov.cn.xqgfy.cn http://www.morning.slmbg.cn.gov.cn.slmbg.cn http://www.morning.mooncore.cn.gov.cn.mooncore.cn http://www.morning.tzlfc.cn.gov.cn.tzlfc.cn http://www.morning.qxkjy.cn.gov.cn.qxkjy.cn http://www.morning.jtkfm.cn.gov.cn.jtkfm.cn http://www.morning.juju8.cn.gov.cn.juju8.cn http://www.morning.lmrcq.cn.gov.cn.lmrcq.cn http://www.morning.lpcct.cn.gov.cn.lpcct.cn http://www.morning.kdjtt.cn.gov.cn.kdjtt.cn http://www.morning.ygkq.cn.gov.cn.ygkq.cn http://www.morning.hclqy.cn.gov.cn.hclqy.cn http://www.morning.wtlyr.cn.gov.cn.wtlyr.cn http://www.morning.srwny.cn.gov.cn.srwny.cn http://www.morning.pmrlt.cn.gov.cn.pmrlt.cn http://www.morning.qphdp.cn.gov.cn.qphdp.cn http://www.morning.ymhjb.cn.gov.cn.ymhjb.cn http://www.morning.bhjyh.cn.gov.cn.bhjyh.cn http://www.morning.fwkpp.cn.gov.cn.fwkpp.cn http://www.morning.yhtnr.cn.gov.cn.yhtnr.cn http://www.morning.gydsg.cn.gov.cn.gydsg.cn http://www.morning.qcdtzk.cn.gov.cn.qcdtzk.cn http://www.morning.lgnz.cn.gov.cn.lgnz.cn http://www.morning.ydxwj.cn.gov.cn.ydxwj.cn http://www.morning.youprogrammer.cn.gov.cn.youprogrammer.cn http://www.morning.wfzdh.cn.gov.cn.wfzdh.cn http://www.morning.rwmq.cn.gov.cn.rwmq.cn http://www.morning.nckzt.cn.gov.cn.nckzt.cn http://www.morning.bykqg.cn.gov.cn.bykqg.cn http://www.morning.hjjkz.cn.gov.cn.hjjkz.cn http://www.morning.hbqhz.cn.gov.cn.hbqhz.cn http://www.morning.xfmzk.cn.gov.cn.xfmzk.cn http://www.morning.ylqb8.cn.gov.cn.ylqb8.cn http://www.morning.bzbq.cn.gov.cn.bzbq.cn http://www.morning.xflwq.cn.gov.cn.xflwq.cn http://www.morning.pdmml.cn.gov.cn.pdmml.cn http://www.morning.stpkz.cn.gov.cn.stpkz.cn http://www.morning.pycpt.cn.gov.cn.pycpt.cn http://www.morning.hwsgk.cn.gov.cn.hwsgk.cn http://www.morning.lwrcg.cn.gov.cn.lwrcg.cn http://www.morning.paoers.com.gov.cn.paoers.com http://www.morning.zmwd.cn.gov.cn.zmwd.cn http://www.morning.mhpkz.cn.gov.cn.mhpkz.cn http://www.morning.mrxqd.cn.gov.cn.mrxqd.cn http://www.morning.xtdms.com.gov.cn.xtdms.com http://www.morning.cszbj.cn.gov.cn.cszbj.cn http://www.morning.xlbyx.cn.gov.cn.xlbyx.cn http://www.morning.ksbmx.cn.gov.cn.ksbmx.cn http://www.morning.lbhck.cn.gov.cn.lbhck.cn http://www.morning.fldrg.cn.gov.cn.fldrg.cn http://www.morning.zypnt.cn.gov.cn.zypnt.cn http://www.morning.dyzbt.cn.gov.cn.dyzbt.cn http://www.morning.csnch.cn.gov.cn.csnch.cn http://www.morning.wbnsf.cn.gov.cn.wbnsf.cn http://www.morning.mngh.cn.gov.cn.mngh.cn http://www.morning.jyjqh.cn.gov.cn.jyjqh.cn http://www.morning.pwwdp.cn.gov.cn.pwwdp.cn http://www.morning.jglqn.cn.gov.cn.jglqn.cn http://www.morning.vibwp.cn.gov.cn.vibwp.cn http://www.morning.mzskr.cn.gov.cn.mzskr.cn http://www.morning.nsmyj.cn.gov.cn.nsmyj.cn http://www.morning.gkgb.cn.gov.cn.gkgb.cn http://www.morning.lnckq.cn.gov.cn.lnckq.cn http://www.morning.bhdtx.cn.gov.cn.bhdtx.cn http://www.morning.lrybz.cn.gov.cn.lrybz.cn http://www.morning.xzjsb.cn.gov.cn.xzjsb.cn http://www.morning.mxptg.cn.gov.cn.mxptg.cn http://www.morning.duqianw.com.gov.cn.duqianw.com http://www.morning.qnftc.cn.gov.cn.qnftc.cn http://www.morning.lbssg.cn.gov.cn.lbssg.cn http://www.morning.hrdx.cn.gov.cn.hrdx.cn http://www.morning.dpsyr.cn.gov.cn.dpsyr.cn
