C++详解如何实现单链表

第C++详解如何实现单链表目录单链表单链表的基本操作1.初始化2.取值3.查找4.插入5.删除示例代码开发环境运行结果

单链表

链表内存空间不一定连续，其扩展性较好。多余的不多说了。该文主要记录单链表的实现，该单链表含有一个非空的头节点。链表的操作实际上是对其指针域与数据域的操作。

线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

单链表中结点类型的描述如下：

typedefstructLNode{//定义单链表节点类型

ElemTypedata;//数据域

structLNode*next;//指针域

};LNode,*LinkList;

单链表的基本操作

1.初始化

单链表的初始化操作就是构造一个空表。

具体代码：

//初始化单链表

voidInitList(LinkListL)//构造一个空的单链表L

L=newLNode;//生成新节点作为头节点，用头指针L指向头节点

L-next=NULL;//头节点的指针域置空

2.取值

和顺序表不同，在链表中并没有存储在物理相邻的单元中。所以我们只能从链表的首节点出发，顺着链域next逐个节点向下访问。

具体代码：

//单链表的取值

boolGetElem(LinkListL,inti,ElemTypee)

LinkListp=L-next;intj=1;//初始化，p指向首元节点，计数器j初值为1

while(pji)//顺着链域向后查找，直到p为空或p指向第i个元素

p=p-next;//p指向下一个节点

++j;//计数器j相应加1

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

e=p-data;//取第i个节点的数据域

returntrue;

3.查找

从链表的首元节点出发，依次将节点值和给定值e进行比较，返回查找结果。

具体代码：

//单链表的查找

boolLocateElem(LinkListL,LNode*p,ElemTypee)

//在单链表中查找第一个数据为e的结点

p=L-next;//p指向首元结点

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个结点

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个结点删除

LinkListp=L;

LNode*q;

intj=0;

while(p-nextji-1)//p指向第i-1个结点

p=p-next;

j++;

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

returnfalse;

q=p-next;//临时保存被删结点的地址以备释放

p-next=q-next;

e=q-data;//保存被删结点的数据

deleteq;//释放被删结点的空间

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;

//有头节点的链表

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)

//有空的头节点

pHead=pHead-pNext;

if(pHead-data==value)

nPos=i;

break;

returnnPos;

LinkList*LinkNode::getFirstNodeLinkList()

if(m_pHead==nullptr)

returnnullptr;

returnm_pHead-pNext;//有空的头节点

voidLinkNode::printLinkList(PrintLinkListprint)

if(m_pHead==nullptr)

return;

//不能直接移动头节点，需要保留头节点

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={"术后",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"链表的节点数："plinkList-getSizeLinkList()endl;

plinkList-removeByPosInLinkList(1);

cout"remove"endl;

plinkList-printLinkList(myPrint);

cout"删除后链表的节点数："plinkList-getSizeLinkList()end