第2章之线性链表内容摘要：
位置 ,使指针 p指向 ai1 step2 申请并生成新结点 s step3 使 s插入到 ai1和 ai之间 示例 下一页 上一页 停止放映 [第 20页 /41] void Insert(LinkListamp。 head, int i, ElemType x) { if(i1) cout不存在第 i个位置。 else { LNode *p=head。 //p最终将指向第 i1个结点 int k=0。 //p目前指向第 0个结点 (头结点 ) while( p!=NULLamp。 amp。 ki1 ) { p=pnext。 k++。 } if(p==NULL) cout i超出链表最大位置。 else { LNode *s=new LNode。 //建立新结点 s sdata = x。 snext=pnext。 //定义结点 s的指针域 pnext=s。 //修改结点 p的指针域 } } } 插入算法 C++源程序 下一页 上一页 停止放映 [第 21页 /41] （ 4） 在单链表中查找数据值为 x的结点 返回指向第 i个结点的指针。 单链表查找算法操作步骤 : step1 初始化 ,指针 P指向头指针 step2 P非空且当前值不为 x的循环 step3 每循环一次 ,P后移一个位置 step4 循环结束 ,返回指向 ai的指针 P，或空指针。 下一页 上一页 停止放映 [第 22页 /41] Lnode * Find( LinkListamp。 head, ElemType x ) { LNode *p=headnext。 //p指向第一个结点 while ( p!=NULL amp。 amp。 pdata!=x ) //寻找 x循环 p = pnext。 //指针右移 if((p!=NULL)amp。 amp。 (pdata==x )) return p。 //找到了，返回地址 else return NULL。 //没找到返回空指针 } 查找算法 C++源程序 下一页 上一页 停止放映 [第 23页 /41] 其他形式的链表 链表检索只能从头指针开始 ,且只能顺链表方向移动。 在单链表中 ,从表的任一结点 ai找其前趋结点 ,时间复杂度是 O（ n）。 如果让链表首尾相接，构成环形，这就是单循环链表。 链表可以从两个方向检索，效果更佳；这就是 双向循环链表。 下一页 上一页 停止放映 [第 24页 /41] 单循环链表 单循环链表表示形式： head ... head a1 a2 an 单循环链表为空的条件 : head next=head 表示形式为 : 下一页 上一页 停止放映 [第 25页 /41] 单循环链表特点 • 从表中任一结点出发 ,均可以找到表中其它结点。 • 找其前趋结点的时间复杂度是 O（ n）。 下一页 上一页 停止放映 [第 26页 /41] 双向循环链表 • 在单向循环链表中，也存在检索前趋结点费时的问题（所需时间是 O（ n））。 • 双向循环链表，其存储结构： typedef struct DNode { ElemType data。 //数据域 struct DNode *prior， *next。 // 指针域 } *LinkList。 下一页 上一页 停止放映 [第 27页 /41] 双向循环链表结点结构 prior data next 指向后继结点 指针域 数据域 指向前趋结点 指针域 下一页 上一页 停止放映 [第 28页 /41] 双向循环链表表示形式 双向循环链表表示形式： head head ... ...。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。