momoc-数据结构-双向循环链表 附带超详细题解

解题思路:

双链表插入过程      

以下介绍的是头插法

截取双向链表某一段

在p 后面插入元素  s

假如p->next指向下一个元素x

注意：先把后元素连接 再将前元素连接

第一步：（这一步千万不要倒过来 否则会出错）先把p->next元素（用x 元素代替），

x->prior指针指向x->prior=s      （ p->next->prior=s）

x->next(即p->next->next)指针不需要改变 

第二步：s->next=x;  到了这一步就实现了p元素与x元素的连接，就不需要再对x进行操作

第三步：p->next=s;  此时p->next不再指向x元素  第三步：p->next=s;  此时p->next不再指向x元素  

第四步：s->prior=p;   最后实现了双向链表的插入与连接

双向链表的删除过程

首先先找到要删除的位置

例如p就是要删除的位置

只要将p的前后元素相连 再把p元素释放掉即可删除x

第一步：获取p的前驱元素s=p->prior;

第二步： s->next=p->next;  

第三步：p->next->prior=s;

             p->next=NULL

             p->prior=NULL

             free(p);

注意事项:使用c++提交，c提交编译不通过。也不知道是啥原因

参考代码:

#include <stdio.h> 
#include <stdlib.h>
/*
解题的方法不用于题目，
插入时使用的是头插法
所以删除，输出操作与题目也不一致 
*/

typedef int ElemType;
typedef struct DuLNode{
	ElemType data;
	struct DuLNode *next;
	struct DuLNode *prior;
}DuLNode,*DuLinkList;
void Int_List (DuLinkList &L){
 	L=(DuLinkList)malloc(sizeof(DuLNode));
 	L->next=L;
    L->prior=L;	
 }
 void printf1(DuLinkList L)//输出的是也要反过来 
 {
 	DuLinkList p;
 	p=L;
 	while(p->prior!=L)
 	{
 		p=p->prior;
 	    printf("%d ",p->data);
	 }
	 printf("\n");
 } 
  DuLinkList DuLinkList_getELemp1(DuLinkList L,int i)//寻找删除的元素位置
 {
 	DuLinkList p;
 	int j=1;
 	p=L->prior;
	 while(p!=L && j<i)
	 {
	 	p=p->prior;
	 	j++;
	 }
	 if(p==L && j<i)//位置不合法  
	 return 0;
	 else 
	 return p;
 }
 int LinsInsert_DuL(DuLinkList &L,int i,ElemType e)//插入操作  头插法 
 {
 	DuLinkList p,s;
    p=DuLinkList_getELemp1(L,i);//获取插入位置 
    if(!p) return 0;//插入的位置不合法
 	s=(DuLinkList)malloc(sizeof(DuLNode));
 	if(!s) return 0;
 	s->data=e;
 	p->next->prior=s;//第一步操作 
 	s->next=p->next;//第二步 
 	p->next=s;//第三步 
 	s->prior=p;//第四步 
 	return 1;
 }
 int LinkListdelete_DuL( DuLinkList &L,int i) 
 {
 	DuLinkList p,s;
 	p=DuLinkList_getELemp1(L,i); 
 	if(!p) return 0; //删除的位置不合法
	s=p->prior;//获取删除位置的前驱元素 (第一步) 
	s->next=p->next;//s->next指向p的下一个元素（第二步） 
	p->next->prior=s;//p的上一个元素指向s（第三步） 
	p->next=NULL;
	p->prior=NULL; 
	free(p);//释放内存 
 	return 1;
 }
int main (){
	int a,i,e;
	DuLinkList L;
	Int_List(L);
	while(scanf("%d",&a)!=EOF){
		if(a==0)//输出 
		{
			printf1(L);
		}
		else if(a==1){//插入 
			scanf("%d %d",&i,&e);
			LinsInsert_DuL(L,i,e);
		} 
		else if(a==2){//删除 
			scanf("%d",&i);
			LinkListdelete_DuL(L,i); 
		}
	}
    free(L);
	return 0;
	
}