建立有序双向循环链表

 

#include "stdafx.h"
#include <iostream>
//建立有序双向循环链表
using namespace std;
typedef struct Dbnode{
	int data;      //节点数据
	Dbnode *left;  //前驱结点指针
	Dbnode *right; //后继节点指针
}Dbnode;
void Print(Dbnode *head);
//根据数据创建节点
Dbnode *CreateNode(int data){
	Dbnode *pnode=new Dbnode;//
	if (pnode==NULL){ //如果内存申请失败，返回NULL
		return NULL;
	}
	pnode->data=data;
	pnode->left=pnode;//新节点的前驱和后继指针都指向自身
	pnode->right=pnode;
	return pnode;
}

//建立有向循环链表，返回表头节点
void InsertNode(Dbnode **head,int data){
	if (head==NULL){
		return;
	}
	Dbnode *phead=*head;
	Dbnode *pnode=CreateNode(data);//创建一个新节点
	Dbnode *node=NULL;
	if (phead==NULL){ //如果链表为空
		phead=pnode;
	}
	else if (phead->data>data){ //如果比头节点值小，插入头节点前
		phead->left->right=pnode;
		pnode->left=phead->left;
		pnode->right=phead;
		phead->left=pnode;
		phead=pnode;
	}else{ //如果值大于等于头节点，插入头节点后面
		node=phead;
		phead=phead->right;
		while (*head!=phead && phead->data < data){
			phead=phead->right;
		}
		phead=phead->left;
		phead->right->left=pnode;//有链接
		pnode->right=phead->right;
		phead->right=pnode;//左链接
		pnode->left=phead;
		phead=node;
	}
	*head=phead;//二维指针指向操作后的链表
}
//打印双向循环链表
void Print(Dbnode *head){
	if (NULL==head){ //head为NULL表示为空链表
		getchar();
		return;
	}
	cout<<head->data<<" "; //先打印出表头
	Dbnode *p=head->right;
	while (head!=p){ //依次遍历，直到到达表尾
		cout<<p->data<<" ";
		p=p->right;
	}
	cout<<endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	Dbnode *pA=NULL;
	InsertNode(&pA,32);
	InsertNode(&pA,16);
	InsertNode(&pA,12);
	InsertNode(&pA,3);
	InsertNode(&pA,40);
	InsertNode(&pA,60);
	InsertNode(&pA,13);
	Print(pA);
    system("pause");
	delete [] pA;
	return 0;
}