【数据结构】-双链表(带头结点）

叁歲伎倆 2023-02-27 12:20 3阅读 0赞

### 双链表-带头结点 ###

*  1.头文件及类型定义
 *  2.双链表结点类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化双链表
     *  4.2 判空
     *  4.3 查找操作
     *   *  4.3.1 按位查找
         *  4.3.2 按值查找
     *  4.4 插入操作
     *   *  4.4.1指定结点插入
         *   *  4.4.1.1后插
             *   *  4.4.1.1.1 给结点
                 *  4.4.1.1.2 给元素值
             *  4.4.1.2 前插
         *  4.4.2 按位插入
     *  4.5 删除操作
     *  4.6 创建双链表
     *  4.7 销毁双链表
     *  4.8 求表长
     *  4.9 遍历
     *  4.10 main函数
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define ElemType int

# 2.双链表结点类型定义 #

typedef struct DNode {
        				//定义双链表结点类型
    	ElemType data;
    	struct DNode* prior, * next;	//前驱和后继指针
    }DNode, * DLinkList;

# 3.函数声明 #

/*函数声明*/
    DLinkList InitDLinkList(DLinkList& L);					//1.初始化双链表
    bool Empty(DLinkList L);								//2.判空
    DNode* GetElem(DLinkList L, int i);						//3-1.查找操作-按位查找
    DNode* LocateElem(DLinkList L, ElemType e);				//3-2.查找操作-按值查找
    bool InsertNextDNode1(DNode* p, DNode* s);				//4-1-1.插入操作-指定结点后插1-给结点
    bool InsertNextDNode2(DNode* p, ElemType e);			//4-1-2.插入操作-指定结点后插2-给元素值
    bool InsertPriorDNode(DNode* p, DNode* s);				//4-2.插入操作-指定结点前插
    bool InsertDLinkList(DLinkList& L, int i, ElemType e);	//4-3.插入操作-按位插入
    bool DeleteNextDNode(DNode* p);							//5.删除操作-删除指定结点p的后继结点q
    DLinkList List_HeadInsert(DLinkList& L);				//6.创建双链表：头插法
    void DestoryList(DLinkList& L);							//7.销毁操作
    int Length(DLinkList L);								//8.求表长
    void PrintDLinkList(DLinkList L);						//9.遍历

# 4.基本操作 #

## 4.1 初始化双链表 ##

//1.初始化双链表(带头结点)
    DLinkList InitDLinkList(DLinkList& L) {
        
    	L = (DNode*)malloc(sizeof(DNode));		//创建头结点
    	if (L == NULL)
    		return NULL;    //内存不足，分配失败
    	L->prior = NULL;	//头结点的prior永远指向NULL，可作判断逆向遍历的条件
    	L->next = NULL;		//头结点之后暂时没有结点
    	return L;
    }

## 4.2 判空 ##

//2.判空
    bool Empty(DLinkList L) {
        
    	return (L->next == Null);
    }

## 4.3 查找操作 ##

### 4.3.1 按位查找 ###

//3-1.查找操作-按位查找：返回第i个结点
    DNode* GetElem(DLinkList L, int i) {
        
    	if (i < 0)
    		return NULL;
    	int j = 0;
    	DNode* p = L;
    	while (p != NULL && j < i) {
        
    		p = p->next;
    		j++;
    	}
    	return p;		//也可能返回NULL，当输入i大于双链表长度时
    }

### 4.3.2 按值查找 ###

//3-2.查找操作-按值查找：找到第一个数据域为e的结点
    DNode* LocateElem(DLinkList L, ElemType e) {
        
    	DNode* p = L->next;
    	while (p->data != e) {
        
    		p = p->next;
    	}
    	return p;
    }

## 4.4 插入操作 ##

### 4.4.1指定结点插入 ###

#### 4.4.1.1后插 ####

##### 4.4.1.1.1 给结点 #####

//4-1-1.插入操作-指定结点后插1-给结点
    bool InsertNextDNode1(DNode* p, DNode* s) {
        
    	if (p == NULL || s == NULL)		//非法参数
    		return false;
    	DNode* q = p->next;
    	s->next = q;
    	if (p->next != NULL)	//判断p是不是最后一个结点
    		q->prior = s;		//如果是，则跳过此句，因为p的后继为NULL，没有前驱
    	s->prior = p;
    	p->next = s;
    	return true;
    }

##### 4.4.1.1.2 给元素值 #####

//4-1-2.插入操作-指定结点后插2-给元素值
    bool InsertNextDNode2(DNode* p, ElemType e) {
        
    	if (p == NULL)		//非法参数
    		return false;
    	DNode* q = p->next;		//q为p原先的后继结点
    	DNode* s = (DNode*)malloc(sizeof(DNode));	//s为p新的后继结点
    	if (s == NULL)
    		return false;		//内存不足，分配失败
    	s->data = e;	//为新结点赋值
    	s->next = q;
    	if(q!=NULL)			//判断q是不是最后一个结点
    		q->prior = s;		//如果是，则跳过此句，因为q为NULL，没有前驱
    	s->prior = p;
    	p->next = s;
    	return true;
    }

#### 4.4.1.2 前插 ####

//4-2.插入操作-指定结点前插
    bool InsertPriorDNode(DNode* p, DNode* s) {
        
    	DNode* q = p->prior;	//先找到p的前驱结点q
    	return InsertNextDNode1(q, s);	//对q进行后插操作
    }

### 4.4.2 按位插入 ###

//4-3.插入操作-按位插入
    bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
        
    	DNode* p = GetElem(L, i-1);		//按位查找i-1个结点p
    	return InsertNextDNode2(p, e);	//对p结点进行后插操作
    }

## 4.5 删除操作 ##

//5.删除操作-删除指定结点p的后继结点q
    bool DeleteNextDNode(DNode* p) {
        
    	if (p == NULL)
    		return false;	//非法参数：p不存在
    	DNode* q = p->next;
    	if (q == NULL)
    		return false;	//p没有后继结点
    	p->next = q->next;
    	if (q->next != NULL)				//判断q是不是最后一个结点
    		q->next->prior = p;		//如果是，则跳过此句，因为q->next为NULL，没有前驱
    	free(q);
    	return true;
    }

## 4.6 创建双链表 ##

//6.创建双链表：头插法（创建方法与单链表相同，其他方法不再声明，仅用头插法测试）
    DLinkList List_HeadInsert(DLinkList& L) {
        
    	L = InitDLinkList(L);		//初始化双链表
    	ElemType x;
    	int i = 1;		//用作记录插入第几个元素
    	printf("开始创建双链表！\n请输入%d个元素：", i);
    	scanf("%d", &x);
    	while (x != 0) {
        
    		if (InsertNextDNode2(L, x)) 		//头插法本质是头结点的后插操作
    			printf("成功插入第%d个元素：%d\n", i, x);
    		else
    			printf("插入第%d个元素失败！\n", i);
    		printf("请输入%d个元素：", ++i);
    		scanf("%d", &x);
    	}
    	printf("双链表创建完成！\n");
    	return L;
    }

## 4.7 销毁双链表 ##

//7.销毁操作
    void DestoryList(DLinkList& L) {
        
    	printf("开始销毁双链表！\n");
    	//循环释放各个数据结点--对头结点依次做删除操作
    	while (L->next != NULL) 
    		DeleteNextDNode(L);
    	free(L);	//释放头结点
    	L = NULL;	//头指针指向NULL
    }

## 4.8 求表长 ##

//8.求表长
    int Length(DLinkList L) {
        
    	int len = 0;
    	DNode* p = L->next;
    	while (p != NULL) {
        
    		p = p->next;
    		len++;
    	}
    	return len;
    }

## 4.9 遍历 ##

//9.遍历
    void PrintDLinkList(DLinkList L) {
        
    	DNode* p = L->next;
    	printf("遍历双链表：\n");
    	while (p != NULL) {
        
    		printf("%d\t", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }

## 4.10 main函数 ##

int main() {
        
    	DLinkList L;
    	int i;
    
    	/*以下操作只要涉及对双链表的改动，均遍历双链表*/
    
    	/*1、头插法建立双链表*/
    	L = List_HeadInsert(L);
    	printf("当前表长为：%d\n", Length(L));
    	PrintDLinkList(L);
    
    	/*2、按位插入*/
    	ElemType e1;
    	printf("请输入您所要插入的位序i和元素值e：");
    	scanf("%d%d", &i, &e1);
    	if (InsertDLinkList(L, i, e1))
    		printf("您已成功插入元素值：%d\n", e1);
    	else
    		printf("位序i不合法，插入元素值%d失败！\n", e1);
    	PrintDLinkList(L);
    
    	/*3、按位查找*/
    	printf("请输入您要查找的位序i：");
    	scanf("%d", &i);
    	DNode* p1 = GetElem(L, i);
    	printf("位序为%d的值为：%d\n", i, p1->data);
    
    	/*4、按值查找*/
    	ElemType e2;
    	printf("请输入您要查找的元素值e：");
    	scanf("%d", &e2);
    	DNode* p2 = LocateElem(L, e2);
    
    	/*5、指定结点前插*/
    	DNode* p3 = (DNode*)malloc(sizeof(DNode));
    	p3->data = p2->data;
    	if (InsertPriorDNode(p1, p3)) {
        	//将p2插入p1前
    		printf("前插成功！\n");
    		DeleteNextDNode(p2->prior);
    	}
    	else
    		printf("前插失败！\n");
    	PrintDLinkList(L);
    
    	/*6、删除指定结点的后继结点，此处删除p2的后继结点*/
    	ElemType e3 = p1->next->data;
    	if (DeleteNextDNode(p1))
    		printf("此结点后继结点删除成功，值为：%d\n", e3);
    	else
    		printf("此结点后继结点删除失败！");
    	PrintDLinkList(L);
    
    	/*7、销毁双链表*/
    	DestoryList(L);
    	if (L == NULL)
    		printf("双链表已销毁！\n");
    	else
    		printf("双链表销毁失败！\n");
    	return 0;
    }

# 5.小结 #

1.  **说明**  
    本文仅用带头结点的双链表进行测试，不带头结点的双链表可参考不带头结点的单链表，基本操作大多相似。
2.  **要注意的点**  
    在双链表中的后插操作和指定结点的后继结点的删除操作中，要特别注意边界情况的处理：若插入结点或被删除结点是最后一个结点，其后继结点为NULL，故前驱指针不可赋值(因为就不存在)，需要进行判断。  
    当然，在引入循环双链表之后这个问题可以避免(因为不存在后继结点不存在的情况)。