【练习3.4】
给定两个已排序的表L1和L2，只使用基本的表操作编写计算L1∩L2的过程。
【练习3.5】
给定两个已排序的表L1和L2，只使用基本的表操作编写计算L1∪L2的过程。
思路比较简单，测试代码如下，两道题比较相似，测试代码就放一起了。
1 #include <iostream> 2 #include "linklist.h" 3 using namespace std; 4 using namespace linklist; 5 template class List<int>; 6 int main(void) 7 { 8 List<int> primer; 9 10 //原始链表 11 cout << "/*additem()*/" << endl; 12 primer.additem(2); 13 primer.additem(3); 14 primer.additem(5); 15 primer.additem(7); 16 primer.additem(8); 17 primer.additem(11); 18 primer.additem(13); 19 primer.additem(17); 20 primer.additem(23); 21 primer.additem(24); 22 primer.traverse(); 23 cout << " /*end*/ " << endl; 24 25 //测试求交 26 cout << "/*intersection()*/" << endl; 27 List<int> odd; 28 odd.additem(3); 29 odd.additem(5); 30 odd.additem(7); 31 odd.additem(9); 32 odd.additem(11); 33 odd.additem(13); 34 odd.additem(15); 35 odd.additem(17); 36 odd.additem(19); 37 odd.additem(21); 38 odd.additem(23); 39 odd.additem(25); 40 odd.additem(27); 41 odd.additem(29); 42 odd.traverse(); 43 cout <<" "<<flush; 44 odd.intersecton(primer); 45 odd.traverse(); 46 cout << " /*end*/ " << endl; 47 48 //测试求并 49 cout << "/*join()*/" << endl; 50 List<int> natural; 51 natural.additem(1); 52 natural.additem(2); 53 natural.additem(4); 54 natural.additem(8); 55 natural.additem(16); 56 natural.traverse(); 57 cout << endl;; 58 natural.join(primer); 59 natural.traverse(); 60 cout << " /*end*/ " << endl; 61 62 system("pause"); 63 }
主要思路就是两个链表同时前进并比较元素大小，在合适的节点处删除或插入节点，时间复杂度O(n)。
为了满足中途插入或删除的需求，在3.4处补充了一个最初没有的辅助删除操作，3.5补充了一个辅助插入操作。
练习3.4，求交代码如下：
1 //练习3.4新增，删除指定地址的下一个节点，如地址为nullptr，则删除头节点 2 template <typename T> bool List<T>::remove(Node<T>* pos) 3 { 4 if (length == 0) 5 { 6 cout << "No data!" << endl; 7 return false; 8 } 9 if (pos == nullptr) 10 { 11 pos = front; 12 front = front->next; 13 delete pos; 14 } 15 else 16 { 17 Node<T>* temp = pos->next; 18 pos->next = pos->next->next; 19 delete temp; 20 } 21 --length; 22 return true; 23 } 24 //练习3.4新增，计算两升序链表元素交集并直接覆盖在原链表上 25 template <typename T> void List<T>::intersecton(List<T> inorder) 26 { 27 //原表多保存一个prev以删除节点时传参用 28 Node<T>* curr = front; 29 Node<T>* prev = nullptr; 30 Node<T>* curr2 = inorder.front; 31 while (curr != nullptr && curr2 != nullptr) 32 { 33 //原表元素小于新表，删除原表元素 34 if (curr->data < curr2->data) 35 { 36 curr = curr->next; 37 remove(prev); 38 } 39 //新表元素大于原表，新表查看下一个节点 40 else if (curr2->data < curr->data) 41 curr2 = curr2->next; 42 //两表元素相等，指针共同后移，保留元素 43 else 44 { 45 prev = curr; 46 curr = curr->next; 47 curr2 = curr2->next; 48 } 49 } 50 //如果新链表结束后，原链表尾部还有元素，全部删除 51 while (curr != nullptr) 52 { 53 curr = curr->next; 54 remove(prev); 55 } 56 }
练习3.5，求并代码如下：
1 //练习3.5新增，增加一个节点于在指定地址的下一个节点，如地址为nullptr，则于头节点插入 2 template <typename T> bool List<T>::additem(const T &item, Node<T> *pos) 3 { 4 Node<T>* pnew = new Node<T>(item); 5 if (pos == nullptr) 6 { 7 pnew->next = front; 8 front = pnew; 9 } 10 else 11 { 12 pnew->next = pos->next; 13 pos->next = pnew; 14 } 15 ++length; 16 return true; 17 } 18 //练习3.5新增，计算两升序链表元素并集并直接覆盖在原链表上 19 template <typename T> void List<T>::join(List<T> inorder) 20 { 21 Node<T>* curr = front; 22 Node<T>* prev = nullptr; 23 Node<T>* curr2 = inorder.front; 24 while (curr != nullptr && curr2 != nullptr) 25 { 26 //原链表元素小于新链表元素，原链表查看下一个节点 27 if (curr->data < curr2->data) 28 { 29 prev = curr; 30 curr = curr->next; 31 } 32 //新链表元素小于原链表元素，则插入一个带相同值的元素在curr前（即在prev后） 33 else if (curr2->data < curr->data) 34 { 35 additem(curr2->data, prev); 36 //因为是在prev指针【后】插入元素，为保证升序，插入后prev向后移动 37 if (prev == nullptr) 38 prev = front; 39 else 40 prev = prev->next; 41 curr2 = curr2->next; 42 } 43 //两元素相等，共同查看下一个节点 44 else 45 { 46 prev = curr; 47 curr = curr->next; 48 curr2 = curr2->next; 49 } 50 } 51 while (curr2 != nullptr) 52 { 53 additem(curr2->data, prev); 54 if (prev == nullptr) 55 prev = front; 56 else 57 prev = prev->next; 58 curr2 = curr2->next; 59 } 60 }