[C++知识库]双链表带头结点纯C语言详细实现源码

//双链表带头结点 
#include<stdio.h>
#include<stdlib.h>
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode ,* DinkList;

//	初始化双链表
DinkList initList(DinkList list){
	DNode *newNode = (DNode *)malloc(sizeof(DNode));
	(*newNode).prior = NULL;
	(*newNode).next = NULL;
	list = newNode;
//	printf("\n初始化双链表：\n",(*list).data);
	return list;
}

//向双链表指定[位置]插入数据
int insertList(DinkList list,int index,int data){
	DNode *tmp=list;
	int j=0;	
	if(index<1){
		return 0;
	} 
	while(tmp!=NULL&&j<index-1){
		tmp = (*tmp).next;
		j++;
	} 
	if(tmp==NULL){
		return 0;
	}	
	DNode *newNode=(DNode *)malloc(sizeof(DNode));
	if(newNode==NULL){
		return 0;
	}
	(*newNode).next = (*tmp).next;
	if((*tmp).next!=NULL){
		(*tmp).next->prior = newNode;
	}
	(*newNode).prior = tmp;
	(*tmp).next = newNode;
	(*newNode).data = data;
	return 1;
}

//向指定[结点][后面]插入数据 
int insertNextNode(DNode *p,int data){
	printf("\n\n向指定[结点][后面]插入数据 :\n");
	if(p==NULL){
		return 0;
	}	
	DNode *newNode=(DNode *)malloc(sizeof(DNode));
	if(newNode==NULL){
		return 0;
	}
	(*newNode).next=(*p).next;
	if((*p).next!=NULL){
		(*p).next->prior=newNode;
	}
	(*newNode).prior=p;
	(*p).next=newNode;
	(*newNode).data=data;
	
	return 1; 	
}

//向指定结点[前面]插入数据
int insertPriorNode(DNode *p, int data){
	printf("\n\n向指定结点[前面]插入数据 :\n");
	if(p==NULL){
		return 0;
	}
	DNode *tmp = (*p).prior;
	if(tmp!=NULL){
		DNode *newNode = (DNode *)malloc(sizeof(DNode));
		if(newNode==NULL){
			return 0;
		}
		(*newNode).data = data;
		(*newNode).prior = tmp;
		(*newNode).next = p;
		(*p).prior = newNode;
		(*tmp).next = newNode;
		return 1;
	} 
}

//删除双链表的指定[位置]的数据 
int deleteList(DinkList list,int index){
	printf("\n\n删除双链表的指定[位置]的数据  :\n");
	DNode* tmp=list;
	int j=0;
	if(index<1){
		return 0;
	} 
	while(tmp!=NULL&&j<index-1){
		tmp=(*tmp).next;
		j++;
	}
	if(tmp==NULL){
		return 0;
	} 
	DNode *p=(*tmp).next;
	if(p == NULL){
		return 0;
	}
	(*tmp).next=(*p).next;
	if((*p).next!=NULL){
		(*p).next->prior=tmp;	
	}
//	*data=(*p).data;
	
	free(p);
	
	return 1;
}

//删除指定[结点]p
int deleteNode(DNode *p){
	
	printf("\n\n删除指定[结点]p :\n");
		if(p==NULL){
		return 0;
	}
	
	DNode *tmp=(*p).prior;
	if(tmp!=NULL){
		(*tmp).next=(*p).next;
		if((*p).next!=NULL){
			(*p).next->prior = tmp;
		}
	free(p);
	return 1;
}
return 0;
}

//按位查找
DNode* getElementByIndex(DinkList list,int index){
	
	printf("\n\n按位查找,找到的数据（第一个位置的数据）:\n");
	DNode *tmp=list;
	int j=0;
	
	if(index<0){
		return NULL;
	}
	
	while(tmp!=NULL&&j<index){
		tmp=(*tmp).next;
		j++;
	}
	printf("%d,\n",(*tmp).next->data);
	return tmp;
}

//按值查找
DNode* getElementByData(DinkList list,int data){
	printf("\n\n按值查找,找到的位置（值为3的数据位置） :\n");
	DNode *tmp=list;
	int j = 0;	
	while(tmp!=NULL&&(*tmp).data!=data){
		tmp=(*tmp).next;
		j++;
	}
	printf("%d,\n",j);
	return tmp;
}

//求表的长度
int getLength(DinkList list){
	int length = 0;
	DNode *tmp = list;
	while((*tmp).next!=NULL){
		tmp = (*tmp).next;
		length++;
	}
	return length;
}

//新建一个链表：头插法
void constructLinkListOne(DinkList list){
	int i = 0;
	printf("\n\n新建一个链表头插法:\n");
	for(;i < 5;i++){
		insertList(list,1,i+1);
		printf("%d,",(*list).next->data);
	}
	
}

//新建一个链表：尾插法 
void constructLinkListTwo(DinkList list){
	int i = 0,j = 0;
	printf("\n新建一个链表尾插法 :\n");
	for(;i < 5;i++){
		insertList(list,j+1,i+1);
		j++;
	}
	bianli(list);
}
//遍历
void bianli(DinkList list){
	DNode *tmp = list; 
	while((*tmp).next!=NULL){		
		tmp = (*tmp).next;
		printf("%d,",(*tmp).data);				
	}
	printf("\n");
}

int main(){
	int length=0;
	int i=0;
	DinkList list;
	list=initList(list);
	constructLinkListOne(list);	
	constructLinkListTwo(list);
	
	printf("\n\n插数据在指定位置(1):\n");
	insertList(list,1,999);
	bianli(list);
	DNode *tmp=list;
	for(;i<2;i++){
		tmp=(*tmp).next;
	}
	insertNextNode((*tmp).next,888);
	bianli(list);
	insertPriorNode((*tmp).next, 777);
	bianli(list);
	deleteList(list,4);
	bianli(list);
	deleteNode((*tmp).next);
	bianli(list);
	getElementByIndex(list,1);
	getElementByData(list,3);
	length=getLength(list);
	printf("\n表长：\n%d",length);
	return 0;
}