数据结构之“Ordered List and Sorted List”（六）

本文主要是介绍数据结构之“Ordered List and Sorted List”（六），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        本文将学习“SortedList”的指针实现，并比较数组实现和指针实现的性能。

一、SortedListAsLinkedList（点击打开链接）

        

        如上图，SortedListAsLinkedList（SortedList的指针实现）也采用的是多继承，其中接口继承自SortedList，实现继承自ListAsLinkedList。声明如下：

#pragma once
#include "ListAsLinkedList.h"class SortedListAsLinkedList : public virtual SortedList, public virtual ListAsLinkedList
{
public:SortedListAsLinkedList();~SortedListAsLinkedList();void Insert(Object &);Object & operator[](unsigned int) const;Object & operator[](Position const &) const;Position & FindPosition(Object const &) const;void Withdraw(Position const &);
};

         SortedListAsLinkedList没有任何新增接口。实现如下：

#include "stdafx.h"
#include "SortedListAsLinkedList.h"SortedListAsLinkedList::SortedListAsLinkedList()
{
}SortedListAsLinkedList::~SortedListAsLinkedList()
{
}void SortedListAsLinkedList::Insert(Object & object)
{const Node<Object*>* prevPtr = NULL;const Node<Object*>* ptr = linkedList.Head();while (ptr != NULL && *ptr->Datum() < object){prevPtr = ptr;ptr = ptr->Next();}if (!prevPtr)linkedList.Prepend(&object);elselinkedList.InsertAfter(prevPtr, &object);++count;
}Object & SortedListAsLinkedList::operator[](unsigned int offset) const
{return ListAsLinkedList::operator[](offset);
}Object & SortedListAsLinkedList::operator[](Position const & arg) const
{return ListAsLinkedList::operator[](arg);
}Position & SortedListAsLinkedList::FindPosition(Object const & object) const
{return ListAsLinkedList::FindPosition(object);
}void SortedListAsLinkedList::Withdraw(Position const & arg)
{ListAsLinkedList::Withdraw(arg);
}

        除“Insert”函数外， SortedListAsLinkedList的实现全部继承自ListAsLinkedList。“Insert”函数需要设计两个跟踪指针。

二、测试

    // test for SortedListAsLinkedList{SortedListAsLinkedList list1;Int pArray[] = { Int(18), Int(2), Int(3), Int(14), Int(5) };for (unsigned int i = 0; i < 5; ++i)list1.Insert(pArray[i]);list1.Put(std::cout);for (unsigned int i = 0; i < 5; ++i)list1.Withdraw(list1.FindPosition(pArray[i]));}

三、性能比较

1，时间复杂度

        基于数组实现的SortedList由于可以采用binary-search算法，查找的效率相对基于指针的SortedList要高。在插入和删除方面，基于数组的SortedList需要移动元素，而基于指针的SortedList需要使用跟踪指针和遍历List，效率都是O(n)。

2，空间复杂度

        由于两者都没有新增成员变量，故其空间复杂度的比较与之前的OrderedList相同。

        综上，在效率上，基于数组的SortedList要优于基于指针的SortedList。但后者没有大小限制，空间上更灵活。

这篇关于数据结构之“Ordered List and Sorted List”（六）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---