




已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
本文由 太阳城()提供struct node int data;struct node* next;创建单链表的程序为:struct node* create(unsigned int n)/创建长度为n的单链表assert(n 0);node* head;head = new node;head-next = NULL;cout head-data;if (n = 1) return head;node* p = head;for (unsigned int i = 1; i next = 0; cout 请输入第 i+1 tmp-data; p-next = tmp; p = tmp;return head;问题1:链表逆置思想为:head指针不断后移,指针反向即可,代码为:void reverse(node*& head)if (head != NULL & head-next != NULL) node* p = head; node* q = head-next; p-next = NULL; while (q-next != NULL) head = q-next; q-next = p; p = q; q = head; head-next = p;return;问题2:删除不知头结点链表的某个节点如果单向链表不知道头节点,一个指针指向其中的一个节点,问如何删除这个指针指向的节点?思想为:把这个节点的下一个节点的值复制给该节点,然后删除下一个节点即可。问题3:怎么判断链表中是否有环?思想为:设置两个指针,一个步长为1,另一个步长为2,依次后移,如果相遇且都不为空,则有环。与这个类似的问题包括:怎么快速检测出一个巨大的链表中的死链?或者如何找出一个单链表的中间节点?代码为:bool loop(node* head)bool flag = true;if (head = NULL) flag = false;node* one = head;node* two = head-next;if (two = NULL) flag = false;while (one != two) if (one != NULL) one = one-next; if (two != NULL) two = two-next; if (two = NULL) break; two = two-next; if (one = NULL | two = NULL) break; if (one = NULL | two = NULL) flag = false;return flag;问题4:如果一个单向链表,其中有环,怎么找出这个链表循环部分的第一个节点?思想为:假设该节点在x位置处,假设步长为1的指针和步长为2的指针相遇在x+z处,循环的长度为y,那么2(x+z)-(x+z)=k*y,那么当一个指针再从开始出后移时,另一个指针从相遇点开始后移时,这两个指针就会在循环开始处相遇。代码为:node* findLoopPlace(node* head, unsigned int* place = NULL)/查找循环的位置,place存储位置if (!loop(head) return NULL;node* one = head;node* two = head-next;unsigned int count = 1;while (one != two) one = one-next; two = two-next-next;one = head;while (one != two) if (count != 1) one = one-next; two = two-next; count+;*place = count;return one;问题5:如何查找链表中倒数第k个节点?思想为:两个指向头结点的指针,一个先向后移动k位,然后两个同时向后面移动直到一个节点到达链尾,前面一个指针的位置就是了。node* findLastK(node* head,unsigned int k)/查找单链表倒数第k个位置node* p = head;unsigned int count = 0;while (p != NULL) p = p-next; count+;if (count k) return NULL;p = head;node* q = head;for (unsigned int i = 0; i next;while (p != NULL) q = q-next; p = p-next;return q;问题6:编程序判断两个链表是否相交。这个问题的精彩解说请参见编程之美一书之编程判断两个链表是否相交,这里就不写了,该书的pdf文档在网上很好下。文章后面给了两个扩展问题:(1)如果链表可能有环,如何做判断?思想为:首先应该明白,只有一个链表有环的情况下是不会相交的,只有都有环或者都没有环的情况下才可能相交,都没有环的情况下最简便的方法就是判断链尾是否相交即可;都有环的情况下,分别找到环上的任一点,一个不动,另一个步进,即可判断是否相交。(2)如何求相交链表的第一个节点?应该为单链表情况思想为:方法一是先把任一个链表连成环,即从表尾接到表头,按照问题4的解法;方法二是计算两个链表的长度,而两个链表是按照尾部对齐的,那么从短链表的第一个位置从长链表的第长度差+1的位置依次比较指针值,相等的位置即是。相关程序包括:单链表中在某个位置插入环以及销毁链表等,代码如下:void insertCircle(node* head, unsigned int n)/在第n个位置形成环,记head为n=1node* p = head;node* q = head;unsigned int count = 1;while(p-next != NULL) p = p-next; count+;if (n = count) for (unsigned int i = 1; i next; p-next = q;return;void destroy(node* head)/销毁链表if (loop(head) node *q = findLoopPlace(head); while (head != q) node* p = head; head
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 难点解析人教版八年级物理上册第4章光现象综合练习试卷(含答案详解版)
- 考点解析人教版八年级物理上册第6章质量与密度-密度专项攻克试题(详解版)
- 2025年建筑施工土石方开挖安全规范考核试卷
- 2025年船舶航行雄安新区水上交通安全岗前培训考核试卷
- 考点解析-人教版八年级物理上册第4章光现象-光的色散同步测评试题(解析版)
- 研究儿童需求成就教学深度
- 基于“计数单位”感悟数与运算的一致性
- 考点解析人教版八年级物理上册第6章质量与密度-密度综合练习试卷
- 考点解析-人教版八年级上册物理《物态变化》达标测试试题(含详细解析)
- 2025年建筑工地劳务承包合同协议
- 中国蛇伤救治指南2024
- 四年级环境教育:污水变清
- 勤劳的小蜜蜂课件
- 2024年青岛市市属事业单位遴选考试真题
- 自体输血管理制度与技术规范
- 《电商平台提价运营策略对比分析-以拼多多与淘宝特价版为例》12000字
- 2024秋七年级英语上册 Unit 3 Is this your pencil Period 1 Section A (1a-1c)教学实录(新版)人教新目标版
- 《神经外科手术的麻醉》课件
- 2025年上半年泸州市纳溪区总工会招考社会化专职工会工作者易考易错模拟试题(共500题)试卷后附参考答案
- 网格员安全知识培训课件
- GB/T 15972.40-2024光纤试验方法规范第40部分:传输特性的测量方法和试验程序衰减
评论
0/150
提交评论