双向循环链表 (C语言实现双向循环链表) ------- 算法笔记003

客官°小女子只卖身不卖艺 2023-07-01 15:56 90阅读 0赞

## 概念 ##

> 我们常说的单链表是有向的链表，因为链表1中有next指针它对应指向链表2的地址  
> 而链表2无法指向链表1，所以我们说它是单向的链表。  
> 而双向链表则是链表1可以访问到链表2，链表2也可以访问到链表1  
> 双向循环链表则是头尾相连的双向链表

## 结构定义 ##

typedef struct Double{ 
    	ElemType data;
    	struct Double * next,* prior;
    }Doul,*DoulLink;

***注: 从图中我们可以看到结构定义中多了一个指向前一个节点的指针prior***

## 双向链表插入,删除原理图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]

## 程序代码 ##

> 创建一个双向链表

Doul * createDL(Doul * L,int size){ 
     	
     	  if(!L)
    		return NULL;
    	   
    	   
    		  DoulLink p,q; 
    		  int i;
    		  q=L;
    		  
    		for(i=0;i<size;i++){ 
    			p=(DoulLink)malloc(sizeof(Doul));
    			p->data='A'+i;
    	  		p->prior=q;
    	  		p->next=q->next; //null
    			q->next=p;
    			q=p;
    		}
    	  	q=L;
    	  	p->next=L->next;  //最后一个节点指向头结点的下一个元素节点
    	  	q->next->prior=p; //第一个元素节点的prior指向最后一个节点
    	  	L=q->next; //L指向第一个元素节点
    	  	free(q);  //释放头结点
    	  	return L;
     }

> 实现在第几个位置插入元素

void InsertDoul(Doul **L,ElemType data,int pos){ 
    		DoulLink p=(*L);
    		int i;
    		
    		for(i=0;i<pos-2;i++){ 
    			p=p->next;	
    		}
    		if(!p){ 
    			return;
    		}
    		if(p!=(*L)){ 
    			DoulLink s=(DoulLink)malloc(sizeof(Doul));
    			s->data=data;
    			s->next=p->next;
    			s->prior=p;
    			p->next->prior=s;
    			p->next=s;
    		}else{ 
    			if(pos==2){ 
    				DoulLink s=(DoulLink)malloc(sizeof(Doul));
    				s->data=data;
    				s->next=p->next;
    				s->prior=p;
    				p->next->prior=s;
    				p->next=s;
    			}else{ 
    				DoulLink s=(DoulLink)malloc(sizeof(Doul));
    				s->data=data;
    				s->next=p;
    				s->prior=p->prior;
    				p->prior->next=s;
    				p->prior=s;
    			}
    			
    		}
    	}

> 删除数据  
> 原理的思路同样：通过给定的数，遍历到对应的节点进行prior,next指针的操作

## 工程代码 ##

#include <stdio.h>
    #include <stdlib.h>
    #define ok 1;
    #define error 0;
    
    typedef struct DoulNode{ 
    	char data;
    	struct DoulNode *prior;
    	struct DoulNode *next;
    }DoulNode,*DoulLink;
     
     typedef int Status; 
    
     DoulLink createDL(DoulLink L,int size){ 
     	
     	  if(!L)
    		return NULL;
    	   
    	   
    		  DoulLink p,q; 
    		  int i;
    		  q=L;
    		  
    		for(i=0;i<size;i++){ 
    			p=(DoulLink)malloc(sizeof(DoulNode));
    			p->data='A'+i;
    	  		p->prior=q;
    	  		p->next=q->next;
    			q->next=p;
    			q=p;
    		}
    	  	q=L;
    	  	p->next=L->next;
    	  	q->next->prior=p;
    	  	L=q->next;
    	  	free(q);
    	  	return L;
     }
    
    
    void Caesar(DoulLink *L,int n){ 
    	if(n==0){ 
    		return;
    	}
    	
    	int i;
    	if(n>0){ 
    		for(i=0;i<n;i++){ 
    			(*L)=(*L)->next;
    		}	
    	}
    	if(n<0){ 
    	   n=-n;
    	   for( i=0;i<n;i++){ 
    	   	(*L)=(*L)->prior;
    	   }
    	}
    	
    	
    }
    
    int main(int argc, char *argv[]) { 
    	DoulLink L=(DoulLink)malloc(sizeof(DoulNode));
    	L=createDL(L,26);
    	DoulLink *Dl=&L;
    	
    	
    	int n;
    	printf("请输入一个整数:");
    	scanf("%d",&n); 
    	Caesar(Dl,n);
    	int i;
    	for(i=0;i<26;i++){ 
    		printf("%c",L->data);
    		L=L->next;
    		
    	}
    	printf("\n\n");
    	system("pause");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200123183101936.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70