一、定義說(shuō)明：
??????? 單鏈表是通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素。每個(gè)結(jié)點(diǎn)都有data數(shù)據(jù)域（用來(lái)存放數(shù)據(jù)元素）和next指針域（用來(lái)存放后繼節(jié)點(diǎn)的地址）。
??????? 對(duì)于順序表，單鏈表可以解決順序表需要一整個(gè)大量的連續(xù)的存儲(chǔ)單元的缺點(diǎn)，單鏈表的元素可以離散地分布在存儲(chǔ)空間中，即非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，不能直接找到表中某個(gè)特定的結(jié)點(diǎn)，當(dāng)查找某個(gè)特定的結(jié)點(diǎn)時(shí)，需要從表頭開(kāi)始一個(gè)一個(gè)遍歷。因?yàn)閱捂湵砀郊恿酥羔樣颍秉c(diǎn)就是存儲(chǔ)空間增大。
??????? 單鏈表有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種類型。引入頭結(jié)點(diǎn)的好處：①便于第一個(gè)結(jié)點(diǎn)的處理：增加頭結(jié)點(diǎn)后，第一個(gè)結(jié)點(diǎn)的地址保存在頭結(jié)點(diǎn)的指針域中，則對(duì)鏈表的第一個(gè)元素的操作和其他元素相同，無(wú)需進(jìn)行特殊處理。（若單鏈表不帶頭結(jié)點(diǎn)，則第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)，在其前插入結(jié)點(diǎn)和刪除該結(jié)點(diǎn)操作復(fù)雜些。）②便于空表和非空表的統(tǒng)一處理：增加頭結(jié)點(diǎn)后，無(wú)論鏈表是否為空，頭指針都是指向頭結(jié)點(diǎn)的非空指針。
二、帶頭結(jié)點(diǎn)的程序說(shuō)明
2.1 單鏈表的存儲(chǔ)結(jié)構(gòu)
typedef struct LNode {
Elemtype data; //數(shù)據(jù)域
struct LNode* next; //指針域
}LNode, * LinkList;2.2 初始化
bool Initlist(LinkList &L)
{
//L = (LinkList)malloc(sizeof(LNode)); //c語(yǔ)言定義頭結(jié)點(diǎn)
L = new LNode; //定義頭結(jié)點(diǎn)
L->next = NULL; //尾指針為空，頭結(jié)點(diǎn)指向空
return true;
}2.3 頭插法建立單鏈表
void List_HeadInsert(LinkList& L)
{
int n; //輸入元素的個(gè)數(shù)
cout << "頭插法--請(qǐng)輸入元素個(gè)數(shù)n：" << endl;
cin >> n;
LinkList s; //定義指針變量s
cout << "請(qǐng)依次輸入元素：" << endl;
while (n--)
{
s = new LNode; //定義變量結(jié)點(diǎn)
cin >> s->data;
s->next = L->next;
L->next = s;
}
}2.4 尾插法建立單鏈表
void List_TailInsert(LinkList& L)
{
int n; //輸入元素的個(gè)數(shù)
cout << "尾插法--請(qǐng)輸入元素個(gè)數(shù)n：" << endl;
cin >> n;
LinkList r; //定義一個(gè)表尾指針
r = L;
LinkList s;//定義指針變量s
cout << "請(qǐng)依次輸入元素：" << endl;
while (n--)
{
s = new LNode;
cin >> s->data;
s -> next = NULL;
r->next = s;
r = s;
}
}2.5 打印鏈表
void Print_list(LinkList& L)
{
LinkList s;
s = L->next;
while(s)
{
cout << s->data << " ";
s = s->next;
}
cout << endl;
}2.6 求鏈表的長(zhǎng)度
int Length_list(LinkList& L)
{
int length=0;
LinkList s;
s = L->next;
while (s)
{
length++;
s = s->next;
}
return length;
}2.7 按位置序號(hào)查找結(jié)點(diǎn)
LNode* GetElem(LinkList& L, int i)
{
if (i<1 || i>Length_list(L))
return NULL;
int j = 1;
LNode* p = L->next; //鏈表第一個(gè)結(jié)點(diǎn)賦給p，L是頭結(jié)點(diǎn)
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p; //返回第i個(gè)結(jié)點(diǎn)的指針，"p != NULL"其實(shí)是在和表長(zhǎng)對(duì)比，但我這里其實(shí)不需要
}2.8 按值查找位置信息
int LocateElem(LinkList& L, Elemtype e)
{
LNode* p = L->next; //第一個(gè)結(jié)點(diǎn)賦給p;
int j = 1;
while (p != NULL && p->data != e)
{
p = p->next;
j++;
}
return j;
}2.9在第i個(gè)結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)
bool ListInsert(LinkList& L, int i, Elemtype e)
{
if (i<1 || i>Length_list(L) + 1)
return false; //判斷i的合法性
if (i == 1)//這樣就能在第1個(gè)位置插入結(jié)點(diǎn)了
{
LinkList p;
p = new LNode; //創(chuàng)建想要插入的結(jié)點(diǎn)信息
p->next = L->next;
p->data = e;
L->next = p;
}
else
{
LinkList s;
s = GetElem(L, i - 1); //查找到第i-1個(gè)結(jié)點(diǎn),是查不到第1個(gè)位置的
LinkList p;
p = new LNode; //創(chuàng)建想要插入的結(jié)點(diǎn)信息
p->next = s->next;
p->data = e;
s->next = p;
}
return true;
}2.10 刪除第i個(gè)位置的結(jié)點(diǎn)
bool ListDelete(LinkList& L, int i)
{
if (i<1 || i>Length_list(L))
return false;
if (i == 1)
{
LNode* p = L->next;//第一個(gè)結(jié)點(diǎn)賦給p;
L->next = p->next;
free(p);
}
else
{
LinkList s;
s = GetElem(L, i - 1);//查找到第i-1個(gè)結(jié)點(diǎn),是查不到第1個(gè)位置的
LinkList p; //被刪除的結(jié)點(diǎn)
p = s->next;
s->next = p->next;
free(p);
}
return true;
}2.11單鏈表的逆置
bool ListReverse(LinkList& L)
{
if (!L->next)
return false; //空鏈表不需要逆置
LinkList r, p, q; //r代表前驅(qū)節(jié)點(diǎn)，p當(dāng)前節(jié)點(diǎn)，q后繼節(jié)點(diǎn)
r = NULL;
p = L->next;
q = p->next; //從單鏈表的第一個(gè)節(jié)點(diǎn)開(kāi)始，沿著鏈表滑動(dòng)，直到最后一個(gè)節(jié)點(diǎn)，逐一反轉(zhuǎn)
while (p)
{
p->next = r;
r = p;
p = q;
if (q) //保證指向后繼節(jié)點(diǎn)的指針q不會(huì)移出表尾
q = q->next;
}
L->next = r; //當(dāng)從循環(huán)出來(lái)時(shí)說(shuō)明p為空，則r就是最后一個(gè)節(jié)點(diǎn)，此時(shí)把最后一個(gè)節(jié)點(diǎn)作為首節(jié)點(diǎn)
}2.12 兩個(gè)鏈表的合并
//（11）兩個(gè)鏈表的合并,把B有順序地插入A中(假設(shè)A是有順序的)
void CombineList(LinkList& A, LinkList& B)
{
LinkList q, p, r;
q = A; //q指向A的頭指針
p = B->next; //p指向B的第一個(gè)結(jié)點(diǎn)
while (p)
{
while ((q->next) && (q->next->data < p->data))
{
q = q->next;
} //找到現(xiàn)在的p應(yīng)該插入到哪的位置
r = p;
p = p->next;
r->next = q->next;
q->next = r;
}
}
2.13 main函數(shù)
#include<iostream>
#include"stdlib.h"
using namespace std;
#define Elemtype int
int main()
{
LinkList L;
//(1)初始化鏈表，形成帶有"頭節(jié)點(diǎn)"的空鏈表
Initlist(L);
//(2)使用頭插法建立鏈表
List_HeadInsert(L);
Print_list(L);
//(3)使用尾插法建立鏈表
List_TailInsert(L);
Print_list(L);
//(4)按照序號(hào)進(jìn)行查找
int n1;
cout << "想要查找的位置序號(hào)是：" << endl;
cin >> n1;
LinkList p;
p = GetElem(L, n1);
cout << p->data << endl;
//(5)按值查找結(jié)點(diǎn)位置信息
int n2;
cout << "想要查找的數(shù)值是：" << endl;
cin >> n2;
cout << LocateElem(L,n2) << endl;
//(6)在第i個(gè)位置插入結(jié)點(diǎn)
int n3;
int n4;
cout << "想要（后插法）插入的位置和值分別是：" << endl;
cin >> n3 >> n4;
ListInsert(L, n3, n4);
Print_list(L);
//(7)在第i個(gè)位置插入結(jié)點(diǎn)
int n5;
cout << "想要?jiǎng)h除的位置分別是：" << endl;
cin >> n5;
ListDelete(L, n5);
Print_list(L);
//(8)鏈表逆置
ListReverse(L);
Print_list(L);
//(9)合并兩個(gè)鏈表
LinkList L1;
Initlist(L1);
List_TailInsert(L1);
cout << "合并兩個(gè)鏈表的結(jié)果是：" << endl;
CombineList(L, L1);
Print_list(L);
system("pause");
return 0;
}三、不帶頭結(jié)點(diǎn)的程序說(shuō)明
????????如果不帶頭結(jié)點(diǎn)的單鏈表，則對(duì)表頭的操作（插入和刪除）要特殊處理，例如HeadInsert（頭插法創(chuàng)建單鏈表）每次插入后都要更新頭指針，而對(duì)于帶頭結(jié)點(diǎn)的單鏈表，它的頭指針指向永遠(yuǎn)是頭結(jié)點(diǎn)，只需要修改頭結(jié)點(diǎn)的后繼就可以完成插入。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-745794.html
3.1 單鏈表的存儲(chǔ)結(jié)構(gòu)
typedef struct LNode {
Elemtype data;
struct LNode* next;
}LNode,*LinkList;3.2 初始化
bool InitList(LinkList& L)
{
L = new LNode;
L = NULL; //不帶頭結(jié)點(diǎn)，區(qū)別：L->next=NULL
return true;
}3.3 頭插法建立單鏈表
void HeadInsert(LinkList& L)
{
int n;
cout << "請(qǐng)輸入插入元素的個(gè)數(shù)" << endl;
cin >> n;
cout << "請(qǐng)依次輸入元素的值" << endl;
LinkList s; //定義指針變量s
while (n--)
{
s = new LNode; //定義變量結(jié)點(diǎn)
cin >> s->data;
s->next = L;
L = s;//更新頭指針
}
}3.4 尾插法建立單鏈表
void TailInsert(LinkList& L)
{
int n;
cout << "請(qǐng)輸入插入元素的個(gè)數(shù)" << endl;
cin >> n;
cout << "請(qǐng)依次輸入元素的值" << endl;
LinkList s; //定義指針變量s
LinkList r; //定義一個(gè)表尾指針r
r = new LNode;
while (n--)
{
if (L == NULL)
{
s = new LNode;
cin >> s->data;
s->next = L;
L = s; //更新頭指針L
r = s; //更新尾指針r
}
else
{
s = new LNode;
cin >> s->data;
s->next = r->next;
r->next = s;
r = s;
}
}
}3.5 打印鏈表
void PrintList(LinkList& L)
{
LinkList s;
s = L;
while (s)
{
cout << s->data << " ";
s = s->next;
}
cout << endl;
}3.6 求鏈表的長(zhǎng)度
int Length_list(LinkList& L)
{
int length = 0;
LinkList s;
s = L;
while (s)
{
length++;
s = s->next;
}
return length;
}3.7 按位置序號(hào)查找結(jié)點(diǎn)
LNode* GetElem(LinkList& L, int i)
{
if (i<1 || i>Length_list(L))
return NULL;
int j = 1;
LNode* p = L; //鏈表第一個(gè)結(jié)點(diǎn)賦給p
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p; //返回第i個(gè)結(jié)點(diǎn)的指針，"p != NULL"其實(shí)是在和表長(zhǎng)對(duì)比，但我這里其實(shí)不需要
}3.8 按值查找位置信息
int LocateElem(LinkList& L, Elemtype e)
{
LNode* p = L; //第一個(gè)結(jié)點(diǎn)賦給p;
int j = 1;
while (p != NULL && p->data != e)
{
p = p->next;
j++;
}
return j;
}3.9在i位置插入新的結(jié)點(diǎn)（方法一）
//（8）在第i個(gè)位置插入結(jié)點(diǎn)(后插法)
bool ListInsert(LinkList& L, int i, Elemtype e)
{
if (i<1 || i>Length_list(L) + 1)
return false; //判斷i的合法性
if (i == 1)//這樣就能在第1個(gè)位置插入結(jié)點(diǎn)了
{
LinkList p;
p = new LNode; //創(chuàng)建想要插入的結(jié)點(diǎn)信息
p->next = L;
p->data = e;
L = p; //更新頭指針
}
else//不是在第1個(gè)位置插入結(jié)點(diǎn)
{
LinkList s;
s = GetElem(L, i - 1); //查找到第i-1個(gè)結(jié)點(diǎn)
LinkList p;
p = new LNode; //創(chuàng)建想要插入的結(jié)點(diǎn)信息
p->next = s->next;
p->data = e;
s->next = p;
}
return true;
}
3.10 在i位置插入新的結(jié)點(diǎn)（方法二）
//（9）在第i個(gè)位置插入結(jié)點(diǎn)(前插法)
bool List_HeadInsert(LinkList& L, int i, Elemtype e)
{
if (i<1 || i>Length_list(L) + 1)
return false; //判斷i的合法性
LinkList s;
s = GetElem(L, i); //查找到第i個(gè)結(jié)點(diǎn)
LinkList p;
p = new LNode;
p->next = s->next;
p->data = s->data;//定義一個(gè)結(jié)點(diǎn)p，復(fù)制原本i結(jié)點(diǎn)的全部信息
s->next = p;
s->data = e;//再把原本i結(jié)點(diǎn)變成插入的新結(jié)點(diǎn)的信息
return true;
}3.11 刪除第i個(gè)位置的結(jié)點(diǎn)
bool ListDelete(LinkList& L, int i)
{
if (i<1 || i>Length_list(L))
return false;
if (i == 1)
{
LNode* p = L;//第一個(gè)結(jié)點(diǎn)賦給p;
L = p->next; //更新頭指針
free(p);
}
else
{
LinkList s;
s = GetElem(L, i - 1);//查找到第i-1個(gè)結(jié)點(diǎn),是查不到第1個(gè)位置的
LinkList p; //被刪除的結(jié)點(diǎn)
p = s->next;
s->next = p->next;
free(p);
}
return true;
}3.13 main函數(shù)
#include<iostream>
using namespace std;
#include"stdlib.h"
#define Elemtype int
int main()
{
LinkList L;
InitList(L);
//（1）使用頭插法創(chuàng)建鏈表
//HeadInsert(L);
//PrintList(L);
//(2)使用尾插法創(chuàng)建鏈表
TailInsert(L);
PrintList(L);
//(3)按照位置序號(hào)進(jìn)行查找
//int n1;
//cout << "想要查找的位置序號(hào)是：" << endl;
//cin >> n1;
//LinkList p;
//p = GetElem(L, n1);
//cout << p->data << endl;
//(4)按值查找結(jié)點(diǎn)位置信息
//int n2;
//cout << "想要查找的數(shù)值是：" << endl;
//cin >> n2;
//cout << LocateElem(L, n2) << endl;
//(5)后插法插入結(jié)點(diǎn)
//ListInsert(L, 1, 1);
//PrintList(L);
//（6）前插法插入結(jié)點(diǎn)
//List_HeadInsert(L, 1, 3);
//PrintList(L);
//(7)刪除結(jié)點(diǎn)
ListDelete(L, 1);
PrintList(L);
system("pause");
return 0;
}四、思考
????????對(duì)于單鏈表，分為不帶頭結(jié)點(diǎn)和帶頭結(jié)點(diǎn)，有頭結(jié)點(diǎn)只是可以少一些對(duì)于頭指針的更新操作，鏈表的第一個(gè)元素和其他元素的處理是通用的，就會(huì)方便一點(diǎn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-745794.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)（2）—單鏈表（帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
