龙空技术网

C语言 循环双向链表

zhexuewei 110

前言:

而今咱们对“循环链表c实现”大概比较关怀,同学们都想要剖析一些“循环链表c实现”的相关知识。那么小编同时在网络上搜集了一些对于“循环链表c实现””的相关知识,希望各位老铁们能喜欢,朋友们快快来了解一下吧!

#include <stdio.h>#include <stdlib.h>#include <conio.h>typedef int DataType;    /* 循环双链表元素类型 */typedef struct node {	DataType data;       /* 循环双链表元素 */	struct node *prior;  /* 循环双链表元素前驱指针 */	struct node *next;   /* 循环双链表元素后继指针 */} DLNode, *CDLinkList;   /* 循环双链表结点类型、循环双链表类型 */void wait(){	printf("\n请按任意键...\n");	getch();}int go_on(){	int flag = 1;	char choice;	while(1) {		printf("\n继续吗?[Y/N]");		choice = getche();		if(choice == 'Y' || choice == 'y')			break;		else if(choice == 'N' || choice == 'n') {			flag = 0;			break;		}	}	return (flag);}/* 初始化,构造一个空的带头结点的循环双链表 */void Init_CDLinkList(CDLinkList *L){	*L = (DLNode *) malloc(sizeof(DLNode));	if(*L == NULL) {		printf("\n内存分配失败.\n");		exit(-1);	}	(*L)->prior = *L;	(*L)->next = *L;}/* 判断带头结点的循环双链表是否为空 */int Empty_CDLinkList(CDLinkList L){	if(L->prior == L && L->next == L)		return (1);	else		return (0);}/* 求带头结点的循环双链表的长度 */int Length_CDLinkList(CDLinkList L){	DLNode *p = L;	int k;	k = 0;	while(p->next != L) {		k++;		p = p->next;	}	return (k);}void Length(CDLinkList L){	int k;	k = Length_CDLinkList(L);	printf("\n表长:%d\n", k);}/* 按序号查找元素,在带头结点的循环双链表中查找第i个元素,若查找成功,则返回指向第i个元素结点的指针,否则返回空 */DLNode *Locatei_CDLinkList(CDLinkList L, int i){	DLNode *p = L;	int j = 0;	while(p->next != L && j<i) {		j++;		p = p->next;	}		if(j == i)		return (p);	else		return (NULL);}/* 按值查找元素,在带头结点的循环双链表中查找元素值为x的第1个结点,若查找成功,则返回指向x所在结点的指针,*k返回其位置序号,否则返回空,*k无意义 */DLNode *Locatex_CDLinkList(CDLinkList L, int x, int *k){	DLNode *p = L->next;	int j = 1;	while(p != L && p->data != x) {		j++;		p = p->next;	}		if(p != L) {		*k = j;		return(p);	}	else		return (NULL);}void Locatei(CDLinkList L){	DLNode *p;	int flag = 1, i;	while(flag) {		printf("\n请输入要查找元素的位置:");		scanf("%d", &i);		p = Locatei_CDLinkList(L, i);		if(p != NULL && i != 0)			printf("\n查找成功,第%d个元素是%d.\n", i, p->data);		else			printf("\n查找失败,没有第%d个元素.\n", i);		flag = go_on();	}}void Locatex(CDLinkList L){	DLNode *p;	DataType x;	int flag = 1, k;	while(flag) {		printf("\n请输入要查找元素:");		scanf("%d", &x);		p = Locatex_CDLinkList(L, x, &k);		if(p != NULL)			printf("\n查找成功,%d是第%d个元素.\n", p->data, k);		else			printf("\n查找失败!没有元素%d.\n", x);		flag = go_on();	}}/* 插入元素,在带头结点的循环双链表中第i个位置之前插入元素x,即插入在第i个位置 */int Insert_CDLinkList(CDLinkList L, int i, DataType x){	DLNode *p, *s;	int len;	len = Length_CDLinkList(L);		if(i<1 || i>len+1) {    /* 插入位置错,不能插入 */		printf("\n插入位置错,不能插入.\n");		return (0);         /* 插入失败,返回0 */	}		p = Locatei_CDLinkList(L, i-1);  /* 查找第i-1个结点 */	s = (DLNode *)malloc(sizeof(DLNode));	if (s == NULL) {		printf("\n内存分配失败.\n");		exit(-1);	}		s->data = x;	s->prior = p;     /* 新结点插入在第i-1个结点后面 */	s->next = p->next;	p->next->prior = s;	p->next = s;	return (1);       /* 插入成功,返回1 */}void Insert(CDLinkList L){	DataType x;	int i, flag = 1, insert_flag;	while(flag) {		printf("\n请输入要插入元素的位置:");		scanf("%d", &i);		printf("请输入要插入元素:");		scanf("%d", &x);		insert_flag = Insert_CDLinkList(L, i, x);		if(insert_flag == 1)			printf("\n插入成功!\n");		else			printf("\n插入失败!\n");		flag = go_on();	}}/* 删除元素,在带头结点的循环双链表中删除第i个位置的元素 */int Delete_CDLinkList(CDLinkList L, int i){	CDLinkList p, s;	int len;	if(Empty_CDLinkList(L) == 1) {		printf("\n表空,不能删除.\n");		return (0);	}		len = Length_CDLinkList(L);	if(i<1 || i>len) {  /* 删除位置错,不能删除 */		printf("\n删除位置错,不能删除.\n");		return (0);     /* 删除失败,返回0 */	}		p = Locatei_CDLinkList(L, i-1);  /* 查找第i-1个结点 */	s = p->next;        /* s指向第i个结点 */	p->next = s->next;  /* 从链表中删除第i个结点 */	s->next->prior = p;	free(s);     /* 释放*s */	return (1);  /* 删除成功,返回1 */}void Delete(CDLinkList L){	int i, flag = 1, delete_flag;	while(flag) {		printf("\n请输入要删除元素的位置:");		scanf("%d", &i);		delete_flag = Delete_CDLinkList(L, i);		if(delete_flag == 1)			printf("\n删除成功.\n");		else			printf("\n删除失败.\n");		flag = go_on();	}}/* 输出带头结点循环双链表中的所有数据元素 */void Display_CDLinkList(CDLinkList L){	DLNode *p = L;	if(Empty_CDLinkList(L) == 1)		printf("\n表空,没有元素.\n");	else {		printf("\n循环双链表所有元素\n");		while(p->next != L) {			p = p->next;			printf("%6d", p->data);		}	}}int main(void){	CDLinkList L;	char choice;	int flag = 1;	Init_CDLinkList(&L);	do {		printf("\n");		printf("-------循环双链表(带头结点)-------\n");		printf("       1.......插入元素\n");		printf("       2.......删除元素\n");		printf("       3.......按位置查找元素\n");		printf("       4.......按值查找元素\n");		printf("       5.......输出表长\n");		printf("       6.......输出元素\n");		printf("       0.......退出\n");		printf("请选择[1/2/3/4/5/6/0]: ");		choice = getche();		switch(choice) {			case '1':				Insert(L);				break;			case '2':				Delete(L);				break;			case '3':				Locatei(L);				break;			case '4':				Locatex(L);				break;			case '5':				Length(L);				break;			case '6':				Display_CDLinkList(L);				break;			case '0':				flag = 0;				break;		}		wait();	} while(flag == 1);	return 0;}

运行结果:

-------循环双链表(带头结点)-------       1.......插入元素       2.......删除元素       3.......按位置查找元素       4.......按值查找元素       5.......输出表长       6.......输出元素       0.......退出请选择[1/2/3/4/5/6/0]: 1请输入要插入元素的位置:1请输入要插入元素:30插入成功!继续吗?[Y/N]Y请输入要插入元素的位置:2请输入要插入元素:50插入成功!继续吗?[Y/N]Y请输入要插入元素的位置:3请输入要插入元素:70插入成功!继续吗?[Y/N]Y请输入要插入元素的位置:4请输入要插入元素:90插入成功!继续吗?[Y/N]Y请输入要插入元素的位置:5请输入要插入元素:100插入成功!继续吗?[Y/N]N请按任意键...-------循环双链表(带头结点)-------       1.......插入元素       2.......删除元素       3.......按位置查找元素       4.......按值查找元素       5.......输出表长       6.......输出元素       0.......退出请选择[1/2/3/4/5/6/0]: 6循环双链表所有元素    30    50    70    90   100请按任意键...-------循环双链表(带头结点)-------       1.......插入元素       2.......删除元素       3.......按位置查找元素       4.......按值查找元素       5.......输出表长       6.......输出元素       0.......退出请选择[1/2/3/4/5/6/0]: 5表长:5请按任意键...-------循环双链表(带头结点)-------       1.......插入元素       2.......删除元素       3.......按位置查找元素       4.......按值查找元素       5.......输出表长       6.......输出元素       0.......退出请选择[1/2/3/4/5/6/0]: 3请输入要查找元素的位置:3查找成功,第3个元素是70.继续吗?[Y/N]N请按任意键...-------循环双链表(带头结点)-------       1.......插入元素       2.......删除元素       3.......按位置查找元素       4.......按值查找元素       5.......输出表长       6.......输出元素       0.......退出请选择[1/2/3/4/5/6/0]: 4请输入要查找元素:90查找成功,90是第4个元素.继续吗?[Y/N]N请按任意键...-------循环双链表(带头结点)-------       1.......插入元素       2.......删除元素       3.......按位置查找元素       4.......按值查找元素       5.......输出表长       6.......输出元素       0.......退出请选择[1/2/3/4/5/6/0]: 2请输入要删除元素的位置:70删除位置错,不能删除.删除失败.继续吗?[Y/N]N请按任意键...-------循环双链表(带头结点)-------       1.......插入元素       2.......删除元素       3.......按位置查找元素       4.......按值查找元素       5.......输出表长       6.......输出元素       0.......退出请选择[1/2/3/4/5/6/0]: 2请输入要删除元素的位置:3删除成功.继续吗?[Y/N]N请按任意键...-------循环双链表(带头结点)-------       1.......插入元素       2.......删除元素       3.......按位置查找元素       4.......按值查找元素       5.......输出表长       6.......输出元素       0.......退出请选择[1/2/3/4/5/6/0]: 6循环双链表所有元素    30    50    90   100请按任意键...

标签: #循环链表c实现