专栏首页C语言及其他语言【优秀题解】问题 1678: 算法2-18~2-19:双向循环链表

【优秀题解】问题 1678: 算法2-18~2-19:双向循环链表

解题思路:

双链表插入过程

以下介绍的是头插法

截取双向链表某一段

在p 后面插入元素 s

假如p->next指向下一个元素x

注意:先把后元素连接 再将前元素连接

第一步:(这一步千万不要倒过来 否则会出错)先把p->next元素(用x 元素代替),

x->prior指针指向x->prior=s ( p->next->prior=s)

x->next(即p->next->next)指针不需要改变

第二步:s->next=x; 到了这一步就实现了p元素与x元素的连接,就不需要再对x进行操作

第三步:p->next=s; 此时p->next不再指向x元素 第三步:p->next=s; 此时p->next不再指向x元素

第四步:s->prior=p; 最后实现了双向链表的插入与连接

双向链表的删除过程

首先先找到要删除的位置

例如p就是要删除的位置

只要将p的前后元素相连 再把p元素释放掉即可删除x

第一步:获取p的前驱元素s=p->prior;

第二步: s->next=p->next;

第三步:p->next->prior=s;

p->next=NULL

p->prior=NULL

free(p);

注意事项:使用c++提交,c提交编译不通过。也不知道是啥原因 参考代码:

#include <stdio.h>

#include <stdlib.h>

/*

解题的方法不用于题目,

插入时使用的是头插法

所以删除,输出操作与题目也不一致

*/

typedef int ElemType;

typedef struct DuLNode{

ElemType data;

struct DuLNode *next;

struct DuLNode *prior;

}DuLNode,*DuLinkList;

void Int_List (DuLinkList &L){

L=(DuLinkList)malloc(sizeof(DuLNode));

L->next=L;

L->prior=L;

}

void printf1(DuLinkList L)//输出的是也要反过来

{

DuLinkList p;

p=L;

while(p->prior!=L)

{

p=p->prior;

printf("%d ",p->data);

}

printf("\n");

}

DuLinkList DuLinkList_getELemp1(DuLinkList L,int i)//寻找删除的元素位置

{

DuLinkList p;

int j=1;

p=L->prior;

while(p!=L && j<i)

{

p=p->prior;

j++;

}

if(p==L && j<i)//位置不合法

return 0;

else

return p;

}

int LinsInsert_DuL(DuLinkList &L,int i,ElemType e)//插入操作 头插法

{

DuLinkList p,s;

p=DuLinkList_getELemp1(L,i);//获取插入位置

if(!p) return 0;//插入的位置不合法

s=(DuLinkList)malloc(sizeof(DuLNode));

if(!s) return 0;

s->data=e;

p->next->prior=s;//第一步操作

s->next=p->next;//第二步

p->next=s;//第三步

s->prior=p;//第四步

return 1;

}

int LinkListdelete_DuL( DuLinkList &L,int i)

{

DuLinkList p,s;

p=DuLinkList_getELemp1(L,i);

if(!p) return 0; //删除的位置不合法

s=p->prior;//获取删除位置的前驱元素 (第一步)

s->next=p->next;//s->next指向p的下一个元素(第二步)

p->next->prior=s;//p的上一个元素指向s(第三步)

p->next=NULL;

p->prior=NULL;

free(p);//释放内存

return 1;

}

int main (){

int a,i,e;

DuLinkList L;

Int_List(L);

while(scanf("%d",&a)!=EOF){

if(a==0)//输出

{

printf1(L);

}

else if(a==1){//插入

scanf("%d %d",&i,&e);

LinsInsert_DuL(L,i,e);

}

else if(a==2){//删除

scanf("%d",&i);

LinkListdelete_DuL(L,i);

}

}

free(L);

return 0;

} 点击“http://www.dotcpp.com/blog/9013.html”去撩原作者。

本文分享自微信公众号 - 编程范(dotcpp)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「优质题解」出圈

    https://www.dotcpp.com/oj/problem1160.html

    编程范 源代码公司
  • 【编程经验】关于链表、还有编译器

    关注我们 最近有小白来问VC6.0和其他编译器怎么下,小编回了一些,但是也是确实比较多......所以今天就不单单分享知识了,还要分享资源! ...

    编程范 源代码公司
  • 中国互联网究竟有多牛?看完惊呆了!

    来源:四川省人民检察院官方头条号 ...

    编程范 源代码公司
  • github+hexo搭建博客(二)

    背景: 在github+hexo搭建好个人博客后,会发现默认的主题不是自己喜欢的,就想去更换博客主题 更换博客主题 在github+hexo搭建博客(一)中有...

    运维小白
  • JVM性能调优监控工具jps、jstack、jmap、jhat、jstat使用详解

    JDK本身提供了很多方便的JVM性能调优监控工具,除了集成式的VisualVM和jConsole外,还有jps、jstack、jmap、jhat、jstat等小...

    IT技术小咖
  • CentOS 6 添加常用 yum 源 转

    CentOS 的官方源去掉了一些与版权有关的软件,因此想要安装这些软件或者手动下载安装,或者使用其他源. 下面我推荐常用的两个源, 这两个源基本可以满足一般服务...

    双面人
  • 全面复盘台风“山竹”应急保障

    2018年9月16日,今年第22号超强台风“山竹”经过整整13天的酝酿之后,形成了中心风力高达18级以上的巨无霸,携带着狂暴的超能量由西太平洋北上,正面侵袭粤港...

    腾讯数据中心
  • 13年5月 软考笔记整理

    虚拟存储器为了给用户提供更大的随机存储空间而采用的一种存储技术。它将内存(主存)与外存(辅存)结合使用,好像有一个容量巨大的内存储器,工作速度接近于主存,每位成...

    week
  • Java 面试知识点解析「基础知识」

    答:面向过程是一种站在过程的角度思考问题的思想,强调的是功能行为,功能的执行过程,即先干啥,后干啥。

    Java3y
  • Docker Registry v2 配置文件详解

    /etc/docker/registry/config.yml 详解。 你可以在 docker run 时通过 -e 参数设置环境变量来配置。为了避免命令的繁杂...

    康怀帅

扫码关注云+社区

领取腾讯云代金券