//***********************************
//**      链表各种操作回顾     **  
//***********************************

#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;
}