单链表的常见基础算法（二）

r囧r小猫 2023-05-30 04:57 39阅读 0赞

**1、求单链表中的一个最小值  
2、单链表逆置  
3、L为带头结点的单链表，实现从尾到头反向输出每个结点值  
4、递归删去不带头结点的单链表中所有值为x的结点  
5、无序链表中删除所有值为x的结点并释放其空间  
6、带头结点的单链表中删除所有介于给定的两个值之间的元素  
7、带头结点的单链表中删除一个最小值结点  
8、对带头结点的单链表L，设计一个算法使其元素递增有序  
9、按递增次序输出单链表中各节点的数据元素，并释放结点所站的存储空间**

*  **求单链表中的一个最小值**

LNode GetMin(LinkList &L){
        
    	LNode *p=L->next;
    	if(p==NULL) return NULL;
    	LNode *minp=p;
    	while(p!=NULL){
         //遍历单链表，寻找单链表中的最小值
    		if(p->data<minp->data)
    			minp=p;
    		p=p->next;
    	}
    	return minp;
    }

*  **单链表逆置**

//方法一：采用头插法
    LinkList Reverse(LinkList &L){
        
    	LNode *p=L>next,*q;
    	L->next=NULL;//采用头插法，首先将原链表的头结点置为空
    	if(p==NULL) return NULL;
    	//头插法
    	while(p!=NULL){
        
    		q=p->next;
    		p->next=L->next;
    		L->next=p;
    		p=q;
    	}
    	return L;
    }
    //方法二：通过尾指针和头指针的移动
    LinkList Reverse(LinkList &L,LNode *r){
        
    	LNode *p,*r;
    	p=L;
    	while(p->next!=r){
        
    		q=p->next;
    		p->next=q->next;
    		q->next=r->next;
    		r->next=q;
    	}
    	return L;
    }

*  **L为带头结点的单链表，实现从尾到头反向输出每个结点值**

方法一：逆置算法，先将链表逆置，然后遍历结点依次输出
    方法二：使用递归
    void R_Print(LinkList &L){
        
    	if(L->next!=NULL){
        
    		R_Print(L->next)
    		print(L->data);
    	}
    }

*  **递归删去不带头结点的单链表中所有值为x的结点**

void Del_x(LinkList &L,ElemType x){
        
    	LNode *p;
    	if(L==NULL) return;
    	if(L->data==x){
        
    		p=L;
    		L=L->next;
    		free(p);
    		Del_x(L,x);
    	}
    	else{
        
    		Del_x(L->next,x);
    	}
    }

*  **无序链表中删除所有值我x的结点并释放其空间**

//方法一：用一般在单链表中删除结点的方法
    void Del_x(LinkList &L,ElemType){
        
    	LNode *p,*q,*pre;
    	pre=L;
    	p=L->next;
    	while(p!=NULL){
        
    		if(p->data==x){
         //找到值为x的结点删除
    			q=p;
    			p=p->next;
    			pre->next=q->next;
    			free(q);
    		}else{
        
    			pre=p;
    			p=p->next;
    		}
    	}
    }
    方法二：尾插法建立单链表
    void Del(LinkList &L,ElemType x){
        
    	LNode *p=L->next,*r=L,*q;
    	while(p!=NULL){
        
    		if(p->data==x){
        
    			q=p;
    			p=p->next;
    			free(q);
    		}else{
        
    			r->next=p;
    			r=p;
    			p=p->next;
    		}
    	}
    	r=NULL;
    }

*  **带头结点的单链表中删除所有介于给定的两个值之间的元素**

void Del_Range(LinkList &L,ElemType x,ElemType y){
        
    	LNode *p=L->next,*q,*pre;
    	pre=L;
    	while(p!=NULL){
        
    		if(p->data>=x&&p->data<=y){
        
    			q=p;
    			p=p->next;
    			pre->next=q->next;
    			free(q);
    		}else{
        
    			pre=p;
    			p=p->next;
    		}
    	}
    }

*  **带头结点的单链表中删除一个最小值结点**

void Del_Min(LinkList &L){
        
    	LNode *pre,*minp,*minpre,*p;
    	p=L->next;
    	minp=p;
    	pre=L;
    	while(p!=NULL){
        
    		if(p->data<minp->data){
        
    			minp=p;
    			minpre=pre;
    		}
    		pre=p;
    		p=p->next;
    	}
    	//删除minp结点
    	minpre=minp->next;
    	free(minp);
    }

*  **对带头结点的单链表L，设计一个算法使其元素递增有序**

//首先构造只含一个数据结点的链表，然后每次遍历链表中的一个元素，找合适的位置将其插入【直接插入排序算法的思想】
    void Sort(LinkList &L){
        
    	LNode *p=L->next,*r,*pre;
    	pre=L;
    	p->next=NULL;
    	while(p!=NULL){
        
    		r=p->next;
    		pre=L;
    		while(pre->next!=NULL&&pre->next->data<p->data){
        
    			pre=pre->next;
    		}
    		//将p结点插入pre结点之后
    		p->next=pre->next;
    		pre->next=p;
    		p=r;
    	}
    }
    //方法二：通过暴力比较,容易想到，不推荐
    
    ```cpp
    void Sort(LinkList &L){
        
    	LNode *p=L->next,*q;
    	ElemType temp;
    	while(p!=NULL){
        
    		q=p->next;
    		while(q!=NULL){
        
    			if(q->data<p->data){
        
    				temp=p->data;
    				p->data=q->data;
    				q->data=temp;
    			}
    			q=q->next;
    		}
    		p=p->next;
    	}
    }

*  **按递增次序输出单链表中各节点的数据元素，并释放结点所站的存储空间**

//对链表进行遍历，每次找出链表中最小值的元素，输出并删除
    void PrintMinToMax(LinkList &L){
        
    	LNode *p,*pre,*minpre,*minp;
    	while(L->next!=NULL){
        
    		p=L->next;
    		minp=p;
    		minpre=pre=L;
    		while(p!=NULL){
        
    			if(p->data<minp->data){
        
    				minp=p;
    				minpre=pre;
    			}
    			pre=p;
    			p=p->next;
    		}//最小值找到
    		print(minp->data);
    		//删除
    		minpre->next=minp->next;
    		free(minpre); // 一次输出完成
    	}
    	//释放头结点
    	free(L);
    }

*  **带头结点的单链表，查找链表倒数第k个位置上的结点，输出对应元素**

void getElem(LinkList L,int k){
        
    	LNode *p=L->next;
    	int length=0,n;
    	//求单链表的表长
    	while(p!=NULL){
        
    		length++;
    		p=p->next;
    	}
    	n=length-k+1;//查找链表倒数第k个位置的结点相当于查找链表中第n个结点的位置
    	if(n<=0) return;
    	p=L->next;
    	while(k!=0){
        
    		p=p->next;
    		k--;
    	}
    	cout<<p->data<<ednl;
    }

*  **对带头结点的循环链表表示队列，只有队尾指针没有头指针，写出出队、入队算法**

//入队
    void EnQueue_LinkList(LinkList &r,ElemType x){
        
    	//直接在队尾进行插入即可
    	LNode *s=(LNode *)malloc(Sizeof(LNode));
    	s->data=x;
    	s->next=r->next;
    	r->next=s;
    	r=s;
    }
    //出队
    void DeQueue_LinkList(LinkList &r,ElemType x){
        
    	if(r->next==r) return;//队空
    	LNode *p=r->next *q;
    	q=p->next;
    	p->next=q->next;
    	if(q==r){
        //只有一个元素
    		r=p;
    	}
    	free(q);
    	
    }

*  **判断一个链表是否存在环**

bool isLoop(LinkList L){
        
    	LNode *p,*q;
    	p=q=L;
    	//让p指针每次走一步，q指针每次走两步，若存在环，则p、q会相遇
    	while(q!=NULL&&q->next!=NULL&&p!=q){
        
    		p=p->next;
    		q=q->next->next;
    	}
    	if(p1==p2)
    		reutrn true;
    	else
    		return false;
    }