[数据结构与算法] 单链表的实现（带头结点/不带头结点）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 单链表的实现（带头结点/不带头结点） -> 正文阅读

[数据结构与算法]单链表的实现（带头结点/不带头结点）

带头结点

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

//单链表结点的定义 
typedef struct LNode{
	int data;
	struct LNode *next;	
}LNode,*LinkedList;

//单链表的初始化
bool InitList(LinkedList &L){
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL) return false;
	L->next=NULL;
	return true;
} 
//头插法建立单链表
LinkedList InsertHead(LinkedList &L){
	LNode *s;int x;
	L=(LNode *)malloc(sizeof(LNode));
	L->next=NULL;
	cout<<"请输入要插入的数据（9999为退出）："<<endl;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		cout<<"请输入要插入的数据（9999为退出）："<<endl;
		scanf("%d",&x);
	}
	return L;	
}
//尾插法建立单链表
LinkedList InsertTail(LinkedList &L){
	LNode *s;int x;
	L=(LNode *)malloc(sizeof(LNode));
	L->next=NULL;
	LinkedList p=L;
	cout<<"请输入要插入的数据（9999为退出）："<<endl;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		p->next=s;
		p=s;
		cout<<"请输入要插入的数据（9999为退出）："<<endl;
		scanf("%d",&x);	
	}
	p->next=NULL;
	return L;
}
//判断单链表是否为空
bool isEmpty(LinkedList &L){
	return L==NULL; 
}
//按照位序插入
bool ListInsert(LinkedList &L,int i,int e){
	if(i<1) return false;
	LNode *p=L;
	int j=0;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
//	1 2 3 4
	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 InsertNextNode(LNode *p,int 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 InsertBeforeNode(LNode *p,int e){
	if(p==NULL) return false;
	LNode* s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL) return false;
	//改变p数据的值 
	s->data=p->data;
	p->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
//按位序删除
bool ListDelete(LinkedList &L,int i,int &e){
	if(i<1) return false;
	LinkedList p=L;
	int j=0;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	if(p==NULL) return false;
	if(p->next==NULL) return false;
	e=p->next->data;
	p->next=p->next->next;
	return true;
}
//指定节点的删除
bool DeleteNode(LinkedList &L,LNode *p){
	if(p==NULL) return false;
	if(p->next!=NULL){
		p->data=p->next->data;
		p->next=p->next->next;
		return true;
	}
	LinkedList s=L;
	while(s->next->next!=NULL){
		s=s->next;
	}
	s->next=NULL; 
}
//按值查找
LNode * LocateElem(LinkedList &L,int e){
	LNode *p=L->next;
	while(p!=NULL&&p->data!=e) p=p->next;
	return p;
}
//输出链表
void print(LinkedList L){
	LinkedList p=L;
	cout<<"链表：";
	while(p!=NULL){
		if(p->next==NULL){
			cout<<p->data;
		}
		else{
			cout<<p->data<<"->"; 
		}
		p=p->next;
	}
}

?不带头结点

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

//单链表结点的定义 
typedef struct LNode{
	int data;
	struct LNode *next;	
}LNode,*LinkedList;

//单链表的初始化
bool InitList(LinkedList &L){
	L=NULL;
	return true;
} 
//头插法建立单链表
LinkedList InsertHead(LinkedList &L){
	LNode *s;int x;
	L=NULL;
	cout<<"请输入要插入的数据（9999为退出）："<<endl;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		s->next=NULL;
		LNode * l=L;
		L=s;
		L->next=l;
		cout<<"请输入要插入的数据（9999为退出）："<<endl;
		scanf("%d",&x);
	}
	return L;	
}
//尾插法建立单链表
LinkedList InsertTail(LinkedList &L){
	LNode *s;int x;
	L=NULL;
	cout<<"请输入要插入的数据（9999为退出）："<<endl;
	scanf("%d",&x);
	LinkedList p; 
	int flag=0;
	while(x!=9999){
		if(flag==0){
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		s->next=NULL;
		L=s;
		p=L;
		flag=1;
		cout<<"请输入要插入的数据（9999为退出）："<<endl;
		scanf("%d",&x);	
		continue;
		}
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		s->next=NULL;
		p->next=s;
		p=s;
		cout<<"请输入要插入的数据（9999为退出）："<<endl;
		scanf("%d",&x);	
	}
	p->next=NULL;
	return L;
}
//判断单链表是否为空
bool isEmpty(LinkedList &L){
	return L==NULL; 
}
//按照位序插入
bool ListInsert(LinkedList &L,int i,int e){
	if(i<1) return false;
	if(i==1){//插到第一个 
		LNode *s=(LNode *)malloc(sizeof(LNode));
		if(s==NULL) return false;
		s->data=e;
		s->next=L;
		L=s;
		LinkedList p=L;
		return true;
	}
	LNode *p=L;
	int j=0;
	while(p!=NULL&&j<i-2){
		p=p->next;
		j++;
	}
	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 InsertNextNode(LNode *p,int 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 InsertBeforeNode(LNode *p,int e){
	if(p==NULL) return false;
	LNode* s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL) return false;
	//改变p数据的值
	s->data=p->data;
	p->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
//按位序删除
bool ListDelete(LinkedList &L,int i,int &e){
	if(i<1) return false;
	if(L==NULL) return false;
	if(i==1){
		e=L->data;
		L=L->next;
		return true;
	}
	LinkedList p=L;
	int j=0;
	while(p!=NULL&&j<i-2){
		p=p->next;
		j++;
	}
	if(p==NULL) return false;
	if(p->next==NULL) return false;
	e=p->next->data;
	p->next=p->next->next;
	return true;
}
//指定节点的删除
bool DeleteNode(LinkedList &L,LNode *p){
	if(p==NULL) return false;
	if(p->next!=NULL){
		p->data=p->next->data;
		p->next=p->next->next;
		return true;
	}
	LinkedList s=L;
	while(s->next->next!=NULL){
		s=s->next;
	}
	s->next=NULL; 
}
//按值查找
LNode * LocateElem(LinkedList &L,int e){
	LNode *p=L->next;
	while(p!=NULL&&p->data!=e) p=p->next;
	return p;
}
//输出链表 
void print(LinkedList L){
	LinkedList p=L;
	cout<<"链表：";
	while(p!=NULL){
		if(p->next==NULL){
			cout<<p->data;
		}
		else{
			cout<<p->data<<"->"; 
		}
		p=p->next;
	}
}

?总结：推荐使用带头结点的链表实现，用起来比较方便

如果感觉文章写的不错，可以点个小小的赞哦~