上机3_线性表（2）

题目

设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。
要求：
1、定义带头结点的双向链表的型DLIST。
2、定义双向链表DLIST的基本操作。
3、定义函数int swap(elementtype x, DLIST &h)，查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1，否则返回0。
4、在主函数中测试所编写函数的正确性。

代码

#include <iostream>
using namespace std;

typedef int ElemType;

struct dcelltype {
   
	ElemType data;
	dcelltype* next, * prior;
};
typedef dcelltype* DLIST;
typedef dcelltype* position;

void Insert(ElemType x, position p, DLIST& L)
{
   
	position q = new dcelltype;
	q->data = x;
	q->next = p->next;
	p->next = q;
	q->prior = p;
	if (q->next != NULL)
		q->next->prior = q;
}

void Delete(position p, DLIST& L)
{
   
	if (p->prior != NULL)
		p->prior->next = p->next;
	if (p->next != NULL)
		p->next->prior = p->prior;
	delete p;
}

position Previous(position p, DLIST L)
{
   
	position q;
	if (p->prior == NULL)
	{
   
		cout << "不存在前驱位置";
		return NULL;
	}
	else
	{
   
		q = p->prior;
		return q;
	}
}

position MakeNull(DLIST& L)
{
   
	L = new dcelltype;
	L->next = NULL;
	return L;
}

// 后面与 LIST 相同
position Locate(ElemType x, DLIST L)
{
   
	position p = L;
	while (p->data != x && p->next != NULL)
	{
   
		p = p->next;
	}
	if (p->data != x)
	{
   
		return NULL;
	}
	return p;
}

ElemType Retrieve(position p, DLIST L)
{
   
	return p->next->data;
}

position Next(position p, DLIST L)
{
   
	position q;
	if (p->next == NULL)
	{
   
		cout << "不存在后继位置";
		return NULL;
	}
	else
	{
   
		q = p->next;
		return q;
	}
}

position First(DLIST L)
{
   
	return L;
}

position End(DLIST L)
{
   
	position q = L;
	while (q->next != NULL)
		q = q->next;
	return q;
}

int Swap(ElemType x, DLIST& L)
{
   
	position p = Locate(x, L);
	if (NULL == p)
	{
   
		return 0;
	}
	if (Next(First(L), L) == p)
	{
   
		// Do Nothing
	}
	else if (End(L) == p)
	{
   
		p->prior->next = NULL;
		p->next = p->prior;
		p->prior = p->prior->prior;
		p->prior->next = p;
		p->next->prior = p;
	}
	else
	{
   
		position tmp = p->prior;
		p->prior->next = p->next;
		p->next->prior = p->prior;
		p->prior = p->prior->prior;
		p->prior->next = p;
		p->next = tmp;
		p->next->prior = p;
	}
	return 1;
}

int main()
{
   
	DLIST dList = nullptr;
	MakeNull(dList);
	Insert(3, End(dList), dList);
	Insert(1, End(dList), dList);
	Insert(4, End(dList), dList);
	Insert(1, End(dList), dList);
	Insert(5, End(dList), dList);
	Insert(9, End(dList), dList);
	Insert(2, End(dList), dList);
	Insert(6, End(dList), dList);
	for (position i = First(dList); i != End(dList); i = Next(i, dList))
	{
   
		cout << Retrieve(i, dList) << ' ';
	}
	cout << endl;
	Swap(6, dList);
	for (position i = First(dList); i != End(dList); i = Next(i, dList))
	{
   
		cout << Retrieve(i, dList) << ' ';
	}
	cout << endl;
}