[Day07]程序菜鸟自学C++资料结构演算法 – 链结串列实作应用

前言：讲解完链结串列的概念後，紧接着就要来进行实作了。
跟做阵列的时候一样，先创建一个新的专案，就可以开始编写代码了。

这样就完成链结串列的建立和一些基本的功能了，写了修改、新增、删除还有这些程序在不同位置的应用，简单测试一下没甚麽大问题，有兴趣的人可以尝试看看其他功能
(￣▽￣)~*

今日小结：这次的概念比较少，但程序却有不少(一百多行了…)，读起来肯定没比较轻松，还有给个小诀窍，在看程序码的时候不是很常出现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;
}