数据结构第二章课后习题第九题(交换双向链表中当前结点和前驱结点的顺序)

已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，
写出算法change（p），交换p所指向的结点和它的前缓结点的顺序。




#include 
#define ok 1
#define error 0

using namespace std;
typedef int ElemType;
typedef int status;


//定义
typedef struct DNode
{
	ElemType data;
	struct DNode *prior, *next;
 }DNode, *DLinkList;
 

//创建双向循环链表 
status CreatList_R(DLinkList &L, int n)
{
	L = new DNode ;                           //初始化一个双向循环链表，表中暂时只有一个头结点 
	L->next = L;                              //头结点的next域指向头结点 
	L->prior = L;                             //头结点的prior域指向头结点 
	DNode *p = L;                             //结点指针p初始化指向头结点 
	for (int i = 0; i < n; i++)
	{
		DNode *s = new DNode;                 //生成一个新结点s 
		cin >> s->data;                       //将输入的数据存放在新结点的数据域中
		 
		//将新结点链接在头结点之后 
		p->next = s;                        
		s->next = L;
		s->prior = p;
		p = s;
	}
	return ok;
}



void Change(DLinkList p)  
{
	DNode *q = p->prior;          //指针q指向p的前驱结点 
	
	q->prior->next = p;           // p的前驱的前驱之后继为p 
	p->prior = q->prior;          // p的前驱指向其前驱的前驱
	
	q->next = p->next;            // p的前驱的后继为p的后继
	p->next->prior = q;           // p的后继的前驱指向原p的前驱
	
	q->prior = p;                 // p与其前驱交换
	p->next = q;                  // p的后继指向其原来的前驱
}


//输出
status DispList(DLinkList L)
{
	DNode *p = L->next;
    while (p != L)                   //遍历 
    {
	    cout << p->data << ' ';
    	p = p->next;
    }
} 

 
int main()
{
	int n;
	DLinkList L;
	cout << "链表长度：";
	cin >> n;
	cout << "输入链表元素值：";
	CreatList_R(L, n);
	cout << "输出链表元素：" << endl;
	DispList(L);
	cout << endl;
	
	cout << "输入要交换的结点值：" << endl;
	DNode *s = new DNode;
	cin >> s->data;
	DNode *p = L->next;
    while (p != L)
    {
    	if (p->data == s->data)
    		Change(p);
    	
		p = p->next;
	}
	cout << "输出交换之后的链表元素：" ;
	DispList(L);
	return 0;
}