使用C++實作的線性表

版權聲明：您好，轉載請留下本人部落格的位址，謝謝 https://blog.csdn.net/hongbochen1223/article/details/44681317

現在大三下學期了，由于參加了阿裡巴巴的大四實習生校園招聘，第一輪電話面試就被刷下來了，這讓我意識到了自己的能力還很不足，意識到了自己與那些大公司需要的人還有很長的路要走。

在電話面試中，基本上是根據我填寫的履歷來的，我寫的是對linux核心非常感興趣，是以，面試官問我了一些關于核心的一些問題，我竟頭腦發蒙，啥都想不起來了。第一個問題就是問我從計算機上電開始，linux核心的啟動過程。這一下我竟然連MBR,GRUB，initrd什麼的都想不起來了，之前看過幾本linux核心的書，但是看完之後總在腦海中什麼也沒有留下，然後我就問了面試官這個問題，他告訴我一定要和項目相結合才能夠獲得比較好的效果。

然後他問我感覺自己的算法怎麼樣，我說一般，然後就沒有然後了，算法的問題也沒有問我，估計是對我失望了，哎，我自己也意識到了自己的算法不行了，是以自己這幾天惡補算法和作業系統，linux核心的東西。

下面是我的一個線性表的C++實作。

自己實作了一個異常類：

#ifndef EXCEPTION_H
#define EXCEPTION_H

// bad initializers
class BadInitializers {
   public:
      BadInitializers() {}
};

// insufficient memory
class NoMem {
   public:
      NoMem() {}
};

// improper array, find, insert, or delete index
// or deletion from empty structure
class OutOfBounds {
   public:
      OutOfBounds() {}
};

// use when operands should have matching size
class SizeMismatch {
   public:
      SizeMismatch() {}
};

// use when zero was expected
class MustBeZero {
   public:
      MustBeZero() {}
};

// use when zero was expected
class BadInput {
   public:
      BadInput() {}
};

#endif // EXCEPTION_H
           

下面是C++定義的線性表，由于使用了模闆類，是以其類定義和類實作不允許分開，隻能放在一個檔案中了：

#ifndef LINEARLIST_H
#define LINEARLIST_H

#include "Exception.h"
#include 

template
class LinearList
{
public:
    LinearList(int ListMaxSize = 10);
    ~LinearList(){delete [] element;}
    bool isEmpty() const{return length == 0;}     //判斷線性表是否為空
    int Length(){return length;}           //獲得線性表的長度
    LinearList& insert(int k,const T& x);    //向線性表的k中插入一個元素x
    LinearList& Delete(int k,T& x);          //删除線性表中k位置的元素，并傳回到x中
    bool Find(int k,T& x) const;                    //傳回線性表中第k個位置的元素
    int Search(const T& x) const;               //查找線性表中元素為x的位置
    LinearList& add(const T& x);                   //線上性表後面插入一個元素
    LinearList& clear();                     //清空線性表中的元素
    bool contains(T& x);                        //判斷線性表中是否含有 元素x
    T& get(int x);                                  //擷取x位置的元素
    LinearList& set(int index,T& x); //用指定的元素代替線性表中相應位置的元素
    void print();
private:
    int MaxSize;
    int length;
    T* element; //一維動态數組
};

template
LinearList::LinearList(int ListMaxSize)
{
    MaxSize = ListMaxSize;
    length = 0;
    element = new T[MaxSize];
}

template
bool LinearList::Find(int k, T &x) const
{
    /**
    *   如果提供的k值小于1或者是大于其現在的長度
    *   則傳回false
    *   如果提供的k值是可以的，則直接使x等于目前
    *   位置的值，并傳回true
    */
    if(k < 1 || k > length)
        return false;
    x = element[k];
    return true;
}

template
int LinearList::Search(const T &x) const
{
    /**
      * 尋找元素值為x的位置并傳回
      */
    for(int i = 0;i < length;i++){
        if(x == element[i])
            return ++i;
    }

    return 0;
}

template
LinearList& LinearList::insert(int k, const T &x)
{
    if(k < 0 || k > length)
        throw OutOfBounds();
    if(length == MaxSize)
        throw NoMem();
    for(int i = length;i >k;i--){
        element[i]  = element[i-1];
    }
    element[k] = x;
    length++;

    return *this;
}

template
LinearList& LinearList::Delete(int k, T &x)
{
    if(!Find(k,x))
        throw OutOfBounds();

    for(int i = k;i < length;i++){
        element[i-1] = element[i];
    }

     length--;
    return *this;
}

template
LinearList& LinearList::add(const T& x)
{
    if(length == MaxSize)
        throw NoMem();

    element[length] = x;
    length++;

    return *this;
}

template
void LinearList::print()
{
    for(int i = 0; i < this->Length();i++){
        std::cout << element[i] << std::endl;
    }
}

template
LinearList& LinearList::clear()
{
    for(int i = 0;i < this->Length();i++){
        element[i] = 0;
    }

    length = 0;

    return *this;
}

template
bool LinearList::contains(T &x)
{
    bool isContains = false;

    for(int i = 0;i < length;i++){
        if(element[i] == x)
            isContains = true;
    }

    return isContains;
}

template
T& LinearList::get(int x)
{
    if(x < 0 || x >= length)
        throw OutOfBounds();
    return element[x];
}

template
LinearList& LinearList::set(int index, T &x)
{
    if(index < 0 || index >= length)
        throw OutOfBounds();
    element[index] = x;
}

#endif // LINEARLIST_H
           

我一定能夠把算法搞好的。