【数据结构】循环双链表的c语言实现

定义结构体

typedef struct CNode{
	int data;
	struct CNode *prior;//前驱 
	struct CNode *next;//后继 
}CNode,*CLinkList;

初始化

void init(CLinkList &L){
	L = (CNode *)malloc(sizeof(CNode));
	L->prior = L;//前驱指向自己 
	L->next = L;//后继指向自己 
}

结点后插与尾插

//结点后插 
void InsertNextNode(CNode *p,CNode *s){
	p->next->prior = s;
	s->next = p->next;
	p->next = s;
	s->prior = p;
}

//尾插 
void insertTail(CLinkList &L){
	int e,n,i;
	CNode *temp = L;
	printf("以下使用尾插法创建循环双链表n输入要输入元素的个数n");
	scanf("%d",&n);
	printf("n输入%d个元素n",n);
	for(i=0;i
		while(temp->next != L)
			temp = temp->next;
		CNode *s = (CNode *)malloc(sizeof(CNode));
		scanf("%d",&e);
		s->data = e;
		s->prior = NULL;
		s->next = NULL;
		InsertNextNode(temp,s);//调用后插结点函数实现插入 
	}
}

结点前插与前插

//结点前插 
void InsertPriorNode(CNode *p,CNode *s){
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;
}

//前插 
void insertHead(CLinkList &L){
	int e,n,i;
	CNode *temp = L;
	printf("以下使用前插法创建循环双链表n输入要输入元素的个数n");
	scanf("%d",&n);
	printf("n输入%d个元素nn",n);
	for(i=0;i
		scanf("%d",&e);
		if(temp->next == L){
			CNode *s = (CNode *)malloc(sizeof(CNode));
			s->data = e;
			L->next = s;
			L->prior = s;
			s->next = L;
			s->prior = L;
		}
		else{
			CNode *s = (CNode *)malloc(sizeof(CNode));
			s->data = e;
			s->next = NULL;
			s->prior = NULL;
			//调用前插结点函数，在第一个节点进行插入 
			InsertPriorNode(L->next,s); 
		}
	}
}

按位查找

//按位查找 
void getElem(CLinkList &L,int pos){
	CNode *p = L;
	while(pos!=0){
		p = p->next;
		pos--;
	}
	printf("n按位查找的值为:%dn",p->data);
}

按值查找

//按值查找
void LocateElem(CLinkList &L,int e){
	int pos = 0;
	CNode *p = L;
	while(e!=p->data){
		p = p->next;
		pos++;
	}
	printf("值%d在链表中的位置为:%dn",e,pos);
} 

求链表长度

void Length(CLinkList &L){
	int len=0;
	CNode *p = L;
	while(p->next != L){
		p = p->next;
		len++;
	}
	printf("该链表的长度为:%d",len);
}

输出链表

void show(CLinkList &L){
	CNode *p = L;
	printf("输出整个链表:n");
	while(p->next != L){
		p = p->next;
		printf("%d ",p->data);
	}
	printf("n");
}

完整程序

#include 
#include 

typedef struct CNode{
	int data;
	struct CNode *prior;//前驱 
	struct CNode *next;//后继 
}CNode,*CLinkList;

void init(CLinkList &L){
	L = (CNode *)malloc(sizeof(CNode));
	L->prior = L;//前驱指向自己 
	L->next = L;//后继指向自己 
}

//结点后插 
void InsertNextNode(CNode *p,CNode *s){
	p->next->prior = s;
	s->next = p->next;
	p->next = s;
	s->prior = p;
}

//尾插 
void insertTail(CLinkList &L){
	int e,n,i;
	CNode *temp = L;
	printf("以下使用尾插法创建循环双链表n输入要输入元素的个数n");
	scanf("%d",&n);
	printf("n输入%d个元素n",n);
	for(i=0;i
		while(temp->next != L)
			temp = temp->next;
		CNode *s = (CNode *)malloc(sizeof(CNode));
		scanf("%d",&e);
		s->data = e;
		s->prior = NULL;
		s->next = NULL;
		InsertNextNode(temp,s);//调用后插结点函数实现插入 
	}
}

//结点前插 
void InsertPriorNode(CNode *p,CNode *s){
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;
}

//前插 
void insertHead(CLinkList &L){
	int e,n,i;
	CNode *temp = L;
	printf("以下使用前插法创建循环双链表n输入要输入元素的个数n");
	scanf("%d",&n);
	printf("n输入%d个元素nn",n);
	for(i=0;i
		scanf("%d",&e);
		if(temp->next == L){
			CNode *s = (CNode *)malloc(sizeof(CNode));
			s->data = e;
			L->next = s;
			L->prior = s;
			s->next = L;
			s->prior = L;
		}
		else{
			CNode *s = (CNode *)malloc(sizeof(CNode));
			s->data = e;
			s->next = NULL;
			s->prior = NULL;
			//调用前插结点函数，在第一个节点进行插入 
			InsertPriorNode(L->next,s); 
		}
	}
}

//按位查找 
void getElem(CLinkList &L,int pos){
	CNode *p = L;
	while(pos!=0){
		p = p->next;
		pos--;
	}
	printf("n按位查找的值为:%dn",p->data);
}

//按值查找
void LocateElem(CLinkList &L,int e){
	int pos = 0;
	CNode *p = L;
	while(e!=p->data){
		p = p->next;
		pos++;
	}
	printf("值%d在链表中的位置为:%dn",e,pos);
} 

void Length(CLinkList &L){
	int len=0;
	CNode *p = L;
	while(p->next != L){
		p = p->next;
		len++;
	}
	printf("该链表的长度为:%dn",len);
}

void show(CLinkList &L){
	CNode *p = L;
	printf("输出整个链表:n");
	while(p->next != L){
		p = p->next;
		printf("%d ",p->data);
	}
	printf("n");
}

int main(){
	CNode *A,*B;
	int location,value;
	
	init(A);
	init(B);

	printf("A链表:n");
	insertTail(A);
	show(A);
	insertHead(A);
	show(A);
	printf("n输入按位查找的位置:n");
	scanf("%d",&location);
	getElem(A,location);
	printf("n输入要查找的元素值:n");
	scanf("%d",&value);
	LocateElem(A,value);
	Length(A); 
	
	printf("B链表:n");
	insertTail(B);
	show(B);
	insertHead(B);
	show(B);
	printf("n输入按位查找的位置:n");
	scanf("%d",&location);
	getElem(B,location);
	printf("n输入要查找的元素值:n");
	scanf("%d",&value);
	LocateElem(B,value);
	Length(B);
	
	return 0;
}