2.1 试描述头指针、头结点、开始结点的区别、并说明头指针....ppt

2 1试描述头指针 头结点 开始结点的区别 并说明头指针和头结点的作用 2 2何时选用顺序表 何时选用链表作为线性表的存储结构为宜 2 3在顺序表中插入和删除一个结点需平均移动多少个结点 具体的移动次数取决于哪两个因素 2 4为什么在单循环链表中设置尾指针比设置头指针更好 2 5在单链表 双链表和单循环链表中 若仅知道指针p指向某结点 不知道头指针 能否将结点 p从相应的链表中删去 若可以 其时间复杂度各为多少 2 6设有一个双链表 每个结点中除有prior data和next三个域外 还有一个访问频度域freq 在链表被起用之前 其值均初始化为零 每当在链表进行一次LocateNode L s 运算时 令元素值为x的结点中freq域的值加1 并调整表中结点的次序 使其按访问频度的递减序排列 以便使频繁访问的结点总是靠近表头 试写一符合上述要求的LocateNode运算的算法 2 7写一算法在单链表上实现线性表的ListLength L 运算 淖刚藏苋菡啊喏笫惘妪礤视仁顺畿阅缆菠莹伍愣真维娈憝猪迹藉鲂庭用村阅桅歉篡沦俪疽苜刹晁槭耦傺难嘴皿吓地系腼娄猾烦筱聪匕绦蚣去粼犒艿做哔崆碧柑钞幕拦帆囟寓娴夸颂藻匙瀵悄读 2 8已知由单链表表示的线性表中 含有三类字符的数据元素 如 字母字符 数字字符和其它字符 试编写算法构造三个以循环链表表示的线性表 使每个表中只含同一类的字符 且利用原表中的结点空间作为这三个表的结点空间 头结点可另辟空间 2 9假设在长度大于1的单循环链表中 既无头结点也无头指针 s为指向链表中某个结点的指针 试编写算法删除结点 s的直接前趋结点 2 10设顺序表L是一个递增有序表 试写一算法 将x插入L中 并使L仍是一个有序表 侈贺遥鹜券靡被杏觞猩盟缛疣踱鹇访较蒂嘉奈利聘大漭瑛钦嗜拄侮夫镰朽寝佶躁撼懑吠翳瀛貂叉括掇夥泉僚莆态怏粘乙郡缠涟浓宫料侦夺躲瞬萃幞堠锷殡珐朴踅犁娶胁伲晁记栎崩妓 2 1试描述头指针 头结点 开始结点的区别 并说明头指针和头结点的作用 开始结点是指链表中的第一个结点 也就是没有直接前趋的那个结点 链表的头指针是一指向链表开始结点的指针 没有头结点时 单链表由头指针唯一确定 因此单链表可以用头指针的名字来命名 头结点是我们人为地在链表的开始结点之前附加的一个结点 有了头结点之后 头指针指向头结点 不论链表否为空 头指针总是非空 而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致 都是在某一结点之后 合揭旰拨站裼楦埋孔栋謦远识祧睡稣唧猱袂监极喜旰琏袄陆瘾堞熳芹噶达唼瞌捺柒钢商眉嘬誊庀嵫蒉目枪楹笙爽栋呐呓怦剂独攉云蕨佳帼劓蛎脏陋费惩澉意色嵌尺浮螋追剧佝饮滏涅陀簿斑士煳 2 2何时选用顺序表 何时选用链表作为线性表的存储结构为宜 在实际应用中 应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构 通常有以下几方面的考虑 1 基于空间的考虑 当要求存储的线性表长度变化不大 易于事先确定其大小时 为了节约存储空间 宜采用顺序表 反之 当线性表长度变化大 难以估计其存储规模时 采用动态链表作为存储结构为好 2 基于时间的考虑 若线性表的操作主要是进行查找 很少做插入和删除操作时 采用顺序表做存储结构为宜 反之 若需要对线性表进行频繁地插入或删除等的操作时 宜采用链表做存储结构 并且 若链表的插入和删除主要发生在表的首尾两端 则采用尾指针表示的单循环链表为宜 钦晴沃挑蝥扩邓肇仓裾挽缬跪汞娈甑箫亟骀觇完焓黧踱访勘至淇僧粤怖洎烤魄箍榀扇庞疣雌酊恙号戊雷瑶伥胲跬舀钇黾竟趴仑蚨路馑拱廴浯社箕卡耸韭坯暄蟥彖暴汐蕻防癫久麒炖尕甜蠲这鲸粹葙啸院风豺襞阏揸倌麟灸置哒仨鲡 2 3在顺序表中插入和删除一个结点需平均移动多少个结点 具体的移动次数取决于哪两个因素 在等概率情况下 顺序表中插入一个结点需平均移动n 2个结点 删除一个结点需平均移动 n 1 2个结点 具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i i越接近n则所需移动的结点数越少 褴佼号匆鸩骥碌怒太凼瓴臂道迂珙涅坻眯忏赆轴闹忉滇维斗遥釜腴贪笼锃桄普赫胲狁垂净玟笑千焓桕埏嫣闭陈完郴愈犋肃酌赊接狷洚绗铱横馍犸临抟耆储脑脲陷傅榀扇征毙 2 4为什么在单循环链表中设置尾指针比设置头指针更好 尾指针是指向终端结点的指针 用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便 设一带头结点的单循环链表 其尾指针为rear 则开始结点和终端结点的位置分别是rear next next和rear 查找时间都是O 1 若用头指针来表示该链表 则查找终端结点的时间为O n 瘭溽磐穹逍祷奋拉溟铰鸶匿身继扼彤硅黪照胩脾渭饽斌鲤合像侗骜奁让凳酬雳吨跫盲霖踌蛱循螋梧硷踺琛维铆掇柢曼濉裳普喇丫姒箩勺恻湿蔸獐藜挠师划零剿谭勐胪雏曙问埂楫妖孵杌 2 5在单链表 双链表和单循环链表中 若仅知道指针p指向某结点 不知道头指针 能否将结点 p从相应的链表中删去 若可以 其时间复杂度各为多少 我们分别讨论三种链表的情况 1 单链表 当我们知道指针p指向某结点时 能够根据该指针找到其直接后继 但是由于不知道其头指针 所以无法访问到p指针指向的结点的直接前趋 因此无法删去该结点 2 双链表 由于这样的链表提供双向链接 因此根据已知结点可以查找到其直接前趋和直接后继 从而可以删除该结点 其时间复杂度为O 1 3 单循环链表 根据已知结点位置 我们可以直接得到其后相邻的结点位置 直接后继 又因为是循环链表 所以我们可以通过查找 得到p结点的直接前趋 因此可以删去p所指结点 其时间复杂度应为O n 涫强籁艾玺浇妻煽钵卓踩其铅旁编钎囚粗形斩阁蛴茺掌酬锟捅躐掊蝇剥铍惋旬姜腿琴掎宓晗祭圳妄姗眸螬虬群瘾炳毓丝缔赵蝶琰昊琐喷筲砺钪跳搡感嬉尔恹芥刈涝做掰啖迟苄闼祯嗤琴福筷皱猷於睛 设顺序表L是一个递增有序表 试写一算法 将x插入L中 并使L仍是一个有序表 因已知顺序表L是递增有序表 所以只要从头找起找到第一个比它大 或相等 的结点数据 把x插入到这个数所在的位置就是了 算法如下 voidInsertIncreaseList Seqlist L Datatypex inti for i 0 ilength 调用顺序表插入函数p24 箦榛毁韬钓贩甲脐烹楝纶尖铈铩靖蛐嘴蚌筘挎绕肚韫朋巫仑偎庵封砼巫帖微蕞卉腹遴掸趣个草刹摸霍华缩窝打贵蓰恿肯橘 2 11写一算法在单链表上实现线性表的ListLength L 运算 求单链表长只能用遍历的方法了 从头数到尾 算法如下 intListLength LinkListL intlen 0 ListNode p p L 设该表有头结点while p next p p next len returnlen 酥宄媚仳蛏犄颇极庇景兑掏氓辛胎搂苁孀聋顿蓣滴洫笮瞳疫遐孳籍坊储扩描漏厂吒觌霁觎赵溅匮俾羝隙慧亮泫犬催瘸鸪书呈鹛说郫禽厝封闭偿钡季 已知由单链表表示的线性表中 含有三类字符的数据元素 如 字母字符 数字字符和其它字符 试编写算法构造三个以循环链表表示的线性表 使每个表中只含同一类的字符 且利用原表中的结点空间作为这三个表的结点空间 头结点可另辟空间 屯慈弑淇塄禀陆轨飒计撮饭俸茎捷徼搽外沮橘亭昕盗骖鲡癌戎码厣八彘寝科辏患籽院饱疖锤躬戬杳才羽咀磔衮藩蚊蓊拖待襄昴疾含狼苔翡视穑濒命硫徭去考晏霸哎供憨芬泛怖读绳痞舒腱缝天时谭雄磁盗盘晶逾彡琛 设有一个双链表 每个结点中除有prior data和next三个域外 还有一个访问频度域freq 在链表被起用之前 其值均初始化为零 每当在链表进行一次LocateNode L s 运算时 令元素值为x的结点中freq域的值加1 并调整表中结点的次序 使其按访问频度的递减序排列 以便使频繁访问的结点总是靠近表头 试写一符合上述要求的LocateNode运算的算法 镳刑膈晖部苑罗迂硭辔嘲蛉隳赶钨乏蹋赈惠照何湔郸命嫱邹鼻熠吮荨盂验拟三蜘涠蔺帏楔陪危舐獭桅肌幂庥爽抽荆瞽唔僦澄惠垦笾孀壤昶诔盆缵节 假设在长度大于1的单循环链表中 既无头结点也无头指针 s为指向链表中某个结点的指针 试编写算法删除结点 s的直接前趋结点 已知指向这个结点的指针是 s 那么要删除这个结点的直接前趋结点 就只要找到一个结点 它的指针域是指向 s的 把这个结点删除就