双向链表的创建、打印、求长、插入、删除、查值、清空、销毁

删除双向链表中的最后一个结点需单独对待

doublyLinkedList.h

#include "iostream"
using namespace std;

typedef struct DuLNode {
	int data;
	struct DuLNode *prior;
	struct DuLNode *next;
}DuLNode, *DuLinkedList;
//创建链表
bool createDuLinkedList(DuLinkedList &L, int n) {
	if (n < 1)
	{
		cout << "您输入的长度不合法！" << endl;
		exit(EXIT_FAILURE);
	}
	L = (DuLinkedList)malloc(sizeof(DuLNode));  //向系统申请分配size个字节的内存空间，返回类型是void*类型
	if (!L)
	{
		cout << "内存分配失败！" << endl;
		exit(EXIT_FAILURE);
		return false;
	}
	L->next = NULL;
	DuLinkedList p, q;
	p = L;
	for (int i = 0; i < n; i++)
	{
		q = (DuLinkedList)malloc(sizeof(DuLNode));
		if (!q)
		{
			cout << "内存分配失败！" << endl;
			exit(OVERFLOW);
			return false;
		}
		cin >> q->data;
		q->next = NULL;
		q->prior = p;
		p->next = q;
		p = q;
	}
	return true;
}
//输出链表
void printDuLinkedList(DuLinkedList &L) {
	DuLinkedList p;
	p = L->next;
	while (p != NULL)       //双向链表为空的时候
	{
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl;
}
//获取双向链表的长度
int getDuLinkedListLength(DuLinkedList &L) {
	int j = 0;
	DuLinkedList p;
	p = L->next;
	while (p)
	{
		j++;
		p = p->next;
	}
	return j;
}
//在第i个元素之前插入元素
bool insertElem(DuLinkedList &L, int i, int n) {
	DuLinkedList p, q;
	q = (DuLinkedList)malloc(sizeof(DuLNode));
	if (!q)
	{
		cout << "内存分配失败！" << endl;
		exit(EXIT_FAILURE);
	}
	if (i > getDuLinkedListLength(L)||i<1)
	{
		cout << "输入不合法" << endl;
		exit(EXIT_FAILURE);
	}
	p = L;
	for (int j = 0; j < i; j++)
	{
		p = p->next;  //定位到第i个元素
	}
	q->data = n;
	q->prior = p->prior;
	p->prior->next = q;
	q->next = p;
	p->prior = q;
	return true;
}
//删除第i个元素
bool deleteDuLinkedList(DuLinkedList &L, int i) {
	DuLinkedList p;
	if (i > getDuLinkedListLength(L) || i < 1)
	{
		cout << "输入不合法！" << endl;
		exit(EXIT_FAILURE);
	}
	p = L;
	int j = 0;
	while ((p->next != NULL) && (j < i))
	{
		p = p->next;
		j++;     //定位到第i个元素
	}
	if (p->next == NULL)   //因为最后一个节点的p->next==NULL;；
	{
		p->prior->next = NULL;
	}
	else
	{
		p->next->prior = p->prior;
		p->prior->next = p->next;
	}
	free(p);
	return true;
}
//查询第i个元素的值,并返回
int getElem(DuLinkedList &L, int i) {
	DuLinkedList p;
	if (i > getDuLinkedListLength(L)||i<1)
	{
		cout << "输入不合法" << endl;
	}
	p = L;
	for (int j = 0; j < i; j++)
	{
		p = p->next;
	}
	return p->data;
}
//查询链表中是否含有e,并返回位序
int searchElem(DuLinkedList &L, int e) {
	DuLinkedList p;
	p = L->next;
	int i = 1;
	while (p && (p->data != e))
	{
		p = p->next;
		i++;
	}
	if (!p)
	{
		cout << "链表中无该值！" << endl;
		return true;
	}
	else
	{
		return i;
	}
}

//清空双向链表
bool clearList(DuLinkedList &L) {
	if (L->next = NULL)
	{
		return true;
	}
	DuLinkedList p, q;
	p = q = L->next;
	while (p!=NULL)
	{
		p = p->next;
		free(q);
		q = p;
	}
	L->next = L->prior = NULL;
	return true;
}
//销毁双向链表
bool destoryList(DuLinkedList &L) {
	if (L == NULL)
	{
		return true;
	}
	DuLinkedList p, q;
	p = q = L->next;
	while (p)
	{
		p = q->next;
		free(q);
		q = p;
	}
	free(L);
	return true;
}

main.cpp

#include "stdafx.h"
#include "doublyLinkedList.h"
int main()
{
	DuLinkedList list1;
	int length, i, elem;
	cout << "请输入要创建的链表长度：";
	cin >> length;
	createDuLinkedList(list1,length);
	cout << "打印链表：";
	printDuLinkedList(list1);
	cout << "请输入要插入元素的位置：";
	cin >> i;
	cout << "请输入要插入的元素的大小：";
	cin >> elem;
	insertElem(list1, i, elem);
	cout << "打印链表：";
	printDuLinkedList(list1);
	cout << "请输入要删除的元素位置：";
	cin >> i;
	deleteDuLinkedList(list1, i);
	cout << "打印链表：";
	printDuLinkedList(list1);
	cout << "请输入要查找的元素的位置：";
	cin >> i;
	cout << getElem(list1, i) << endl;
	cout << "请输入要查找的元素的值：";
	cin >> elem;
	cout << searchElem(list1,elem) << endl;
	cout << "清空链表"<<endl;
	cout << "打印链表：";
	printDuLinkedList(list1);
	system("pause");
	return 0;
}