/*********** 循环双链表 ***********/

//定义
#include<stdio.h>
#include<malloc.h>

typedef char ElemType;
typedef struct node
{
	ElemType data; //数据域
	struct node *prior,*next; //分别指向前驱和后继结点的指针
} Dlink;

//初始化
void initList(Dlink *&L){
	L=(Dlink *)malloc(sizeof(Dlink)); //创建头结点L
	L->prior=L->next=NULL;
}

//求表长
int getLength(Dlink *L){
	int i=0;
	Dlink *p=L->next;
	while(p!=NULL){
		i++;
		P=p->next;
	}
	return i;
}

//按位查找
int getElem(Dlink *L,int i,ElemType &e){
	int j=1;
	Dlink *p=L->next;
	if(i<1||i>getLength(L)){
		//无效位置
		return 0;
	}
	while(j<i){
		p=p->next;
		j++;
	}
	e=p->data;
	return 1;
}

//按值查找
int locate(Dlink *L,ElemType x){
	int i=1;
	Dlink *p=L->next;
	while(p!=NULL&&p->data!=x){
		p=p->next;
		i++;
	}
	if(p==NULL){
		return 0;
	}else{
		return i;
	}
}

//插入运算
int insElem(Dlink *L,ElemType x,int i){
	int j=1;
	Dlink *p=L,*s;
	s=(Dlink *)malloc(sizeof(Dlink));
	s->data=x;
	s->prior=s->next=NULL;
	if(i<1||i>getLength(L)+1) //无效位置
		return 0;
	while(j<i){
		//找到第i-1个结点,由p指向它
		p=p->next;
		j++;
	}
	s->next=p->next; //*s的next域指向*p的下一个结点
	s->prior=p; //*s的prior域指向*p
	if(p->next!=NULL){ 
		s->next->prior=s;
	}
	p->next=s;
	return 1;
}

//删除运算
int delElem(Dlink *L,int i){
	int j=1;
	Dlink *p=L,*q;
	if(i<1||i>getLength(L)) //无效位置
		return 0;
	while(j<i){
		//找到第i-1个结点,由*p指向它
		p=p->next;
	}
	q=p->next; //*q指向*p的下一个结点,即要删除的结点
	p->next=q->next; //删除结点
	if(q->next!=NULL){
		//若*q不是最后结点,则将*q之后的结点的prior域指向*p
		q->next->prior=p;
	}
	free(q); //释放第i个结点占用的空间
	return 1;
}

 

最后修改于 2019-11-12 18:54:19
如果觉得我的文章对你有用,请随意赞赏
扫一扫支付
上一篇