本文共 6557 字，大约阅读时间需要 21 分钟。
10.2-6
The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2.The setsS1 andS2 are usuallydestroyedbytheoperation. Show how to support UNION in O(1) time using a suitable list data structure. 译：简单来说就是将链表S1和链表S2合并到S。
我的做法和题意稍有违反，我不返回S，而是直接将S2合并到S1中，但其实原理是一样的。只要将遍历s2，将s2的每个元素接到s1中即可，非常简单。
//CircularDoubleLink.h#pragma once#include#include template class Node{public: Node(ElemType* pData = NULL, Node * pNext = NULL, Node * pPrev = NULL); ElemType const& GetData() const; void SetData(ElemType val) ; Node * const& GetNext() const; void SetNext(Node * val); Node * const& GetPrev() const; void SetPrev(Node * val) ;private: ElemType* m_pData; Node * m_pNext; Node * m_pPrev;};template class CircularDoubleLink{public: CircularDoubleLink(); unsigned int const& GetLength() const; bool Insert(ElemType elem, unsigned int pos); bool InsertByPosNode(ElemType elem, Node * posNode, Node ** RetInsetNode = NULL); bool Delete(unsigned int pos, ElemType* elem); bool Search(unsigned int pos, ElemType* elem) const; bool Visit(ElemType* elem, const unsigned int& pos) const; bool Empty(); bool Union(const CircularDoubleLink& LinkB);//将B链表中元素合并到该链表中 Node * HavaHeadNode(); Node * const& GetHeadNode() const;private: Node * m_pHeadNode; unsigned int m_length;};//————————————————————————————————//Node类的实现template Node ::Node(ElemType* pData /* = NULL */, Node * pNext /* = NULL */, Node * pPrev /* = NULL */) :m_pNext(pNext),m_pData(pData),m_pPrev(pPrev){}template void Node ::SetNext(Node * val){ m_pNext = val;}template Node * const& Node ::GetNext() const{ return m_pNext;}template void Node ::SetData(ElemType val){ m_pData = val;}template ElemType const& Node ::GetData() const{ return *m_pData;}template void Node ::SetPrev(Node * val){ m_pPrev = val;}template Node * const& Node ::GetPrev() const{ return m_pPrev;}//————————————————————————————————//SinglyLink类实现template CircularDoubleLink ::CircularDoubleLink() :m_pHeadNode(new Node ()),m_length(0){ m_pHeadNode->SetNext(m_pHeadNode); m_pHeadNode->SetPrev(m_pHeadNode);}template bool CircularDoubleLink ::InsertByPosNode(ElemType elem, Node * posNode, Node ** RetInsetNode /*= NULL*/){ Node * insertNode = new Node (new ElemType(elem),posNode->GetNext(),posNode); posNode->GetNext()->SetPrev(insertNode); posNode->SetNext(insertNode); ++m_length; if (RetInsetNode) { *RetInsetNode = insertNode; } return true;}template bool CircularDoubleLink ::Insert(ElemType elem, unsigned int pos){ if (pos > GetLength() || pos < 0) { assert(false && "Error: SinglyLink's insert pos is out of range!\n"); return false; } for(Node * pCurrentNode = m_pHeadNode; ; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { InsertByPosNode(elem, pCurrentNode); return true; } } assert(false && "Error: SinglyLink Insert failed for unknow reason!"); return false;}template bool CircularDoubleLink ::Delete(unsigned int pos, ElemType* elem){ if (pos >= GetLength() || pos < 0) { assert(false && "Error: SinglyLink's delete pos is out of range!\n"); } for(Node * pCurrentNode = m_pHeadNode->GetNext(); ; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { Node * deleteNode = pCurrentNode; deleteNode->GetNext()->SetPrev(deleteNode->GetPrev()); pCurrentNode->GetPrev()->SetNext(deleteNode->GetNext()); *elem = deleteNode->GetData(); delete deleteNode; --m_length; return true; } } assert(false && "Error: SinglyLink pos delete failed for unknow reason!"); return false;}template unsigned int const& CircularDoubleLink ::GetLength() const{ return m_length;}template bool CircularDoubleLink ::Search(unsigned int pos, ElemType* elem) const{ if (pos >= GetLength() || pos < 0) { assert(false && "Error: SinglyLink's search pos is out of range!\n"); } for(Node * pCurrentNode = m_pHeadNode->GetNext(); ; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { *elem = pCurrentNode->GetData(); return true; } } return false;}template bool CircularDoubleLink ::Visit(ElemType* elem, const unsigned int& pos) const{ if (pos >= GetLength() || pos < 0) { return false; } return Search(pos,elem);}template bool CircularDoubleLink ::Empty(){ return !m_length;}template Node * CircularDoubleLink ::HavaHeadNode(){ return m_pHeadNode;}template bool CircularDoubleLink ::Union(const CircularDoubleLink& LinkB){ for(Node * linkBCurrentNode = LinkB.GetHeadNode()->GetNext(); linkBCurrentNode != LinkB.GetHeadNode(); linkBCurrentNode = linkBCurrentNode->GetNext() ) { InsertByPosNode(linkBCurrentNode->GetData(),m_pHeadNode->GetPrev()); } return true;}template Node * const& CircularDoubleLink ::GetHeadNode() const{ return m_pHeadNode;}
//Util.h#pragma oncenamespace Util{ template void PrintMemory(const T& dateStruct, unsigned int size) { cout << "PrintMemory: "; for (int i = 0; i != size; i++) { ElemType tempElem; if (!dateStruct.Visit(&tempElem,i)) { printf("\n"); return; } printf("%d ",tempElem); } printf("\n"); }} //main.cpp#include "Util.h"#include "CircularDoubleLink.h"#includeusing namespace std;typedef int ElemType;int main(){ CircularDoubleLink testCircularDoubleLinkA; CircularDoubleLink testCircularDoubleLinkB; for (int i = 0; i != 5; i++) { testCircularDoubleLinkA.Insert(i+1,i); testCircularDoubleLinkB.Insert(i+6,i); } cout << "testCircularDoubleLinkA:\n"; Util::PrintMemory(testCircularDoubleLinkA,testCircularDoubleLinkA.GetLength()); cout << "testCircularDoubleLinkB:\n"; Util::PrintMemory(testCircularDoubleLinkB,testCircularDoubleLinkB.GetLength()); cout << "\nUnion testCircularDoubleLinkB to testCircularDoubleLinkA...\n"; testCircularDoubleLinkA.Union(testCircularDoubleLinkB); cout << "\ntestCircularDoubleLinkA:\n"; Util::PrintMemory(testCircularDoubleLinkA,testCircularDoubleLinkA.GetLength()); cout << "testCircularDoubleLinkB:\n"; Util::PrintMemory(testCircularDoubleLinkB,testCircularDoubleLinkB.GetLength()); return 0;}
testCircularDoubleLinkA:
PrintMemory: 1 2 3 4 5 testCircularDoubleLinkB: PrintMemory: 6 7 8 9 10Union testCircularDoubleLinkB to testCircularDoubleLinkA…
testCircularDoubleLinkA:
PrintMemory: 1 2 3 4 5 6 7 8 9 10 testCircularDoubleLinkB: PrintMemory: 6 7 8 9 10
转载地址：http://wiyii.baihongyu.com/