数据结构实现－链表－循环链表.txt

包括数据结构中的常见的排序

#include <iostream>
using namespace std ;

class Node
{
public:
	int data ;
	Node *L_link ;
	Node *R_link ;
} ;

/*************************************************************************************************************************
** 函数：得到 末尾 结点
** 参数：header 的 地址
** 返回：末尾结点的地址
*************************************************************************************************************************/

Node* Get_Tail_Node(Node **header)					
{
	Node *recent = (*header) ;

	while (recent->R_link != (*header) )
		recent = recent->R_link ;

	return recent ;
}

int Get_Node_Count(Node **header)
{
	int count = 0 ;
	Node *recent = (*header)->R_link ;

	while (recent != (*header) )
	{
		++count ;
		recent = recent->R_link ;
	}

	return count ;
}

Node* Get_Certain_Node(Node **header, int no)
{
	if (no < 0 || no > Get_Node_Count(header) )	// 安全性检查
		return NULL ;

	if (no == 0)								// header的序号为0
		return (*header) ;

	int count = 0 ;	
	Node *recent = (*header)->R_link ;

	while (recent != (*header) )
	{
		++count ;
		if (count == no)
			return recent ;

		recent = recent->R_link ;
	}

	return NULL ;
}


/*************************************************************************************************************************
** 函数：在某一具体位置插入一结点，使之成为序号为no的结点
** 参数：header 的 地址
** 返回：要插入的序号
*************************************************************************************************************************/


void Insert_Node(Node **header, int no)
{
	if (no < 0 || no > Get_Node_Count(header)+1 )	// 安全性检查
		return ;


}

Node* List_Builder()
{
	/*----------创建表头指针-------------*/
	Node *header = new Node() ;
	header->L_link = header ;
	header->R_link = header ;

	while (true)
	{
		cout << "Another Node ? (Y/N) " ;
		char c = 0 ;
		cin >> c ;	cout << endl ;

		if (c != 'n' && c != 'N')
		{
			Node *temp = new Node() ;				// 分配空间

			cout << "Please Enter The Value : " ;	// 输入Value
			cin >> temp->data ;
			cout << endl ;

			Node *tail = Get_Tail_Node(&header) ;

			/****************把该结点插入链表尾部**********************/
			temp    ->  L_link = tail ;
			temp    ->  R_link = header ;
			header  ->  L_link = temp ;
			tail    ->  R_link = temp ;

		}
		else
			break ;
	}

	return header ;

}


/**************函数：打印链表*******************/

void List_Printer(Node **header)					
{

	cout << "----------L--------------------------------------R-------------->" << endl ;
	Node *recent = (*header)->R_link ;

	while (recent != (*header) )
	{
		cout << recent->data << "-->" ;
		recent = recent->R_link ;
		if (recent == (*header) )
			cout << "HEADER" ;
	}
	cout << endl << endl ;

	recent = (*header)->L_link ;

	cout << "----------R--------------------------------------L-------------->" << endl ;

	while (recent != (*header) )
	{
		cout << recent->data << "-->" ;
		recent = recent->L_link ;
		if (recent == (*header) )
			cout << "HEADER" ;
	}
	cout << endl << endl ;
}


int main()
{
	Node *header = List_Builder() ;

	List_Printer(&header) ;

	cout << "The number of nodes : " << Get_Node_Count(&header) << endl << endl ;

	for(int i=1; i<=Get_Node_Count(&header); i++)
	{
		Node *temp = Get_Certain_Node(&header, i) ;
		cout << i << " : " << temp->data << endl ;
	}

	return 0 ;
}



/********************************************************************************
*
* Notice : This Program Can Be Launched In VC6.0 Environment
*
********************************************************************************/