单链表上的基本操作

单链表的定义

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

typedef struct LNode{			//定义单链表结点类型
    ElemType data;				//数据域
    struct LNode *next;		//指针域
}LNode,*LinkList;

单链表上基本操作的实现

1.采用头插法建立单链表

LinkList List_HeadInsert(LinkList &L){				//逆向建立单链表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));				//创建头结点
    L->next = NULL;									//初始化为空链表
    scanf("%d",&x);									//输入结点的值
    while(x!=9999){									//输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));			//建立新结点
        s->data = x;
        s->next = L->next;
        L->next = s;								//将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}			

2.采用尾插法建立单链表

LinkList List_TailInsert(LinkList &L){				//正向建立单链表
    int x;											//设置元素类型为整型
    L=(LinkList)malloc(sizeof(LNode));				
    LNode *s,*r=L;									//r为表尾指针
    scanf("%d",&x);
    while(x!=9999){
        s = (LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next = s;
        r = s;										//r指向新的表尾结点
        scanf("%d",&x);
        
    }
    r->next = NULL;
    return L;
}

3.按序号查找结点值

LNode *GetElem(LinkList L,int i){
    int j=1;							//计数，初始为1
    LNode *p = L->next;					//第1个结点指针赋给p
    if(i==0)
        return L;						//若i等于0，则返回头结点
    if(i<1)
        return NULL;					//若i无效，则返回NULL
    while(p&&j<i)						//从第一个结点开始找，查找第i个结点
    {
        p=p->next;
        j++;
    }
    return p;							//返回第i个结点的指针，若i大于表长，则返回NULL
}

4.按值查找表结点

LNode *LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;
    while(p!=NULL&&p->data!=e)			//从第i个结点开始查找data域为e的结点
    {
        p=p->next;
    }
    return p;							//找到后返回该结点指针，否则返回NULL
}

5.插入结点操作

//p所指结点是s所指结点的前驱结点
void Insert(LinkList &L,int i,int x){
	LNode *p;
	LNode *s=(LNode*)malloc(sizeof(LNode));				//一定要分配空间！！！！！
	s->data=x;
	s->next=NULL; 
	p=GetElem(L,i-1);
	if(p!=NULL){
		s->next =p->next;
		p->next=s;
	}else{
		cout<<"插入值非法"<<endl;
		return ; 
	}
	
}

对某一结点进行前插操作

//注意与插入结点相对比!!!!!!!!
void Delect(LinkList &L,int i){
	//p所指结点是q所指结点的前驱结点
	LNode *p;
	LNode *q=(LNode*)malloc(sizeof(LNode));			   //申请空间 
	p=GetElem(L,i-1);				    //查找删除位置的前驱结点
	if(p==NULL||p->next==NULL)          //p==NULL是i值不合法的情况 
	{								    //p->next==NUll是i-1号结点后已无其他结点 
		cout<<"删除值非法"<<endl;
		free(q);
		return ;
	}
	q=p->next;					//令q指向被删除的结点
	p->next=q->next;			//将*q结点从链中“断开”
	free(q);
								
}	

6.删除结点操作

//p所指结点是q所指结点的前驱结点
p=GetElem(L,i-1)			//查找删除位置的前驱结点
q=p->next;					//令q指向被删除的结点
p->next=q->next;			//将*q结点从链中“断开”
free(q);					//释放结点的储存空间

拓展:删除结点*p

q=p->next;					//令q指向*p的后继节点
p->data = p->next->data		//和后继结点交换数据域
p->next = q->next;			//将*q结点从链中“断开”
free(q);					//释放后继结点的储存空间

单链表上基本操作的完整实现

程序源代码

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
typedef struct LNode{			//定义单链表结点类型
    ElemType data;				//数据域
    struct LNode *next;		//指针域
}LNode,*LinkList;
LinkList List_HeadInsert(LinkList &L){				//逆向建立单链表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));				//创建头结点
    L->next = NULL;									//初始化为空链表
    scanf("%d",&x);									//输入结点的值
    while(x!=9999){									//输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));			//建立新结点
        s->data = x;
        s->next = L->next;
        L->next = s;								//将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}
LNode *GetElem(LinkList L,int i){
    int j=1;							//计数，初始为1
    LNode *p = L->next;					//第1个结点指针赋给p
    if(i==0)
        return L;						//若i等于0，则返回头结点
    if(i<1)
        return NULL;					//若i无效，则返回NULL
    while(p&&j<i)						//从第一个结点开始找，查找第i个结点
    {
        p=p->next;
        j++;
    }
    return p;							//返回第i个结点的指针，若i大于表长，则返回NULL
}	
LNode *LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;
    while(p!=NULL&&p->data!=e)			//从第i个结点开始查找data域为e的结点
    {
        p=p->next;
    }
    return p;							//找到后返回该结点指针，否则返回NULL
}
void PrintLinkList(LinkList L){        //这段代码根据链表表尾结点的 next 指针指向 NULL 来遍历整个链表。
	LNode *tmp = L->next;
	if(tmp==NULL)
	{
		cout<<"链表为空"<<endl;
		return ; 
	}
	while(tmp!=NULL){
		cout<<tmp->data<<" ";
		tmp=tmp->next;
	}
	cout<<endl; 
}	
void Insert(LinkList &L,int i,int x){
	LNode *p;
	LNode *s=(LNode*)malloc(sizeof(LNode));				//申请空间 
	s->data=x;
	s->next=NULL; 
	p=GetElem(L,i-1);
	if(p!=NULL){
		s->next =p->next;
		p->next=s;
	}else{
		cout<<"插入值非法"<<endl;
		return ; 
	}
	
}
//注意与插入结点相对比!!!!!!!!
void Delect(LinkList &L,int i){
	//p所指结点是q所指结点的前驱结点
	LNode *p;
	LNode *q=(LNode*)malloc(sizeof(LNode));			   //申请空间 
	p=GetElem(L,i-1);				    //查找删除位置的前驱结点
	if(p==NULL||p->next==NULL)          //p==NULL是i值不合法的情况 
	{								    //p->next==NUll是i-1号结点后已无其他结点 
		cout<<"删除值非法"<<endl;
		free(q);
		return ;
	}
	q=p->next;					//令q指向被删除的结点
	p->next=q->next;			//将*q结点从链中“断开”
	free(q);
								
}	
int main(){
	LinkList L;						//声明一个单链表 
	List_HeadInsert(L);				//使用头插法插入4个元素，分别是1,2,3,4 
	PrintLinkList(L);				//遍历这个单链表
	LNode *tmp;
	tmp=GetElem(L,2);				//找到位置为2的元素 
	if(tmp!=NULL){
		cout<<"位置为2的元素是："<<tmp->data<<endl;
	}else{
		cout<<"非法的位置"<<endl;
	}
	tmp=LocateElem(L,1);			//找到值为1的元素
	if(tmp!=NULL){
		cout<<"存在值为1的元素："<<tmp->data<<endl;
	}else{
		cout<<"没有找到该值"<<endl;
	}
	PrintLinkList(L);				//遍历这个单链表
	Insert(L,5,110);				//在5这个位置插入元素110
	PrintLinkList(L);				//遍历这个单链表
	Delect(L,2);        			//删除位序为2的元素
	PrintLinkList(L);				//遍历这个单链表
	return 0;
} 

程序输出

4 3 2 1
位置为2的元素是：3
存在值为1的元素：1
4 3 2 1
4 3 2 1 110
4 2 1 110