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

定义结构体

typedef struct DoubleNode{
	int data;
	struct DoubleNode *prev;//前驱 
	struct DoubleNode *next;//后驱 
}DNode,*LinkList;

链表初始化

void init(LinkList &L){
	L = (DNode *)malloc(sizeof(DNode));
	L->prev = NULL;
	L->next = NULL;
}

尾插法

//尾插法 
void TailInsert(LinkList &L){
	int n,e;
	DNode *s,*p=L;
	printf("输入要输入元素的个数:n");
	scanf("%d",&n);
	printf("输入元素的值:n");
	for(int i=0;i
		scanf("%d",&e);
		s = (DNode *)malloc(sizeof(DNode));
		s->data = e;
		p->next =s;
		s->prev =p;
		p = s;
	}
	p->next = NULL;
}

遍历输出链表

void show(LinkList &L){
	DNode *p = NULL;
	p = L->next;
	while(p!=NULL){
		printf("%d ",p->data);
		p = p->next;
	}	
}

在指定位置插入结点

//在指定位置插入结点 
void InsertList(LinkList &L){
	int n,e;
	DNode *p,*ptr,*prev;
	p = (DNode *)malloc(sizeof(DNode));
	printf("n输入要插入的位置序号及其元素值:n");
	scanf("%d%d",&n,&e);
	p->data = e;
	p->prev= NULL;
	p->next = NULL;
	
	ptr = L->next;
	if(n == 1){
		p->next = ptr;
		ptr->prev = p;
		L->next = p;
		p->prev = L;
		L->data++;
	}
	else{
		for(int i=0;i
			prev = ptr;
			ptr = ptr->next;
		}
		p->next = ptr;
		ptr->prev = p;
		prev->next = p;
		p->prev = prev;
		L->data++;
	}
}

在指定位置删除结点

//在指定位置删除结点 
void DeleteNode(LinkList &L){
	int n,e;
	DNode *p,*ptr;
	printf("n输入要删除元素的位置序号及其元素值:n");
	scanf("%d%d",&n,&e);
	p = L;
	if(n == 1){
		ptr = p->next;
		p->next = ptr->next;
		ptr->next->prev = p;
		e = ptr->data;
		free(ptr);
		L->data--;
	}
	else{
		p = p->next;
		for(int i=1;i
			ptr = p;
			p = p->next;
		}
		ptr->next = p->next;
		p->next->prev = ptr;
		e = p->data;
		free(p);
		L->data--;
	}
}

查找某元素是否存在

//查找某元素是否存在 
void FindNode(LinkList &L){
	int e;
	DNode *p;
	int location = 1;
	p = L->next;
	printf("n输入要查找的元素值:n");
	scanf("%d",&e);
	while(p!=NULL){
		p = p->next;
		location++;
		if(e == p->data)
			break;
		else
			continue;
	}
	if(location < L->data)
		printf("要查找的元素值的位置序号为:%d",location);
	else
		printf("nerrorn");
}

完整程序

#include 
#include 

typedef struct DoubleNode{
	int data;
	struct DoubleNode *prev;//前驱 
	struct DoubleNode *next;//后驱 
}DNode,*LinkList;

void init(LinkList &L){
	L = (DNode *)malloc(sizeof(DNode));
	L->prev = NULL;
	L->next = NULL;
}

//尾插法 
void TailInsert(LinkList &L){
	int n,e;
	DNode *s,*p=L;
	printf("输入要输入元素的个数:n");
	scanf("%d",&n);
	printf("输入元素的值:n");
	for(int i=0;i
		scanf("%d",&e);
		s = (DNode *)malloc(sizeof(DNode));
		s->data = e;
		p->next =s;
		s->prev =p;
		p = s;
	}
	p->next = NULL;
}

void show(LinkList &L){
	DNode *p = NULL;
	p = L->next;
	while(p!=NULL){
		printf("%d ",p->data);
		p = p->next;
	}	
}

//在指定位置插入结点 
void InsertList(LinkList &L){
	int n,e;
	DNode *p,*ptr,*prev;
	p = (DNode *)malloc(sizeof(DNode));
	printf("n输入要插入的位置序号及其元素值:n");
	scanf("%d%d",&n,&e);
	p->data = e;
	p->prev= NULL;
	p->next = NULL;
	
	ptr = L->next;
	if(n == 1){
		p->next = ptr;
		ptr->prev = p;
		L->next = p;
		p->prev = L;
		L->data++;
	}
	else{
		for(int i=0;i
			prev = ptr;
			ptr = ptr->next;
		}
		p->next = ptr;
		ptr->prev = p;
		prev->next = p;
		p->prev = prev;
		L->data++;
	}
}

//在指定位置删除结点 
void DeleteNode(LinkList &L){
	int n,e;
	DNode *p,*ptr;
	printf("n输入要删除元素的位置序号及其元素值:n");
	scanf("%d%d",&n,&e);
	p = L;
	if(n == 1){
		ptr = p->next;
		p->next = ptr->next;
		ptr->next->prev = p;
		e = ptr->data;
		free(ptr);
		L->data--;
	}
	else{
		p = p->next;
		for(int i=1;i
			ptr = p;
			p = p->next;
		}
		ptr->next = p->next;
		p->next->prev = ptr;
		e = p->data;
		free(p);
		L->data--;
	}
}

//查找某元素是否存在 
void FindNode(LinkList &L){
	int e;
	DNode *p;
	int location = 1;
	p = L->next;
	printf("n输入要查找的元素值:n");
	scanf("%d",&e);
	while(p!=NULL){
		p = p->next;
		location++;
		if(e == p->data)
			break;
		else
			continue;
	}
	if(location < L->data)
		printf("要查找的元素值的位置序号为:%d",location);
	else
		printf("nerrorn");
}

int main(){
	DNode *L;
	init(L);
	TailInsert(L);
	show(L);
	InsertList(L);
	show(L);
	DeleteNode(L);
	show(L);
	FindNode(L);
	return 0;
}