指针单链表

你的名字 2023-02-23 08:44 91阅读 0赞

## 使用指针域进行初始化单链表的两种方式 ##

## 1.头插法进行初始化（详情见代码注释） ##

#include <iostream>
    #include <stdlib.h>
    using namespace std;
    typedef struct LNode{
        
    	int data; //数据域
    	struct LNode *next;//指针域
    }LNode,*LinkList;  //定义非指针变量和指针变量的结点
    LinkList initLinkList(LinkList &L){
         //定义函数进行初始话
    	LNode *s; //定义指针变量存储新建结点
    	L = (LinkList)malloc(sizeof(LNode)); //新建一个LinkList类型的结点，并且将地址赋给L
    	L->next = NULL; //将L指向的结点的指针域初始化为空
    	int value;  
    	cin>>value;
    	while(value!=-1){
        
    		s = (LinkList)malloc(sizeof(LNode));//初始化新建结点
    		s->data  = value; //将value数据存入s指向的结点的数据域
    		s->next = L->next;  //将新建结点的指针域置为空值，即为尾结点
    		L->next = s; //将s指向的结点的地址赋值给L的指针域
    		cin>>value;
    	}
    	return L;
    }
    int main(){
        
    	LinkList L; 
    	initLinkList(L);  //调用函数
    	return 0;
    }

## 2.尾插法进行初始化（详情见代码注释） ##

LinkList initLinkList2(LinkList &L){
        
    	int value;   //创建输入的值 
    	L = (LinkList)malloc(sizeof(LNode)); //新建结点，并使用指针L指向结点 
    	LNode *s , *r = L; //创建两个指针变量，*s为插入输入的变量 *r为尾部指针 
    	cin>>value;   //输入数据 
    	while(value!=-1){
        
    		s = (LNode *)malloc(sizeof(LNode));   //将新建的结点的地址给s 
    		s->data = value;   //新建的结点数据为value 
    		r->next=s;   //r指向的结点的指针域更改为s的地址 
    		r=s;   //r指向s 
    		cin>>value;
    	}
    	r->next = NULL;   //将尾部结点的指针域赋值为null 
    	return L;
    }

## 单链表的操作 ##

## 1.按照序号查找结点值 ##

LNode *GetElem(LinkList L,int i ){
        
    	int j=1;    //计数变量 
    	LNode *p = L->next;   //将第一个有数据的结点的地址赋给p; 
    	if(i==0){
           //如果i==0返回头结点 
    		return L; 
    	}
    	if(i<1){
           //非法下标，返回null 
    		return NULL;
    	}
    	while(p&&j<i){
           //从第一个结点开始找，查找第 i个结点 
    		p=p->next;
    		j++;
    	}
    	return p; //返回指针变量 ，当i大于表长，返回null值
    }

## 2.按照值查找结点 ##

LNode  *locateElem (LinkList L,int e){
        
    	LNode *p = L->next;   //将第一个结点的地址赋给p 
    	while(p->data!=e && p!=NULL)   //从第一个结点开始查找数据域为E的结点 
    	p=p->next;    
    	return p;
    }

## 3.插入结点操作 ##

LNode *InsertElem(LinkList L,int e,int i){
        
    	LNode *p = GetElem(L,i-1); //寻找插入位置的前驱结点
    	LNode *s = (LinkList)malloc(sizeof(LNode)); //开辟新结点
    	s->data = e;   //修改新节点的数据
    	s->next = p->next;   //新节点的指针域指向原来结点的后继
    	p->next = s;   //原来结点的后继指向新结点
    	cout<<"插入成功"<<endl; 
    }

## 4.删除结点操作 ##

LNode *DelElem(LinkList L,int i){
        
    	LNode *p = GetElem(L,i-1);   //寻找删除结点的前驱 
    	LNode *q = p->next;   //临时变量存储p结点的后继 
    	p->next = q->next;   // p结点的后继指向删除结点的后继 
    	free(q);   //删除q指向的结点 
    }

## 所有代码及测试 ##

#include <iostream>
    #include <stdlib.h>
    using namespace std;
    typedef struct LNode{
        
    	int data;
    	struct LNode *next;
    }LNode,*LinkList;
    LinkList initLinkList(LinkList &L){
        
    	LNode *s;
    	L = (LinkList)malloc(sizeof(LNode));
    	L->next = NULL;
    	int value;
    	cin>>value;
    	while(value!=-1){
        
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data  = value;
    		s->next = L->next;
    		L->next = s;
    		cin>>value;
    	}
    	return L;
    }
    
    LinkList initLinkList2(LinkList &L){
        
    	int value;   //创建输入的值 
    	L = (LinkList)malloc(sizeof(LNode)); //新建结点，并使用指针L指向结点 
    	LNode *s , *r = L; //创建两个指针变量，*s为插入输入的变量 *r为尾部指针 
    	cin>>value;   //输入数据 
    	while(value!=-1){
        
    		s = (LNode *)malloc(sizeof(LNode));   //将新建的结点的地址给s 
    		s->data = value;   //新建的结点数据为value 
    		r->next=s;   //r指向的结点的指针域更改为s的地址 
    		r=s;   //r指向s 
    		cin>>value;
    	}
    	r->next = NULL;   //将尾部结点的指针域赋值为null 
    	return L;
    }
    
    LNode *GetElem(LinkList L,int i ){
        
    	int j=1;    //计数变量 
    	LNode *p = L->next;   //将第一个有数据的结点的地址赋给p; 
    	if(i==0){
           //如果i==0返回头结点 
    		return L; 
    	}
    	if(i<1){
           //非法下标，返回null 
    		return NULL;
    	}
    	while(p&&j<i){
           //从第一个结点开始找，查找第 i个结点 
    		p=p->next;
    		j++;
    	}
    	return p; //返回指针变量 ，当i大于表长，返回null值
    }
    
    LNode  *locateElem (LinkList L,int e){
        
    	LNode *p = L->next;   //将第一个结点的地址赋给p 
    	while(p->data!=e && p!=NULL)   //从第一个结点开始查找数据域为E的结点 
    	p=p->next;    
    	return p;
    }
    
    LNode *InsertElem(LinkList L,int e,int i){
        
    	LNode *p = GetElem(L,i-1);
    	LNode *s = (LinkList)malloc(sizeof(LNode));
    	s->data = e;
    	s->next = p->next;
    	p->next = s;
    	cout<<"插入成功"<<endl; 
    }
    
    LNode *DelElem(LinkList L,int i){
        
    	LNode *p = GetElem(L,i-1);   //寻找删除结点的前驱 
    	LNode *q = p->next;   //临时变量存储p结点的后继 
    	p->next = q->next;   // p结点的后继指向删除结点的后继 
    	free(q);   //删除q指向的结点 
    }
    int main(){
        
    	LinkList L;
    	initLinkList2(L);
    	LNode *p = GetElem(L,2);   //将返回的地址给p 
    	cout<<p->data<<endl;//输出检索数据 
    	LNode *l = locateElem(L,2);
    	cout<<l<<endl;//输出结点的地址
    	cout<<l->data<<endl;//输出结点的数据 
    	InsertElem(L,2,2);
    	DelElem(L,2); 
    	return 0;
    }