C++模闆實作動态數組及執行個體化（優化質數尋找算法）

前言：淺談動态數組

在C++與其他進階語言中，本就存在着靜态數組這一線性資料結構。靜态數組是具有固定元素個數的群體，每個元素都可通過下标索引直接通路。

盡管靜态數組是十分重要的資料結構，但也存在缺陷，因為其大小在編譯時就已經确定，故在運作時無法修改。

最關鍵的是，因為靜态數組會因為數組越界問題帶來重大安全隐患，故動态數組在某些應用場景下就顯得尤為重要了。

文章目錄

• 前言：淺談動态數組
• 一、dynamic Array代碼實作
• 二、有關IS_Prime的算法
• • Prime(質數)是個啥家夥？
  • 引入：
  • • 正常法：
    • 正常法改進：
    • **埃拉托斯特尼篩法！**
• 三、動态數組模闆執行個體化實作埃氏算法
• 四、總結

一、dynamic Array代碼實作

//此檔案名為Array
#include <cassert>

template<class T>
class Array{
	public:
		Array(long long sz=100); // constructor
		Array(const Array<T> &a);  //copy_constructor
		~Array();  //destructor
		Array<T>& operator = (const Array<T> &array); //重載運算符 = 實作指派操作
		T &operator [] (long long i); //重載索引運算符 [] 實作下标索引
		const T &operator [] (long long i) const;
		operator T*(); //重載“星星運算符 ”讓程式更漂亮 ^&^
		operator const T*() const;
		long long get_size() const; //擷取私有成員size外部接口
		void resize(long long sz); //更改私有成員size外部接口

	private:
			T* list;	//T類型指針，為動态數組首位址
			long long size; //數組大小，這兒也可以定義一個常量宏，每次更改#define size number即可
};
//構造函數
template<class T>
Array<T>::Array(long long sz){
	assert(sz>=0);	//judge size，其大小應該為非負數
	size=sz;
	list=new T[size]; //動态配置設定size個T型記憶體空間，還可以使用<cstdlib>頭檔案下的malloc函數
}

//析構函數
template<class T>
Array<T>::~Array(){
	delete [] list;	//注意不同于釋放單個記憶體的方式，malloc函數對應為 free關鍵字
}

//複制構造函數
template<class T>
Array<T>::Array(const Array<T> &a){
	size=a.size;      //從右值對象a中取得size大小
	list=new T[size];
	for(long long i=0;i<size;i++)	//逐個指派
		list[i]=a.list[i];
}

//重載運算符“=”
template<class T>
Array<T>& Array<T>::operator =(const Array<T> &array){
	if(array!=this)	//若本對象數組大小與array不一，則删除本對象并重新配置設定記憶體空間！
	{
		if(size!=array.size)
		{
			delete [] list;
			size=array.size;
			list=new T[size];
		}
		//若等大，則直接進行指派操作
		for(long long i=0;i<size;i++){
			list[i]=array.lsit[i];
		}
	}
	return *this; //在數組很大的情況下，傳回本對象的引用避免了臨時變量的建立，節省了時間特别是空間！
	}
	
//重載下标運算符[]
template<class T>
T & Array<T>::operator [](long long n){
	assert(0<=n&&n<=size);
	return list[n];//注意，傳回值為單個T類型資料
}

//重載const版本
template<class T>
const T & Array<T>::operator [](long long n)const{
	assert(0<=n&&n<=size);
	return list[n];
}

//重載星星運算符，将array類的對象名轉化為T類型的指針！
template <class T>
Array<T>::operator T*(){
	return list;
}
//const版本
template <class T>
Array<T>::operator const T*()const{
	return list;
}

//擷取數組大小
template <class T>
long long Array<T>::get_size() const{
	 return size;
}
//更改數組大小，大家自行分析一下語句作用，大部分操作上文已實作。
template <class T>
void Array<T>::resize(long long sz){
	assert(sz>=0);
	if(sz==this->size)
	   return ;
	T *newlist=new T[sz];
	long long n=sz<size?sz:size;
	size=sz;
	for(long long i=0;i<n;i++)
		newlist[i]=list[i];
		delete [] list;
		list=newlist;
}
int main(){
	return 0;
}
           

二、有關IS_Prime的算法

Prime(質數)是個啥家夥？

百度她說啊：

“質數又叫素數，是在大于1的自然數中，除1和其本身以外沒有其他因數的自然數。例：7隻能被1、7整除，不能被其他數字整除，那麼7就是質數。質數有：2、3、5、7、11、13、17等。其中，2是最小的質數，也是唯一的偶數質數。

引入：

現在來做道大家都見識過的初級程式設計題：

請實作一個IS_Prime函數，對于給定的整型參數 N>=1，該函數将把自然數中，小于 N 的質數，從小到大列印出來。

如，當 N = 10，則列印出：

2 3 5 7

正常法：

即簡單暴力枚舉法，從2開始(因1非質)，設定循環變量N，通過試除法（這裡不多贅述，就時根據質數定義來的，若未了解，建議大家自己給模拟出來），逐個判斷其是否為質數，因為是逐個，是以2~N-1間每個數都需要判斷，若符合質數判斷函數，則将其存下 。

bool isPrime(int n){
	bool flag=true;
    for(int i = 2; i < n; i++){
        if (n % i == 0) {
            flag=false;
            break;
        }
    }
    return flag;
}

//main函數如下：

int main(){
	int n=100;
	for(int i=2;i<=n;i++)
	{
		if(isPrime(i))
		cout<<i<<endl;
	}
	return 0;
}
//寫出main函數的意義是為了告訴大家在main中還有一個for循環，
//是以時間複雜度将近n的平方；
           

正常法改進：

我們在現有算法一的基礎上進行改進~

在枚舉過程中，如果能找準枚舉變量或者減少問題規模，那麼就是更好的算法！

由質數的定義還可以知道，偶數一定為非質數。是以，可将循環邊界除以二，那麼算法的平均複雜度将提高一倍！

我們再稍微聰明一點！除了2以外，所有的質因數都是奇數。是以，我們就先嘗試 2，然後再嘗試從 3 開始一直到 N/2 的所有奇數。

嘿嘿，或許大家也知道：其實隻要從 2 一直嘗試到√N，就可以了。估計有些網友想不通了，為什麼隻要到√N 即可？

簡單d釋一下：因數都是成對出現的。比如，100的因數有：1和100，2和50，4和25，5和20，10和10。看出來沒有？成對的因數，其中一個必然小于等于100的開平方，另一個大于等于100的開平方。我們隻要找到N的一對因數，那麼其就為非質數了，是以問題轉化為尋找N的較小因數，而它的範圍在2~√N 之間。

　　

那麼，就有小夥伴一下子能想到，尋找2~√N之間的奇數即可。

是以到目前為止，最優算法如下：

bool isPrime(int n){
	bool flag=true;
    for(int i = 2; i < sqrt(n); i++){
        if (n%2==0||n%i==0) {
            flag=false;
            break;
        }
    }
    return flag;
}//注意，此時main函數仍同上
           

可是呐，學無止境，下面給大家介紹一種時間複雜度接近n的算法：

埃拉托斯特尼篩法！

埃拉托斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由希臘數學家埃拉托斯特尼所提出的一種簡單檢定素數的算法。要得到自然數n以内的全部素數，必須把不大于根号n的所有素數的倍數剔除，剩下的就是素數。

首先，2是公認最小的質數，是以，先把所有2的倍數去掉；然後剩下的那些大于2的數裡面，最小的是3，是以3也是質數；然後把所有3的倍數都去掉，剩下的那些大于3的數裡面，最小的是5，是以5也是質數……

　　

　　上述過程不斷重複，就可以把某個範圍内的合數全都除去（就像被篩子篩掉一樣），剩下的就是質數了。維基百科上有一張很形象的動畫，能直覺地展現出篩法的工作過程。

　

三、動态數組模闆執行個體化實作埃氏算法

//注意，需包含實作動态數組模闆的檔案Arrady
#include <iostream>
#include <iomanip>
#include "Array.h"
using namespace std;


int main(){
	Array<long long> a(10);//用于存放質數的動态數組
	long long cnt=0;
	long long n;
	cout<<" Please Enter a value :";
	cin>>n;
	for(long long i=2;i<=n;i++){
		bool isPrime=1;
		for(long long j=0;j<cnt;j++)
		if(i%a[j]==0)
		{
			isPrime=false;
			break;
		}

		//把i寫入質數數組
		if(isPrime)
		{
			//如果數組滿了，則動态加倍
			if(cnt==a.get_size())
				a.resize(cnt*2);
				
				a[cnt++]=i;
		}
	}
	
	//輸出質數
	for(long long i=0;i<cnt;i++)
			cout<<setw(8)<<a[i]<<endl;//setw()為字寬
	return 0;
}
           

列印百萬以内的質數，注意，隻跑了48.14seconds!

而使用前面幾種算法，估計沒吃個瓜的時間，是看不到它的列印結果咯…

四、總結

關于C++模闆的知識，這也隻是冰山一角，不過卻也可以使用它來解決一些問題，如實作這動态數組，乃至其他資料結構。

而有關質數的算法，以上算法為一個循序漸進的改進過程，最終可以在時間複雜度上達到一個不錯的效果。

正所謂：山外青山樓外樓，算法怎能就此休？除埃氏篩法外，還有着線性篩法等超乎想象的高效率算法！并且，此文章并未就空間複雜度改進算法。

下面給出兩篇參考部落格，以飨讀者：

線性篩法

質數高效算法時間、空間複雜度的逐漸求精

如果大家覺得有所收獲還請“飛鴻踏雪”，還請各位大佬指點評價！