1、單鏈表的定義
?由于順序表的插入刪除操作需要移動(dòng)大量的元素，影響了運(yùn)行效率，因此引入了線性表的鏈?zhǔn)酱鎯?chǔ)——單鏈表。單鏈表通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素，不需要使用地址連續(xù)的存儲(chǔ)單元，因此它不要求在邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰。
單鏈表的特點(diǎn)：
- 單鏈表不要求邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰，因此不需要連續(xù)的存儲(chǔ)空間。
- 單鏈表是非隨機(jī)的存儲(chǔ)結(jié)構(gòu)，即不能直接找到表中某個(gè)特定的結(jié)點(diǎn)。查找某個(gè)特定的結(jié)點(diǎn)時(shí)，需要從表頭開(kāi)始遍歷，依次查找。
優(yōu)點(diǎn)：
- 支持動(dòng)態(tài)內(nèi)存分配。由于單鏈表不需要預(yù)先分配一段連續(xù)的空間，因此可以根據(jù)實(shí)際需求動(dòng)態(tài)地申請(qǐng)、釋放節(jié)點(diǎn)空間，避免浪費(fèi)內(nèi)存。
-
支持高效的插入、刪除操作。由于單鏈表中的節(jié)點(diǎn)是通過(guò)指針相連的，因此在插入、刪除一個(gè)節(jié)點(diǎn)時(shí)，只需要修改其前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)的指針即可，時(shí)間復(fù)雜度為O ( 1 ) 。
?
?缺點(diǎn)：
- 不支持隨機(jī)訪問(wèn)。由于單鏈表中的節(jié)點(diǎn)不是連續(xù)存儲(chǔ)的，因此不能像數(shù)組一樣通過(guò)下標(biāo)來(lái)直接訪問(wèn)一個(gè)元素，需要從頭節(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表才能訪問(wèn)任意位置的元素。
?創(chuàng)建一個(gè)類
template <class T> // T為單鏈表存儲(chǔ)的元素類型
class linkList
{
private:
struct Node
{
public:
T data; // 結(jié)點(diǎn)的數(shù)據(jù)域
Node* next; // 結(jié)點(diǎn)的指針域，指向后繼結(jié)點(diǎn)
Node(const T value, Node* p = NULL) // 具有兩個(gè)參數(shù)的Node構(gòu)造函數(shù)
{
data = value;
next = p;
}
Node(Node* p = NULL) // 具有一個(gè)參數(shù)的Node構(gòu)造函數(shù)
{
next = p;
}
};
Node* head; // 單鏈表的頭指針
Node* tail; // 單鏈表的尾
int curLength; // 單鏈表的當(dāng)前長(zhǎng)度
Node* getPosition(int i)const; // 返回指向單鏈表中第i個(gè)元素的指針
public:
linkList(); // 構(gòu)造函數(shù)
~linkList(); // 析構(gòu)函數(shù)
void clear(); // 將單鏈表清空，使之成為空表
bool empty()const; // 判空
int size(); // 返回單鏈表的當(dāng)前實(shí)際長(zhǎng)度
void insert(int i, const T& value); // 在位置i上插入一個(gè)元素value，表的長(zhǎng)度增1
void remove(int i); // 刪除位置i上的元素value，若刪除位置合法，表的長(zhǎng)度減1
int search(const T& value)const; // 查找值為value的元素第一次出現(xiàn)的位序
T visit(int i)const; // 訪問(wèn)位序?yàn)閕的元素值，“位序”0表示第一個(gè)元素，類似于數(shù)組下標(biāo)
void traverse()const; // 遍歷單鏈表
void headCreate(); // “頭插法”
void tailCreate(); // “尾插法”
void inverse(); // 逆置單鏈表
int prior(const T& value)const; // 查找值為value的元素的前驅(qū)
};?2、單鏈表的初始化
- 通常會(huì)用頭指針來(lái)標(biāo)識(shí)一個(gè)單鏈表，頭指針為nullptr時(shí)表示一個(gè)空表。
- 但是，為了操作方便，會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。
- 頭結(jié)點(diǎn)的數(shù)據(jù)域可以不設(shè)任何信息，也可以記錄表長(zhǎng)等信息。
?
代碼實(shí)現(xiàn)：?
template <class T>
linkList<T>::linkList()
{
head = tail = new Node(); // 創(chuàng)建帶有頭結(jié)點(diǎn)的空表
curLength = 0;
}
?3、單鏈表的建立
3.1、頭插法建立單鏈表
頭插法建立單鏈表是說(shuō)將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭，即頭結(jié)點(diǎn)之后。
思路：輸入一個(gè)結(jié)束標(biāo)志flag，使用一個(gè)while循環(huán)，判斷條件是 value != flag
代碼實(shí)現(xiàn)：
template <class T> // 頭插法創(chuàng)建
void linkList<T>::headCreate()
{
Node* p;
T value, flag;
cin >> flag; // 輸入結(jié)束標(biāo)志
cin >> value;
while (value != flag)
{
p = new Node(value);
p->next = head->next;
head->next = p;
curLength++;
cin >> value;
}
}3.2、尾插法建立單鏈表
尾插法建立單鏈表，就是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾。
代碼實(shí)現(xiàn)：
template <class T> // 尾插法創(chuàng)建鏈表
void linkList<T> ::tailCreate()
{
Node* p;
T value, flag;
cin >> flag; // 輸入結(jié)束標(biāo)志
cin >> value;
while (value != flag)
{
p = new Node(value);
tail->next = p;
tail = p;
curLength++;
cin >> value;
}
}4、單鏈表的遍歷?
代碼實(shí)現(xiàn)：
template <class T>
void linkList<T> ::traverse()const
{
Node* p = head->next;
while (p != nullptr)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}5、單鏈表的長(zhǎng)度
代碼實(shí)現(xiàn)：
template <class T>
int linkList<T>::size()
{
return curLength;
}6、單鏈表的查找
6.1、按值查找
代碼實(shí)現(xiàn)：
template <class T>
int linkList<T> ::search(const T& value)const
{
Node* current = head->next;
int i = 0;
while (current != nullptr)
{
if (current->data == value)
{
break;
}
else
{
current = current->next;
i++;
}
}
if (current != nullptr)
{
return i;
}
return -1;
}6.2、按位查找
代碼實(shí)現(xiàn)：
template <class T> // 訪問(wèn)位序?yàn)閕的元素返回其數(shù)據(jù)域
T linkList<T> ::visit(int i)const
{
if (i < 0 || i>(curLength - 1))
{
T a = 0;
return a;
}
Node* current = head->next;
while (i--)
{
current = current->next;
}
return current->data;
}
7、單鏈表的插入
返回指向單鏈表中第i個(gè)元素的指針
template <class T>
typename linkList<T> ::Node* linkList<T> ::getPosition(int i)const
{
Node* ptemp = head;
int k = 0;
while (k < i)
{
ptemp = ptemp->next;
k++;
}
return ptemp;
}代碼實(shí)現(xiàn)：
template <class T>
void linkList<T> ::insert(int i, const T& value)
{
Node* current = getPosition(i);
Node* newNode = new Node(value);
newNode->next = current->next;
current->next = newNode;
curLength++;
}8、單鏈表的刪除
代碼實(shí)現(xiàn)：
template <class T>
void linkList<T>::remove(int i)
{
Node* current = getPosition(i);
Node* del = current->next;
current->next = del->next;
delete del;
curLength--;
}9、單鏈表的判空
代碼實(shí)現(xiàn)：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-768368.html
template <class T>
bool linkList<T>::empty()const
{
return head->next == nullptr;
}總代碼實(shí)現(xiàn)：
#include<stack>
template <class T> // T為單鏈表存儲(chǔ)的元素類型
class linkList
{
private:
struct Node
{
public:
T data; // 結(jié)點(diǎn)的數(shù)據(jù)域
Node* next; // 結(jié)點(diǎn)的指針域，指向后繼結(jié)點(diǎn)
Node(const T value, Node* p = NULL) // 具有兩個(gè)參數(shù)的Node構(gòu)造函數(shù)
{
data = value;
next = p;
}
Node(Node* p = NULL) // 具有一個(gè)參數(shù)的Node構(gòu)造函數(shù)
{
next = p;
}
};
Node* head; // 單鏈表的頭指針
Node* tail; // 單鏈表的尾
int curLength; // 單鏈表的當(dāng)前長(zhǎng)度
Node* getPosition(int i)const; // 返回指向單鏈表中第i個(gè)元素的指針
public:
linkList(); // 構(gòu)造函數(shù)
~linkList(); // 析構(gòu)函數(shù)
void clear(); // 將單鏈表清空，使之成為空表
bool empty()const; // 判空
int size(); // 返回單鏈表的當(dāng)前實(shí)際長(zhǎng)度
void insert(int i, const T& value); // 在位置i上插入一個(gè)元素value，表的長(zhǎng)度增1
void remove(int i); // 刪除位置i上的元素value，若刪除位置合法，表的長(zhǎng)度減1
int search(const T& value)const; // 查找值為value的元素第一次出現(xiàn)的位序
T visit(int i)const; // 訪問(wèn)位序?yàn)閕的元素值，“位序”0表示第一個(gè)元素，類似于數(shù)組下標(biāo)
void traverse()const; // 遍歷單鏈表
void headCreate(); // “頭插法”
void tailCreate(); // “尾插法”
void inverse(); // 逆置單鏈表
int prior(const T& value)const; // 查找值為value的元素的前驅(qū)
};
template <class T>
linkList<T>::linkList()
{
head = tail = new Node(); // 創(chuàng)建帶有頭結(jié)點(diǎn)的空表
curLength = 0;
}
template <class T>
linkList<T>::~linkList()
{
clear();
delete head; // 刪除頭結(jié)點(diǎn)
}
template <class T>
bool linkList<T>::empty()const
{
return head->next == nullptr;
}
template <class T>
int linkList<T>::size()
{
return curLength;
}
template <class T>
void linkList<T>::clear()
{
Node* p = head->next;
while (p)
{
head = head->next;
delete p;
p = head;
}
}
template <class T>
typename linkList<T> ::Node* linkList<T> ::getPosition(int i)const
{
Node* ptemp = head;
int k = 0;
while (k < i)
{
ptemp = ptemp->next;
k++;
}
return ptemp;
}
template <class T>
void linkList<T> ::insert(int i, const T& value)
{
Node* current = getPosition(i);
Node* newNode = new Node(value);
newNode->next = current->next;
current->next = newNode;
curLength++;
}
template <class T>
void linkList<T>::remove(int i)
{
Node* current = getPosition(i);
Node* del = current->next;
current->next = del->next;
delete del;
curLength--;
}
template <class T>
void linkList<T> ::traverse()const
{
Node* p = head->next;
while (p != nullptr)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
template <class T>
int linkList<T> ::search(const T& value)const
{
Node* current = head->next;
int i = 0;
while (current != nullptr)
{
if (current->data == value)
{
break;
}
else
{
current = current->next;
i++;
}
}
if (current != nullptr)
{
return i;
}
return -1;
}
template <class T> // 訪問(wèn)位序?yàn)閕的元素返回其數(shù)據(jù)域
T linkList<T> ::visit(int i)const
{
if (i < 0 || i>(curLength - 1))
{
T a = 0;
return a;
}
Node* current = head->next;
while (i--)
{
current = current->next;
}
return current->data;
}
template <class T> // 頭插法創(chuàng)建
void linkList<T>::headCreate()
{
Node* p;
T value, flag;
cin >> flag; // 輸入結(jié)束標(biāo)志
cin >> value;
while (value != flag)
{
p = new Node(value);
p->next = head->next;
head->next = p;
curLength++;
cin >> value;
}
}
template <class T> // 尾插法創(chuàng)建鏈表
void linkList<T> ::tailCreate()
{
Node* p;
T value, flag;
cin >> flag; // 輸入結(jié)束標(biāo)志
cin >> value;
while (value != flag)
{
p = new Node(value);
tail->next = p;
tail = p;
curLength++;
cin >> value;
}
}
template <class T> // 頭插法逆置
void linkList<T> ::inverse()
{
Node* temp = nullptr;
Node* p = head->next;
head->next = nullptr;
while (p != nullptr)
{
temp = p;
p = p->next;
temp->next = head->next;
head->next = temp;
}
}
template <class T>
int linkList<T> ::prior(const T& value)const
{
Node* current = head->next;
int a = 0;
Node* p = nullptr;
while (current != nullptr)
{
if (current->data == value)
{
break;
}
else
{
current = current->next;
a++;
}
}
if (current != nullptr)
{
return a - 1;
}
return -1;
}
執(zhí)行
#include<iostream>
using namespace std;
#include"SList.h"
int main()
{
linkList<int>* lk1, * lk2;
lk1 = new linkList<int>();
lk2 = new linkList<int>();
int i;
int val;
lk1->headCreate(); // 測(cè)試頭插法創(chuàng)建單鏈表
lk2->tailCreate(); // 測(cè)試尾插法創(chuàng)建單鏈表
lk1->traverse(); // 測(cè)試遍歷
lk2->traverse(); // 測(cè)試遍歷
cout << "查找值為2的位序：" << lk1->search(2) << endl;
cout << "查找位序?yàn)?的值" << lk1->visit(2) << endl;
cout << "長(zhǎng)度：" << lk1->size();
return 0;
}執(zhí)行結(jié)果
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-768368.html
到了這里，關(guān)于【C++】單鏈表——單鏈表的基本操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
