数据结构练习题(三).doc

数据结构练习题解答（三） 第三章 链表 3-2 试编写一个算法，在带表头结点的单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回0。 【解答】 template ListNode * List :: GetANode int i //取得单链表中第i个结点地址, i从0开始计数, i 0时返回指针0, i 0时返回表头结点地址。 if i 1 return NULL; ListNode * p first; int k 0; while p ! NULL k i p p→link; k++; return p; 3-3 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。 【解答】 #include template class List; template class ListNode friend class List ; public: ListNode ; //构造函数 ListNode const Type item ; //构造函数 private: Type data; ListNode *link; ; template class List public: List const Type finishied ; //建立链表 void Browse ; //打印链表 void Merge List hb ; //连接链表 private: ListNode *first, *last; ; //各成员函数的实现 template ListNode ::ListNode : link NULL //构造函数, 仅初始化指针成员。 template ListNode ::ListNode const Type item : data item , link NULL //构造函数, 初始化数据与指针成员。 template List :: List const Type finishied //创建一个带表头结点的单链表，finished是停止建表输入的标志， //是所有输入值中不可能出现的数值。 first last new ListNode ; //创建表头结点 Type value; ListNode *p, *q, *s; cin value; while value ! finished //循环建立各个结点 s new ListNode value ; q first; p first→link; while p ! NULL p→data value q p; p p→link; //寻找新结点插入位置 q→link s; s→link p; //在q, p间插入新结点 if p NULL last s; cin value; template void List :: Browse //浏览并输出链表的内容 cout \nThe List is : \n; ListNode *p first→link; while p ! NULL cout p→data; if p ! last cout →; else cout endl; p p→link; template void List :: Merge List hb //将当前链表this与链表hb按逆序合并，结果放在当前链表this中。 ListNode *pa, *pb, *q, *p; pa first→link; pb hb.first→link; //检测指针跳过表头结点 first→link NULL; //结果链表初始化 while pa ! NULL pb ! NULL //当两链表都未结束时 if pa→data pb→data q pa; pa pa→link; //从pa链中摘下 else q pb; pb pb→link; //从pb链中摘下 q→link first→link; first→link q; //链入结果链的链头