C++詳解如何實現(xiàn)單鏈表

第C++詳解如何實現(xiàn)單鏈表目錄單鏈表單鏈表的基本操作1.初始化2.取值3.查找4.插入5.刪除示例代碼開發(fā)環(huán)境運行結(jié)果

單鏈表

鏈表內(nèi)存空間不一定連續(xù)，其擴展性較好。多余的不多說了。該文主要記錄單鏈表的實現(xiàn)，該單鏈表含有一個非空的頭節(jié)點。鏈表的操作實際上是對其指針域與數(shù)據(jù)域的操作。

線性表的鏈?zhǔn)酱鎯τ址Q為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素。為了建立數(shù)據(jù)元素之間的線性關(guān)系，對每個鏈表結(jié)點，除存放元素自身的信息外，還需要存放一個指向其后繼的指針。

單鏈表中結(jié)點類型的描述如下：

typedefstructLNode{//定義單鏈表節(jié)點類型

ElemTypedata;//數(shù)據(jù)域

structLNode*next;//指針域

};LNode,*LinkList;

單鏈表的基本操作

1.初始化

單鏈表的初始化操作就是構(gòu)造一個空表。

具體代碼：

//初始化單鏈表

voidInitList(LinkListL)//構(gòu)造一個空的單鏈表L

L=newLNode;//生成新節(jié)點作為頭節(jié)點，用頭指針L指向頭節(jié)點

L-next=NULL;//頭節(jié)點的指針域置空

2.取值

和順序表不同，在鏈表中并沒有存儲在物理相鄰的單元中。所以我們只能從鏈表的首節(jié)點出發(fā)，順著鏈域next逐個節(jié)點向下訪問。

具體代碼：

//單鏈表的取值

boolGetElem(LinkListL,inti,ElemTypee)

LinkListp=L-next;intj=1;//初始化，p指向首元節(jié)點，計數(shù)器j初值為1

while(pji)//順著鏈域向后查找，直到p為空或p指向第i個元素

p=p-next;//p指向下一個節(jié)點

++j;//計數(shù)器j相應(yīng)加1

if(!p||ji)returnfalse;//i值不合法

e=p-data;//取第i個節(jié)點的數(shù)據(jù)域

returntrue;

3.查找

從鏈表的首元節(jié)點出發(fā)，依次將節(jié)點值和給定值e進(jìn)行比較，返回查找結(jié)果。

具體代碼：

//單鏈表的查找

boolLocateElem(LinkListL,LNode*p,ElemTypee)

//在單鏈表中查找第一個數(shù)據(jù)為e的結(jié)點

p=L-next;//p指向首元結(jié)點

while(pp-data!=e)

p=p-next;

if(p)

returntrue;

returnfalse;

}

4.插入

//單鏈表的插入

boolListInsert(LinkListL,inti,ElemTypee)

LinkListp=L;

LNode*s;

intj=0;

while(pji-1)//p指向第i-1個結(jié)點

p=p-next;

j++;

if(!p||i1)//i大于表長+1或小于1，插入位置不合法

returnfalse;

s=newLNode;

s-data=e;

s-next=p-next;

p-next=s;

returntrue;

5.刪除

//單鏈表的刪除

boolListDelete(LinkListL,inti,ElemTypee)

//將單鏈表的第i個結(jié)點刪除

LinkListp=L;

LNode*q;

intj=0;

while(p-nextji-1)//p指向第i-1個結(jié)點

p=p-next;

j++;

if(!(p-next)||i1)//i大于表長或小于1，刪除位置不合法

returnfalse;

q=p-next;//臨時保存被刪結(jié)點的地址以備釋放

p-next=q-next;

e=q-data;//保存被刪結(jié)點的數(shù)據(jù)

deleteq;//釋放被刪結(jié)點的空間

returntrue;

示例代碼

直接上代碼：

LinkList.h

#pragmaonce

typedefstructLINKLIST{

void*data;

structLINKLIST*pNext;

}LinkList;

typedefvoid(*PrintLinkList)(void*);

//無頭的鏈表

classLinkNode

public:

LinkNode();

~LinkNode();

voidinsertLinkList(intpos,void*data);

voidremoveByPosInLinkList(intpos);

intgetSizeLinkList();

intfindValueInLinkList(void*value);

LinkList*getFirstNodeLinkList();

voidprintLinkList(PrintLinkListprint);

private:

LinkList*m_pHead;

intm_size;

};

LinkList.cpp

//LinkList.cpp

#include"LinkList.h"

#includeiostream

usingnamespacestd;

LinkNode::LinkNode()

m_pHead=newLinkList;

m_pHead-data=nullptr;

m_pHead-pNext=nullptr;

m_size=0;

LinkNode::~LinkNode()

if(m_pHead!=nullptr)

while(m_pHead!=nullptr)

LinkList*pNext=m_pHead-pNext;

deletem_pHead;

m_pHead=nullptr;

m_pHead=pNext;

voidLinkNode::insertLinkList(intpos,void*data)

if(m_pHead==nullptr)

return;

if(data==nullptr)

return;

//插入位置矯正

if(pos0||posm_size)

pos=m_size;

LinkList*insertNode=newLinkList;

insertNode-data=data;

insertNode-pNext=nullptr;

//找到前一個位置（pos從0開始）

LinkList*pPre=m_pHead;

for(inti=0;ipos;++i)

pPre=pPre-pNext;

//有頭節(jié)點的鏈表

insertNode-pNext=pPre-pNext;

pPre-pNext=insertNode;

m_size++;

voidLinkNode::removeByPosInLinkList(intpos)

if(m_pHead==nullptr)

return;

if(pos0||pos=m_size)

return;

//找到前一個位置（pos從0開始）

LinkList*pPre=m_pHead;

for(inti=0;ipos;++i)

pPre=pPre-pNext;

LinkList*delNode=pPre-pNext;

pPre-pNext=delNode-pNext;

deletedelNode;

delNode=nullptr;

m_size--;

intLinkNode::getSizeLinkList()

returnm_size;

intLinkNode::findValueInLinkList(void*value)

intnPos=-1;

if(m_pHead==nullptr)

returnnPos;

if(value==nullptr)

returnnPos;

LinkList*pHead=m_pHead;

for(inti=0;im_size;++i)

//有空的頭節(jié)點

pHead=pHead-pNext;

if(pHead-data==value)

nPos=i;

break;

returnnPos;

LinkList*LinkNode::getFirstNodeLinkList()

if(m_pHead==nullptr)

returnnullptr;

returnm_pHead-pNext;//有空的頭節(jié)點

voidLinkNode::printLinkList(PrintLinkListprint)

if(m_pHead==nullptr)

return;

//不能直接移動頭節(jié)點，需要保留頭節(jié)點

LinkList*pTemp=m_pHead;

pTemp=pTemp-pNext;

while(pTemp!=nullptr)

print(pTemp-data);

pTemp=pTemp-pNext;

coutendl;

}

mian.cpp

#includeiostream

#include"LinkList.h"

usingnamespacestd;

typedefstructPERSON{

charname[64];

intage;

intscore;

}Person;

voidmyPrint(void*data)

Person*p=(Person*)data;

cout"name:"p-name"age:"p-age"score:"p-scoreendl;

voidtest()

LinkNode*plinkList=newLinkNode;

Personp1={"husdh",23,78};

Personp2={"hudfs",23,98};

Personp3={"術(shù)后",23,78};

Personp4={"喀什",23,67};

plinkList-insertLinkList(0,p1);

plinkList-insertLinkList(1,p2);

plinkList-insertLinkList(2,p3);

plinkList-insertLinkList(3,p4);

plinkList-printLinkList(myPrint);

cout"鏈表的節(jié)點數(shù)："plinkList-getSizeLinkList()endl;

plinkList-removeByPosInLinkList(1);

cout"remove"endl;

plinkList-printLinkList(myPrint);

cout"刪除后鏈表的節(jié)點數(shù)："plinkList-getSizeLinkList()end