資料結構、算法與應用 C++語言描述 第10章部分習題

// dictionaryr.h

//
// Created by Dell on 2021/6/7.
//
#include <utility>
#include "iostream"


#ifndef TEST_DICTIONARY_H
#define TEST_DICTIONARY_H

template<class K, class E>
class dictionary
{
public:
    virtual ~dictionary() {};
    virtual bool empty() const = 0;//
    virtual int size() const = 0;
    virtual std::pair<const K, E>* find(const K&) const = 0; // 關鍵字不能被改變
    virtual void erase(const K&) = 0;
    virtual void insert(const std::pair<const K, E>&) = 0;
};

template <class T>
void changeLength1D(T* &a, int oldLength, int newLength)
{
    if(newLength < 0)
    {
        std::cout << "The new Length must bigger than 0"<<std::endl;
        return;
    }
    // 生成一個新的數組指針
    T* temp = new T[newLength];
    int number = std::min(oldLength, newLength);
    std::copy(a, a+number, temp);
    delete [] a;
    a = temp;
}

#endif //TEST_DICTIONARY_H

           

// sortedArrayList

//
// Created by Dell on 2021/6/7.
//
#include "dictionary.h"
#include <utility>
#include "iostream"
#include "algorithm"


#ifndef TEST_SORTEDARRAYLIST_H
#define TEST_SORTEDARRAYLIST_H


template<class K, class E>
class sortedArrayList : public dictionary<K, E>
{
    template<class M, class N>
    friend std::ostream &operator<<(std::ostream &os, sortedArrayList<M, N>&);
public:
    explicit sortedArrayList(int initialLength = 10);
    bool empty() const;
    int size() const;
    std::pair<const K, E>* find(const K&) const;
    void erase(const K&);
    void insert(const std::pair<const K, E>& );

private:
//    std::pair<const K, E>* element;
    std::pair<K, E>* element; // 這裡不能用const，否則後邊會修改不了順序，不能插入
    int mapSize, arrayLength;
};

template<class K, class E>
sortedArrayList<K, E>::sortedArrayList(int initialLength) {
    arrayLength=initialLength;
    element = new std::pair<K, E>[arrayLength];
    mapSize=0;
}

template<class K, class E>
bool sortedArrayList<K, E>::empty() const {
    return mapSize==0;
}

template<class K, class E>
int sortedArrayList<K, E>::size() const {
    return mapSize;
}

template<class K, class E>
std::pair<const K, E>* sortedArrayList<K, E>::find(const K& key) const {
    int i=0;
    for (i=0;i<mapSize;++i){
        if((element+i)->first >= key)
            break;
    }
    if(!empty() && (element+i)->first == key)
        return (std::pair<const K, E>*)element+i; // 這裡進行類型轉換
    return NULL;
}

template<class K, class E>
void sortedArrayList<K, E>::insert(const std::pair<const K, E>& thePair){
    if (mapSize==arrayLength){ // 檢查長度
        changeLength1D(element, arrayLength, 2 * arrayLength);
        arrayLength*=2;
    }
    int i=0;
    for (i=0;i<mapSize;++i){
        if((element+i)->first >= thePair.first)
            break;
    }

    if (mapSize !=0 && (element+i)->first == thePair.first){ // 大小不等于零保證原來就存在元素
        (element+i)->second = thePair.second;
        return;
    }

    // 全體向後移一個位置
    if (i<mapSize)
        std::copy_backward(element+i, element+mapSize, element+mapSize+1); //這裡從後邊拷貝指派，是因為共享記憶體
    *(element+i) = thePair;
    ++mapSize;
}

template<class K, class E>
void sortedArrayList<K, E>::erase(const K& theKey){
    int i=0;
    for (i=0;i<mapSize;++i){
        if((element+i)->first >= theKey)
            break;
    }
    if ((element+i)->first == theKey){
        std::copy(element+i+1, element+mapSize, element+i); // 主義前後兩個指派函數的差別
//        delete (element+mapSize); // 這裡怎麼釋放記憶體
        --mapSize;
    }
}

template<class K, class E>
std::ostream &operator<<(std::ostream &os, sortedArrayList<K, E> &map) {
    for (int i = 0; i < map.size(); ++i)
        os << (map.element+i)->first << "   " << (map.element+i)->second << std::endl;
    return os;
}

#endif //TEST_SORTEDARRAYLIST_H