banner
cos

cos

愿热情永存，愿热爱不灭，愿生活无憾
github
tg_channel
bilibili
ホームアーカイブ关于♪歌单NFT作品集

テンプレートクラスのカプセル化(1)——単方向リスト

#链表#c++#数据结构115
AI 翻訳
この記事はAIを通じて中国語から日本語に翻訳されました。原文を表示
AI が生成した要約
This is a template class implementation of a singly linked list in C++. It includes functions such as finding an element by index or value, deleting an element, inserting an element, printing the list, and reversing the list. The code also includes a Node class and a List class, with the List class having a constructor and destructor. The code is written in C++ and uses nullptr, a C++11 feature.

ReverseList 関数を追加し、単方向リストの逆転操作を行いました
バグを修正し、リストを逆転する際に特別なケースとして 1 つのノードの状況を処理しました
さらに N 個のバグを修正し、空のリストの特別なケースを処理しました

テンプレートクラスにデータ構造を追加してみました
まだ見落としがあるかもしれませんので、指摘を歓迎します
多くは語らず、コードを示します
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個の要素を検索
							   //見つかった場合はそのノードへのポインタを返し、見つからなければnullptrを返す
	LNode<T>* Find(T data);	 //値で検索: 要素dataを検索
							 //見つかった場合はそのノードへのポインタを返し、見つからなければnullptrを返す
	void
	Delete(int pos =
			   1);	//削除操作(リストのpos番目のノードを削除) デフォルトは最初の要素を削除
	void Insert(T data, int pos = 1);  //デフォルトは頭挿入法 dataをpos番目の要素に挿入
	void PrintList();				   //リストを表示
	int getLength();				   //リストの長さを取得
};

コンストラクタとデストラクタ#

ヘッドノードにはデータを格納せず、すべての操作は head->next から開始します

//コンストラクタ ヘッドにスペースを割り当て、データを格納しない
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 個の要素を検索し、見つかった場合はそのノードへのポインタを返し、見つからない場合や位置が不正な場合は nullptr を返します。

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 {		   //そうでなければ位置が不正、nullptrを返す
		cout << "位置が不正です。" << endl;
		return nullptr;
	}
}

(2) 値で検索#

要素 data を検索し、見つかった場合はそのノードへのポインタを返し、見つからない場合は nullptr を返します。

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

完全なコード#

#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個の要素を検索
							   //見つかった場合はそのノードへのポインタを返し、見つからなければnullptrを返す
	LNode<T>* Find(T data);	 //値で検索: 要素dataを検索
							 //見つかった場合はそのノードへのポインタを返し、見つからなければnullptrを返す
	void
	Delete(int pos =
			   1);	//削除操作(リストのpos番目のノードを削除) デフォルトは最初の要素を削除
	void Insert(T data, int pos = 1);  //デフォルトは頭挿入法 dataをpos番目の要素に挿入
	void PrintList();				   //リストを表示
	int getLength();				   //リストの長さを取得
	void ReverseList();				   //リストを逆転
};

//リスト操作クラスの実装
//コンストラクタ ヘッドにスペースを割り当て、データを格納しない
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個の要素を検索
// 見つかった場合はそのノードへのポインタを返し、見つからなければnullptrを返す
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 {		   //そうでなければ位置が不正、nullptrを返す
		cout << "位置が不正です。" << endl;
		return nullptr;
	}
}

//(2) 値で検索: 要素dataを検索
//見つかった場合はそのノードへのポインタを返し、見つからなければnullptrを返す
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 << "---------------------- リスト P --------------------" << endl;
	Head.PrintList();
}
template <class T> void reverseList(List<T>& Head) {
	T data;
	cout << "---------------------- リスト P --------------------" << endl;
	Head.PrintList();
	cout << endl;

	Head.ReverseList();
	cout << "------------- 逆転後、リスト 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;
}
読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。