【Weiss】【第03章】练习3.2

【练习3.2】

给你一个链表L和另一个链表P，它们包含以升序排列的整数。操作printlots(L,P)将打印L中那些由P所指定的位置上的元素。

例如，如果p=1,3,4,6，那么，L的第一、第三、第四和第六个元素被打印出来。

你应该只使用基本的表操作，该过程的运行时间是多少？

Answer:

老样子，先放折叠的实测代码。

 #include <iostream>

 #include <string>

 #include "linklist.h"

 using namespace std;

 using namespace linklist;

 template class List<unsigned int>;

 template class List<string>;

 int main(void)

 {

     List<unsigned int> number;

     //测试按升序插入

     cout << "/*addinorder()*/" << endl;

     number.addinorder();

     number.addinorder();

     number.addinorder();

     number.addinorder();

     number.addinorder();

     number.addinorder();

     number.addinorder();

     number.traverse();

     cout << "\n/*end*/\n\n" << endl;

     List<string> word;

     cout << "/*initialize*/" << endl;

     word.additem("The");

     word.additem("day");

     word.additem("after");

     word.additem("tommorow");

     word.additem("will");

     word.additem("be");

     word.additem("a");

     word.additem("sunny");

     word.additem("day");

     word.traverse();

     cout << "\n/*end*/\n\n" << endl;

     //测试printlots，打印word的第2，3，5，7个元素

     cout << "/*printlots()*/" << endl;

     word.printlots(number);

     cout << "\n/*end*/\n\n" << endl;

     system("pause");

 }

在对此前的链表例程

http://www.cnblogs.com/catnip/p/4328889.html

添加下面的成员函数后（类内成员函数声明需自行添加），该实测代码可以正确运行。

因为条件的链表是升序的，所以虽然没要求写，这儿首先还是在链表例程里面加了个自动按升序插入的例程。

 //练习3.2新增，按序插入

 template <typename T> bool List<T>::addinorder(const T &item)

 {

     Node<T>* pnew = new Node<T>(item);

     Node<T>* curr = front;

     Node<T>* prev = nullptr;

     while (curr != nullptr && curr->data < item)

     {

         prev = curr;

         curr = curr->next;

     }

     //如果元素小于头元素，则头指针指向新节点

     if (prev == nullptr)

         front = pnew;

     //否则，找到最后一个不大于元素的节点，将节点插入在此后

     else

         prev->next = pnew;

     //最后，新节点的后向指针连接第一个比新元素大（或为空）的节点

     pnew->next = curr;

     ++length;

     return true;

 }

然后，虽然题目中要求两个链表元素都是整数，实际上只要第二个链表元素是整数就可以。

假如第一个链表的元素不是整数，那么类模板的一个实例就要访问另一个实例，则需加上一句友元声明。

 //头节点及链表主体操作

 template <typename T> class List

 {

     template <typename X> friend class List;

         //......

 }

最后，按题目要求打印的例程

 //练习3.2新增，坑爹的函数....

 template <typename T> void List<T>::printlots(const List<unsigned int>& inorder)

 {

     //计数器，记录已经查询到当原链表第几个元素

     //不同于数组，计数器从“第一个”开始计算

     unsigned int counter = ;

     Node<T>* scan = front;

     for (Node<unsigned int>* iter = inorder.front; iter != nullptr; iter = iter->next)

     {

         //遍历辅助链表，iter->data表示“需要原链表输出其第iter->data个元素”

         //当data过大时直接返回

         if (iter->data > length)

             return;

         //迭代直至counter==index并打印

         for (; counter < iter->data; ++counter)

             scan = scan->next;

         cout << scan->data << ends;

     }

 }

巴特西

【Weiss】【第03章】练习3.2

最新文章

热门文章