考研数据结构——

双向链表

• 结构体定义
• 1. 尾插法初始化双向链表
• 2. 向后遍历双链表
• 3. 向前遍历双链表
• 4. 获取指定位序结点
• 5. 指定结点后插入结点（目前无法加在第一个位置）
• 6. 删除指定元素后的元素 （目前删不了第一个）

结构体定义

/**
	双向链表的定义 
*/ 
typedef struct DNode {
	int data;
	struct DNode *prior, *next; 
}DNode, *DLinkList;

1. 尾插法初始化双向链表

• 由于是尾插法， 需要 一个始终指向尾部元素的结点 endNode
• 初始化双向链表（prior为NULL， 初始next为NULL）
• ⭐插入的逻辑

1. 先将新插入的元素的 next 指向 插入前元素的next
2. 将新插入的元素的 prior指向 插入前的元素
3. 将插入元素前 之前指向的元素 （也就是 新元素的next）的prior指向新插入的元素即 dnode->next->prior = dnode； ⭐注意插入的元素要是最后一个元素的话，dnode->next就是NULL， 所以这里加个条件判断一下，要不要真正的执行
4. 插入元素前的元素要指向 新插入的元素， 即插入前的元素->next = dnode； （⭐注意这一步一般是最后执行的）

/**
	1. 初始化一个双向链表 （后插入式） 
*/

void initDLinkList(DLinkList &L) {
	
	// 设置一个初始的变量与接收的元素值
	DNode* dnode; 
	int x;
	// 设置一个始终指向最后的结点(初始指向头结点)
	DNode* endNode = L; 
	// L 表示的就是头结点  头结点的前指针指向NULL，后指针指向第一个元素（当第一个元素为空的时候，指向NULL） 
	// 为头结点开辟空间
	L = (DlinkList)malloc(sizeof(DNode));
	if(L==NULL) {
		// 表示开辟空间失败
		printf("\n\n开辟空间失败！\n\n");
		return ; 
	}
	// 前指NULL， 后指NULL 
	L->prior=NULL; 
	L->next=NULL;
	L->data = 0;
	printf("请输入要插入阶段值，输入-1结束\n\n");
	while(true) {
		scanf("%d", &x);
		if(x==-1) {
			return;
		}
		dnode = (DLinkList)malloc(sizeof(DNode));
		if(dnode==NULL){
			// 表示开辟空间失败
			printf("\n\n开辟空间失败！\n\n");
			return;
		}	
		// 插入的逻辑
		// 1. 新插入的结点的后一个为  前一个元素的后一个  
		dnode->next = endNode->next;
		// 2. 新插入的结点的前一个为  前一个结点
		dnode->prior = endNode;
		// 3. 插入位置的原结点（新节点在步骤1指向的）  要指向新插入的结点
		// 但是如果插入的时最后面的话， 新插入的位置后没有结点了（要判断一下 dnode的next是否为NULL）
		if(dnode->next != NULL) 
			dnode->next->prior = dnode; 
		// 4. 插入位置前的指向要指向新插入的位置
		endNode->next = dnode;
		// 尾插法， 所以endNode指向新插入进来的元素
		endNode = dnode; 
	}
}

2. 向后遍历双链表

• 因为双链表最后一个结点的next为NULL
• 如果这个dnode值为NULL表示到最后一个结点了

/**
	2. 后向遍历 
*/
void DLinkListPrintByNext(DNode* dnode) {
	// 从传进来的结点进行遍历
	printf("\n\n后向遍历的结果\n\n"); 
	while(dnode!=NULL) {
		printf(">>>%d", dnode->data);
		dnode= dnode->next; 
	}
	printf("\n\n");
}

3. 向前遍历双链表

• 向前遍历要注意判断是否到 头结点了，头结点不用输出
• 头结点的判断为 dnode->prior=NULL

/**
	3. 前向遍历 
*/ 
void DLinkListPrintByPrior(DNode* dnode) {
	// 从传进来的结点进行遍历
	printf("\n\n前向遍历的结果\n\n");
	
	//  dnode->prior如果为空表示到 头结点了，就不用输出了 
	while(dnode->prior!=NULL) {
		printf(">>>%d", dnode->data);
		dnode = dnode->prior;
	} 
	printf("\n\n");
}

4. 获取指定位序结点

逻辑和单链表的逻辑一样的

/**
	4.  查找元素， 将找到的节点返回。

 
*/
DNode* getElem(DLinkList L, int el) {
	// 第一个元素
	DNode* dnode = L->next; 
	// 开始循环查找 
	while(dnode!=NULL) {
		if(dnode->data == el) {
			// 找到了该元素，返回该结点
			return dnode; 
		}
		
		// 如果本结点不是
		dnode = dnode->next; 
	}
	// 如果循环结束没找到
	printf("\n\n没找到该节点\n\n");
	return NULL; 
	
}

5. 指定结点后插入结点（目前无法加在第一个位置）

• 具体思想： 传进来的结点后面插入结点
• ⭐插入的逻辑

1. 先将新插入的元素的 next 指向 插入前元素的next
2. 将新插入的元素的 prior指向 插入前的元素
3. 将插入元素前 之前指向的元素 （也就是 新元素的next）的prior指向新插入的元素即 dnode->next->prior = dnode； ⭐注意插入的元素要是最后一个元素的话，dnode->next就是NULL， 所以这里加个条件判断一下，要不要真正的执行
4. 插入元素前的元素要指向 新插入的元素， 即插入前的元素->next = dnode； （⭐注意这一步一般是最后执行的）

/**
	5. 在指定结点(指定的结点表示结点值)后插入结点
*/

void insertNextByNode(DNode* dnode) {
	// 创建一个要插入的结点
	DNode* newDnode;
	int x;
	
	// 为新结点分配空间 
	newDnode = (DLinkList)malloc(sizeof(DNode));
	if(newDnode==NULL) {
		// 表示开辟空间失败
		printf("\n\n开辟空间失败！\n\n");
		return ; 
	}
	printf("请输入插入结点的值：");
	scanf("%d", &x);
	// 为新结点赋值
	newDnode->data = x; 
	
	// 下面是插入的逻辑
	// 新的结点piror指向传入的结点，  next指向传入结点指向的结点
	newDnode->prior = dnode;
	newDnode->next = dnode->next;
	
	// 原传入的结点的next可能是NULL， 所以先判断一下是否为null
	// 不等于NULL， 才可以将它的piror设置为 新结点 
	if(newDnode->next != NULL)
		 newDnode->next->prior = newDnode;
	// 最后一步设置 传入的结点指向新结点
	dnode->next = newDnode;
} 

6. 删除指定元素后的元素 （目前删不了第一个）

• 删除的逻辑⭐

1. 先将要删除的元素 保留 dnodeT
2. 将传入元素的下一个指向 ，要删除元素的下一个。
   

   
   

   （⭐要判断传入元素是否为最后一个， 判断删除元素是否为空dnodeT！=NULL）

3. 将删除元素下一个元素的piror指向传入的元素。
   

   
   

   （⭐但是要判断删除的是不是最后一个元素， 这样就不要将删除的下一个piror指向传入的元素了，因为删除的元素后没有元素了）

4. 释放掉删除的元素

/**
	6. 删除指定指定结点后续结点 
*/ 

void delDnodeByNode(DNode* dnode) {
	
	// 将要删除的结点先赋值一个临时的
	DNode* dnodeT = dnode->next; 
	// 判断传入结点 后 是否为空 (即传入结点是否是最后一个) （即要删除的元素溢出了） 
	if(dnodeT!=NULL) 
		dnode->next =  dnodeT->next;
	else 
		return; 
	// 将删除结点的下一个piror指向删除传入的结点（即被删除的结点前一个）
	// 判断被删除结点是否为最后一个(dnodeT->next!=NULL) （如果时最后一个， 删除后就没有后续元素， 也不用指向前面了） 
	if(dnodeT->next!=NULL) 
		dnodeT->next->prior = dnode; 
	else
		return ;
	
	// 释放掉删除结点
	free(dnodeT); 
}