/*用结构体实现链表的创建、遍历、结点插入、结点删除 *//*本题中链表结点的输入必须是升序（可以相邻的相同），删除的时候也是把与要删除同数据的多个相同的结点都删除掉*/#include 
     
         using namespace std;       struct  node  //结点结构   { int data ;     node * next;   };        int n=0; //全局整型变量存放链表中结点个数   node * head ;  //全局指针变量存放链表头结点地址-头指针    int main()  { node * CreateList( );  //建立链表函数声明     void  PrintList( node *); //输出链表中结点信息函数声明     node * InsertNode(node *,node *); //在链表中插入结点函数声明     node * DeleteNode(node *,int); //在链表中删除结点函数声明      node * deleteAll(node *);//删除整个链表  bool isNULL(node *head); //判断链表是否为空链表    /*创建链表*/      head=CreateList( ); //调用链表创建函数，返回所建链表的头指针       /*遍历输出链表*/    PrintList(head);  //调用链表遍历函数，输出全部结点信息       /*往链表中插入结点*/      char IsGo;  //是否继续操作标志     cout<
      
       <<"是否进行链表结点插入操作?(插入结点请按y或Y,退出插入操作请按其它键)";    cin>>IsGo;    node *stu;       while(IsGo=='y'||IsGo=='Y')    {   stu=new node;    //创建要插入的新结点         cout<
       
        <<"输入要插入的新结点数据:";         cin>>stu->data;      //输入要插入的新结点数据           head=InsertNode(head,stu);    //调用插入函数，返回链表头指针          cout<<"是否继续插入新结点? (继续插入请按y或Y,退出请按其它键)";         cin>>IsGo;        }          /*遍历输出链表*/     PrintList(head);  //调用链表遍历函数，输出全部结点信息        /*删除链表结点*/     int del_num; //要删除的结点的数据      cout<
        
         <<"是否进行链表结点删除操作?(删除结点请按y或Y,退出删除操作请按其它键)";     cin>>IsGo;     while(IsGo=='y'||IsGo=='Y')     {         cout<
         
          <<"输入要删除的节点的数据:";  //输入要插入的结点          cin>>del_num;  //输入要删除的结点的数据             head=DeleteNode(head,del_num);    //删除后链表的头地址          cout<<"是否继续删除结点? (继续插入请按y或Y,退出请按其它键)";         cin>>IsGo;         }       /*遍历输出链表*/     PrintList(head);  //调用链表遍历函数，输出全部结点信息   /*删除整个链表*/    cout<
          
           <<"开始删除整个链表..."<
           
            > s->data ; //输入新结点数据 predata=s->data; head = NULL ; //头指针初始值为NULL if( s->data==0) //第一个结点数据就为0，建立一个空链表 { cout<<"您建立的空链表"<
            
             data != 0 ) //通过判断新结点数据来进行循环 { if ( head == NULL ) head = s ; //头指针赋值 else p->next = s ; //将新结点插入已有链表的最后 p = s ; // p指向链表中最后的结点 n=n+1; //结点个数增1 s = new node ; //动态建立一个新结点 cout<<"请输入一个整数值作为新结点的数据信息,输入0时建立链表结束"<
             
              > s->data ; //输入新结点数据 while(s->data
              
               data!=0) //因为题目要求升序输入数据，如果发现新结点的数据小于当前链表中的最后一个结点的数据，要求重新输入 { cout<<"重新输入新结点数据，保证链表中结点数据是升序！"<
               
                >s->data; } if(s->data == 0 ) //如果输入的新结点数据为0，则退出当前循环 break; predata=s->data; } p -> next = NULL ; //设置链表尾部为空 delete s ; //释放数据为0的结点 cout<
                
                 <<"链表建立完成..."; cout<<"建立的链表中共有"<
                 
                  <<"个节点"<
                  
                   <
                   
                    data<
                    
                     next; }while(p!=NULL) ; else { cout<<"链表是空链表!"<
                     
                      next=NULL; } else //原来的链表不是空表 { while((s->data>p->data) && (p->next!=NULL)) //用循环定位要插入的结点位置p，使s插入到p之前的位置 {q=p; //q记录下当前的p，即q指向p的前一个结点 p=p->next; //p后移一个结点 } if(s->data<=p->data) //要插入的结点数据比最后一个结点数据小 { if(head==p) //判断是否插入链表中的第一个结点之前 { head=s; //插到原来第一个结点之前 s->next=p; } else //插到q指向的结点之后，p指向的结点之前 { q->next=s; s->next=p; } } else //要插入的结点数据比最后一个结点数据还大 { p->next=s; // 插到链表最后的结点之后，作为链表的尾结点 s->next=NULL; } } n=n+1; //结点数加１ cout<<"成功完成一个新结点插入..."<
                      
                       data && p->next!=NULL) //p指向的不是所要找的结点且后面还有结点 { q=p; //q用来记录p前一个结点 p=p->next; } //p后移一个结点 if(delData==p->data) //找到了要删除的结点 { do { if(p==head) //如果要删除的是头结点 { head=p->next; //若p指向的是首结点，把第二个结点地址赋予head n=n-1; delete p; p=head; } else { q->next=p->next; //否则将下一结点地址赋给前一结点地址 n=n-1; delete p; //释放被删除结点空间 p=q->next; } }while(p!=NULL&&p->data==delData); //判断与被删除结点相邻的结点是否还是要被删除的结点 cout<<"成功删除数据为"<
                       
                        <<"的结点"<
                        
                         next; head=p; delete q; n=n-1; q=p; }while(p!=NULL); } return head;}bool isNULL(node *head) //判断链表是否为空链表{ if(head==NULL) return true; else return false;}