2025年c++单向链表实现（c++单链表的实现）

大家好，我是讯享网，很高兴认识大家。

#include <iostream>

//带头结点的链表

using namespace std;

typedef int ElemType;

//定义单链表

typedef struct LNode{

ElemType data;//数据域

struct LNode *next;//指针域

} LNode,Linklist;

//初始化单链表

bool InitList(Linklist &L){

L=(LNode)malloc(sizeof(LNode));//分配一个头结点

if(L==NULL)

return false;

L->next=NULL;

return true;

}

//尾插法建立单链表

Linklist List_TailInsert(Linklist &L){

ElemType x;

LNode *s,r=L;//r为尾指针

cout<<“请输入要插入的下一个数字,输入9999则表示结束！”<<endl;

cin>>x;//输入结点的值

while(x!=9999){

s=(LNode)malloc(sizeof(LNode));

s->data=x;//将x输入为s的数据

r->next=s;//r后接s

r=s;//将尾指针变为s

cin>>x;

}

r->next=NULL;

return L;

}

//头插法建立单链表

Linklist List_HeadInsert(Linklist &L){

LNode s;

ElemType x;

L->next=NULL;//防止脏数据

cout<<“请输入要插入的下一个数字,输入8888则表示结束！”<<endl;

cin>>x;

while(x!=8888){

s=(LNode)malloc(sizeof(LNode));

s->data=x;//x传入s的数据域中

s->next=L->next;//s指向和头结点指向相同

L->next=s;//s变成第一个结点

cin>>x;

}

return L;

}

//显示链表

void displayList(Linklist &L){

cout<<“当前链表为”<<endl;

LNode *r;

r=L->next;//r从第1个节点开始

while(r!=NULL){

cout<<r->data<<“ ”;

r=r->next;

}

cout<<endl;

}

//按位查找

LNode *GetElem(Linklist &L,int i){

if(i<0){

return NULL;

}

LNode *p;//指向扫描的结点

int j=0;//当前p指向第几个结点

p=L;//p变为头结点，头结点是第0个结点

while(p!=NULL&&j<i){

p=p->next;

j++;

}

讯享网

return p;

}

//后插操作

bool InsertNextNode(LNode*p,ElemType e){

if(p==NULL)

return false;

LNode *s=(LNode *)malloc(sizeof(LNode));//分配内存

if(s==NULL)

return false;//内存有可能分配失败

s->data=e;

s->next=p->next;

p->next=s;

return true;

}

//前插操作

bool InsertPriorNode(LNode*p,ElemType e){

if(p==NULL)

return false;

LNode *s=(LNode *)malloc(sizeof(LNode));//分配内存

if(s==NULL)

return false;//内存有可能分配失败

s->next=p->next;

p->next=s;

s->data=p->data;

p->data=e;

return true;

}

//删除指定的结点

bool DeleteNode(Linklist &L,LNode *p,ElemType &e){

if(p==NULL)

return false;

e=p->data;

//有个问题，如果是最后一个结点，只能从表头开始依次寻找p的前驱结点

if(p->next==NULL){

LNode *s=L;//s变为了头结点

while(s->next!=p){

s=s->next;

}

s->next=NULL;

free(p);

return true;

}

else{

LNode *q=p->next;

p->data=p->next->data;

p->next=q->next;

free(q);

return true;

}

//按位序插入

bool ListInsert(Linklist &L,int i,ElemType e){

LNode *p=GetElem(L,i-1);

InsertNextNode(p,e);//这里也可以用前插操作，只要上面改成i+1就可以

}

//按位序删除

bool ListDelete(Linklist &L,int i,ElemType &e){

LNode *p=GetElem(L,i);

/*另一种实现方式

if(p==NULL)

return false;

if(p->next==NULL)

return false;

LNode q=p->next;

e=q->data;

p->next=q->next;

free(q);/

DeleteNode(L,p,e);

}

//查看表长

int length(Linklist &L){

int j=0;

LNode *p=L;

while(p->next!=NULL){

p=p->next;

j++;

}

return j;

}

int main()

{

Linklist L;

InitList(L);

int number;

cout<<“===========输入1实现头插法建立链表===========”<<endl;

cout<<“===========输入2实现尾插法建立链表===========”<<endl;

cout<<“==============输入3实现插入操作==============”<<endl;

cout<<“==============输入4实现删除操作==============”<<endl;

cout<<“================输入5查看表长================”<<endl;

cout<<“================输入6查看链表================”<<endl;

cin>>number;

while(number!=0){

if(number==1){

List_TailInsert(L);

}

else if(number==2){

List_HeadInsert(L);

}

else if(number==3){

int len=length(L);

cout<<“请输入要插入的位置”<<endl;

int i;

cin>>i;

if(i>len+1||i<1)

cout<<“输入的位置出错！”<<endl;

else{

cout<<“请输入要插入的数据”<<endl;

ElemType e;

cin>>e;

ListInsert(L,i,e);

}

else if(number==4){

int len=length(L);

cout<<“请输入要删除的位置”<<endl;

int j;

cin>>j;

if(j<1||j>len)

cout<<“输入的位置出错！”<<endl;

else{

int data=-1;

ListDelete(L,j,data);

cout<<“删除的值为”<<data<<endl;

}

else if(number==5){

int len=length(L);

cout<<“表长为”<<len<<endl;

}

else if(number==6){

displayList(L);

}

else{

cout<<“输入的数字不符合规定！”<<endl;

}

cout<<“===========请重新选择数字，输入0表示结束！===========”<<endl;

cin>>number;

}

displayList(L);

return 0;

}

2025年c++单向链表实现（c++单链表的实现）

相关推荐