單鏈表的基本操作實(shí)現(xiàn)
1.頭文件
??頭文件和源文件分開有很多好處：可以提高編譯速度、提高代碼的可維護(hù)性、提高代碼的可重用性和可擴(kuò)展性，同時(shí)也可以使代碼結(jié)構(gòu)更清晰，方便代碼的管理和維護(hù)。
LinkList.h
#pragma once
#include<assert.h>
//定義單鏈表節(jié)點(diǎn)
typedef struct LNode
{
int data;
LNode* next;
}LNode;
test.cpp
#include<iostream>
using namespace std;
#include"LinkList.h"
?????????????文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-723886.html
2.類定義和多種算法的實(shí)現(xiàn)
??（下面所有函數(shù)都默認(rèn)在類中實(shí)現(xiàn)）
??我們以帶頭單向非循環(huán)鏈表為例:
??帶頭單向非循環(huán)鏈表是一種鏈表數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針域。在這種鏈表中，有一個(gè)特殊的節(jié)點(diǎn)稱為頭節(jié)點(diǎn)，它指向鏈表的第一個(gè)節(jié)點(diǎn)。頭節(jié)點(diǎn)不是鏈表的一部分，僅用于方便操作。
?????????????
2.1創(chuàng)建空表
??我們定義了一個(gè)名為L(zhǎng)inkList的類，代表一個(gè)單鏈表。這個(gè)類有兩個(gè)私有成員：一個(gè)指向LNode類型的指針_head，代表鏈表的頭節(jié)點(diǎn)，以及一個(gè)整型變量_size，代表鏈表的大小。
//定義單鏈表類
class LinkList
{
public:
//默認(rèn)構(gòu)造函數(shù)
LinkList()
{
_head = new LNode(0);//創(chuàng)建頭結(jié)點(diǎn)(哨兵位節(jié)點(diǎn))
_size = 0;
}
private:
LNode* _head;
int _size;
};
?????????????
2.2頭插法創(chuàng)建n個(gè)元素的線性鏈表
??先以頭插單個(gè)元素為例：
??我們可以先創(chuàng)建一個(gè)新的節(jié)點(diǎn)來(lái)存儲(chǔ)該元素。然后，檢查鏈表是否為空，如果為空，則新節(jié)點(diǎn)就是鏈表的第一個(gè)節(jié)點(diǎn)； 否則，新節(jié)點(diǎn)將插入到當(dāng)前頭節(jié)點(diǎn)的后面。插入完成后，_size（代表鏈表元素個(gè)數(shù)的變量）加1。
void push_front(const int& val)
{
//創(chuàng)建一個(gè)插入的新節(jié)點(diǎn)，將要插入的值val賦值給它
LNode* newnode = new LNode(val);
LNode* cur = _head->next;//保存原來(lái)第一個(gè)結(jié)點(diǎn)
//進(jìn)行頭插操作
_head->next = newnode;
_head->next->next = cur;//連接原來(lái)的第一個(gè)節(jié)點(diǎn)
_size++;
}
??加上n循環(huán)即可實(shí)現(xiàn)頭插法創(chuàng)建n個(gè)元素的線性鏈表
//頭插法創(chuàng)建n個(gè)元素
void push_front_n()
{
cout << "請(qǐng)輸入要插入的元素個(gè)數(shù):";
int n;
cin >> n;
cout << endl;
cout << "輸入要插入的元素:";
while (n)
{
int tmp;
cin >> tmp;
push_front(tmp);
n--;
}
}
?????????????
2.3一個(gè)帶頭節(jié)點(diǎn)的鏈表存放一組整數(shù)，設(shè)計(jì)一個(gè)算法刪除值等于x的所有節(jié)點(diǎn)。
??無(wú)返回值版本
??我們先檢查鏈表是否為空，如果為空，則輸出一條錯(cuò)誤消息并返回。如果鏈表非空，它開始遍歷鏈表，檢查每個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是否為要?jiǎng)h除的節(jié)點(diǎn)。如果是，則刪除該節(jié)點(diǎn)并釋放其內(nèi)存；如果不是，則移動(dòng)到下一個(gè)節(jié)點(diǎn)。 在遍歷過程中，保持對(duì)當(dāng)前節(jié)點(diǎn)的引用，以防止刪除連續(xù)的要?jiǎng)h除的節(jié)點(diǎn)時(shí)出現(xiàn)問題。
//刪除所有x的節(jié)點(diǎn)
void erase_all_x(int x)
{
LNode* cur = _head;
if (cur->next == nullptr)//判斷是否為空鏈表
{
cout << "該鏈表為空不可刪除\n";
return;
}
else
{
while (cur && cur->next)//刪除的數(shù)據(jù)有可能連續(xù)，所以最好保持當(dāng)前節(jié)點(diǎn)
{
if (cur->next->data == x)//如果下一個(gè)節(jié)點(diǎn)為要?jiǎng)h除節(jié)點(diǎn)
{
LNode* tmp = cur->next;//用臨時(shí)指針保存要?jiǎng)h除的節(jié)點(diǎn)
cur->next = cur->next->next;//鏈表指向刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
delete tmp;//刪除節(jié)點(diǎn)中的元素
tmp = nullptr;
}
else//如果下個(gè)節(jié)點(diǎn)不是刪除節(jié)點(diǎn)，那直接指向下個(gè)節(jié)點(diǎn)
{
cur = cur->next;
}
}
}
}
??有返回值版本
//刪除所有x的節(jié)點(diǎn)，有刪除節(jié)點(diǎn)返回true，無(wú)刪除節(jié)點(diǎn)返回false
bool erase_all_x(int x)
{
LNode* cur = _head;
if (cur->next == nullptr)
{
cout << "該鏈表為空不可刪除\n";
return false;
}
else
{
int count = 0;//設(shè)計(jì)一個(gè)計(jì)數(shù)器，統(tǒng)計(jì)是否有刪除的節(jié)點(diǎn)
while (cur && cur->next)//刪除的數(shù)據(jù)有可能連續(xù)，所以最好保持當(dāng)前節(jié)點(diǎn)
{
if (cur->next->data == x)
{
count++;//有刪除的節(jié)點(diǎn)，count++
LNode* tmp = cur->next;
cur->next = cur->next->next;//刪除x節(jié)點(diǎn)
delete tmp;
tmp = nullptr;
}
else//如果下個(gè)節(jié)點(diǎn)不是刪除節(jié)點(diǎn)，那直接指向下個(gè)節(jié)點(diǎn)
{
cur = cur->next;
}
}
if (count == 0)//count==0，則沒有可以刪除的節(jié)點(diǎn)
{
cout << "鏈表中沒有可以刪除的元素" << endl;
return false;
}
return true;
}
}
?????????????
2.4計(jì)算線性表中值為偶數(shù)的節(jié)點(diǎn)個(gè)數(shù)
??我們定義函數(shù)用于遍歷鏈表并計(jì)算其中偶數(shù)節(jié)點(diǎn)的數(shù)量。首先，它檢查鏈表是否為空，如果為空，則輸出一條錯(cuò)誤消息。如果鏈表非空，它開始遍歷鏈表，檢查每個(gè)節(jié)點(diǎn)的數(shù)據(jù)是否為偶數(shù)。如果是偶數(shù)，則計(jì)數(shù)器加1。 遍歷完成后，輸出鏈表中偶數(shù)節(jié)點(diǎn)的數(shù)量。
//打印鏈表中值為偶數(shù)的節(jié)點(diǎn)個(gè)數(shù)
void print_even_number()
{
LNode* cur = _head->next;
int count = 0;
if (cur == nullptr)
{
cout << "該鏈表為空，沒有節(jié)點(diǎn)\n";
}
else//核心就在不斷通過指針遍歷尋找即可
{
while (cur)//遍歷鏈表中的每一個(gè)節(jié)點(diǎn)
{
if (cur->data % 2 == 0)
{
count++;//如果cur為偶數(shù)，計(jì)數(shù)++;
}
cur = cur->next;
}
cout << "該鏈表中偶數(shù)節(jié)點(diǎn)的個(gè)數(shù)為:" << count << endl;
}
}
?????????????
2.5一個(gè)帶頭節(jié)點(diǎn)的單鏈表heada存放一組整數(shù)，設(shè)計(jì)分裂heada算法，偶數(shù)放在heada中，奇數(shù)放在headb中
??我們定義該函數(shù)用于將鏈表中的偶數(shù)節(jié)點(diǎn)和奇數(shù)節(jié)點(diǎn)分開，使得偶數(shù)節(jié)點(diǎn)在heada鏈表中，奇數(shù)節(jié)點(diǎn)在headb鏈表中。
??函數(shù)使用兩個(gè)指針cur1和cur2分別遍歷heada和headb鏈表。在遍歷過程中，如果當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是偶數(shù)節(jié)點(diǎn)，則保持原鏈表不變，移動(dòng)cur1指針；
??如果當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是奇數(shù)節(jié)點(diǎn)，則將其從原鏈表中刪除，并添加到headb鏈表的末尾，同時(shí)移動(dòng)cur1和cur2指針。 最后，函數(shù)返回修改后的heada和headb鏈表。
//分裂鏈表，偶數(shù)在heada中，奇數(shù)在headb中
void divide_LinkList(LNode* heada, LNode* headb)
{
LNode* cur1 = heada;
LNode* cur2 = headb;
while (cur1 && cur1->next)//退出循環(huán)的條件要cur1和cur1下個(gè)節(jié)點(diǎn)不為空
{
if (cur1->next->data % 2 == 0)//為偶數(shù)原鏈表不變
{
cur1 = cur1->next;//cur1直接向后移動(dòng)
}
else//若鏈表為奇數(shù)，需要移動(dòng)放入headb中
{
//交換鏈表節(jié)點(diǎn)操作
LNode* tmp = cur1->next;
cur1->next = cur1->next->next;
//調(diào)整cur2，使其獲得cur1的節(jié)點(diǎn)，斷開cur1節(jié)點(diǎn)的后面節(jié)點(diǎn)的連接
cur2->next = tmp;
cur2->next->next = nullptr;
//cur1和cur2各向后移動(dòng)
cur2 = cur2->next;
}
}
}
?????????????
3.main函數(shù)和源碼實(shí)現(xiàn)
3.1測(cè)試實(shí)現(xiàn)：
test_LinkList1();
test_LinkList2();
test_LinkList3();
?????????????
3.2LinkList.h
#pragma once
#include<assert.h>
//定義單鏈表節(jié)點(diǎn)
typedef struct LNode
{
int data;
LNode* next;
LNode(const int& val)
:data(val)
, next(nullptr)
{}
}LNode;
//定義單鏈表類
class LinkList
{
public:
//默認(rèn)構(gòu)造函數(shù)
LinkList()
{
_head = new LNode(0);//創(chuàng)建頭結(jié)點(diǎn)(哨兵位節(jié)點(diǎn))
_size = 0;
}
//拷貝構(gòu)造函數(shù) lt1(lt)
LinkList(const LinkList& lt)
{
LNode* oldcur = lt._head->next;
//這個(gè)this指針是新建的鏈表lt1的
this->_head = new LNode(0);
this->_size = 0;
LNode* newcur = _head;
while (oldcur)//深拷貝以完成鏈表的賦值操作
{
//將舊鏈表中的值賦值到新鏈表中
LNode* tmp = new LNode(oldcur->data);
//向后移動(dòng)新舊鏈表節(jié)點(diǎn)
newcur->next = tmp;
newcur = newcur->next;
oldcur = oldcur->next;
_size++;
}
}
//析構(gòu)函數(shù)
~LinkList()
{
LNode* cur = _head->next;
while (cur)
{
LNode* tmp = cur;
cur = cur->next;
delete tmp;
tmp = nullptr;
}
}
//單鏈表打印
void print()
{
LNode* cur = _head->next;
if (cur == nullptr)
{
cout << "該單鏈表為空\(chéng)n";
}
else
{
cout << "該單鏈表中的元素為:";
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
cout << "NULL\n";
}
}
//單鏈表尾插
void push_back(const int& val)
{
LNode* newnode = new LNode(val);
LNode* cur = _head;
while (cur && cur->next)//找到尾結(jié)點(diǎn)
{
cur = cur->next;
}
cur->next = newnode;//尾插
_size++;
}
//單鏈表頭插
void push_front(const int& val)
{
LNode* newnode = new LNode(val);
LNode* cur = _head->next;
_head->next = newnode;
_head->next->next = cur;
_size++;
}
//單鏈表尾刪
void pop_back()
{
LNode* cur = _head->next;
LNode* prev = _head;
if (cur == nullptr)
{
cout << "單鏈表為空不可刪除\n";
}
else
{
while (cur && cur->next)//找到尾結(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)
{
cur = cur->next;
prev = prev->next;
}
prev->next = nullptr;
delete cur;
cur = nullptr;
_size--;
}
}
//單鏈表頭刪
void pop_front()
{
LNode* cur = _head->next;
if (cur == nullptr)
{
cout << "單鏈表為空不可刪除\n";
}
else
{
_head->next = cur->next;
delete cur;
cur = nullptr;
_size--;
}
}
//頭插法創(chuàng)建n個(gè)元素
void push_front_n()
{
cout << "請(qǐng)輸入要插入的元素個(gè)數(shù):";
int n;
cin >> n;
cout << endl;
cout << "輸入要插入的元素:";
while (n)
{
int tmp;
cin >> tmp;
push_front(tmp);
//LNode* newnode = new LNode(tmp);
//LNode* cur = _head->next;
//if (cur == nullptr)
//{
// _head->next = newnode;
//}
//else
//{
// newnode->next = cur;
// _head->next = newnode;
//}
n--;
//_size++;
}
}
//刪除第n個(gè)元素
void erase(int n)
{
assert(n > 0 && n <= _size);
LNode* cur = _head;
if (cur->next == nullptr)
{
cout << "該鏈表為空不可刪除\n";
return;
}
else
{
LNode* tmp = cur;
while (n)//找到刪除節(jié)點(diǎn)的前一個(gè)位置
{
tmp = cur;
cur = cur->next;
n--;
}
tmp->next = tmp->next->next;
delete cur;
cur = nullptr;
}
}
//單鏈表節(jié)點(diǎn)個(gè)數(shù)
void print_size()
{
cout << "單鏈表節(jié)點(diǎn)個(gè)數(shù)為:" << _size << endl;
}
//刪除所有x的節(jié)點(diǎn)，有刪除節(jié)點(diǎn)返回true，無(wú)刪除節(jié)點(diǎn)返回false
bool erase_all_x(int x)
{
LNode* cur = _head;
if (cur->next == nullptr)
{
cout << "該鏈表為空不可刪除\n";
return false;
}
else
{
int count = 0;//設(shè)計(jì)一個(gè)計(jì)數(shù)器，統(tǒng)計(jì)是否有刪除的節(jié)點(diǎn)
while (cur && cur->next)//刪除的數(shù)據(jù)有可能連續(xù)，所以最好保持當(dāng)前節(jié)點(diǎn)
{
if (cur->next->data == x)
{
count++;//有刪除的節(jié)點(diǎn)，count++
LNode* tmp = cur->next;
cur->next = cur->next->next;//刪除x節(jié)點(diǎn)
delete tmp;
tmp = nullptr;
}
else//如果下個(gè)節(jié)點(diǎn)不是刪除節(jié)點(diǎn)，那直接指向下個(gè)節(jié)點(diǎn)
{
cur = cur->next;
}
}
if (count == 0)//count==0，則沒有可以刪除的節(jié)點(diǎn)
{
cout << "鏈表中沒有可以刪除的元素" << endl;
return false;
}
return true;
}
}
//打印鏈表中值為偶數(shù)的節(jié)點(diǎn)個(gè)數(shù)
void print_even_number()
{
LNode* cur = _head->next;
int count = 0;
if (cur == nullptr)
{
cout << "該鏈表為空，沒有節(jié)點(diǎn)\n";
}
else
{
while (cur)//遍歷鏈表中的每一個(gè)節(jié)點(diǎn)
{
if (cur->data % 2 == 0)
{
count++;//如果cur為偶數(shù)，計(jì)數(shù)++;
}
cur = cur->next;
}
cout << "該鏈表中偶數(shù)節(jié)點(diǎn)的個(gè)數(shù)為:" << count << endl;
}
}
//返回當(dāng)前鏈表的頭結(jié)點(diǎn)
LNode* get_head()
{
return _head;
}
//分裂鏈表，偶數(shù)在heada中，奇數(shù)在headb中
void divide_LinkList(LNode* heada, LNode* headb)
{
LNode* cur1 = heada;
LNode* cur2 = headb;
while (cur1 && cur1->next)
{
if (cur1->next->data % 2 == 0)//為偶數(shù)原鏈表不變
{
cur1 = cur1->next;
}
else//若鏈表為奇數(shù)，需要移動(dòng)放入headb中
{
//交換鏈表節(jié)點(diǎn)操作
LNode* tmp = cur1->next;
cur1->next = cur1->next->next;
cur2->next = tmp;
cur2->next->next = nullptr;
//cur1和cur2各向后移動(dòng)
cur2 = cur2->next;
}
}
}
private:
LNode* _head;
int _size;
};
?????????????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-723886.html
3.3test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"LinkList.h"
void test_LinkList1()
{
LinkList lt;
//鏈表打印
lt.print();
//測(cè)試空鏈表刪除
lt.pop_front();
//尾插
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.print();
//頭插
lt.push_front(5);
lt.push_front(6);
lt.push_front(7);
lt.push_front(8);
lt.print();
//打印鏈表節(jié)點(diǎn)
lt.print_size();
//尾刪
lt.pop_back();
lt.pop_back();
lt.print();
//頭刪
lt.pop_front();
lt.pop_front();
lt.print();
lt.print_size();
}
void test_LinkList2()
{
//頭插法創(chuàng)建n個(gè)元素的鏈表
LinkList lt;
lt.push_front_n();
lt.print();
lt.print_size();
}
void test_LinkList3()
{
LinkList lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
lt.push_back(7);
lt.push_back(8);
lt.push_back(9);
lt.push_back(10);
lt.print();
lt.print_size();
lt.push_back(6);
lt.push_back(6);
lt.push_back(6);
//刪除第11節(jié)點(diǎn)的元素
lt.erase(11);
lt.print();
//刪除所有元素為6的節(jié)點(diǎn)
cout << "是否刪除成功:" << lt.erase_all_x(6) << endl;
lt.print();
cout << "是否刪除成功:" << lt.erase_all_x(6) << endl;
lt.print();
//打印所有節(jié)點(diǎn)為偶數(shù)的個(gè)數(shù)
lt.print_even_number();
//拷貝構(gòu)造函數(shù)
LinkList lt1(lt);
lt1.print();
lt1.print_size();
//編譯器生成了默認(rèn)的賦值運(yùn)算符重載
LinkList lt2 = lt1;
lt2.print();
//創(chuàng)建空鏈表
LinkList lt3;
lt3.print();
lt1.push_back(11);
lt1.push_back(14);
lt1.push_back(12);
lt1.push_back(13);
lt1.print();
//分離鏈表lt1，使lt1只含有偶數(shù)，lt3只含有奇數(shù)
lt1.divide_LinkList(lt1.get_head(), lt3.get_head());
lt1.print();
lt3.print();
}
int main()
{
//不想輸入數(shù)據(jù)就調(diào)用test_LinkList1()或test_LinkList3();
//test_LinkList1();
//test_LinkList2();
test_LinkList3();
return 0;
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)上機(jī)練習(xí)——單鏈表的基本操作、頭文件、類定義、main函數(shù)、多種鏈表算法的實(shí)現(xiàn)，含注釋的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
