shuangxianglianbiao.cpp

该程序为双向链表

		CurrentNode->PreviousNode = TempNode->PreviousNode ;
		TEmpNode = TempNode->PreviousNode ;
		TEmpNode->NextNode = CurrentNode ;
		cout<<TempNode->Data;
		delete TempNode;
		}
	cout<<"\n Status : Mission SuccessFull ."
		<<"\n Node Removed From Middle SuccessFully . "
		<<"\n Press Any Key To Continue . ";
	getch();
	return true;
}
/**********************************************************************/
//删除链表尾节点
template< class NodeType >
bool DoubleLinkList< NodeType >::RemoveFromRear()
{
	cout<<"\n Operation : Removal Of A Node From Rear Of A Double Linked List .\n";
	if( IsEmpty() )
		{
		cout<<"\n Invalid Operation ."
			<<"\n Status : Mission Failed . "
			<<"\n Press Any Key To Continue . ";
		getch();

		return false;
		}
	else
		{
		Node< NodeType > *TempNode = RearNode;
		if( FirstNode == RearNode )
			FirstNode = RearNode = NULL;
		else
			RearNode = RearNode->PreviousNode;
		RearNode->NextNode = NULL;
		cout<<TempNode->Data;
		delete TempNode;
		cout<<"\n Status : Mission SuccessFull ."
			<<"\n Node Removed From Rear Of The Double Linked List Successfully  .";
		return true;
		}
		cout<<"\n Press Any Key To Continue . ";
		getch();
}
/**********************************************************************/
//从链表FirstNode开始遍历
template< class NodeType >
void DoubleLinkList< NodeType >::TraverseForward()
{
	Node< NodeType > *CurrentNode = FirstNode ;
	cout<<"\n Mission : Traversing & Printing A Double Linked List ."
		<<"\n           In Forward Direction ."
		<<"\n The Double Linked List Follows : \n";
	while ( CurrentNode != NULL)
		{
		cout<<CurrentNode->Data<<" , ";
		CurrentNode = CurrentNode->NextNode;
		}
	cout<<"\n Status : Operation Successfull ."
		<<"\n Traversed & Printed Double Linked List Successfully . "
		<<"\n Press Any Key To Continue .";
	getch();
}
/**********************************************************************/
//从链表RearNode开始遍历
template< class NodeType >
void DoubleLinkList< NodeType >::TraverseBackwards()
{
	Node< NodeType > *CurrentNode = RearNode ;
	cout<<"\n Mission : Traversing & Printing A Double Linked List ."
		<<"\n           In Backward Direction "
		<<"\n The Double Linked List Follows : \n";
	while ( CurrentNode != NULL)
		{
		cout<<CurrentNode->Data<<" , ";
		CurrentNode = CurrentNode->PreviousNode;
		}
	cout<<"\n Status : Operation Successfull ."
		<<"\n Traversed & Printed Double Linked List Successfully . "
		<<"\n Press Any Key To Continue .";
	getch();
}
/**********************************************************************/
//链表长度
template< class NodeType >
int DoubleLinkList< NodeType >::LenghtOfDoubleLinkList()
{
	int NosOfNodes = 0 ;
	Node< NodeType > *CurrentNode = FirstNode ;
cout<<"\n Mission : Traverse & Calculate The Number Of Nodes In A Double Linked List ."<<"\n The Double Linked List Follows : \n";
	while ( CurrentNode != NULL)
		{
		NosOfNodes++;
		CurrentNode = CurrentNode->NextNode;
		}
	cout<<"\n Status : Operation Successfull ."
<<"\n Traversed & Calculated Number Of Nodes In A Double Linked List Successfully . "<<"\n Press Any Key To Continue .";
	getch();
	return NosOfNodes;
}
/**********************************************************************/
//查找链表，若查找项在链表中，输出"Item is found in the list."
template< class NodeType>
void DoubleLinkList< NodeType >::Search(NodeType &SearchItem)
{
	Node< NodeType > *CurrentNode;
	if(FirstNode==NULL)
	{
		cout<<"不能查找."<<endl;
		getch();
	}
	else
	{
		CurrentNode=FirstNode;
		while(CurrentNode!=NULL)
		{
			if(CurrentNode->Data==SearchItem)
				cout<<"Item is Found in the List."<<endl;
			else
			{
				CurrentNode=CurrentNode->NextNode;
			}
		}
		if(CurrentNode==NULL)cout<<"Item is not found in the List."<<endl;
		getch();
	}
}
/**********************************************************************/
//删除节点。此操作从双向链表中删除给定的元素（若存在）
//1链表为空2要删除的是链表的第一个节点3要删除的元素在链表中的某个地方4要删除的元素不在链表中
template< class NodeType >
void DoubleLinkList< NodeType >::deleteNode(NodeType &deleteItem)
{
	Node< NodeType > *CurrentNode;
	Node< NodeType > *trailCurrentNode;//pointer just before CurrentNode
	if(FirstNode==NULL)
	{
		cout<<"cannot delete from an empty list."<<endl;
		getch();
	}
	else
	{
		if(FirstNode->Data==deleteItem)//删除第一个节点
		{
			CurrentNode=FirstNode;
			FirstNode=FirstNode->NextNode;
			if(FirstNode!=NULL)
				FirstNode->PreviousNode=NULL;
			delete CurrentNode;
		}
		else
		{
			CurrentNode=FirstNode;
			while(CurrentNode!=NULL&&CurrentNode->Data!=deleteItem)//查找节点
			{
				CurrentNode=CurrentNode->NextNode;
			}
			if(CurrentNode==NULL)
				cout<<"要删除的节点不在链表中."<<endl;
			else
			{
				trailCurrentNode=CurrentNode->PreviousNode;
				trailCurrentNode->NextNode=CurrentNode->NextNode;
				CurrentNode->NextNode->PreviousNode=trailCurrentNode;
				delete CurrentNode;
			}
		}
		getch();
	}
}
/**********************************************************************/
//排序，由大到小
template< class NodeType >
void DoubleLinkList< NodeType >::Sort()
{
	NodeType data;
	Node< NodeType > *CurrentNode;
	Node< NodeType > *trailCurrentNode;
	CurrentNode=FirstNode;
	trailCurrentNode=FirstNode;
	for(;trailCurrentNode!=NULL;trailCurrentNode=trailCurrentNode->NextNode)
	{
		while(CurrentNode!=NULL)
		{
			if(CurrentNode->Data<trailCurrentNode->Data)
			{
				data=trailCurrentNode->Data;
				trailCurrentNode->Data=CurrentNode->Data;
				CurrentNode->Data=data;
			}
			else
			{
				CurrentNode=CurrentNode->NextNode;
			}
		}
		CurrentNode=FirstNode;
	}
	getch();
}
/**********************************************************************/
//根据顺序增加节点,由大到小
template< class NodeType >
void DoubleLinkList< NodeType >::InsertNode( NodeType &InsertItem )
{
	Node< NodeType > *NewNode=CreateNode(InsertItem);
	Node< NodeType > *CurrentNode;
	Node< NodeType > *trailCurrentNode;
	if(FirstNode==NULL)
	{
		FirstNode=RearNode=NewNode;
		getch();
	}
	else
	{
		CurrentNode=FirstNode;
		if(FirstNode->Data<InsertItem)//插入链首
		{
			FirstNode->PreviousNode=NewNode;
			NewNode->NextNode=FirstNode;
			FirstNode=NewNode;
			FirstNode->PreviousNode=NULL;
		}
		else
		{
			while(CurrentNode!=NULL)//查找插入点
			{
				if(CurrentNode->Data<InsertItem)
				{
					trailCurrentNode=CurrentNode->PreviousNode;
					CurrentNode->PreviousNode=NewNode;
					NewNode->NextNode=CurrentNode;
					NewNode->PreviousNode=trailCurrentNode;
					trailCurrentNode->NextNode=NewNode;
				}
				else
				{
					CurrentNode=CurrentNode->NextNode;
				}
			}
		}
		if(CurrentNode->Data>InsertItem)
		{
			NewNode->PreviousNode=RearNode;//插入链尾
			RearNode->NextNode=NewNode;
			RearNode=NewNode;
			RearNode->NextNode=NULL;
		}
		getch();
	}
}
/**********************************************************************/
// 根据用户选择调用不同功能
void List::handle_choice(int choice) //	根据用户选择（choice）调用对应处函数
 {
  switch(choice) // 处理选择
   {
  case 1:
	  display_list();
	  break;
    case 2:  // 若选择添加记录，
     add_record();// 调用添加记录的功能模块，
	 paixuoflist();
     break;        
  	case 3:  // 若选择在记录里查找，
     lenghtoflist(); // 调用按姓查找的模块
     cout<<"现在存在的联系人有"<<ptr_num<<"个\n\n\n\n";
     break;                
    case 4:  // 若选择删除记录，
     system("cls");
	 delete_record(); // 调用按全名查找后删除记录的模块
     break;	 
	case 5:
	search_by_fullname();
	break;
	case 6:  //若选择修改记录，
	 modify_record();system("cls"); //调用修改记录的功能模块
	 break;
	case 7:  // 若选择退出,
     write_list_to_file();  // 保存记录
     if(head_ptr != NULL)   // 删除链表
      { 
       delete_list(); 
      }
     break;
    default : // 若选择了菜单中不存在的条目,
     cout <<"无效选择！\n"; // 显示出错信息.
     break;
   }
 } // handle_choice的结束
/*********************************************************************/
// 添加记录的功能模块.
void List::add_record()    // 在链表中增加一个记录
 {
  friend_node *new_rec_ptr; // 定义一个friend_node类的指针.
  new_rec_ptr = new friend_node; //  用new为新建指针动态分配空间.
                         
  if(new_rec_ptr != NULL) // 若分配成功，则输入数据并将其插入链表
   {  system("cls");                    
    // 由用户输入姓名及电话号码.
    cin.ignore(20,'\n');
    cout << "姓名: ";
    cin.get(new_rec_ptr->full_name,15);
    cin.ignore(20,'\n');
	cout << "年龄: ";
    cin.get(new_rec_ptr->age_num,20);
    cin.ignore(20,'\n');
    cout << "电话号码: ";
    cin.get(new_rec_ptr->phone_num,15);
    cin.ignore(20,'\n');
    insert_node(new_rec_ptr);
   }	
  else  // 若插入链表时发生内部错误，显示出错警告
   {    
    cout << "警告！: 系统出错！记录将无法保存！.\n";
   }system("cls");
 } //  add_record的结束
/*********************************************************************/
// 将结点插入链表的功能模块.
void List::insert_node(friend_node *new_rec_ptr) 
//将一个由new_rec_ptr 指向的新节点插入链表中
 {
system("cls");
  friend_node *before_ptr;
  friend_node *after_ptr;
  if(head_ptr == NULL)
   {                             // 若链表首结点为空，将新结点设为
    new_rec_ptr->prev=new_rec_ptr->next = NULL;    //首结点 
    head_ptr = new_rec_ptr;
   }
  else
   {
    if(strcmp(new_rec_ptr->full_name, head_ptr->full_name) < 0)
     {                                  // 若新结点应排在首结点之前,
     make_node_new_head(new_rec_ptr);  // 将新结点设为首结点.
     }
    else                             // 若都不是，判断新结点
	{                                //  应插入的位置
      current_ptr = position_insertion_point(new_rec_ptr->full_name);
      before_ptr = current_ptr;      // 用指针保存应插入处结点两边的位置
      after_ptr = current_ptr->next; // 两边的位置
      if(after_ptr == NULL) // 若after_ptr为空, 将新结点设为尾结点
       {                    
        add_node_to_end(new_rec_ptr);
       }
      else                  // 若不是则将新结点插入
       {                    //  before_ptr和after_ptr之间.
        before_ptr->next = new_rec_ptr;
        new_rec_ptr->next = after_ptr;
        new_rec_ptr->prev=current_ptr;
		after_ptr->prev=new_rec_ptr;
       }
     }
    }
 } // insert_node的结束
/*********************************************************************/
// 判定新结点的插入位置并使current_ptr指向它
friend_node * List::position_insertion_point(char fullname[20])
 {       // 根据姓氏，返回其在链表中的正确位置。新节点即将插入此点。
  char temp_name[20];
  friend_node *temp_ptr;
  int tempint;
  if(head_ptr->next!= NULL) //若链表上存在不止一个结点，则沿
   {                        //链表找出正确的插入位置
    current_ptr = head_ptr;
    temp_ptr = current_ptr->next;
    strcpy(temp_name, temp_ptr->full_name);
    //循环找到正确的插入位置.
    tempint = strcmp(fullname,temp_name);
    while((tempint > 0) && (current_ptr->next !=NULL))
     {
      current_ptr = temp_ptr;
	  // 检查当前结点是否为首结点
	  if(current_ptr->next != NULL)
	  {
       temp_ptr = current_ptr->next;
       strcpy(temp_name, temp_ptr->full_name);
       tempint = strcmp(fullname,temp_name);
	  }
     }
   }