单链表的创建,删除,插入,查找及源码(c++实现)
程序员文章站
2022-05-06 09:42:02
...
单链表节点的结构体
typedef struct LNode{
ElemType data;//节点的数据域
struct LNode *next; //节点的指针域---(结构体自引用),指向结构体的指针,指向同一类型不同结构
}LNode,*LinkList;
创建单链表
- 前插法
因为每次插入在链表的头部,所以应该逆序输入数据
void createlist(LinkList &L,int n,char b[]){
L=new Lnode;
L->next=NULL;//创建一个只有头结点的空链表
for(int i=0;i<n;i++){//创建一个节点,输入数据,并把节点放在头结点L的后边,因此整个链表看起来就像
LinkList p = new Lnode;//是不断的将新赋值的节点放在链表的最前边,成为首元节点,所以叫前插法
p->data=b[i];
p->next=L->next;
L->next=p;
}
}
- 后插法
void createlist(LinkList &L,int n,char b[]){
L=new Lnode;
L->next= NULL;
LinkList r=L;
for(int i=0;i<n;i++)//使新赋值的节点放在最后边,指针r始终指向尾结点
{
LinkList p=new Lnode;
p->data=b[i];
p->next=NULL;
r->next=p;
r=p;
}
}
单链表的插入
void ListInsert(LinkList &L,int i,char e)
{
if(i<=length(L)){//判断插入的位置是否合理
LinkList p=L;int j=0;
while(p&&(j<i-1))//如果p不为空且j小于要插入的位置,继续循环
{p=p->next;++j; }
if(!p||j>i-1)cout<< "error\n";
LinkList s=new Lnode;
s->data=e;
s->next=p->next;//注意这里交换的两步顺序不能搞反
p->next=s;
cout<< "succ\n";
}
else
cout<< "error\n";
}
单链表的删除
void ListDelete(LinkList &L,int i)//删除第i个节点
{if(i<=length(L)){
LinkList p=L;int j=0;
while((p->next)&&(j<i-1)){//找到第i-1个节点
p=p->next;++j;
}
if(!(p->next)||(j>i-1))//判断删除位置是否合理
cout<<"error\n";
LinkList q=p->next;//临时保存被删节点的地址以备释放
p->next=q->next;
delete q;
cout<<"succ\n";
}
else
cout<<"error\n";
}
单链表的查找
void ListFind(LinkList L,char e)
{
LinkList p=L->next;
int i=1;
while(p&&p->data!=e){
p=p->next;
i++;}
if(p!=NULL){
cout<<i;
}
else
{cout<<"error\n";}
}
源码
#include<iostream>
using namespace std;
typedef struct Lnode
{
char data;
struct Lnode *next;
}Lnode,*LinkList;
//void createlist(LinkList &L,int n,char b[])//后插法
//{
// L=new Lnode;
// L->next= NULL;
// LinkList r=L;
// for(int i=0;i<n;++i)
// {
// LinkList p=new Lnode;
// p->data=b[i];
// p->next=NULL;
// r->next=p;
// r=p;
// }
//}
void createlist(LinkList &L,int n,char b[]){
L=new Lnode;
L->next=NULL;
for(int i=0;i<n;i++){
LinkList p = new Lnode;
p->data=b[i];
p->next=L->next;
L->next=p;
}
}
void print(LinkList L)
{
cout<<"表的数据如下";
L=L->next;
while(L!=NULL)
{
cout<<L->data;
L=L->next;
}
cout<<"\n";
}
int length(LinkList L)
{
int m=0;
L=L->next;
while(L!=NULL)
{
m++;
L=L->next;
}
return m;
}
void ListInsert(LinkList &L,int i,char e)
{
if(i<=length(L)){
LinkList p=L;int j=0;
while(p&&(j<i-1))
{p=p->next;++j; }
if(!p||j>i-1)cout<< "error\n";
LinkList s=new Lnode;
s->data=e;
s->next=p->next;
p->next=s;
cout<< "succ\n";
}
else
cout<< "error\n";
}
void ListDelete(LinkList &L,int i)
{if(i<=length(L)){
LinkList p=L;int j=0;
while((p->next)&&(j<i-1))
{
p=p->next;++j;}
if(!(p->next)||(j>i-1))
cout<<"error\n";
LinkList q=p->next;
p->next=q->next;
delete q;
cout<<"succ\n";
}
else
cout<<"error\n";
}
void ListFind(LinkList L,char e)
{
LinkList p=L->next;
int i=1;
while(p&&p->data!=e){
p=p->next;
i++;}
if(p!=NULL){
cout<<i;
}
else
{cout<<"error\n";}
}
int main()
{
LinkList L;
int a ,b,c;
char f,e;
cout<<"请输入要创建表的个数";
cin>>a;
cout<<" 要创建表的数据";
char d[10];
int i = 0;
for(;i<a;i++){
cin>>d[i];
}
createlist(L, a, d);
print(L);
cout<<"\n";
cout<<"插入表时要插入的位置";
cin>>b;
cout<<"插入的数据";
cin>>f;
ListInsert(L, b, f);
print(L);
cout<<"删除表中数的位置";
cin>>c;
ListDelete(L,c);
print(L);
cout<<"要查找表的数";
cin>>e;
print(L);
ListFind(L,e);
cout<<"\n";
return 0;
}
结果
- 需要注意的是因为头结点为空,数据是从首元节点开始的,所以链表的位置是从下标1开始的,0位置给了头结点,头结点是首元节点之前附设的一个节点,其指针域指向首元节点。本身不一定存储信息,其存在是为了使首元结点像其他节点一样方便操作,不需特殊处理。