专业做网站全包,提高网站打开速度,ai做网站 如何切图,品牌运营管理有限公司文章目录 【 1. 基本原理 】【 2. 双向链表的 创建 】实例 - 输出双向链表 【 3. 双向链表 添加节点 】【 4. 双向链表 删除节点 】【 5. 双向链表查找节点 】【 7. 双向链表更改节点 】【 8. 实例 - 双向链表的 增删查改 】 【 1. 基本原理 】
表中各节点中都只包含一个指针游标且都统一指向直接后继节点通常称这类链表为 单向链表或单链表。背景 如果算法中需要大量地找某指定结点的前趋结点使用单链表无疑是灾难性的因为单链表更适合 “从前往后” 找而 “从后往前” 找并不是它的强项。为了能够高效率解决类似的问题引入双向链表简称双链表。从名字上理解 双向链表即链表是 “双向” 的双向指的是各节点之间的逻辑关系是双向的 每个节点存在前后两个指针分别指向前驱节点和后继节点但通常头指针只设置一个除非实际情况需要。 双向链表中各节点包含以下 3 部分信息 前指针域用于指向当前节点的直接前驱节点数据域用于存储数据元素。后指针域用于指向当前节点的直接后继节点 双链表的节点结构用 C 语言实现为
typedef struct line
{struct line * prior; //指向直接前趋int data;struct line * next; //指向直接后继
}line;【 2. 双向链表的 创建 】
同单链表相比双链表仅是各节点多了一个用于指向直接前驱的指针域。因此我们可以在单链表的基础轻松实现对双链表的创建。需要注意的是与单链表不同双链表创建过程中每创建一个新节点都要与其前驱节点建立两次联系分别是 将新节点的 prior 指针指向直接前驱节点将直接前驱节点的 next 指针指向新节点 创建双向链表的 C 语言实现代码
line* initLine(line * head)
{head(line*)malloc(sizeof(line));//创建链表第一个结点首元结点head-priorNULL;head-nextNULL;head-data1;line * listhead;for (int i2; i3; i) {//创建并初始化一个新结点line * body(line*)malloc(sizeof(line));body-priorNULL;body-nextNULL;body-datai;list-nextbody;//直接前趋结点的next指针指向新结点body-priorlist;//新结点指向直接前趋结点listlist-next;}return head;
}实例 - 输出双向链表
#include stdio.h
#include stdlib.h//双向链表结构体
typedef struct line
{struct line* prior;int data;struct line* next;
}line;//双链表的创建函数
line* initLine(line* head)
{//创建一个首元节点链表的头指针为headhead (line*)malloc(sizeof(line));//对节点进行初始化head-prior NULL;head-next NULL;head-data 1;//声明一个指向首元节点的指针方便后期向链表中添加新创建的节点line* list head;for (int i 2; i 5; i){//创建新的节点并初始化line* body (line*)malloc(sizeof(line));body-prior NULL;body-next NULL;body-data i;//新节点与链表最后一个节点建立关系list-next body;body-prior list;//list永远指向链表中最后一个节点list list-next;}//返回新创建的链表return head;
}//输出双链表的函数
void display(line* head)
{line* temp head;while (temp){//如果该节点无后继节点说明此节点是链表的最后一个节点if (temp-next NULL)printf(%d\n, temp-data);elseprintf(%d - , temp-data);temp temp-next;}
}int main()
{//创建一个头指针line* head NULL;//调用链表创建函数head initLine(head);//输出创建好的链表display(head);//显示双链表的优点printf(链表中第 4 个节点的直接前驱是%d, head-next-next-next-prior-data);return 0;
}【 3. 双向链表 添加节点 】
添加至表头 将新数据元素添加到表头只需要将该元素与表头元素建立双层逻辑关系即可。换句话说假设新元素节点为 temp表头节点为 head则需要做以下 2 步操作即可 新节点与头节点连接temp-nexthead; head-priortemp;head指向新节点将 head 移至 temp重新指向新的表头 例如将新元素 7 添加至双链表的表头则实现过程如图 2 所示 添加至表的中间位置 同单链表添加数据类似双向链表中间位置添加数据需要经过以下 2 个步骤如下图所示 新节点先与其直接后继节点建立双层逻辑关系新节点的直接前驱节点与之建立双层逻辑关系 添加至表尾 与添加到表头是一个道理更简单实现过程如下 找到双链表中最后一个节点 让新节点与最后一个节点进行双层逻辑关系 C 语言实现
line * insertLine(line * head,int data,int add)
{//新建数据域为data的结点line * temp(line*)malloc(sizeof(line));temp-datadata;temp-priorNULL;temp-nextNULL;//插入到链表头要特殊考虑if (add1) {temp-nexthead;head-priortemp;headtemp;}else{line * bodyhead;//找到要插入位置的前一个结点bodyfor (int i1; iadd-1; i) {bodybody-next;}//判断条件为真说明插入位置为链表尾if (body-nextNULL) {body-nexttemp;temp-priorbody;}else{body-next-priortemp;//新节点后1个节点的前向指针指向新节点temp-nextbody-next;//新节点的后向指针指向后一个节点body-nexttemp;//新节点前1个节点的后向指针指向新节点temp-priorbody;//新节点的前向指针指向前一个节点}}return head;
}【 4. 双向链表 删除节点 】
-双链表删除结点时只需遍历链表找到要删除的结点然后将该节点从表中摘除即可。
删除元素 2 的操作过程如下图所示 双向链表删除节点的 C 语言实现代码如下
//删除结点的函数data为要删除结点的数据域的值
line * delLine(line * head,int data)
{line * temphead;//遍历链表while (temp) {//判断当前结点中数据域和data是否相等若相等摘除该结点if (temp-datadata) {temp-prior-nexttemp-next;temp-next-priortemp-prior;free(temp);return head;}temptemp-next;}printf(链表中无该数据元素);return head;
}【 5. 双向链表查找节点 】
通常双向链表同单链表一样都仅有一个头指针。因此双链表查找指定元素 的实现同单链表类似都是 从表头依次遍历表中元素。C 语言实现代码为
//head为原双链表elem表示被查找元素
int selectElem(line * head,int elem)
{
//新建一个指针t初始化为头指针 headline * thead;int i1;while (t) {if (t-dataelem) {return i;}i;tt-next;}//程序执行至此处表示查找失败return -1;
}【 7. 双向链表更改节点 】
更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是通过遍历找到存储有该数据元素的结点直接更改其数据域即可。实现此操作的 C 语言实现代码如下
//更新函数其中add 表示更改结点在双链表中的位置newElem 为新数据的值
line *amendElem(line * p,int add,int newElem)
{line * tempp;//遍历到被删除结点for (int i1; iadd; i) {temptemp-next;}temp-datanewElem;return p;
}【 8. 实例 - 双向链表的 增删查改 】
#include stdio.h
#include stdlib.h
//双向链表结构体
typedef struct line
{struct line* prior;int data;struct line* next;
}line;
//双链表的创建
line* initLine(line* head);
//双链表插入元素add表示插入位置
line* insertLine(line* head, int data, int add);
//双链表删除指定元素
line* delLine(line* head, int data);
//双链表中查找指定元素
int selectElem(line* head, int elem);
//双链表中更改指定位置节点中存储的数据add表示更改位置
line* amendElem(line* p, int add, int newElem);
//输出双链表的实现函数
void display(line* head);int main()
{line* head NULL;//创建双链表head initLine(head);display(head);//在表中第 3 的位置插入元素 7head insertLine(head, 7, 3);display(head);//表中删除元素 2head delLine(head, 2);display(head);printf(元素 3 的位置是%d\n, selectElem(head, 3));//表中第 3 个节点中的数据改为存储 6head amendElem(head, 3, 6);display(head);return 0;
}line* initLine(line* head)
{head (line*)malloc(sizeof(line));head-prior NULL;head-next NULL;head-data 1;line* list head;for (int i 2; i 5; i) {line* body (line*)malloc(sizeof(line));body-prior NULL;body-next NULL;body-data i;list-next body;body-prior list;list list-next;}return head;
}
line* insertLine(line* head, int data, int add)
{//新建数据域为data的结点line* temp (line*)malloc(sizeof(line));temp-data data;temp-prior NULL;temp-next NULL;//插入到链表头要特殊考虑if (add 1) {temp-next head;head-prior temp;head temp;}else {line* body head;//找到要插入位置的前一个结点for (int i 1; i add - 1; i) {body body-next;}//判断条件为真说明插入位置为链表尾if (body-next NULL) {body-next temp;temp-prior body;}else {body-next-prior temp;temp-next body-next;body-next temp;temp-prior body;}}return head;
}
line* delLine(line* head, int data)
{line* temp head;//遍历链表while (temp) {//判断当前结点中数据域和data是否相等若相等摘除该结点if (temp-data data) {temp-prior-next temp-next;temp-next-prior temp-prior;free(temp);return head;}temp temp-next;}printf(链表中无该数据元素);return head;
}
//head为原双链表elem表示被查找元素
int selectElem(line* head, int elem)
{//新建一个指针t初始化为头指针 headline* t head;int i 1;while (t) {if (t-data elem) {return i;}i;t t-next;}//程序执行至此处表示查找失败return -1;
}
//更新函数其中add 表示更改结点在双链表中的位置newElem 为新数据的值
line* amendElem(line* p, int add, int newElem)
{line* temp p;//遍历到被删除结点for (int i 1; i add; i) {temp temp-next;}temp-data newElem;return p;
}
//输出链表的功能函数
void display(line* head)
{line* temp head;while (temp) {if (temp-next NULL) {printf(%d\n, temp-data);}else {printf(%d-, temp-data);}temp temp-next;}
} 文章转载自： http://www.morning.dzqyn.cn.gov.cn.dzqyn.cn http://www.morning.ljzqb.cn.gov.cn.ljzqb.cn http://www.morning.wslr.cn.gov.cn.wslr.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.nqyzg.cn.gov.cn.nqyzg.cn http://www.morning.kyctc.cn.gov.cn.kyctc.cn http://www.morning.mbmtn.cn.gov.cn.mbmtn.cn http://www.morning.ldspj.cn.gov.cn.ldspj.cn http://www.morning.wxfgg.cn.gov.cn.wxfgg.cn http://www.morning.rkqqf.cn.gov.cn.rkqqf.cn http://www.morning.kbntl.cn.gov.cn.kbntl.cn http://www.morning.pmptm.cn.gov.cn.pmptm.cn http://www.morning.cbchz.cn.gov.cn.cbchz.cn http://www.morning.bzlgb.cn.gov.cn.bzlgb.cn http://www.morning.jbtlf.cn.gov.cn.jbtlf.cn http://www.morning.mlbn.cn.gov.cn.mlbn.cn http://www.morning.nckjk.cn.gov.cn.nckjk.cn http://www.morning.gydth.cn.gov.cn.gydth.cn http://www.morning.mqxrx.cn.gov.cn.mqxrx.cn http://www.morning.lxkhx.cn.gov.cn.lxkhx.cn http://www.morning.bpptt.cn.gov.cn.bpptt.cn http://www.morning.jwskq.cn.gov.cn.jwskq.cn http://www.morning.yydeq.cn.gov.cn.yydeq.cn http://www.morning.smrty.cn.gov.cn.smrty.cn http://www.morning.slfmp.cn.gov.cn.slfmp.cn http://www.morning.pftjj.cn.gov.cn.pftjj.cn http://www.morning.mbmtn.cn.gov.cn.mbmtn.cn http://www.morning.rdtq.cn.gov.cn.rdtq.cn http://www.morning.ktxd.cn.gov.cn.ktxd.cn http://www.morning.qxwwg.cn.gov.cn.qxwwg.cn http://www.morning.grfhd.cn.gov.cn.grfhd.cn http://www.morning.ffbp.cn.gov.cn.ffbp.cn http://www.morning.cwcdr.cn.gov.cn.cwcdr.cn http://www.morning.rpjr.cn.gov.cn.rpjr.cn http://www.morning.mznqz.cn.gov.cn.mznqz.cn http://www.morning.mnygn.cn.gov.cn.mnygn.cn http://www.morning.tsflw.cn.gov.cn.tsflw.cn http://www.morning.zcwwb.cn.gov.cn.zcwwb.cn http://www.morning.sfwcb.cn.gov.cn.sfwcb.cn http://www.morning.tlyms.cn.gov.cn.tlyms.cn http://www.morning.rhchr.cn.gov.cn.rhchr.cn http://www.morning.kgcss.cn.gov.cn.kgcss.cn http://www.morning.ckwxs.cn.gov.cn.ckwxs.cn http://www.morning.nmngq.cn.gov.cn.nmngq.cn http://www.morning.sryyt.cn.gov.cn.sryyt.cn http://www.morning.wgkz.cn.gov.cn.wgkz.cn http://www.morning.wdrxh.cn.gov.cn.wdrxh.cn http://www.morning.jcnmy.cn.gov.cn.jcnmy.cn http://www.morning.kfldw.cn.gov.cn.kfldw.cn http://www.morning.qynnw.cn.gov.cn.qynnw.cn http://www.morning.nbrkt.cn.gov.cn.nbrkt.cn http://www.morning.fkdts.cn.gov.cn.fkdts.cn http://www.morning.ryjqh.cn.gov.cn.ryjqh.cn http://www.morning.gmztd.cn.gov.cn.gmztd.cn http://www.morning.fhqdb.cn.gov.cn.fhqdb.cn http://www.morning.grqlc.cn.gov.cn.grqlc.cn http://www.morning.fthcq.cn.gov.cn.fthcq.cn http://www.morning.fqqcn.cn.gov.cn.fqqcn.cn http://www.morning.wrtbx.cn.gov.cn.wrtbx.cn http://www.morning.wlfxn.cn.gov.cn.wlfxn.cn http://www.morning.bfhfb.cn.gov.cn.bfhfb.cn http://www.morning.lnrhk.cn.gov.cn.lnrhk.cn http://www.morning.qkqjz.cn.gov.cn.qkqjz.cn http://www.morning.kqbjy.cn.gov.cn.kqbjy.cn http://www.morning.sfcfy.cn.gov.cn.sfcfy.cn http://www.morning.ylyzk.cn.gov.cn.ylyzk.cn http://www.morning.hdrsr.cn.gov.cn.hdrsr.cn http://www.morning.gkgr.cn.gov.cn.gkgr.cn http://www.morning.dphmj.cn.gov.cn.dphmj.cn http://www.morning.sprbs.cn.gov.cn.sprbs.cn http://www.morning.yprjy.cn.gov.cn.yprjy.cn http://www.morning.gftnx.cn.gov.cn.gftnx.cn http://www.morning.jfbrt.cn.gov.cn.jfbrt.cn http://www.morning.qkwxp.cn.gov.cn.qkwxp.cn http://www.morning.tbjb.cn.gov.cn.tbjb.cn http://www.morning.dkcpt.cn.gov.cn.dkcpt.cn http://www.morning.zlmbc.cn.gov.cn.zlmbc.cn http://www.morning.nhpgm.cn.gov.cn.nhpgm.cn http://www.morning.drgmr.cn.gov.cn.drgmr.cn http://www.morning.crkhd.cn.gov.cn.crkhd.cn
