//***********************************
//**      鏈表各種操作回顧     **  
//***********************************

#include <iostream.h>

//------------------------------------------------------------------------------
//***define eare***

//------------------------------------------------------------------------------
//***varible eare***
struct Student
{
 long number;
 float score;
 Student *next;
};

Student *head;//鏈首指針

//------------------------------------------------------------------------------
//***function pro.***
Student *Create(void);     //創建鏈表
void ShowList(Student *head);   //打印鏈表

Student *Delete(Student *head,long number);      //刪除鏈表中某結點
Student *Insert(Student *head,Student *add_node); //插入鏈表結點

//------------------------------------------------------------------------------
//***main code***
void main(void)
{
 Student *phead;
 //long del_node;
 Student add_node;
 //先創建并顯示init的鏈表
 
 phead=Create();
 ShowList(phead);
 
 //刪除鏈表指點結點并顯示modify的鏈表
 /*cout<<"Do you want to delete which node? please input the number:";
 cin>>del_node;
 phead=Delete(phead,del_node);
 ShowList(phead);*/

 //插入鏈表結點并顯示modify的鏈表
 cout<<"please input number&score :"<<endl;
 cin>>add_node.number>>add_node.score;

 phead=Insert(phead,&add_node);
 ShowList(phead);
}

//------------------------------------------------------------------------------
//function: Create() 創建鏈表
//input: void
//output:
//return: Student *
//other: fzh 2006-1-19
//------------------------------------------------------------------------------
Student *Create(void)
{
 Student *pN;    //創建鏈表結點的指針
 Student *pEnd;    //鏈尾指針，用于其后插入結點指針
 pN=new Student;    //新建一個結點，準備插入鏈表
 cout<<"please input numer and score:\n";
 cin>>pN->number>>pN->score; //給結點賦值
 head=NULL;     //一開始鏈表為空
 pEnd=pN;

 while(pN->number !=0)
 {
  if(head==NULL)
   head=pN;
  else
   pEnd->next=pN;

  pEnd=pN;    //N點處
  pN=new Student;
  cout<<"please input numer and score:\n";
  cin>>pN->number>>pN->score;
 }
 pEnd->next =NULL;
 delete pN;
 return (head);
}

//------------------------------------------------------------------------------
//function: ShowList() 顯示鏈表
//input: void
//output:
//return: Student *
//other: fzh 2006-1-19
//------------------------------------------------------------------------------

void ShowList(Student *head)
{
 cout<<"*******now the items of list is***********\n";
 while(head)
 {
  cout<<head->number<<","<<head->score <<endl;
  head=head->next;
 }

}

//------------------------------------------------------------------------------
//function: Delete() 刪除鏈表指點結點
//input: void
//output:
//return: Student *
//other: fzh 2006-1-19
//------------------------------------------------------------------------------
Student *Delete(Student *head,long number)
{
 Student *p;
 Student *pFind;        //"哨兵"指針
 if(!head)
 {
  cout<<"\n the link table is Null!";
  return NULL;
 }
 //情況1：要刪除的結點是鏈首
 if(head->number==number)
 {
  p=head;
  head=head->next;
  delete p;
  cout<<number<<"the head of list have been deleted"<<endl;
  return (head);
 }

 //情況2：要刪除的結點在中間或鏈尾
 for(pFind=head;pFind->next;pFind=pFind->next)/////***
 {
  if(pFind->next->number==number)
  {
   p=pFind->next;//待刪除的結點
   pFind->next=p->next;
   delete p;
   cout<<number<<" have been deleted!"<<endl;
   
   return (head);
  }
 }

 //沒有這個結點
 cout<<" \n no the node ^Q^ "<<endl;
 return NULL;
}

//------------------------------------------------------------------------------
//function: Insert() 插入鏈表結點
//input: void
//output:
//return: Student *
//other: 1.fzh 2006-1-19
// 2.插入要求：創建鏈表時，結點的number是按小到大順序排列的。
//插入后順序一至
//------------------------------------------------------------------------------
Student *Insert(Student *head,Student *add_node)
{
 Student *pFind;        //"哨兵"指針

 //情況1：空鏈表
 if(!head)//(head==NULL)   空鏈表時，將結點置于鏈首
 {
  head=add_node;   //鏈首
  add_node->next=NULL; //鏈尾 
  return head;
 }
 //情況2：插到鏈首
 if(head->number > add_node->number)
 {
  add_node->next=head;
  head=add_node;
  return head;

 }
 //情況3：正常情況
 for(pFind=head;pFind;pFind=pFind->next)/////
 {
  if(pFind->next->number > add_node->number)//找到插入位置
  {
   add_node->next=pFind->next;
   pFind->next=add_node;
   return head;
  }
 }
 return NULL;
}