iT邦幫忙

2021 iThome 鐵人賽

DAY 5
0
Software Development

程式菜鳥自學C++資料結構演算法系列 第 5

[Day05]程式菜鳥自學C++資料結構演算法 – 陣列Array List實作之二

前言:昨天介紹了如何建立專案、建立空陣列、讀取存放資料及修改儲存空間,今天要繼續實作陣列的其他功能。

編寫set()函式修改陣列中的資料。
https://ithelp.ithome.com.tw/upload/images/20210919/201401878hvQmgAKE2.png
https://ithelp.ithome.com.tw/upload/images/20210919/20140187LVFS2OBNgG.png

可以看到陣列的原本第二個資料B已修改成E。
https://ithelp.ithome.com.tw/upload/images/20210919/20140187jMBuCU16JH.png

編寫insert()函式插入新的資料在陣列之中。
https://ithelp.ithome.com.tw/upload/images/20210919/20140187pO2j3bX73j.png
https://ithelp.ithome.com.tw/upload/images/20210919/20140187QwEOI9C8dC.png

可以看到在陣列的第三個位置中插入F。
https://ithelp.ithome.com.tw/upload/images/20210919/20140187jzSMHzEKdf.png

接著編寫remove()函式移除陣列中的資料
https://ithelp.ithome.com.tw/upload/images/20210919/20140187NzHDECLp2T.png
https://ithelp.ithome.com.tw/upload/images/20210919/201401870LrPNR4NUx.png

可以看到原本在第三個位置的F被移除
https://ithelp.ithome.com.tw/upload/images/20210919/20140187umIoMtfbaN.png

編寫pop_back刪除最後一個元素。
https://ithelp.ithome.com.tw/upload/images/20210919/20140187XpzV0rYa4R.png
https://ithelp.ithome.com.tw/upload/images/20210919/201401871CrJHLvRcS.png

可以看到在最後一個位置的元素D被移除了
https://ithelp.ithome.com.tw/upload/images/20210919/20140187RWqEL89A9q.png

邊寫remove_front()函式刪除第一個元素。
https://ithelp.ithome.com.tw/upload/images/20210919/20140187IqcvWhaIvC.png
https://ithelp.ithome.com.tw/upload/images/20210919/20140187SYAgt1l44L.png

第一個位置的A已成功刪除。
https://ithelp.ithome.com.tw/upload/images/20210919/20140187zkWbY5cpWj.png

編寫find()函式查找元素所在的位置。
https://ithelp.ithome.com.tw/upload/images/20210919/20140187CDSKqlve7Z.png
https://ithelp.ithome.com.tw/upload/images/20210919/20140187BXtN0TSZbB.png

假設要查找C的位置,結果如下。
https://ithelp.ithome.com.tw/upload/images/20210919/20140187wugM5pxpwU.png

那如果陣列有多筆相同的資料,要怎麼查找?
寫一個for迴圈,在新增一個變數p存取A的位置,每遇到一次A就印出位置一次,直到陣列結束,就可以囉!
https://ithelp.ithome.com.tw/upload/images/20210919/20140187iPcFcrsI3Q.png
https://ithelp.ithome.com.tw/upload/images/20210919/20140187fs2BBDpVxQ.png

今日小結:呼~陣列的實作就先到這邊告一段落,其實還有很多應用,但是要全部介紹完恐怕會花上太多篇幅,有機會再跟大家分享。雖然這些實作都算是基礎,不過以初學者來說要完全理解也不是甚麼輕鬆事(包括我(≧д≦ヾ)),雖然程式碼看起來很複雜,但只要考清楚陣列在位置上的變動,就可以比較快理解,好了,明天就來介紹陣列的兄弟「鏈結串列」!

template<typename T> //將資料型態參數化的功能,代號為T
class SqlList {
	T* data; //指針變量
	int capacity, n; //分配空間(整數int),n表示數據元素的個數,先設為0

public:
	SqlList(int cap = 3) { //創建一個空的SqlList(不包含任何元素)
		data = new T[cap]; //給予數據成員讓其初始化 
		if(!data) throw "SqlList內存空間分配失敗"; //檢查空間是否成功分配{capacity = 0; n = 0; return}
		capacity = cap; n = 0;
	}
	bool get(int i, T& e) { //讀取,把數據元素放入引用變量e內
		if (i < 1 || i > n) 
			return false;
		e = data[i - 1]; 
		return true;
    }
	bool set(int i, T e) { //修改,把i資料修改成e
		if (i < 1 || i > n) 
			return false;
		data[i - 1] = e; 
		return true;
	}
	bool push_back(T e) { //編寫push_back(放在陣列最尾端)函示來存取陣列中的資料
		if (n==capacity) {
			if (!realloc()) {
				return false;
			}
		 }
		data[n] = e;
		n++;
		return true;
	}
	int size() { //返回當前資料的個數
		return n;
	}
	bool insert(int i, T e) { //在i號位置插入資料e
		if (i < 1 || i > n + 1) return false;
		if (n == capacity) 
			if (!realloc()) return false;
			
		for (int j = n; j >= i; j--) {
			data[j] = data[j - 1];
		}
		data[i - 1] = e;
		n++;
		return true;
	}
	bool remove(int i) { //刪除第i號元素
		if (i < 1 || i > n) return false;
		
		for (int j = i+1; j <= n; j++) {
			data[j - 2] = data[j - 1];
		}
		n--;
		return true;
	}
	bool pop_back() {
		if (n == 0) return false;
		n--;
		return true;
	}
	bool remove_front() {
		for (int j = 2; j <= n; j++) {
			data[j - 2] = data[j - 1];
		}
		n--;
		return true;
	}
	int find(int pos,T e) { //查找元素所在的位置,從pos(重新定義)位置開始找
		for (int i = pos; i <= n; i++)
			if (data[i-1] == e) {
				return i;
			}
		return 0;
	}
private: //分配供多空間給陣列
	bool realloc() {
		T* p = new T[2 * capacity];
		if (!p) return false;
		for (int i = 0; i < n; i++) 
			p[i] = data[i];
		delete[] data;
		data = p;
		capacity *= 2;
		return true;
	}
	
};
#include<iostream>
template<typename T>
void print(SqlList<T>& L) { //編寫print函示
	T e; //數據元素類型e為T類型
	for (int i = 1; i <= L.size(); i++) {
		L.get(i, e);
		std::cout << e << " ";
	}
	std::cout << std::endl;

}

#include<iostream>
int main() { //編寫主程式
	SqlList<char> list; //建立SqlList的變量,數據元素類型設為字元(char)
	char ch;
	if (!list.get(1, ch))std::cout << "沒有找到 \n"; //箭頭方向"<<"是一個運算子。
	else std::cout << ch << std::endl;  //endl就是這一行到這邊結束換下一行(只能輸出,不能輸入)。
	list.push_back('A'); print(list);
	list.push_back('B'); print(list);
	list.push_back('C'); print(list);
	list.push_back('D'); print(list);
	list.set(2, 'E'); print(list);
	list.insert(3, 'F'); print(list);
	list.remove(3); print(list);
	list.pop_back(); print(list);
	list.remove_front(); print(list);

	int i = list.find(1, 'C');
	if (i >= 0) std::cout << "查找成功,位置是:" << i << std::endl;

	list.insert(2, 'A'); 
	list.push_back('A'); print(list);

	
	for (int p = 1; p < list.size();) {
		int i = list.find(p, 'A');
		if (i >= 0) std::cout << "查找成功,位置是:" << i << std::endl;
		p = i + 1;
	}
	
}


上一篇
[Day04]程式菜鳥自學C++資料結構演算法 – 陣列Array List實作之一
下一篇
[Day06]程式菜鳥自學C++資料結構演算法 – 常見的線性串列其一:鏈結串列Linked List
系列文
程式菜鳥自學C++資料結構演算法30

尚未有邦友留言

立即登入留言