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

前言：昨天简单实作了链结串列，今天要来介绍进阶一点的应用，第一个是利用之前写的get()和set()进行下标元素符号的读写，第二个是要做链结串列的反转。

甚麽是下标？下标是一个可以快速存取及设置值的方式，光看中文可能不太清楚什麽意思，其实在前面章节介绍阵列及链结串列时已经有接触过，紧接在名称後的中括号[]，括号内填入阵列的索引值，就可存取或设置值。

前言讲完了就直接开始吧，打开之前链结串列的档案就好，不用再创一个新的！

一. 下标运算符读写：
要先写一个判断链结串列大小的函示。
(上一篇忘记补上了，真对不起(≧д≦ヾ))

再来就是下标运算的读写了，因为和get()都是属於读写类型，所以程序码相似度很高。

接着就是输出结果

可以看到下标是1的Blue改成Purple了(Yello的下标是0)。

这样就完成下标的读写了，这里用字串呈现比较清楚，下一篇会解释怎麽使用字串显示资料。

二. 链结串列的反转：

可以看到链结串列已经反转成功了。

今日小结：这样就讨论完阵列跟链结串列了，辛苦各位了。但还有一段路要走，今天的内容比较少，偶尔这样也不错嘛(￣▽￣)~*最後再用表格的方式帮大家复习阵列和链结串列的特性比较，明天就要进入下一个单元「堆叠」了。

最後在附上这一篇和上一篇的程序码

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;
		}
	}
	void converse() {
		LNode* p = head->next;
		head->next = 0;
		while (p) { //前插法到头节点後
			LNode* q = p->next; //保存下一个节点位址
			p->next = head->next; //指向新链结串列的首节点
			head->next = p;
			p = q;
		}
	}

	int size() { //判断链结串列大小
		LNode* p = head->next;
		int j = 0;
		while (p) {
			j++;
			p = p->next;
		}
		return j;
	}
	
	T& operator[](int i) {//编写下标运算函式，并传回引用变量T
		if (i < 0) throw "下标异常";
		LNode* p = head; int j = -1;
		while (p && j < i) {
			p = p->next;
			j++;
		}
		if (!p) throw "下标异常";
		return p->data;
	}

};
#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;


	LinkList<string> list2;
	list2.push_back("Blue");
	list2.push_back("Red");
	list2.insert_front("Yello");
	list2.push_back("Black");
	list2.traverse(Print); std::cout << std::endl;
	
	list2[1] = "Purple";
	for (int i = 0; i < list2.size(); i++)
		std::cout << list2[i] << " ";
	std::cout << std::endl;

	list2.converse();
	list2.traverse(Print); std::cout << std::endl;

}