資料結構與算法筆記(二) 線性表(數組描述)

c++常用的資料描述方法是數組描述和鍊式描述，線性表可以用來說明這兩方法，先介紹數組描述的線性表。後面再介紹鍊式描述的線性表。

C++ STL容器vector和list相當于線性表的數組描述和鍊式描述。數組描述方法将元素存儲在一個數組中，所有元素依次存儲在一片連續的存儲空間，這就是所謂的順序表

資料對象和資料結構：

資料對象是一組執行個體或值。 // 資料執行個體了解：資料對象int, 5是資料對象 int 的執行個體。還有string, digit之類的資料對象

資料對象通常會有一系列i相關的操作或者函數，把資料對象的執行個體轉換為該對象的另一個執行個體。或者轉化為其他資料對象的執行個體

資料結構：資料結構是一個資料對象，同時這個對象的執行個體以及構成執行個體的元素都存在着聯系，而這些聯系有相關的函數決定。

資料結構研究的是資料對象的描述以及相關函數的具體實作。

1.線性表資料結構：

線性表也稱有序表，它的每一個執行個體都是元素的有序集合。線性表執行個體的形式

資料結構與算法筆記(二) 線性表(數組描述)

,其中，

資料結構與算法筆記(二) 線性表(數組描述)

是線性表的元素，i是索引，n是線性表的長度。元素可以看成原子，他們本身的結構金額線性表無關。

線性表可以用抽象資料類型來說明(abstract data type, ADT)：即說明它的執行個體，也說明它的操作

LinearList

{

執行個體：

有限個元素的集合

操作：

empty();

size();

get(index);

indexOf(x); // 傳回元素的索引值

erase(index); // 删除某個元素

insert(index, x); // 插入元素

output(); // 輸出線性表

建立();

撤銷();

}

可以用抽象類來描述上面的資料類型LineraList

template<typename T>
class linearList
{
	public:
	virtual ~linearList()  {};   // 析構函數
	virtual bool empty() const=0;
	virtual int size() const=0;
	virtual T& get(int index) const=0;
	virtual int indexOf(T x) const=0;
	virtual void erase(int index) const=0;
	virtual void insert(int index, T& x) const=0;
	virtual void output() const=0;
}

上面的類相當于資料結構LinearList的基類，這是一個抽象類。

數組描述：

在數組描述中，用數組來存儲線性表的元素。我們需要一個映射，使得數組的每一個元素對應線性表的一個元素。可以用公式表示為：

location(i) = i

即：第i個線性表中的元素在數組中的位置是i.

改變數組的長度：

增加或者減少新的數組長度，首先要建立一個具有新長度的數組，把舊數組的元素複制到新的數組。

template<typename T>
void changeLength1D(T*& a, int oldLength, int newLength)
{
    if(newLength<0)
         throw illegalParameterValue("New length must >= 0");
    T* temp = new T[newLength];
    int number = min(oldLength, newLength);   // 複制的元素個數 
    copy(a, a+number, temp);
    delete []a ;    // 釋放老數組的記憶體空間 
    a = temp;
}

arrayList類：

定義一個Linearlist(抽象類)的派生類：這個派生類繼承了基類的方法的同時，也要定義一些自己特有的方法

arrayList類的基類：linearlist中定義一些純虛函數(注意春熙函數的定義方法)，是以linearList類是一個抽象類

虛函數virtual functiuonName() const=0表示的是定義為純虛函數，這個純虛函數是隻讀函數

虛函數virtual functiuonName()=0表示的是定義為純虛函數，這個純虛函數不是隻讀函數

linearlist.h

#ifndef LINEAR_LIST_H
#define LINEAR_LIST_H 

#include <iostream>
using namespace std;

template<typename T>    // 定義一個抽象類 
class linearList
{
	public:
	// 抽象類中的純虛函數 
	virtual ~linearList()  {};   // 析構函數
	virtual bool empty() const=0;
	virtual int size() const=0;
	virtual T& get(int index) const=0;
	virtual int indexOf(const T& x) const=0;     // 這裡定義的是虛函數，虛函數virtual functiuonName() const=0表示的是定義為純虛函數，這個純虛函數是隻讀函數 
	virtual void erase(int index) = 0;           // 這裡定義的是虛函數，虛函數virtual functiuonName()=0表示的是定義為純虛函數，這個純虛函數不是隻讀函數
	virtual void insert(int index, T x) = 0;
	// virtual void output(ostream& out) const=0;
};

#endif

arrayList.h

// 定義模闆類： lineaList的派生類
#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H
#include "E:\back_up\code\c_plus_code\digui\external_file\linearlist.h"
#include <iostream>

using namespace std;

template<typename T>
class arrayList : public linearList<T>
{
	private:   // 資料域
	T* element;
	int arrayLength;  // 一維數組的長度 
	int listSize;     // 線性表長度
	//void checkIndex(int index) const;
	public:
	arrayList();     // 無參構造函數 
	arrayList(int capacity);  //構造函數
	arrayList(const arrayList& array);   // 拷貝構造函數
	~arrayList();   //析構函數 
	// ADT方法：abstract data type  抽象資料類型 
	bool empty() const;   // 線性表是否為空
	int size() const;
	T& get(int index) const;
	int indexOf(const T x) const;
	void erase(int index);
	void insert(int index, T x);
	//void output(ostream& out) const;
	// 其他方法
	int capacity() const;
	// 重載流插入運算符 
	// friend ostream& operator<<(ostream& out, const arrayList<T>& array_list);   // 重載流插入運算符 <<隻能以友元函數的形式重載 
	void output() const;
	// 添加新的方法 
	void clear();
	void push_back(T x);    //  線上性表的最右端添加元素 
	T& pop_back();       // 線上性表的最右端删除元素， 且把值傳回來  
};

// 模闆類的實作
//  無參數構造函數 
 template <typename T>
 arrayList<T>::arrayList()
 {
 	arrayLength = 5;   // 初始數組的大小10
	listSize = 0;
	element = new T[arrayLength]; 
 } 
 
 // 有參數的構造函數
 template <typename T>
 arrayList<T>::arrayList(int capacity)
 {
 	if(capacity<1)
 	{
	 	// cout << "The Initial capacity= " << capacity << " Must > 0" << endl;
	 	//throw invalid_argument("The Initial capacity must bigger than zero");
	 	// cout << "Parameter wrong" << endl;
    }
    this->arrayLength = capacity;
	this->listSize = 0;
	this->element = new T[arrayLength]; 
 } 
 
 // 拷貝構造函數
 template <typename T>
 arrayList<T>::arrayList(const arrayList& array_list)
 {
 	arrayLength = array_list.arrayLength;
 	listSize = array_list.listSize;
 	element = new T[arrayLength];
 	for(int i=0; i<listSize; i++)
 	{
	 	element[i] = array_list.element[i];
    }
 } 
 
 // 析構函數
 template<typename T>
 arrayList<T>::~arrayList()
 {
 	delete [] element;
 } 
 
// ADT方法， 抽象資料類型   arralyList基本方法實作
template<typename T>
bool arrayList<T>::empty() const
{
	return listSize==0;
} 

template<typename T>
int arrayList<T>::size() const   // 傳回線性表的長度 
{
	return listSize;
} 

template<typename T>
T& arrayList<T>::get(int index) const
{
	return element[index];
}

template<typename T>
int arrayList<T>::indexOf(const T x) const
{
	int i;
	bool found_flag = false;
 	for(i=0; i<listSize; i++)
    {
 		if(element[i]==x)
 		{
 			found_flag = true;
		 	break;
        }
 	}	
 	return (found_flag)?i:-1; 
}
 
template<typename T>
void arrayList<T>::erase(int index)  // 删除線性表中的某個元素
{
	// 添加索引的檢查函數 checkindex中定義一個異常類 
	for(int i=index; i<listSize-1; i++)
	{
		element[i] = element[i+1];
	}
	listSize--;
} 

template<typename T>
void arrayList<T>::insert(int index, T x)   // 插入一個元素
{
    //int old_listSize = listSize;   // 線性表的原來長度 
	//listSize++;                    // 插入元素後線性表的長度 
	if(listSize>=arrayLength)       // 現象表中的元素個數超出數組的大小
	{
		arrayLength *= 2;   // 增加數組的大小 
		T* old = element;
		element = new T[arrayLength];  // 新數組
		//int i;
		for(int i=0; i<listSize; i++)
		{
			element[i] = old[i];   // 先把element中的元素複制過來 
		}
		delete [] old;    // 釋放old_ListSize的記憶體	 
	} 
	
	// 再執行插入操作 
	int j;
	for(j=listSize-1; j>=index; j--)
	{
		element[j+1] = element[j];   
	} 
	element[++j] = x;
	listSize++;
	
} 
 
template<typename T>
int arrayList<T>::capacity() const   // 傳回數組的大小 
{
	return arrayLength;   
}

template<typename T>
void arrayList<T>::clear()
{
	listSize = 0;    // 線性表長度為0 
	delete [] element;    // 釋放原來的記憶體 
	arrayLength = 5;      
	element = new T[arrayLength];   //配置設定較小的記憶體 
}
/*
template<typename T>
ostream& operator<<(ostream& out, const arrayList<T>& array_list)
{
	for(int i=0; i<listSize; i++)
	{
		out << element[i] << " ";
		if(i%10==0)
		   out << endl;
	}
	out << endl;
} 
*/

template<typename T>
void arrayList<T>::output() const
{
	if(listSize == 0)
	{
		cout << "Empty array !" << endl;
		return;
	}
		
	for(int i=0; i<listSize; i++)
	{
		cout << element[i] << " ";
		if((i+1)%10==0) 
		   cout << endl;
	}
	cout << endl;
}
 
template<typename T>
void arrayList<T>::push_back(T x)
{
	if(listSize>=arrayLength)  // 需要擴充數組的大小
	{
		arrayLength *= 2;
		T* old = element;
		element = new T[arrayLength]; 
		for(int i=0; i<listSize; i++)
		{
			element[i] = old[i];
		}
		delete [] old;  // 釋放記憶體 
	} 
	element[listSize++] = x;   // 線上性表的最右端插入元素 
} 

template<typename T> 
T& arrayList<T>::pop_back()
{
	T& tmp = element[listSize-1];  
	listSize--;
	return tmp;
}  

#endif

main.cpp

#include <iostream>
#include <string>
#include <time.h>
#include "E:\back_up\code\c_plus_code\digui\external_file\linearlist.h"
#include "E:\back_up\code\c_plus_code\digui\external_file\arraylist.h" 
#include "E:\back_up\code\c_plus_code\digui\external_file\chain.h"

using namespace std;

// 實作友元函數

 
int main(int argc, char *argv[])
{
	
    arrayList<double> array(3);
    for(int i=0; i<10; i++)
    {
    	array.insert(i, i*i);
    }
    cout << "array capacity is " << array.size() << endl;
    array.output();
	array.erase(4);
	array.output(); 
	array.insert(4, 10);
	array.output();
	array.clear();
	cout << "array capacity is " << array.size() << endl;
	array.output(); 
	
	array.push_back(1.23);   // 配置設定的最小記憶體5 
	array.push_back(2.3);
	array.push_back(3.3);
	array.push_back(9.6);
	array.push_back(9.1);
	array.push_back(11.2);
	array.push_back(3.1415); 
	array.output();
	double num = array.pop_back();
	cout << "The pop number is " << num << endl;
	array.output();
    
	return 0;     
}

運作結果：

資料結構與算法筆記(二) 線性表(數組描述)

再動态的增加數組的長度的時候，每次為什麼不是+1，+2，而是加倍：

無論數組每次增加多少，都不影響每一次最壞的插入操作時間

資料結構與算法筆記(二) 線性表(數組描述)

,但是影響連續插入時的漸進時間複雜度，假設從長度為1的表開始插入資料，每次都插入到表尾，是以不需要移動表裡的元素,時間複雜度是

資料結構與算法筆記(二) 線性表(數組描述)

。

假設執行

資料結構與算法筆記(二) 線性表(數組描述)

次插入操作，則n次插入的時間為T:

資料結構與算法筆記(二) 線性表(數組描述)

其中A是執行插入操作的時間複雜度：

資料結構與算法筆記(二) 線性表(數組描述)

數組增加長度的操作，代碼如下

//int old_listSize = listSize;   // 線性表的原來長度 
//listSize++;                    // 插入元素後線性表的長度 
if(listSize>=arrayLength)       // 現象表中的元素個數超出數組的大小
{
	arrayLength *= 2;   // 增加數組的大小 
	T* old = element;
	element = new T[arrayLength];  // 新數組
	//int i;
	for(int i=0; i<listSize; i++)
	{
		element[i] = old[i];   // 先把element中的元素複制過來 
	}
	delete [] old;    // 釋放old_ListSize的記憶體	 
}

對于B來說，如果數組長度按照+1,則數組改變長度的時間是：

資料結構與算法筆記(二) 線性表(數組描述)

則：

資料結構與算法筆記(二) 線性表(數組描述)

如果數組的長度每次增加兩倍：

n次插入操作，

資料結構與算法筆記(二) 線性表(數組描述)

，其中k就是執行數組擴容的次數，每次擴容的時間複雜度2的k次方，也即數組擴容前

資料結構與算法筆記(二) 線性表(數組描述)

個元素進行複制

是以k次插入數組擴容的時間複雜度是B,則

資料結構與算法筆記(二) 線性表(數組描述)

是以有：

資料結構與算法筆記(二) 線性表(數組描述)

這就是數組長度每次都增加兩倍的原因：

-------------------------------------------------------分割線---------------------------------------------------------------

添加新的方法，對arrayList進行修改

1.當線性表中的元素個數小于數組長度的1/4時，數組長度減半

2. 添加異常類checkIndex();

資料結構與算法筆記(二) 線性表(數組描述)

1.線性表資料結構：

數組描述：

arrayList類：

添加新的方法，對arrayList進行修改

繼續閱讀

無向圖連通分量的計算

散列函數及哈希表（python實作）

順序表的簡單程式code：

Dijkstra不能得到含有負權邊圖的單源最短路徑

非線性回歸模型的原理及評估——解決行星軌道的拟合問題概述回歸統計普通和權重最小二乘法 L o g i s t i c Logistic Logistic回歸拟合一個行星軌道

Heap的java實作

Binary Tree Preorder Traversal @leetcode

約瑟夫環（Data structure and algorithm -C language）—— #YU 約瑟夫環

資料結構樹與二叉樹筆記合集（C語言）完結

鍊式棧實作括号比對問題

二叉樹的建立和周遊二叉樹的建立二叉樹的周遊：具體程式實作代碼和遞歸建立二叉樹和通路二叉樹代碼，歡迎提議

二叉樹的基本操作（遞歸和非遞歸）遞歸：非遞歸：

[leetcode]Combination Sum II

字元串的模式比對算法（思想+python實作）

字母結點型DSU

圖的兩種存儲方式：鄰接表、鄰接矩陣