凌阳教育的个人空间 https://blog.eetop.cn/204849 [收藏] [复制] [分享] [RSS]

空间首页 动态 记录 日志 相册 主题 分享 留言板 个人资料

日志

双向链表

已有 434 次阅读| 2016-3-21 17:42

循环链表的链式存储结构的结点只有一个指示直接后继的指针域,由此,从某个结点只能顺指针往后寻常其他结点。若要寻查结点的直接前驱,则需要从表头指针出发。换句话说,在单链表中,NextElem的执行时间为O1),而PriorElem的执行时间为On)。为克服单链表这种单向性的缺点,可利用双向链表。

顾名思义,在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前驱,在C语言中可描述如下:

//---------------------线性表的双向链表存储结构------------------------

typedef struct        DuLNode{

       ElemType                     data;

       struct DuLNode             *prior;

       struct DuLNode             *next;

}DuLNode,  *DuLinkList

和单链表的循环表类似,双向链表也可以有循环表,如图c所示,链表中存有两个环,图b所示为只有一个表头结点的空表。

 

在双向链表中,若d为指向表中某一结点的指针(若dDuLinkList型变量),则显然有

d>next->prior=d->prior->next=d

这个表示式恰当地反应了这种结构的特性。

在双向链表中,有些操作如:ListLengthGetElemLocalElem等仅需涉及一个方向的指针,则它们的算法描述和线性链表的操作相同,但在插入、删除时有很大的不同,在双向链表中需同时修改两个方向上的指针,图分别显示了删除和插入结点指针修改的情况。它们的算法分别如算法所示,两者的时间复杂度均为On)。

 Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){

//在带头结点的双链循环线性表L中第i个位置之前插入元素e

//i的合法值为1i≤表长+1.

if(!(p=GetElemP_DuL(L,i))) //L中确定插入位置指针p

return  ERROR;                         //i等于表长加1时,p指向头结点;i大于表长加1时,

                                                 //p=NULL

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))return ERROR;

s->data =e;

s->prior =p->prior ; p->prior->next=s;

s->next=p;      p->prior =s;

return OK;

}//ListInsert_DuL

Status ListDelete_DuL(DuLinkList &L,int i,ElemType e){

//删除带头结点的双链循环线性表L的第i个元素,i的合法值为1i≤表长

if(!(p=GetElemP_DuL(L,i))) //L中确定第i个元素的位置指针p

return  ERROR;                         //p=NULL,即第i个元素不存在

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))return ERROR;

e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);return OK;

}//ListDelete_DuL

凌阳教育,全国唯一一家原厂式嵌入式培训机构,专业从事嵌入式人才培训13年,最近新开课程信息安全工程师培训,想了解更多嵌入式资料下载或者是凌阳教育的动态,请访问凌阳教育官网www.sunplusedu.com


点赞

评论 (0 个评论)

facelist

您需要登录后才可以评论 登录 | 注册

  • 关注TA
  • 加好友
  • 联系TA
  • 0

    周排名
  • 0

    月排名
  • 0

    总排名
  • 0

    关注
  • 1

    粉丝
  • 0

    好友
  • 1

    获赞
  • 3

    评论
  • 3815

    访问数
关闭

站长推荐 上一条 /1 下一条

小黑屋| 关于我们| 联系我们| 在线咨询| 隐私声明| EETOP 创芯网
( 京ICP备:10050787号 京公网安备:11010502037710 )

GMT+8, 2024-3-29 21:21 , Processed in 0.013460 second(s), 6 queries , Gzip On, Redis On.

eetop公众号 创芯大讲堂 创芯人才网
返回顶部