banner
cos

cos

愿热情永存，愿热爱不灭，愿生活无憾
github
tg_channel
bilibili
首頁封存关于♪歌单NFT作品集

模板類封裝(1)——單鏈表

#链表#c++#数据结构115
AI 翻譯
這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文
AI 生成的摘要
这篇文章介绍了一个自封装链表模板类的实现，使用C++语言编写。文章中包括了链表的基本操作，如按序号查找、按值查找、删除操作、插入操作、展示链表和获取链表长度等。此外，还介绍了一个新的操作函数ReverseList，用于将链表逆转。文章最后给出了完整的代码实现，并提醒使用者注意C++11特性中的nullptr的使用。

加入了 ReverseList 函數，逆轉單鏈表操作
改了個 bug，逆轉鏈表時特判一個結點的情況
又改了 N 個 bug，特判空鏈表的情況

試試模板類加上數據結構
肯定還是會有遺漏的地方的，歡迎指正
不多說，上代碼
ps是 c++11 特性，使用時需注意

結點定義#

template <class T> class LNode {
private:
	LNode* next;  //指針
	T Data;		  //數據
public:
	friend class List;
	LNode(T data = 0) {
		Data = data;
		next = nullptr;
	}
	void showdata() { cout << Data << endl; }
};

鏈表操作類定義#

template <class T> class List {
private:
	LNode<T>* head;	 //頭結點 不存儲元素但分配空間
public:
	friend class LNode<T>;
	List();
	~List();
	LNode<T>* FindKth(int K);  //按序號查找查找 查找鏈表中第K個元素
							   //若找到返回指向該結點的指針，找不到返回空指針
	LNode<T>* Find(T data);	 //按值查找: 查找元素data
							 //若找到返回指向該結點的指針，找不到返回空指針
	void
	Delete(int pos =
			   1);	//刪除操作(刪除鏈表第pos個位置上的結點) 默認為刪第一个元素
	void Insert(T data, int pos = 1);  //默認為頭插法 將data插入在第pos個元素
	void PrintList();				   //展示該鏈表
	int getLength();				   //獲取該鏈表長度
};

構造函數和析構函數#

頭結點不放數據，所有操作從 head->next 開始操作

//構造函數 為head分配空間，不放數據
template <class T> List<T>::List() {
	head = new LNode<T>;
	head->next = nullptr;
}
//析構函數 釋放空間
template <class T> List<T>::~List() {
	while (head->next) {
		Delete(1);
	}
	delete head;
}

操作類實現#

(1) 按序號查找#

查找鏈表中第 K 個元素，若找到返回指向該結點的指針，找不到或位置不合法返回空指針。

template <class T> LNode<T>* List<T>::FindKth(int K) {
	LNode<T>* p = head->next;  //第一個元素
	if (!p) {
		cout << "元素未找到，該鏈表是空的!" << endl;
		return nullptr;
	}
	int pos = 1;
	while (p->next && pos < K) {
		p = p->next;
		pos++;
	}
	if (pos == K)
		return p;  //找到第K個則返回指針
	else {		   //否則位置不合法，返回空指針
		cout << "位置不合法。" << endl;
		return nullptr;
	}
}

(2) 按值查找#

查找元素 data，若找到返回指向該結點的指針，若找不到，返回空指針。

template <class T> LNode<T>* List<T>::Find(T data) {
	LNode<T>* p = head->next;
	if (!p) {
		cout << "元素未找到，該鏈表是空的!" << endl;
		return nullptr;
	}
	while (p->next && p->Data != data)
		p = p->next;
	if (p->Data != data) {  //到最後了但元素仍不是data
		cout << "元素未找到!" << endl;
		return nullptr;
	}
	else
		return p;
}

(3) 刪除操作#

刪除鏈表第 pos 個位置上的結點，默認為刪第一个元素

template <class T>
void List<T>::Delete(int pos) {	 //刪除操作(刪除鏈表第i個位置上的結點)
	LNode<T>* p = head->next;
	if (!p) {
		cout << "刪除失敗，該鏈表是空的!" << endl;
		return;
	}
	if (pos == 1) {	 //若要刪除的是表的第一個結點
		head->next = p->next;
		if (p)
			delete p;
		return;
	}
	LNode<T>* s = FindKth(pos - 1);	 //找到第pos-1個元素
	if (!s) {
		cout << "第 " << pos-1 << " 個結點不存在!" << endl;
		return;
	}
	p = s->next;
	if (!p) {
		cout << "第 " << pos << " 個結點不存在!" << endl;
		return;
	} else {
		s->next = p->next;	// s指向第pos+1個結點
		delete p;			//將p從鏈表中刪除
		cout << "刪除成功!" << endl;
	}
}

(4) 插入操作#

默認為頭插法 將 data 插入在第 pos 個元素

template <class T> void List<T>::Insert(T data, int pos) {
	LNode<T>* p = new LNode<T>();//申請新節點p的空間
	p->Data = data;
	if (pos == 1) {	 //插在第一個
		p->next = head->next;
		head->next = p;
		cout << "插入成功!" << endl;
		return;
	}
	LNode<T>* s = FindKth(pos - 1);	 //找到第pos-1個元素
	if (!s) {
		cout << "位置不合法，插入失敗!" << endl;
		return;
	}
	p->next = s->next;
	s->next = p;
	cout << "插入成功!" << endl;
}

(5) 獲取該鏈表長度#

template <class T> int List<T>::getLength() {
	LNode<T>* p = head;	 // p指向表的第一個節點
	int cnt = 0;
	while (p->next) {
		p = p->next;
		cnt++;
	}
	return cnt;
}

(6) 展示該鏈表#

template <class T> void List<T>::PrintList() {
	LNode<T>* p = head;	 // p指向表的頭節點
	if (!head->next)
		cout << "該鏈表是空的!" << endl;
	int cnt = 0;
	while (p->next) {
		p = p->next;
		cnt++;
		cout << "第 " << cnt << " 個數據為:";
		p->showdata();
	}
	cout << "該鏈表總共有 " << cnt << " 個元素。" << endl;
}

(7) 逆轉該鏈表#

大致思想：
在這裡插入圖片描述
代碼：

template <class T> void List<T>::ReverseList() {
	LNode<T>* now = head->next;	 // now指向表的第一個節點
	if(!now) {
		cout << "該鏈表是空的!";
		return;
	}
	LNode<T>* tmp = now->next;	 // 指向now之後的一個節點
	while (tmp) {				 //把tmp放到頭結點後邊
		now->next = tmp->next;
		tmp->next = head->next;
		head->next = tmp;
		tmp = now->next;
	}
}

完整代碼#

#include <Windows.h>
#include <iostream>
#include <string>
using namespace std;
class Student {
public:
	string id;	  //學號
	string name;  //學生姓名
	int age;	  //年齡
	bool operator==(const Student& s) { return id == s.id; }
	bool operator!=(const Student& s) { return id != s.id; }
	bool operator<(const Student& s) { return id < s.id; }
	Student() : name("小明"), age(18) {}
	friend istream& operator>>(istream& is, Student& s) {
		is >> s.id >> s.name >> s.age;
		getchar();
		return is;
	}
	friend ostream& operator<<(ostream& os, const Student& s) {
		os << "學號:" << s.id << "  姓名:" << s.name << "  年齡:" << s.age
		   << endl;
		return os;
	}
};
template <class T> class List;
//結點定義
template <class T> class LNode {
private:
	LNode* next;  //指針
	T Data;		  //數據
public:
	friend class List<T>;
	LNode() { next = nullptr; }
	void showdata() { cout << Data << endl; }
};

//鏈表操作類定義
template <class T> class List {
private:
	LNode<T>* head;	 //頭結點 不存儲元素但分配空間
public:
	friend class LNode<T>;
	List();
	~List();
	LNode<T>* FindKth(int K);  //按序號查找查找 查找鏈表中第K個元素
							   //若找到返回指向該結點的指針，找不到返回空指針
	LNode<T>* Find(T data);	 //按值查找: 查找元素data
							 //若找到返回指向該結點的指針，找不到返回空指針
	void
	Delete(int pos =
			   1);	//刪除操作(刪除鏈表第pos個位置上的結點) 默認為刪第一个元素
	void Insert(T data, int pos = 1);  //默認為頭插法 將data插入在第pos個元素
	void PrintList();				   //展示該鏈表
	int getLength();				   //獲取該鏈表長度
	void ReverseList();				   //逆轉該鏈表
};

//鏈表操作類實現
//構造函數 為head分配空間，不放數據
template <class T> List<T>::List() {
	head = new LNode<T>;
	head->next = nullptr;
}
//析構函數 釋放空間
template <class T> List<T>::~List() {
	while (head->next) {
		Delete(1);
	}
	delete head;
}
//(1) 按序號查找::查找鏈表中第K個元素
// 若找到返回指向該結點的指針，找不到返回空指針
template <class T> LNode<T>* List<T>::FindKth(int K) {
	LNode<T>* p = head->next;  //第一個元素
	if (!p) {
		cout << "元素未找到，該鏈表是空的!" << endl;
		return nullptr;
	}
	int pos = 1;
	while (p->next && pos < K) {
		p = p->next;
		pos++;
	}
	if (pos == K)
		return p;  //找到第K個則返回指針
	else {		   //否則位置不合法，返回空指針
		cout << "位置不合法。" << endl;
		return nullptr;
	}
}

//(2) 按值查找: 查找元素data
//若找到返回指向該結點的指針，找不到返回空指針
template <class T> LNode<T>* List<T>::Find(T data) {
	LNode<T>* p = head->next;
	if (!p) {
		cout << "元素未找到，該鏈表是空的!" << endl;
		return nullptr;
	}
	while (p->next && p->Data != data)
		p = p->next;
	if (p->Data != data) {  //到最後了但元素仍不是data
		cout << "元素未找到!" << endl;
		return nullptr;
	}
	else
		return p;
}

//(3) 刪除操作:刪除鏈表第pos個位置上的結點,默認為刪第一个元素
template <class T>
void List<T>::Delete(int pos) {	 //刪除操作(刪除鏈表第i個位置上的結點)
	LNode<T>* p = head->next;
	if (!p) {
		cout << "刪除失敗，該鏈表是空的!" << endl;
		return;
	}
	if (pos == 1) {	 //若要刪除的是表的第一個結點
		head->next = p->next;
		if (p)
			delete p;
		return;
	}
	LNode<T>* s = FindKth(pos - 1);	 //找到第pos-1個元素
	if (!s) {
		cout << "第 " << pos-1 << " 個結點不存在!" << endl;
		return;
	}
	p = s->next;
	if (!p) {
		cout << "第 " << pos << " 個結點不存在!" << endl;
		return;
	} else {
		s->next = p->next;	// s指向第pos+1個結點
		delete p;			//將p從鏈表中刪除
		cout << "刪除成功!" << endl;
	}
}

//(4)插入操作 默認為頭插法 將data插入在第pos個元素
template <class T> void List<T>::Insert(T data, int pos) {
	LNode<T>* p = new LNode<T>();//申請新節點p的空間
	p->Data = data;
	if (pos == 1) {	 //插在第一個
		p->next = head->next;
		head->next = p;
		cout << "插入成功!" << endl;
		return;
	}
	LNode<T>* s = FindKth(pos - 1);	 //找到第pos-1個元素
	if (!s) {
		cout << "位置不合法，插入失敗!" << endl;
		return;
	}
	p->next = s->next;
	s->next = p;
	cout << "插入成功!" << endl;
}

//(5)獲取該鏈表長度
template <class T> int List<T>::getLength() {
	LNode<T>* p = head;	 // p指向表的頭節點
	int cnt = 0;
	while (p->next) {
		p = p->next;
		cnt++;
	}
	return cnt;
}
//(6)展示該鏈表
template <class T> void List<T>::PrintList() {
	LNode<T>* p = head;	 // p指向表的頭節點
	if (!head->next)
		cout << "該鏈表是空的!" << endl;
	int cnt = 0;
	while (p->next) {
		p = p->next;
		cnt++;
		cout << "第 " << cnt << " 個數據為:";
		p->showdata();
	}
	cout << "該鏈表總共有 " << cnt << " 個元素。" << endl;
}
//(7)逆轉該鏈表
template <class T> void List<T>::ReverseList() {
	LNode<T>* now = head->next;	 // now指向表的第一個節點
	if (!now) {
		cout << "該鏈表是空的!" << endl;
		return;
	}
	LNode<T>* tmp = now->next;	// 指向now之後的一個節點
	while (tmp) {				//把tmp放到頭結點後邊
		now->next = tmp->next;
		tmp->next = head->next;
		head->next = tmp;
		tmp = now->next;
	}
}
//主函數中調用的函數
template <class T> void input(List<T>& Head) {
	T data;
	cout << "請輸入鏈表元素(以空格間隔，回車結束):";
	cin >> data;
	Head.Insert(data);
}
template <class T> void remove(List<T>& Head) {
	int i;
	cout << "請輸入i(刪除鏈表第i個元素):";
	cin >> i;
	getchar();

	Head.Delete(i);
}
template <class T> void findKth(List<T>& Head) {
	int K;
	LNode<T>* s = nullptr;
	cout << "(按序號查找)請輸入K，查找鏈表中第K個元素:";
	cin >> K;
	getchar();
	s = Head.FindKth(K);
	if (!s)
		cout << "未找到!" << endl;
	else {
		cout << "查找成功!該元素為:";
		s->showdata();
	}
}
template <class T> void findData(List<T>& Head) {
	string data;
	cout << "請輸入待查找學生的學號:";
	cin >> data;
	Student t;
	t.id = data;
	getchar();
	LNode<T>* s = nullptr;
	s = Head.Find(t);
	if (!s)
		cout << "未找到該元素！" << endl;
	else {
		cout << "查找成功!該元素在鏈表中。";
	}
}
template <class T> void insert(List<T>& Head) {
	int i;
	T data;
	cout << "在鏈表第i個位置上插入一名學生信息,輸入i:";
	cin >> i;
	cout << "輸入該學生信息，學號 姓名 年齡以空格間隔，回車結束:";
	cin >> data;
	Head.Insert(data, i);
}
template <class T> inline void getlength(List<T>& Head) {
	cout << "該鏈表長度為:" << Head.getLength() << endl;
}
template <class T> void printList(List<T>& Head) {
	cout << "---------------------- List P --------------------" << endl;
	Head.PrintList();
}
template <class T> void reverseList(List<T>& Head) {
	T data;
	cout << "---------------------- List P --------------------" << endl;
	Head.PrintList();
	cout << endl;

	Head.ReverseList();
	cout << "------------- 逆轉後, List P ---------------" << endl;
	Head.PrintList();
}
int main() {
	List<Student> P;
	int choice;
	cout << "1 添加一名學生信息" << endl;
	cout << "2 刪除鏈表第i個元素" << endl;
	cout << "3 按序號查找鏈表中第K個元素" << endl;
	cout << "4 按值查找元素data" << endl;
	cout << "5 在鏈表第i個位置上插入元素data" << endl;
	cout << "6 獲取該鏈表長度" << endl;
	cout << "7 打印所有學生信息" << endl;
	cout << "8 逆轉該鏈表" << endl;
	cout << "9 結束" << endl;
	while (1) {
		cout << "菜單選擇(1-6):";
		cin >> choice;
		getchar();
		switch (choice) {
			case 1: input(P); break;
			case 2: remove(P); break;
			case 3: findKth(P); break;
			case 4: findData(P); break;
			case 5: insert(P); break;
			case 6: getlength(P); break;
			case 7: printList(P); break;
			case 8: reverseList(P); break;
			case 9: break;
			default: cout << "輸入錯誤，請重新輸入";
		}
		if (choice == 9)
			exit(0);
		cout << "按回車鍵繼續…" << endl;
		getchar();
	};
	return 0;
}
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。