数据结构（使用头插法实现双链表）_头插法建立双链表

一.为什么使用双链表？

答：单链表结点中只有一个后继指针，这使得单链表无法直接访问某个结点的前驱结点，只能从头结点开始依次顺序向后遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

为了克服单链表的不足，我们给每个结点增加指向前驱结点的前驱指针（这样每个结点就拥有了两个指针：前驱指针prior和后继指针next）

二.代码分块

1.定义双链表的结点类型

typedef struct DNode{//定义双链表结点类型 
	int Length;//长度 
	int data;//数据域 
	struct DNode *prior,*next;//前驱指针和后继指针 
}DNode,*DLinkList;

2.使用头插法创建双链表

DLinkList BulidList(DLinkList DL){//使用头插法创建双链表 
	DL = (DLinkList)malloc(sizeof(DNode));//分配一个头结点 
	if(DL==NULL){//分配失败 
		return false;
	}
	DL->Length=0;//初始化 
	DL->data = 0;
	DL->next = NULL;
	DL->prior = NULL;
	int addNum;//定义添值变量 
	printf("向链表输入初始值\n");
	printf("请输入要插入的内容：");
	scanf("%d",&addNum);//获取插入内容 
	while(addNum!=99){
		DNode *addPoint; //创建一个指针 
		addPoint = (DNode *)malloc(sizeof(DNode));//指向创建的新结点 
		addPoint->data = addNum;//赋值 
		addPoint->next = DL->next;//头插法 
		addPoint->prior =  DL;
		DL->next = addPoint;
		DL->Length++;
		printf("请再次输入要插入的内容：");
		scanf("%d",&addNum);//获取插入内容 
	}
	return DL;
}

 

 

3.遍历显示双链表的全部数据

void ShowList(DLinkList DL){
	DNode *x;//定义一个指针 
	int num = DL->Length;//num用于暂存该链表长度 
	printf("该链表一共有%d个元素\n",num);
//	x = (LNode *)malloc(sizeof(LNode)); 
	x = DL;//将头结点的信息赋给x 
	x = x->next;//跳过头结点，因为头结点不存储数据 
	while(num>0){
		printf("%d\n",x->data);//输出该节点的数据 
		x = x->next;//移向下一个结点 
		num--;//遍历总数减一 
	}
}

4.按位查找数据元素

LinkList GetElem(DLinkList DL,int findPos){//按位查找 
	DNode *record;//定义一个遍历指针 
	record = DL;//遍历指针指向双链表表头 
	int x = 1;//记录位置变量赋初值1 
	while(record!=NULL){//当双链表没有遍历结束时 
		record = record->next;//指针指向下一个结点 
		if(x==findPos){//当查找位置和当前位置一致时 
			printf("%d值在链表的第%d结点",record->data,x);//输出结果 
			return record;//返回要查找的结点 
		}
		x++;//累加 
		
	}
	printf("没有找到");
	return NULL;//没找到返回空 
}

  

 

5.按位插入数据元素

bool InsertList(DLinkList DL,DNode *InsertPos,DNode *InsertPoint){//插入元素，输入：双链表，前驱结点，插入结点 
	InsertPoint->next = InsertPos->next;//插入结点的后继指针指向前驱结点的后继结点 
	InsertPos->next->prior=InsertPoint;//前驱结点原后继结点的前驱指针指向插入结点 
	InsertPoint->prior = InsertPos;// 插入结点的前驱指针指向前驱结点 
	InsertPos->next = InsertPoint;//前驱结点的后继指针指向插入结点 
	DL->Length++;
}

 

 

 6.按位删除数据元素

bool DelList(DLinkList DL,DNode *DelPos,DNode *DelPoint){//删除数据元素（输入：双链表，删除结点的前驱结点）
	DelPos->next = DelPoint->next;//将前驱结点的后继指针指向删除结点的后继指针 
	DelPoint->next->prior = DelPos;//将删除结点的后继结点的前驱指针指向删除结点的前驱结点 
	free(DelPoint);//释放删除结点的存储空间 
	DL->Length--;//长度-1 
}

 

三.整体代码

//使用头插法实现双链表 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct DNode{//定义双链表结点类型 
	int Length;//长度 
	int data;//数据域 
	struct DNode *prior,*next;//前驱指针和后继指针 
}DNode,*DLinkList;
 
DLinkList BulidList(DLinkList DL){//使用头插法创建双链表 
	DL = (DLinkList)malloc(sizeof(DNode));//分配一个头结点 
	if(DL==NULL){//分配失败 
		return false;
	}
	DL->Length=0;//初始化 
	DL->data = 0;
	DL->next = NULL;
	DL->prior = NULL;
	int addNum;//定义添值变量 
	printf("向链表输入初始值\n");
	printf("请输入要插入的内容：");
	scanf("%d",&addNum);//获取插入内容 
	while(addNum!=99){
		DNode *addPoint; //创建一个指针 
		addPoint = (DNode *)malloc(sizeof(DNode));//指向创建的新结点 
		addPoint->data = addNum;//赋值 
		addPoint->next = DL->next;//头插法 
		addPoint->prior =  DL;
		DL->next = addPoint;
		DL->Length++;
		printf("请再次输入要插入的内容：");
		scanf("%d",&addNum);//获取插入内容 
	}
	return DL;
}
 
void ShowList(DLinkList DL){
	DNode *x;//定义一个指针 
	int num = DL->Length;//num用于暂存该链表长度 
	printf("该链表一共有%d个元素\n",num);
//	x = (LNode *)malloc(sizeof(LNode)); 
	x = DL;//将头结点的信息赋给x 
	x = x->next;//跳过头结点，因为头结点不存储数据 
	while(num>0){
		printf("%d\n",x->data);//输出该节点的数据 
		x = x->next;//移向下一个结点 
		num--;//遍历总数减一 
	}
}
 
DLinkList GetElem(DLinkList DL,int findPos){//按位查找 
	DNode *record;//定义一个遍历指针 
	record = DL;//遍历指针指向双链表表头 
	int x = 1;//记录位置变量赋初值1 
	while(record!=NULL){//当双链表没有遍历结束时 
		record = record->next;//指针指向下一个结点 
		if(x==findPos){//当查找位置和当前位置一致时 
			printf("%d值在链表的第%d结点",record->data,x);//输出结果 
			return record;//返回要查找的结点 
		}
		x++;//累加 
		
	}
	printf("没有找到");
	return NULL;//没找到返回空 
}
 
bool InsertList(DLinkList DL,DNode *InsertPos,DNode *InsertPoint){//插入元素，输入：双链表，前驱结点，插入结点 
	InsertPoint->next = InsertPos->next;//插入结点的后继指针指向前驱结点的后继结点 
	InsertPos->next->prior=InsertPoint;//前驱结点原后继结点的前驱指针指向插入结点 
	InsertPoint->prior = InsertPos;// 插入结点的前驱指针指向前驱结点 
	InsertPos->next = InsertPoint;//前驱结点的后继指针指向插入结点 
	DL->Length++;
}
 
bool DelList(DLinkList DL,DNode *DelPos,DNode *DelPoint){//删除数据元素（输入：双链表，删除结点的前驱结点）
	DelPos->next = DelPoint->next;//将前驱结点的后继指针指向删除结点的后继指针 
	DelPoint->next->prior = DelPos;//将删除结点的后继结点的前驱指针指向删除结点的前驱结点 
	free(DelPoint);//释放删除结点的存储空间 
	DL->Length--;//长度-1 
}
 
int main(){
	DLinkList DL;
	DL = BulidList(DL);//建立双链表 
	ShowList(DL);
	//按位查找部分 
	int findPos=0;//定义要寻找的位置 
	DNode *getPos;//寻找的结点
	printf("\n请输入要寻找结点的位置:");
	scanf("%d",&findPos); //获取位置 
	getPos = GetElem(DL,findPos);//按位查找 
	//插入元素部分(按位插入)
	DNode *InsertPos;//定义前驱结点 指针 
	DNode *InsertPoint;// 定义插入结点 指针 
	int insertNum = 0;//定义插入值 
	printf("\n请输入要插入结点的位置:");
	scanf("%d",&findPos); //获取插入位置
	InsertPos = GetElem(DL,findPos-1);//按位查找,找到前驱结点 
	printf("\n请输入插入结点的值:");
	scanf("%d",&insertNum); //获取值 
	InsertPoint = (DNode *)malloc(sizeof(DNode));//创建插入结点 
	InsertPoint->data = insertNum;//给插入结点赋值 
	InsertList(DL,InsertPos,InsertPoint);//进行插入操作（输入前驱结点和插入结点） 
	ShowList(DL);
	//删除操作（按位删除） 
	int findDelPos = 0;
	DNode *DelPos,*DelPoint;//定义删除结点的前驱结点指针
	printf("\n请输入要删除结点的位置:");
	scanf("%d",&findDelPos); //获取删除位置
	DelPos = GetElem(DL,findDelPos-1);//按位查找,找到前驱结点 
	DelPoint = DelPos->next;//获得要删除的结点 
	DelList(DL,DelPos,DelPoint);//删除操作 
	ShowList(DL);
 
	 
	
	 
}