本文共 7212 字，大约阅读时间需要 24 分钟。
10.2-3
Implement a queue by a singly linked list L. The operations ENQUEUE and DEQUEUE should still take O(1) time. 译：使用一个单链表实现一个队列。入队和出队的时间复杂度都应该是O(1)。
我们假设链表是用头插法，那么1、2、3插进入链表，在链表中的顺序就变成了3、2、1。如果我们想出队，就必须找到链表尾元素出队。因为要保持出队的时间复杂度是O(1)，那么插入操作后要保存第一次插入的结点，出队就可以直接将保存的插入后的结点出队即可，然后出队后还要找到第一次插入的结点的前一个结点，又因为这是单链表，需要遍历整个链表才能找到前一个结点，这显然是违反了时间复杂度为O(1)。
假设链表用尾插法，那么1、2、3插进链表，在链表中的顺序依然是1、2、3、如果我们想出队，只需要将头节点的下一个元素出队。为了保持插入的时间复杂度是O(1)，不可能每次插入的时候都去遍历链表，因此需要保存插入后的新节点，插入的操作就在保存的新节点后面插入。因此入队和出队的时间复杂度是O(1)，这种方法才是可行的。
//SinglyLink.h#pragma once#include#include template class Node{public: Node(Node * pNext = NULL, ElemType* pData = NULL); ElemType const& GetData() const; void SetData(ElemType val) ; Node * const& GetNext() const; void SetNext(Node * val);private: ElemType* m_pData; Node * m_pNext;};template class SinglyLinkList{public: SinglyLinkList(); 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(); Node * HavaHeadNode();private: Node * m_pHeadNode; unsigned int m_length;};//————————————————————————————————//Node类的实现template Node ::Node(Node * pNext /*= NULL*/, ElemType* pData /*= NULL*/) :m_pNext(pNext),m_pData(pData){}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;}//————————————————————————————————//SinglyLink类实现template SinglyLinkList ::SinglyLinkList() :m_pHeadNode(new Node ()),m_length(0){}template bool SinglyLinkList ::InsertByPosNode(ElemType elem, Node * posNode, Node ** RetInsetNode /*= NULL*/){ Node * insertNode = new Node (posNode->GetNext(),new ElemType(elem)); posNode->SetNext(insertNode); ++m_length; *RetInsetNode = insertNode; return true;}template bool SinglyLinkList ::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 != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { Node * insertNode = new Node (pCurrentNode->GetNext(),new ElemType(elem)); pCurrentNode->SetNext(insertNode); ++m_length; return true; } } assert(false && "Error: SinglyLink Insert failed for unknow reason!"); return false;}template bool SinglyLinkList ::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; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { Node * deleteNode = pCurrentNode->GetNext(); pCurrentNode->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& SinglyLinkList ::GetLength() const{ return m_length;}template bool SinglyLinkList ::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; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0 && (pCurrentNode->GetNext() != NULL) ) { *elem = pCurrentNode->GetNext()->GetData(); return true; } } return false;}template bool SinglyLinkList ::Visit(ElemType* elem, const unsigned int& pos) const{ if (pos >= GetLength() || pos < 0) { return false; } return Search(pos,elem);}template bool SinglyLinkList ::Empty(){ return !m_length;}template Node * SinglyLinkList ::HavaHeadNode(){ return m_pHeadNode;}
//QueueBySinglyLink.h#pragma once#include "SinglyLinkList.h"templateclass QueueBySinglyLink{public: QueueBySinglyLink(); bool EnQueue(ElemType elem); bool DeQueue(ElemType* elem); bool Empty(); unsigned int GetLength() const; bool Visit(ElemType* elem, const unsigned int& pos) const;private: SinglyLinkList * m_pSinglyLink; Node * m_TopNode;};template bool QueueBySinglyLink ::Empty(){ return m_pSinglyLink->Empty();}template unsigned int QueueBySinglyLink ::GetLength() const{ return m_pSinglyLink->GetLength();}template bool QueueBySinglyLink ::DeQueue(ElemType* elem){ return m_pSinglyLink->Delete(0,elem);}template bool QueueBySinglyLink ::EnQueue(ElemType elem){ if (m_pSinglyLink->InsertByPosNode(elem,m_TopNode, &m_TopNode)) { return true; } else { assert(false && "Error: QueueBySinglyLink Push failed for allocate node"); return false; }}template QueueBySinglyLink ::QueueBySinglyLink() : m_pSinglyLink(new SinglyLinkList ()), m_TopNode(m_pSinglyLink->HavaHeadNode()){}template bool QueueBySinglyLink ::Visit(ElemType* elem, const unsigned int& pos) const{ return m_pSinglyLink->Visit(elem,pos);}
//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; dateStruct.Visit(&tempElem,i); printf("%d ",tempElem); } printf("\n"); printf("\n"); }} //main.cpp#include "QueueBySinglyLink.h"#include "Util.h"#includeusing namespace std;typedef int ElemType;int main(){ QueueBySinglyLink testQueueBySinglyLink; Util::PrintMemory(testQueueBySinglyLink,testQueueBySinglyLink.GetLength()); cout << (testQueueBySinglyLink.Empty() ? "Empty QueueBySinglyLink." : "Not Empty QueueBySinglyLink.") << endl; for (int i = 1; i != 5; i++) { testQueueBySinglyLink.EnQueue(i); cout << "\nPush:" << i << endl; Util::PrintMemory(testQueueBySinglyLink,testQueueBySinglyLink.GetLength()); cout << (testQueueBySinglyLink.Empty() ? "Empty QueueBySinglyLink." : "Not Empty QueueBySinglyLink.") << endl; } for(int i = 1; i!= 5; i++) { int temp; testQueueBySinglyLink.DeQueue(&temp); cout << "\nPop:" << temp << endl; Util::PrintMemory(testQueueBySinglyLink,testQueueBySinglyLink.GetLength()); cout << (testQueueBySinglyLink.Empty() ? "Empty QueueBySinglyLink." : "Not Empty QueueBySinglyLink.") << endl; } return 0;}
PrintMemory:
Empty QueueBySinglyLink.Push:1
PrintMemory: 1 Not Empty QueueBySinglyLink.Push:2
PrintMemory: 1 2 Not Empty QueueBySinglyLink.Push:3
PrintMemory: 1 2 3 Not Empty QueueBySinglyLink.Push:4
PrintMemory: 1 2 3 4 Not Empty QueueBySinglyLink.Pop:1
PrintMemory: 2 3 4 Not Empty QueueBySinglyLink.Pop:2
PrintMemory: 3 4 Not Empty QueueBySinglyLink.Pop:3
PrintMemory: 4 Not Empty QueueBySinglyLink.Pop:4
PrintMemory: Empty QueueBySinglyLink.
转载地址：http://enyii.baihongyu.com/