C++實(shí)現(xiàn)單向鏈表
之前相關(guān)的文章
#什么是鏈表
鏈表是一種基本的數(shù)據(jù)結(jié)構(gòu)，之前我在C語言里面寫過鏈表的知識(shí)，現(xiàn)在延申到C++，不管是什么語言，鏈表表示的是一種數(shù)據(jù)結(jié)構(gòu)，跟語言沒有強(qiáng)相關(guān)性的。
如果我們需要實(shí)現(xiàn)一個(gè)鏈表，首先最關(guān)鍵的就是節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)表示鏈表的一個(gè)數(shù)據(jù)存儲(chǔ)點(diǎn)，鏈表是由很多個(gè)節(jié)點(diǎn)組成的。
鏈表還需要很多線把很多節(jié)點(diǎn)串聯(lián)在一起，可以用數(shù)組的特性串聯(lián)，也可以用指針串聯(lián)。
/*節(jié)點(diǎn)類*/?
class?Node
{
public:
?DataType?data;
?Node?*next;
};
#鏈表頭部
鏈表是一種數(shù)據(jù)結(jié)構(gòu)，跟數(shù)組一樣，和整型的數(shù)據(jù)一樣，都需要一個(gè)起始位置，鏈表頭就是這個(gè)起始位置，鏈表頭存在，就表示鏈表存在，鏈表頭沒有了，那這個(gè)鏈表也就沒有了。
鏈表頭也是一個(gè)節(jié)點(diǎn)，只是這個(gè)節(jié)點(diǎn)保存的是這個(gè)鏈表的起始位置
頭節(jié)點(diǎn)有點(diǎn)意思，它其實(shí)是不需要存儲(chǔ)數(shù)據(jù)的，所以data的值可有可無。
代碼上我們可以這樣寫，創(chuàng)建一個(gè)鏈表也就是創(chuàng)建一個(gè)鏈表頭
LinkList::LinkList()
{
?head?=?new?Node;
?head->data?=?0;
?head->next?=?NULL;
?size?=?0;
}
#插入一個(gè)數(shù)據(jù)到鏈表中
如果是一個(gè)已經(jīng)成型的鏈表，我們要把一個(gè)數(shù)據(jù)插入到鏈表中，我們需要有幾個(gè)判斷，是從鏈表頭插入，還是鏈表尾部插入，還是從鏈表的中間插入
— — 如果從鏈表頭插入，如下圖
— — 如果從鏈表中間插入，如下圖
— — 如果從鏈表尾部插入，如下圖
— —代碼實(shí)現(xiàn)
int?LinkList::InsertLinklList(Node?*data,?int?n)
{
?Node?*ptemp;
?if?(this->head?==?NULL)?{
?????cout?<"鏈表為空"?<??return?-1;
?}
?if?(data?==?NULL)?{
??cout?<"插入節(jié)點(diǎn)為空"?<??return?-1;
?}
?/*頭部插入*/?
?if?(n<2)?{
??Node?*pnew?=?new?Node;
??pnew->data?=?data->data;
??pnew->next?=?this->head->next;
??this->head->next?=?pnew;
??this->size++;
??return?0;
?}
?/*尾部插入*/?
?if?(n?>?this->size)?{
??ptemp?=?this->head;
??while?(ptemp->next?!=?NULL)?{
???ptemp?=?ptemp->next;
??}
??Node?*pnew?=?new?Node;
??pnew->data?=?data->data;
??pnew->next?=?NULL;
??ptemp->next?=?pnew;
??this->size++;
??return?0;
?}else?{/*中間插入*/?
??ptemp?=?this->head;
??for?(int?i?=?1;?i????ptemp?=?ptemp->next;
??}
??
??Node?*pnew?=?new?Node;
??pnew->data=?data->data;
??pnew->next?=?ptemp->next;
??ptemp->next?=?pnew;
??this->size++;
??return?0;
?}
}
#完整的代碼
#include?
#include?
using?namespace?std;
/*節(jié)點(diǎn)類*/
class?Node
{
public:
?int?data;
?Node?*next;
};
class?LinkList
{
public:
?LinkList();/*構(gòu)造函數(shù)*/
?~LinkList();/*析構(gòu)函數(shù)*/
?int?CreateLinkList(int?size);/*新建一個(gè)鏈表*/
?int?DestroyLinkList();/*銷毀一個(gè)鏈表*/
?int?TravalLinkList();/*遍歷一個(gè)鏈表*/
?int?InsertLinklList(Node?*data,?int?n);/*向鏈表插入一個(gè)數(shù)據(jù)*/
?int?DeleteLinklist(int?n);/*刪除鏈表中的某個(gè)值*/
?int?GetLength();/*獲取鏈表的長(zhǎng)度*/
?bool?IsEmpty();/*判斷鏈表是否為空*/
?Node?*head;/*鏈表頭*/
?int?size;/*鏈表長(zhǎng)度*/
};
LinkList::LinkList()
{
?head?=?new?Node;
?head->data?=?0;
?head->next?=?NULL;
?size?=?0;
}
LinkList::~LinkList()
{
?delete?head;
}
int?LinkList::CreateLinkList(int?n)
{
?if?(n<0)?{
??cout<<"error"<??return?-1;
?}
?Node?*ptemp?=?NULL;
?Node?*pnew?=?NULL;
?this->size?=?n;
?ptemp?=?this->head;
?for(int?i?=0?;?i?{
??pnew?=?new?Node;
??pnew->next?=?NULL;
??cout?<"輸入第"?<"個(gè)節(jié)點(diǎn)值"?<??cin?>>?pnew->data;
??ptemp->next?=?pnew;
??ptemp?=?pnew;
?}
?cout?<"創(chuàng)建完成"?<?return?0;
}
int?LinkList::DestroyLinkList()
{
?Node?*ptemp;
?if?(this->head?==?NULL)?{
??cout?<"鏈表原本就為空"?<??return?-1;
?}
?while?(this->head)
?{
??ptemp?=?head->next;
??free(head);
??head?=?ptemp;
?}
?cout?<"銷毀鏈表完成"?<?return?0;
}
int?LinkList::TravalLinkList()
{
?Node?*ptemp?=?this->head->next;
?if?(this->head?==?NULL)?{
??cout?<"鏈表為空"?<??return?-1;
?}
?while(ptemp)
?{
??cout?<data?<"->";
??ptemp?=?ptemp->next;
?}
?cout?<<"NULL"<?return?0;
}
int?LinkList::InsertLinklList(Node?*data,?int?n)
{
?Node?*ptemp;
?if?(this->head?==?NULL)?{
??cout?<"鏈表為空"?<??return?-1;
?}
?if?(data?==?NULL)?{
??cout?<"插入節(jié)點(diǎn)為空"?<??return?-1;
?}
?/*頭部插入*/
?if?(n<2)?{
??Node?*pnew?=?new?Node;
??pnew->data?=?data->data;
??pnew->next?=?this->head->next;
??this->head->next?=?pnew;
??this->size++;
??return?0;
?}
?/*尾部插入*/
?if?(n?>?this->size)?{
??ptemp?=?this->head;
??while?(ptemp->next?!=?NULL)?{
???ptemp?=?ptemp->next;
??}
??Node?*pnew?=?new?Node;
??pnew->data?=?data->data;
??pnew->next?=?NULL;
??ptemp->next?=?pnew;
??this->size++;
??return?0;
?}
?/*中間插入*/
?else?{
??ptemp?=?this->head;
??for?(int?i?=?1;?i????ptemp?=?ptemp->next;
??}
??Node?*pnew?=?new?Node;
??pnew->data=?data->data;
??pnew->next?=?ptemp->next;
??ptemp->next?=?pnew;
??this->size++;
??return?0;
?}
}
int?LinkList::DeleteLinklist(int?n)
{
?Node?*ptemp;
?Node?*ptemp2;
?if?(n?>?this->size)?{
??cout?<"n太大"?<??return?-1;
?}
?/*刪頭節(jié)點(diǎn)*/
?if?(n???ptemp?=?this->head->next;
??this->head->next?=?ptemp->next;
??free(ptemp);
??this->size--;
??return?0;
?}
?/*尾部刪除*/
?if?(n?==?this->size)?{
??ptemp?=?this->head;
??for?(int?i?=?1;?i?size;i++)?{
???ptemp?=?ptemp->next;
??}
??ptemp2?=?ptemp->next;
??ptemp->next?=?NULL;
??free(ptemp2);
??this->size--;
??return?0;
?}
?/*中間刪除*/
?else
?{
??ptemp?=?this->head;
??for?(int?i?=?1;?i????ptemp?=?ptemp->next;
??}
??ptemp2?=?ptemp->next;
??ptemp->next?=?ptemp2->next;
??free(ptemp2);
??this->size--;
??return?0;
?}
}
int?LinkList::GetLength()
{
?return?this->size;
}
bool?LinkList::IsEmpty()
{
?if?(this->head?==?NULL)?{
??return?true;
?}
?else{
??return?false;
?}
}
int?main(void)
{
?LinkList?list;
?LinkList?*plist?=?&list;
?/*創(chuàng)建6個(gè)節(jié)點(diǎn)的鏈表*/
?plist->CreateLinkList(5);
?plist->TravalLinkList();
?/*向鏈表中插入一個(gè)數(shù)據(jù)*/
?Node?temp;
?temp.data?=?77;
?temp.next?=?NULL;
?/*向0號(hào)位置插入一個(gè)節(jié)點(diǎn)*/
?plist->InsertLinklList(&temp,?0);
?/*遍歷整個(gè)鏈表*/
?plist->TravalLinkList();
?/*向尾部插入一個(gè)鏈表*/
?plist->InsertLinklList(&temp,?plist->GetLength()+1);
?/*遍歷整個(gè)鏈表*/
?plist->TravalLinkList();
?/*向5號(hào)位置插入一個(gè)鏈表*/
?plist->InsertLinklList(&temp,?5);
?/*遍歷整個(gè)鏈表*/
?plist->TravalLinkList();
?plist->DeleteLinklist(0);
?/*遍歷整個(gè)鏈表*/
?plist->TravalLinkList();
?/*刪除第二個(gè)節(jié)點(diǎn)*/
?plist->DeleteLinklist(4);
?/*遍歷整個(gè)鏈表*/
?plist->TravalLinkList();
?/*刪除整個(gè)鏈表*/
?plist->DestroyLinkList();
?system("pause");
?return?(0);
}
#代碼輸出
輸入第1個(gè)節(jié)點(diǎn)值
2
輸入第2個(gè)節(jié)點(diǎn)值
22
輸入第3個(gè)節(jié)點(diǎn)值
3
輸入第4個(gè)節(jié)點(diǎn)值
44
輸入第5個(gè)節(jié)點(diǎn)值
5
創(chuàng)建完成
2->22->3->44->5->NULL
77->2->22->3->44->5->NULL
77->2->22->3->44->5->77->NULL
77->2->22->3->77->44->5->77->NULL
2->22->3->77->44->5->77->NULL
2->22->3->44->5->77->NULL
銷毀鏈表完成
請(qǐng)按任意鍵繼續(xù).?.?.
評(píng)論
圖片
表情