线性表——双链表的增删改查（头插法，尾插法，按序号查找，按值查找，某个位置插入元素，某个位置删除元素）

线性表——双链表的增删改查（头插法，尾插法，按序号查找，按值查找，某个位置插入元素，某个位置删除元素）

在学习双链表之前，可先复习巩固一下单链表，双链表这个删改查原理与单链表大致相同。
原文博客如下 单链表的增删改查

目录

• • 一、双链表的特点
  • 二、双链表的组成
  • 三、代码实现
  • • 结构体
    • 1.头插法
    • 2.尾插法
    • 3.按序号查找
    • 4.按值查找
    • 5.某个位置插入元素
    • 6.某个位置删除元素
    • 打印链表

一、双链表的特点

与单链表不同是，单链表指针域中只有next指针，而双链表有两个指针，前驱指针prior和后继指针next。但是思路与单链表基本类似，不同的是指针指向必须是双向的，a->b,b->a。

二、双链表的组成

prior前驱指针+数据域data+next后继指针。

三、代码实现 结构体

typedef int ElemType;
typedef struct DNode{
	ElemType data; // 数据域
	struct DNode* prior; // 前驱
	struct DNode* next; // 后继
}DNode,*DlinkList;

1.头插法

// 头插法
DlinkList DlinkList_head_insert(DlinkList& DL) {
	// 申请空间，带头结点的链表
	DL = (DlinkList)malloc(sizeof(DNode));
	DL->prior = NULL;
	DL->next = NULL;
	DlinkList s;
	int x;
	scanf("%d", &x);
	while (x != 9999) {
		// 给这个元素申请空间
		s = (DlinkList)malloc(sizeof(DNode));
		s->data = x; // 将输入的值赋给数据域
		s->next = DL->next;
		if (DL->next != NULL) { // 注意这个判断，即后边有元素
			DL->next->prior = s;
		}
		s->prior = DL;
		DL->next = s;
		scanf("%d", &x); // 输入下一个元素
	}
	return DL;
}

2.尾插法

// 尾插法
DlinkList DlinkList_tail_insert(DlinkList& DL) {
	// 申请空间，带头结点的链表
	DL = (DlinkList)malloc(sizeof(DNode));
	DL->prior = NULL;
	DL->next = NULL;
	DlinkList s, r = DL;
	int x;
	scanf("%d", &x);
	while (x != 9999) {
		// 申请空间
		s = (DlinkList)malloc(sizeof(DNode));
		s->data = x;
		r->next = s;
		s->prior = r;
		r = s; // r指向新的表尾结点
		scanf("%d", &x);
	}
	r->next = NULL;
	return DL;
}

3.按序号查找

// 按序号查找元素
DlinkList GetElem(DlinkList DL, ElemType& e) {
	if (0 == e) {
		return DL;
	}
	if (e < 0) {
		return NULL; // e是负值
	}
	DlinkList p = DL->next; // 因为头指针为空，要指向有元素的，即第一个结点
	for (int i = 1; i < e; i++) {
		p = p->next;
	}
	return p;
}

4.按值查找

// 按值查找
DlinkList LocateElem(DlinkList DL, ElemType e) {
	DlinkList p = DL->next; //头指针为空，要指下第一个结点
	while (p != NULL && p->data != e) {
		p = p->next;
	}
	return p;
}

5.某个位置插入元素

// 某个位置插入元素
bool InsertDList(DlinkList& DL, ElemType e, int i) {
	// 先找到要插入元素的上一元素
	e = e - 1;
	DlinkList p = GetElem(DL, e);
	if (p == NULL) {
		return false;
	}
	// 给要插入的元素申请空间
	DlinkList s = (DlinkList)malloc(sizeof(DNode));
	s->data = i; // 将值赋给data域
	s->next = p->next;
	if (p->next != NULL) {
		p->next->prior = s;
	}
	s->prior = p;
	p->next = s;
	return true;
}

6.某个位置删除元素

// 某个位置删除元素
bool DelDList(DlinkList& DL, ElemType e) {
	// 获取这个元素的上一位置
	e = e - 1;
	DlinkList p = GetElem(DL, e);
	if (p == NULL) {
		return false;
	}
	DlinkList q = p->next; // 要删除的元素
	p->next = q->next;
	if (q->next != NULL) {
		q->next->prior = p;
	}
	free(q);
	q = NULL;
	return true;
}

打印链表

//  打印链表
void PrintDlinkList(DlinkList DL) {
	DL = DL->next;
	while (DL != NULL) {
		printf("%3d", DL->data);
		DL = DL->next;
	}
	printf("n");
}

芜湖~今日学习也有好好打卡呢）