分享内容循环链表双向链表操作双向链表虚拟内存空间进程的虚拟内存空间通常分为两部分:用户空间:这是普通程序可以访问的内存区域,包括代码段、数据区、栈区、堆区等。内核空间:这是操作系统内核专用的内存区域,普通程序无法直接访问。内核空间用于存储内核代码、内核数据结构以及驱动程序等。用户空间和内核空间的划分是为了保护内核的稳定性,防止用户程序直接操作内核数据。循环链表上节课学习的链表也称为单向链表。单向链表的尾节点指针指向空地址NULL。如果把尾节点指针是指向链表的头节点,就得到了循环链表(也叫环形链表)循环链表的突现循环链表的创建步骤和单向链表相同①定义节点structnode{intdata;node*next;}②声明、初始化节点变量node a{1,NULL};node b{2,NULL};node c{3,NULL};③ 构建节点之间的关系,建立循环a.nextb;b.nextc;c.nexta;和单向链表的唯一区别在于要把尾节点指针指向头节点循环链表-练习循环链表与单链表相比,最大的区别在于?BA、循环链表的头节点存储了链表的长度信息。B、循环链表的最后一个节点的指针指向头节点。C、循环链表只能单向遍历。D、循环链表的头节点不存储数据。循环链表的遍历在循环链表中,可以从任意节点出发进行(正向)遍历。遍历结束的条件是回到最初出发的节点。node*Pb;do{coutP-data ;PP-next;}while(P!b);coutendl;循环链表的插入、删除在循环链表中插入、删除节点和单向链表相同。除了以下情况:①循环链表初始为空,插入一个节点。这个节点的next指针需要指向它自己。②要删除的是循环链表中唯一的节点。这个节点的next指针指向NULL即可。循环链表的应用● 循环链表由于其环形结构的特点,在需要模拟环形顺序、频繁插入和删除节点的场景中具有独特的优势。● 常见的应用包括约瑟夫环问题、环形队列、多线程调度、音乐播放列表和游戏角色轮换等。循环链表-练习11、在不为空的循环链表中插入一个新节点时,以下说法正确的是?BA、必须找到链表的头节点才能插入。B、可以在任意已知节点后插入新节点,无需找到头节点。C、插入操作的时间复杂度为O(n)。D、插入操作必须从头节点开始遍历。解析:在循环链表中,插入一个新节点时,只需要找到一个已知节点,然后在该节点后插入新节点即可,无需找到头节点。选项A和D错误;选项c错误,和单向链表一样,插入操作的时间复杂度为O(1)。2、在至少有2个节点的循环链表中,如果要删除一个节点,以下步骤正确的是?BA、只需要将该节点的指针指向NULL即可。B、需要找到该节点的前驱节点,然后调整指针。C、只需要将该节点的指针指向下一个节点即可。D、需要重新调整整个链表的指针。解析:和单向链表一样,在循环链表中,删除一个节点需要找到该节点的前驱节点,然后将前驱节点的指针指向被删除节点的下一个节点。选项A和c都忽略了前驱节点的调整;双向链表单向链表,每个节点只能访问后继节点。有时候只知每个元素后面的元素是不够的,还需要知道前面的元素是什么。在单向链表的每个节点添加一个指向前驱节点的指针,就得到双向链表。单向链表变成双向链表只需要两步:1 每个节点添加 prev指针2 prev指针指向前一个节点建立双向链表1定义双向链表的节点(结构体)structnode{intdata;// 数据node*next;// 指向后继节点的指针node*prev;// 指向前驱节点的指针}创建节点node a{1,NULL,NULL};node b{2,NULL,NULL};node c{3,NULL,NULL};通过指针实现双向链接a.nextb;b.nextc;连接后继节点 c.prevb;b.preva;连接前驱节点每个节点都可以访问前驱节点和后继节点遍历双向链表正向遍历:node*Pa;从头节点开始while(P!NULL){直到后继节点为空 coutP-data ;PP-next;找后继节点}反向遍历:node*PC;从尾节点开始while(P!NULL){直到前驱节点为空 coutP-data ;PP-prev;找前驱节点找前驱节点}与单向链表相比● 双向链表的节点可以方便的访问前驱(前一个)节点和后继节点。● 双向链表可以双向遍历(单向链表只能单向遍历)。● 每个节点增加了一个指针,所以双向链表内存占用比单链表多。适用场景● 如果你的应用场景主要集中在单向顺序处理数据,且对内存占用敏感,单向链表是更好的选择。● 如果你需要频繁双向遍历数据,或者需要快速定位节点的前驱和后继,双向链表更适合。双向链表(插八节点)插入节点分:在双向链表的头部、中间、尾部插入节点在头部插入(e插入到a前面)2. 在中间插入新节点(e插入到a后面)3. 在尾部插入新节点(e插入到c后面)插入节点-练习1【真题】以下哪组操作能完成在双向链表中,在p指向的节点之后插入s指向的节点。(其中,next为节点的直接后继,prev为节点的直接前驱)DAp-next-prev s;s-prev p;p-next s;s-next p-next;Bp-next-prev s;p-next s;s-prev p;s-next p-next;C,s-prev p;s-next p-next;p-next s;p-next-prev s;D.s-next p-next;p-next-prev s;s-prev p;p-next s;2、【真题】在一个双向链表中,p指向链表中的一个节点,s指向一待插入节点,现要求在p之前插入s,则正确的操作是?DA,p-prev s;s-next p;p-prev-next s;s-prev p-prev;B.s-prev p-prev;p-prev-next s;s-next p;p-prev s-next;C.s-next p;p-next s;p-prev-next s;s-next p;D.s-prev p-prev;p-prev-next s;s-next p;p-prev s;双向链表(删除节点)删除节点分:删除头节点、删除中间节点、删除尾节点删除头节点a2. 删除中间节点b3. 删除尾节点c删除节点-练习【真题】设p指向双向链表中的一个节点,它的左右节点均为非空。现要求删除节点p,则下列语句序列中不正确的是?DA,p-prev-next p-next;p-prev-next-prev p-prev;B,p-prev-next p-next;p-next-prev p-prev;C.p-next-prev p-prev;p-next-prev-next p-next;D,p-next-prev p-next;p-prev-next p-prev;倒背如流乐乐想要编写一个程序,实现持续输入数字,直到输入数字0时停止。在输入结束后,需要将输入的数字按顺序从头到尾和从尾到头各背诵一次。【输入格式】一行包含多个整数数字,其中最后一个数字为0,每个整数的值均小于2^31。【输出格式】两行,第一行将按照正序输出这些数字,第二行倒序输出这些数字,数字之间用空格分隔。【输入样例】1 3 3 1 4 6 2 0【输出样例】1 3 3 1 4 6 22 6 4 1 3 3 1题目要求正序、倒序输出,推荐使用双向链表,方便双向遍历structnode{intdata;// 数据node*next;// 指向后继节点的指针node*prev;// 指向前驱节点的指针}正序、倒序输出需要知道头节点和尾节点在哪。node *head, *tail;创建节点的两种方式完整代码#includeiostreamusingnamespacestd;structnode{intdata;// 数据node*next;// 指向后继节点的指针node*prev;// 指向前驱节点的指针}intmain(){intn;cinn;//1、读入第一个数,创建第一个节点,头指针指向这个节点node*headnewnode;//动态分配内存head-datan;//新结点的数据head-prevhead-nextNULL;//初始化指针// 2、重复插入新节点直到读到onode*phead;//新节点总是插入p后一个位置while(1){cinn;if(n0)break;//读入的数据为0时,停止输入数据node*snewnode;//分配新结点ss-datan;// 新结点存储数字ns-prevs-nextNULL;//初始化指针// 把s插入p后面s-prevp;p-nexts;// p后移1pp-next;}//3、保存指向尾节点的指针node*tailp;// 4、正序遍历输出phead;//p指向头节点while(p!NULL){coutp-data;pp-next;// 指向后继节点}coutendl;// 5、逆序遍历输出ptail;//p指向尾节点while(p!NULL){coutp-data;pp-prev;//指向前驱节点}coutendl;return0;}本次课程的知识点循环链表的概念循环链表与单向链表的对比双向链表的概念双向链表与单向链表的对比双向链表的操作:插入节点、删除节点1、以下关于双向链表的说法错误的是?CA、双向链表可以方便地实现从任意节点向前或向后遍历B、在双向链表中,删除一个节点需要修改两个节点的指针C、相同数据量时,双向链表比单链表少占内存空间D、双向链表的头节点的前驱指针通常为空2、在双向链表中,每个节点包含的指针域指向的内容是?AA、前驱节点的地址和后继节点的地址B、前驱节点的地址和数据域C、后继节点的地址和数据域D、只有后继节点的地址动态创建链表创建n个节点的单向链表,按顺序存储1~n。请用动态分配内存的方式创建节点。遍历输出每个节点的值。【输入格式】一个正整数n【输出格式】输出单向链表每个节点的值,数值之间用空格隔开。【输入样例】10【输出样例】1 2 3 4 5 6 7 8 9 10#includeiostreamusingnamespacestd;structnode{intdata;// 数据node*next;// 指向后继节点的指针};intmain(){intn;cinn;//1、创建第一个节点,头指针指向这个节点node*headnewnode;//动态分配内存head-data1;//新结点的数据head-nextNULL;//初始化指针// 2、插入值为2~n的新节点(在尾部插入)inti2;node*phead;//新节点总是插入p后一个位置for(inti2;in;i){// 分配新结点snode*snewnode;s-datai;// 新结点存储数字is-nextNULL;//初始化指针// 把s插入p后面p-nexts;// p后移1pp-next;}// 正序遍历输出phead;//p指向头节点while(p!NULL){coutp-data;pp-next;//指向后继节点}coutendl;return0;}
)
