iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
Software Development

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

[Day07]程式菜鳥自學C++資料結構演算法 – 鏈結串列實作應用

前言:講解完鏈結串列的概念後,緊接著就要來進行實作了。
跟做陣列的時候一樣,先創建一個新的專案,就可以開始編寫代碼了。
https://ithelp.ithome.com.tw/upload/images/20210921/20140187us6iN3y52n.png
https://ithelp.ithome.com.tw/upload/images/20210921/20140187qyDr4Uce5v.png
https://ithelp.ithome.com.tw/upload/images/20210921/20140187SC81t30APF.png
https://ithelp.ithome.com.tw/upload/images/20210921/20140187e2oVk74bw6.png

這樣就完成鏈結串列的建立和一些基本的功能了,寫了修改、新增、刪除還有這些程式在不同位置的應用,簡單測試一下沒甚麼大問題,有興趣的人可以嘗試看看其他功能
( ̄▽ ̄)~*
https://ithelp.ithome.com.tw/upload/images/20210921/20140187laY8cZBsQe.png

今日小結:這次的概念比較少,但程式卻有不少(一百多行了…),讀起來肯定沒比較輕鬆,還有給個小訣竅,在看程式碼的時候不是很常出現p = q之類的描述嗎?其實這個要從右看到左,剛好跟平常相反,也就要想成q等於p,如果覺得鏈結串列的程式碼很難懂的話,把圖畫出來也有助於理解喔!希望這些資訊有幫助到大家,明天也要繼續實作鏈結串列的其他應用。

template<typename T>
class LinkList {
	struct LNode //建立左節點結構
	{
		T data;
		LNode* next; //指向下一個元素的指針變量
	};
	LNode* head; //指向最前端的指針變量
public:
	LinkList() { //創建空的鏈結串列,並對head指針初始化
		head = new LNode();
		head->next = 0;
	}
	bool get(int i, T e) { //讀取鏈結串列的資料
		if (i <= 0) return false; //i結點小於0則錯誤
		LNode* p = head;  
		int j = 0; //j為現在訪問的元素
		while (p && j < i) {
			p = p->next;
			j++;
		}
		if (!p) return false; //如果p是空指針則錯誤
		e = p->data; return true; //如果p找到i號節點的數據,則放入引用變量e
	}
	bool set(int i, T e) { //修改鏈結串列的資料,和get概念類似
		if (i <= 0) return false; 
		LNode* p = head;
		int j = 0; 
		while (p && j < i) {
			p = p->next;
			j++;
		}
		if (!p) return false; 
		p->data = e; return true;
	}
	bool insert(int i, T e) { //插入元素至節點內
		if (i <= 0) return false;
		LNode* p = head;
		int j = 0;
		while (p && j < i-1) {
			p = p->next;
			j++;
		}
		if (!p) return false;
		LNode* s = new LNode(); //s為臨時的指針變量,存放新插入的元素
		s->data = e;
		s->next = p->next; //使p指向修改後的新節點
		p->next = s;
		return true;
	}
	bool remove(int i) { //刪除節點的函式,原理和insert相似
		if (i <= 0) return false;
		LNode* p = head;
		int j = 0;
		while (p && j < i) {
			p = p->next;
			j++;
		}
		if (!p) return false;
		LNode* q = p->next;
		p->next = q->next; 
		delete q;
		return true;
	}
	bool insert_front(T e) { //插入節點在鏈結串列最前端
		LNode* s = new LNode(); 
		if (!s) return false;
		s->data = e;
		s->next = head->next; 
		head->next = s;
		return true;
	}
	bool remove_front() { //刪除第一個節點
		LNode* q = head->next;
		head->next = q->next;
		delete q;
		return true;
	}
	bool push_back(T e) { //插入節點在鏈結串列最末端
		LNode* p = head;
		while (p->next)
			p = p->next;
		p->next = new LNode();
		if (!p->next) return false;
		p->next->next = 0; //p->next表示現在的尾節點,而p->next的下一個節點要成為新的尾節點
		p->next->data = e; //同時要把資料放進去
		return true;
	}
	void traverse(void (*fp)(T& e)) { //編寫遍歷操作,fp為函數指針,對p指向的data進行處理
		LNode* p = head->next;
		while (p) {
			fp(p->data);
			p = p->next;
		}
	}
    
    #include<iostream>
template<typename T>
void Print(T &ch) {
	std::cout << ch << " ";
}

主程式碼

#include <string>
using std::string;
int main(){
	LinkList<char> list;
	list.push_back('A'); list.traverse(Print); std::cout << std::endl;
	list.push_back('B'); list.traverse(Print); std::cout << std::endl;
	list.insert_front('C'); list.traverse(Print); std::cout << std::endl;
	list.insert_front('D'); list.traverse(Print); std::cout << std::endl;
	list.insert(3,'E'); list.traverse(Print); std::cout << std::endl;
	list.set(2, 'F'); list.traverse(Print); std::cout << std::endl;
}

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

尚未有邦友留言

立即登入留言