【数据结构】双链表C++

#include<iostream>
using namespace std;
typedef int ElemType;
struct DuLNode{		// 双向链表节点结构体
	ElemType data;
	struct DuLNode* prior, * next;
};
typedef DuLNode* DuLinklist;

/******************************************************************/
/*初始化*/
/******************************************************************/
bool InitList_L(DuLinklist &L) {
	L = new DuLNode;		// 生成新节点作为头节点，用头指针L指向头节点
	if (!L) return false;	// 生成节点失败
	L->prior = L->next = NULL;	//头节点的两个指针域置空
	return true;
}

/******************************************************************/
/*头插法创建双向链表*/
/******************************************************************/
void CreateDuList_H(DuLinklist& L) {
	int n;				// 节点个数
	DuLinklist s;		// 定义一个指针变量
	cout << "请输入元素个数n：" << endl;
	cin >> n;
	cout << "头插法创建单链表..." << endl;
	while (n--)
	{
		s = new DuLNode;		// 生成新节点
		cin >> s->data;
		if (L->next) L->next->prior = s;  // L后面有节点
		s->next = L->next;
		s->prior = L;
		L->next = s;			// 将新节点s插入头节点之后
	}
}

/******************************************************************/
/*插入：在头节点的单链表L中第i个位置之前插入值为e的新节点*/
/******************************************************************/
bool ListInsert_L(DuLinklist&L,int i,int e){
	int j;
	DuLinklist p, s;
	p = L;
	j = 0;
	while (p&&j<i) //查找第i个节点，p指向该节点
	{
		p = p->next;
		j++;
	}
	if (!p || j > i) return false;
	s = new DuLNode;	// 新节点
	s->data = e;		// 将新节点的数据域置为e
	p->prior->next = s;
	s->prior = p->prior;
	s->next = p;
	p->prior = s;
	return true;
}

/******************************************************************/
/*删除：在带头节点的双向链表中，删除第i个节点*/
/******************************************************************/
bool ListDelete_L(DuLinklist& L, int i) {
	DuLinklist p;
	int j;
	p = L;
	j = 0;
	while (p && (j < i)) {
		p = p->next;
		j++;
	}
	if (!p || (j > i)) return false;	// 当i>n或i<1时，删除位置不合理
	// 如果p的后继节点存在：	
	if (p->next) p->next->prior = p->prior;	
	p->prior->next = p->next;
	delete p;							// 释放被删除节点的空间
	return true;
}

/******************************************************************/
/*遍历*/
/******************************************************************/
void visit(ElemType* ep) // 链表遍历辅助函数
{
	cout << *ep << " ";
}
void ListTraverse(DuLinklist L, void(*visit)(ElemType*))
{
	DuLinklist p = L->next;  // p指向开始结点(注意，头结点之后才是开始结点)
	while (p != NULL)    // 若p不是链尾则继续
	{
		visit(&(p->data));
		p = p->next;   // p指向直接后继结点
	}
	cout << endl;
}

/******************************************************************/
/*主函数*/
/******************************************************************/
int main() {
	DuLinklist L;
	cout << "初始化双链表" << endl;
	InitList_L(L);
	cout << "头插法创建双链表" << endl;
	CreateDuList_H(L);
	cout << "遍历双链表" << endl;
	ListTraverse(L, *visit);
	cout << "在i=2中插入2" << endl;
	ListInsert_L(L,2,2);
	cout << "遍历双链表" << endl;
	ListTraverse(L, *visit);
	cout << "删除第2个节点" << endl;
	ListDelete_L(L, 2);
	cout << "遍历双链表" << endl;
	ListTraverse(L, *visit);
}

更多文章请关注《万象专栏》