C++single linked listシングルチェーンテーブルの作成と実行(ダイナミックストレージやメモリ漏洩などの問題を考慮したヘッダノードあり)(1)
これはC++programming IIという授業で配置された小さな作業であり、核心は動的記憶とポインタの理解(特にnewとdeleteの使用)である.時間をかけて、途中でcsdnに来て資料を探しても、関連内容を見た経験が共有されていないので、ブログを書いて成果と心得を記録します.コードのそばには簡単な注釈があり、中英が混在している.重要ではない私は翻訳していません.問題があればコメントを歓迎します.
まず、head:ヘッダノードtail:テールノード/テールを宣言します.
作成(ヘッダファイル)
LinkedList.h:
LinkedList.cppの構造関数:
こうぞうかんすう
肝心なのは来て、注意しないとこの一歩からすでにmemory leakとdangling pointerが生まれています
2つのpush関数、先頭と末尾からノードを追加ノードを追加する唯一の方法. このときの新しいノードはすべて手動で新しいメモリ(new)を割り当てる必要があることに注意して、削除する時手動で削除する(delete) が必要ですは、この値num、next nullptrのノードに新しいアドレスを動的に割り当てます. はその後、チェーンテーブルに追加される.
この場合、3つの状況に注意してください.チェーンテーブルが空です:head=新しいノード+tail=新しいノード チェーンテーブルには1つのノードしかありません:前からpushするとhead=新しいノード、後ろからtail=新しいノード とします.チェーンテーブルには、上の と同じ2つ以上のノードがあります.
push_front(int)
push_back(int)
先頭ノードと末尾ノードの値を返します.
front() & back()
empty()
ノードを最初から削除ノードを削除する第1の態様 .ノードが1つしかない場合を考慮してください.そうしないと、プログラムはcrashになります.head&tailを手動で削除しnullptr(nullを勝手に設定する良い習慣) に設定してください.
pop_front()
すべてのノードを削除ノードを削除する第2の態様 .は、構造関数の実行内容と同じ である.目的:すべてのノードをクリアし、チェーンテーブル をリフレッシュする
clear()
<<を使用してチェーンテーブルコンテンツの印刷を行う
ここではノードのnextがnullptrであるか否かで末尾に達したか否かを判断する(次の部分のremove_duplicates()関数に1つしか残っていない場合tailがどのように処理するか、ノード==tailで印刷エラーが発生するかをチェックするため)
friend function: operator<<
コピーコンストラクタ
deep copyを行うには、手動でノードを1つずつ追加する必要があります
チェーンテーブルのコピー(=)
この場合、5つの状況を考慮する必要があります.空チェーンテーブルコピー空チェーンテーブル 空チェーンテーブルコピー非空チェーンテーブル 非空チェーンテーブルコピー空チェーンテーブル 非空チェーンテーブルコピー非空チェーンテーブル 自己コピー自己(self-assignment)
ここで私は2つの間違いを犯したことがあります. segmentation fault 非空チェーンテーブルが空チェーンテーブルをコピーしたときclear()が終了しtailを手当たり次第にnullptr(clear()はheadからdeleteのみ、最後にheadをnullとしたため) あとはselection_sort(), insert_ordered(int), remove_duplicates()および宿題を書くときにプログラムが報告したすべてのerror;今日は宿題が多すぎて、次の編に書く時間があります.
復習後の3つの関数の実現と誤報分析のノートリンクを添付し、英語全体で障害のない友达が見に来ることができます.https://www.notion.so/lavendershuo/Review-Linked-List-19911524ae42403b8cab305ff36c1943
まず、head:ヘッダノードtail:テールノード/テールを宣言します.
作成(ヘッダファイル)
LinkedList.h:
#ifndef INTLIST_H
#define INTLIST_H
#include
using namespace std;
struct IntNode {
int value;
IntNode *next;
IntNode(int value) : value(value), next(nullptr) {}
};
class IntList {
private:
IntNode *head;
IntNode *tail;
public:
IntList();
IntList(const IntList &cpy);
~IntList();
void push_front(int);
void pop_front();
bool empty() const;
const int & front() const;
const int & back() const;
IntList& operator=(const IntList &rhs);
void push_back(int);
void clear();
void selection_sort();
void insert_ordered(int);
void remove_duplicates();
friend ostream & operator< LinkedList.cppの構造関数:
IntList::IntList(): head(nullptr), tail(nullptr) {}
こうぞうかんすう
肝心なのは来て、注意しないとこの一歩からすでにmemory leakとdangling pointerが生まれています
IntList::~IntList(){
if (head != nullptr){
// 1. go to head
// 2. delete head and set it to null
// 3. use the next of head to go to the next node in the IntList
// 4. delete that node and set it to null
// 5. repeat 3 and 4 until it reaches tail
while(head != nullptr){
IntNode *tmp = head->next; // next nullptr
delete head;
head = tmp; // nullptr
}
}
}
2つのpush関数、先頭と末尾からノードを追加
この場合、3つの状況に注意してください.
push_front(int)
void IntList::push_front(int num){
IntNode* node = new IntNode(num);
if (empty()){
//consider three different senarios: 1. empty; 2. only one node(head == tail == nullptr); 3. two or more than two
tail = node;
head = node;
}else{
node->next = head;
head = node;
}
} // ？
}
push_back(int)
void IntList::push_back(int value_){
IntNode* node = new IntNode(value_);
if (head == nullptr){
push_front(value_);
}
else{
tail->next = node;
tail = node;
}
}
先頭ノードと末尾ノードの値を返します.
front() & back()
const int & IntList::front() const{
return head->value;
}
const int & IntList::back() const{
return tail->value;
}
empty()
bool IntList::empty() const{
return (head == nullptr); // if checking both nodes, when deleting, set to null
}
ノードを最初から削除
pop_front()
void IntList::pop_front(){
// the same three senarios
if (!empty()){
if (head != nullptr){
IntNode* node = head->next;
delete head;
head = node;
}
else if(head == tail){
delete head;
delete tail;
head = nullptr;
tail = nullptr; // avoid the dangling pointer
}
}
}
すべてのノードを削除
clear()
void IntList::clear(){
if (head != nullptr){
// 1. delete head and set it to null
// 2. use the next of head to go to the next node in the IntList
// 3. delete that node and set it to null
// 4. repeat 2 and 3 until it reaches tail
while(head != nullptr){
IntNode *tmp = head->next;
delete head;
head = tmp;
}
}
}
<<を使用してチェーンテーブルコンテンツの印刷を行う
ここではノードのnextがnullptrであるか否かで末尾に達したか否かを判断する(次の部分のremove_duplicates()関数に1つしか残っていない場合tailがどのように処理するか、ノード==tailで印刷エラーが発生するかをチェックするため)
friend function: operator<<
ostream & operator<value;
if (node->next == nullptr){
// test deleting tail success or not; since I cannot handle the positon of tail node properly, this is a good practice
break;
}
out << " ";
node = node->next;
}
return out;
}
コピーコンストラクタ
deep copyを行うには、手動でノードを1つずつ追加する必要があります
IntList::IntList(const IntList &cpy){
head = nullptr; // !
tail = nullptr; // !
if (this != &cpy){
if (!cpy.empty()){
IntNode* tmp = cpy.head;
while(tmp != nullptr){
push_back(tmp->value);
tmp = tmp->next;
}
}
} // ......
}
チェーンテーブルのコピー(=)
この場合、5つの状況を考慮する必要があります.
IntList& IntList::operator=(const IntList &rhs){
if (rhs.empty()){
head = nullptr;
tail = nullptr;
}
else if (&rhs != this){
if (head != nullptr){
clear();
head = nullptr;
tail = nullptr; // clear() does not set head and tail to null which can be used later
}
IntNode* tmp = rhs.head;
while(tmp != nullptr){
push_back(tmp->value);
tmp = tmp->next;
}
}else if (&rhs == this){
return *this;
}
return *this;
}
ここで私は2つの間違いを犯したことがあります.
IntNode* tmp = rhs.head;
// do not assign head with rhs's head, the push_back function does the same
// head = rhs.head;, segmentation fault （ dangling pointer ；
// dangling pointer: deallocates the data the pointer pointing to without modifying the value of the pointer)
while(tmp != nullptr){
push_back(tmp->value);
tmp = tmp->next;
}
復習後の3つの関数の実現と誤報分析のノートリンクを添付し、英語全体で障害のない友达が見に来ることができます.https://www.notion.so/lavendershuo/Review-Linked-List-19911524ae42403b8cab305ff36c1943