数据结构第三章线性表（三）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构第三章线性表（三）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构第三章线性表（三）,数据结构,数据结构

🚀 写在最前：在前面学习了单链表的基本操作，这篇文章学习双链表，以及双链表的一些基本操作。

🚀：求个关注😀，让我们一起探索计算机的奥秘！

一、双链表

双链表一个节点含有两个指针域，前指针域指向前一个节点，后一个指针域指向后一个节点；那为什么有了单链表还需要双链表呢？是因为单链表它很难找到当前节点的前一个节点，是为了方便找到当前节点的前一个节点，所以引入了双链表。双链表的示意图如下图所示。

数据结构第三章线性表（三）,数据结构,数据结构

二、双链表的基本操作

文件结构：

文件结构如下，建有DLinkList.h，用于定义数据结构以及函；DLinkList.cpp用于实现函数的功能；test.cpp用于测试实现的函数是否好用。

数据结构第三章线性表（三）,数据结构,数据结构

①双链表的初始化

DLinkList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>

typedef int EelentType;

typedef struct DLNode {
	EelentType data;
	DLNode* prior;       //前指针，头节点的前指针始终为空
	DLNode* next;        //后指针
}DLNode,*DLinkList;


//定义数据结构操作

//初始化双链表
bool InitDlinkList(DLinkList& L);

DLinkList.cpp

#include"DLinkList.h"

//初始化双链表
bool InitDlinkList(DLinkList& L) {
	L = (DLNode*)malloc(sizeof(DLNode));
	if (L == NULL) {
		printf("空间申请失败导致双链表初始化失败\n");
		return false;
	}
	else {
		L->next = NULL;
		L->prior = NULL;
		return true;
	}
}

test.cpp

#include"DLinkList.h"

int main() {
	DLinkList L1 = NULL;
	
	//初始化L1链表
	if (InitDlinkList(L1)) {
		printf("初始化成功！\n");
	}

	return 0;
}

out:

初始化成功！

D:\C_WorkSpace\DLinkList\x64\Debug\DLinkList.exe (进程 24384)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

②双链表的插入操作

DLinkList.h

//双链表的插入操作
bool DLinkListInsert(DLinkList L, int i, EelmentType e);

DLinkList.cpp

//双链表的插入操作
bool DLinkListInsert(DLinkList L, int i, EelmentType e) {
	//申请新的节点
	DLNode* tmp = (DLNode*)malloc(sizeof(DLNode));
	if (tmp == NULL) {
		printf("空间申请失败导致插入失败\n");
		return false;
	}
	else {
		DLNode* p = L;   //指向节点的指针
		int j = 0;       //定位p指向哪个节点
		while (p != NULL && j < i - 1) {
			p = p->next;
			j++;
		}
		if (p == NULL) {
			printf("插入位置不合法\n");
			return false;
		}
		else {
			tmp->data = e;
			tmp->next = p->next;
			if (p->next!= NULL) {   //这步判断是为了防止是尾插p->next->prior是空指针
				p->next->prior = tmp;
			}
			tmp->prior = p;
			p->next = tmp;
			return true;
		}
	}
}

test.cpp

#include"DLinkList.h"

int main() {
	DLinkList L1 = NULL;
	
	//初始化L1链表
	if (InitDlinkList(L1)) {
		printf("初始化成功！\n");
	}
	DLinkListInsert(L1, 1, 1);
	DLinkListInsert(L1, 2, 2);
	DLinkListInsert(L1, 1, 6);
	printf("位置1上的元素为：%d\n", L1->next->data);
	printf("位置2上的元素为：%d\n", L1->next->next->data);
	printf("位置3上的元素为：%d\n", L1->next->next->next->data);
	return 0;
}

out:
初始化成功！
位置1上的元素为：6
位置2上的元素为：1
位置3上的元素为：2

D:\C_WorkSpace\DLinkList\x64\Debug\DLinkList.exe (进程 19616)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

③双链表的打印

DLinkList.h

//双链表的打印
void DLinkListPrint(DLinkList L);

DLinkList.cpp

//双链表的打印
void DLinkListPrint(DLinkList L) {
	if (L->next == NULL) {
		printf("该双双链表为空\n");
		exit;
	}
	else {
		DLNode* p = L->next;
		while (p != NULL) {
			printf("%d<----->", p->data);
			p = p->next;
		}
		printf("\n");
	}
}

test.cpp

#include"DLinkList.h"

int main() {
	DLinkList L1 = NULL;
	
	//初始化L1链表
	if (InitDlinkList(L1)) {
		printf("初始化成功！\n");
	}
	DLinkListInsert(L1, 1, 1);
	DLinkListInsert(L1, 2, 2);
	DLinkListInsert(L1, 1, 6);
	DLinkListPrint(L1);

	return 0;
}

out:
初始化成功！
6<----->1<----->2<----->

D:\C_WorkSpace\DLinkList\x64\Debug\DLinkList.exe (进程 5992)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

④双链表的删除

DLinkList.h

//双链表的删除
bool DLinkListDelete(DLinkList L, int i);

DLinkList.cpp

//双链表的删除
bool DLinkListDelete(DLinkList L, int i) {
	DLNode* p = L;   //使用tmp指向节点
	int j = 0;         //使用j表示指向哪个节点
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p->next == NULL || p == NULL) {
		printf("删除位置不合法\n");
		return false;
	}
	DLNode* temp = p->next;
	p->next = temp->next;
	if (temp->next != NULL) {  //这步判断是为了防止是删除的是最后一个元素
		temp->next->prior = temp->prior;
	}
	free(temp);
}

test.cpp文章来源地址https://www.toymoban.com/news/detail-852489.html

#include"DLinkList.h"

int main() {
	DLinkList L1 = NULL;
	
	//初始化L1链表
	if (InitDlinkList(L1)) {
		printf("初始化成功！\n");
	}
	DLinkListInsert(L1, 1, 1);
	DLinkListInsert(L1, 2, 2);
	DLinkListInsert(L1, 1, 6);
	DLinkListPrint(L1);         //6 < ----->1 < ----->2 < ----->
	
	DLinkListDelete(L1, 3);
	DLinkListPrint(L1);         //6 < ----->1 < ----->
	
	DLinkListInsert(L1, 1, 17);
	DLinkListDelete(L1, 2);
	DLinkListPrint(L1);         //17 < ----->1 < ----->
	return 0;
}

out:

初始化成功！
6<----->1<----->2<----->
6<----->1<----->
17<----->1<----->

D:\C_WorkSpace\DLinkList\x64\Debug\DLinkList.exe (进程 7084)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

到了这里，关于数据结构第三章线性表（三）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！