双链表的基本操作（CC++）

• 前言
• 一、双链表的操作
• • 1、双链表节点描述
  • 2、创建双链表
  • 3、双链表的插入(在p节点之后插入s节点)
  • 4、双链表的删除(删除p节点的后继节点q)
• 二、使用方法

双链表的基本操作：创建双链表、插入节点、删除节点

//双链表节点描述
typedef struct DNode {
	ElemType data;//节点元素
	DNode* prior, * next;//节点前后两个指针
}DNode, * DLinklist;

//创建双链表
void CreateDLinkList(DLinklist& L) {
	int x;
	DNode* s, * r;
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL) {
		cout << "创建失败..." << endl;
	}
	L->next = NULL;
	L->prior = NULL;
	r = L;
	cout << "请输入:(输入9999结束)" << endl;
	cin >> x;
	while (x != 9999) {
		s = (DNode*)malloc(sizeof(DNode));
		s->data = x;
		r->next = s;
		s->prior = r;
		r = s;
		cin >> x;
	}
	r->next = NULL;
	cout << "创建成功..." << endl;
}

//双链表的插入(在p节点之后插入s节点)
void InsertNextDNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL) {
		cout << "参数有误..." << endl;
		return;
	}
	s->next = p->next;
	if (p->next != NULL) {
		p->next->prior = s;
	}
	p->next = s;
	s->prior = p;
	cout << "插入成功..." << endl;
}

//双链表的删除(删除p节点的后继节点q)
void DeleteNextDNode(DNode* p) {
	if (p == NULL) {
		cout << "参数有误..." << endl;
		return;
	}
	DNode* q = p->next;
	if (q == NULL) {
		cout << "无后继节点..." << endl;
		return;
	}
	p->next = q->next;
	if (q->next != NULL) {
		q->next->prior = p;
	}
	free(q);
	cout << "删除成功..." << endl;
}

#include

using namespace std;
typedef int ElemType;

//双链表节点描述
typedef struct DNode {
	ElemType data;//节点元素
	DNode* prior, * next;//节点前后两个指针
}DNode, * DLinklist;

//创建双链表
void CreateDLinkList(DLinklist& L) {
	int x;
	DNode* s, * r;
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL) {
		cout << "创建失败..." << endl;
	}
	L->next = NULL;
	L->prior = NULL;
	r = L;
	cout << "请输入:(输入9999结束)" << endl;
	cin >> x;
	while (x != 9999) {
		s = (DNode*)malloc(sizeof(DNode));
		s->data = x;
		r->next = s;
		s->prior = r;
		r = s;
		cin >> x;
	}
	r->next = NULL;
	cout << "创建成功..." << endl;
}

//双链表的插入(在p节点之后插入s节点)
void InsertNextDNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL) {
		cout << "参数有误..." << endl;
		return;
	}
	s->next = p->next;
	if (p->next != NULL) {
		p->next->prior = s;
	}
	p->next = s;
	s->prior = p;
	cout << "插入成功..." << endl;
}

//创建节点
DNode* CreatNode() {
	DNode* s;
	int e;
	cout << "请输入节点元素:" ;
	cin >> e;
	s = (DNode*)malloc(sizeof(DNode));
	s->data = e;
	return s;
}

//按值查找表节点
DNode* LocateElem(DLinklist L) {
	DNode* s;
	int e;
	cout << "请输入你要在哪个元素后执行:" ;
	cin >> e;
	s = L->next;
	while (s != NULL && s->data != e) {
		s = s->next;
	}
	return s;
}

//双链表的删除(删除p节点的后继节点q)
void DeleteNextDNode(DNode* p) {
	if (p == NULL) {
		cout << "参数有误..." << endl;
		return;
	}
	DNode* q = p->next;
	if (q == NULL) {
		cout << "无后继节点..." << endl;
		return;
	}
	p->next = q->next;
	if (q->next != NULL) {
		q->next->prior = p;
	}
	free(q);
	cout << "删除成功..." << endl;
}

//打印双链表
void PrintList(DLinklist L) {
	DNode* s;
	s = (DNode*)malloc(sizeof(DNode));
	int i = 1;
	s = L->next;
	while (s)
	{
		cout << "第" << i++ << "节点 " << s->data << endl;
		s = s->next;
	}
}

//菜单
void menu(DLinklist& L) {
	int n;
	do {
		cout << "tt双链表操作菜单tt" << endl;
		cout << "tt1.创建双链表tt" << endl;
		cout << "tt2.双链表的插入tt" << endl;
		cout << "tt3.双链表的删除tt" << endl;
		cout << "tt4.打印双链表tt" << endl;
		cout << "tt5.退出tt" << endl;
		cout << "请输入序号:" ;
		cin >> n;
		switch (n)
		{
		case 1:CreateDLinkList(L);
			break;
		case 2:
			InsertNextDNode(LocateElem(L),CreatNode());
			break;
		case 3:DeleteNextDNode(LocateElem(L));
			break;
		case 4:PrintList(L);
			break;
		case 5: return;
		default:
			cout << "输入错误..." << endl;
			break;
		}
	} while (true);
}
int main() {
	DLinklist L;
	menu(L);
	cout << "程序已结束运行...";
	return 0;
}