#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;
}
到此这篇c++单向链表实现（c++单链表的实现）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/78354.html