数据结构与算法之五 链接列表

/*
创建链表，通过使用节点类来创建
*/
using System;
class Node
{
  public int  data;   //data用来存放节点的数据
  public Node   next;   //next(节点对象)用来存放下一个节点的地址
}
class CreateList
{
  private Node start;   //头指针存放第一个节点的地址.
  private Node current; //定义个当前节点对象，用来遍历链表.
  private Node previous;  //前驱节点.
  public CreateList()
  {
    start=null;         //当初始化类时，设置头指针为空  
  }   
  /*优化的创建链表的方法*/
  public void create2()
  {
    previous=current=start=null;    //最开始的时候都为空，就是链表为一个空链表.
    Console.Write("请输入您要创建链表的个数：");
    int k=Convert.ToInt32(Console.ReadLine());
    for(int i=0;i<k;i++)
    {
      Console.Write("请输入您要插入的第"+(i+1).ToString()+"节点数据:");  
      current=new Node();
      current.data=Convert.ToInt32(Console.ReadLine()); 
        if(start==null)
          start=current;
        else
          previous.next=current;
        previous=current;       
    }
  }
  public void create()    //创建链表的方法:笨蛋方法（最为朴素的方法)
  {   Node first=null;
    if(start==null)
    {
      first=new Node(); //1.分配内存  
      Console.Write("请输入第一个节点值:");  
      first.data=Convert.ToInt32(Console.ReadLine());       //2.设定数据域里面的数据为2
      first.next=null;   //3.设定地址域里面的地址为null
      start=first;      //4.建链接
      current=first;    //当前节点为第一个节点.
    }
    //------------------添加质数为3的节点
    Node second=new Node();   //1。分配内存
    Console.Write("请输入第二个节点值");
    second.data=Convert.ToInt32(Console.ReadLine());            //2.设数据
    second.next=null;         //3.设地址
    first.next=second;        //4.将第一个节点指向第二个节点 
    //---------------------
    Node third=new Node();    //1。分配内存
    Console.Write("请输入第3个节点值");
    third.data=Convert.ToInt32(Console.ReadLine());           //2.设数据
    third.next=null;          //3.设地址
    second.next=third;        //4.将第2个节点指向第3个节点 
    //---------------------------
    Node fourth=new Node();   //1。分配内存
    Console.Write("请输入第4个节点值");
    fourth.data=Convert.ToInt32(Console.ReadLine());            //2.设数据
    fourth.next=null;         //3.设地址
    third.next=fourth;        //4.将第3个节点指向第4个节点
    //-------------------------
    Node fifth=new Node();    //1。分配内存
    Console.Write("请输入第5个节点值");
    fifth.data=Convert.ToInt32(Console.ReadLine());           //2.设数据
    fifth.next=null;          //3.设地址
    fourth.next=fifth;        //4.将第4个节点指向第5个节点     
  }//创建结束
  public void scan()    //遍历链表的方法
  {
    current=start;    //从头指针开始
    int i=1;
    while(current!=null)
    {
        Console.WriteLine("第"+i+"个节点数据为："+current.data);
        current=current.next;   //将当前节点的下一个节点的地址给current,以便current去访问下一个节点.
        i++;
    }
  }
  //插入新节点
  public void insert()
  {
    Console.WriteLine("请输入您要插入的新节点数据");
    int i=Convert.ToInt32(Console.ReadLine());
    Node newnode=new Node();
    newnode.data=i;
    /*判断新节点是否为空，并且链表当中没有该节点:在头节点之前插入*/  
    if((start==null)||(i<=start.data))
    {
      if((start!=null)&&(i==start.data))  
      {
        Console.WriteLine("\n重复节点不允许");
        return; 
      }
      newnode.next=start;
      start=newnode;
      return;
    }
    /*在列表中间插入*/
    previous=current=start; //设置为开始头节点
    while((current!=null)&&(i>=current.data))
    {
      if(i==current.data)
      {
        Console.WriteLine("\n重复数据不允许");
        return; 
      } 
      previous=current;
      current=current.next;
    }
    /*找到前驱节点和后继节点之后*/
    newnode.next=current;
    previous.next=newnode;
  }
  //搜索链表元素
  public void search()
  {
    Console.WriteLine("请输入您要查找的数据:");
    int i=Convert.ToInt32(Console.ReadLine());  //1.定义一个要搜索的数字
    Node current=start; //2.定义当前节点对象current
    while((current!=null)&&(current.data!=i)) //3.如果当前节点不为空，并且当前节点数据不等于你输入的数据，则循环.
    {       
        current=current.next;
    }
    //4。判断是找到了还是没有找到
    if(current==null)
      Console.WriteLine("没有找到");
    else             
      Console.WriteLine("已经找到了您输入的数据");   
  }
  //删除链表元素
  public void delete()
  {
    Console.WriteLine("请输入您要删除的元素");
    int i=Convert.ToInt32(Console.ReadLine());
    previous=current=start;   //设定当前节点为头指针指向的节点.
    if(start==null)
    {
      Console.WriteLine("吃饱了撑的，开始乱删了，滚！XXXXXXXX");  
    }else if(current.data==i)
    {
        start=current.next;
        current.next=null;  //书上忽略了,由系统自动回收不用的内存.
    }else   //否则，有多个节点，要删除我们指定的节点.
    {
        while((current!=null)&&(current.data!=i))
        {//要找下一个符合条件的节点
          previous=current;   //在找符合要求的节点之前，将原来节点的地址给previous
          current=current.next; //当前节点指向下一个节点.
        }
        if(current==null)
          Console.WriteLine("没有找到!");
        else
          previous.next=current.next;   //将要删除的节点的后继节点地址给前驱节点的next.
    }
  }
  /*
  1.定义要删除节点的前驱节点对象：previous;要删除节点：current
  2.previous和current都指向start
  3.遍历链表，以便找到要删除的节点.到底什么时候遍历链表呢？
  while(current!=null)并且(current.data!=17)
  {
      previous=current;
      current=current.next; // 要查找下一个节点，同时，前驱节点指向刚才的current节点.
  }
  如果current==空:null
    说明没有找到
  else  
    找到了则： previous.next=current.next;
  */
  public static void Main(string[]args)
  {
    CreateList list=new CreateList();
    //list.create2(); //创建链表  
    list.scan();
    list.insert();
    list.delete();
    list.scan();
    //list.search();
  }
}

/*
针对链表为空的时候进行插入一个节点的实现;
链表的实现通过节点类来实现.
*/
using System;
class Node  //定义一个节点类
{
  public int data;    //数据
  public Node next;   //next:存放下一个节点的地址.  
}
//定义实现对节点操作的类
class LinkedListInsert
{
  //定义一个头指针的属性
  private Node Start;
  private Node current; //当前节点.
  //定义构造方法
  public LinkedListInsert()
  {
    Start=null; 
  }
  //定义一个静态插入方法
  public void insert()
  { //直接赋值 
    if(Start==null)
    {
        //1.第一步是给新的节点分配内存
        Node first= new Node();  //分3步画图，记到本上.
        //2.设置新节点的数据为2
        first.data=2;
        //3.将新节点（即质数为2的节点）的地址给头指针,即头指针指向质数为2的节点
        Start=first;
        //4.设置fist的下一个节点为空(null)
        first.next=null;  
        //----------------------下面所实现的就应该再插入一个节点的情况;仍然按照插入第一个节点的情况步骤来做，不同点注意将新的点地址给谁了？     
        Node second=new Node();
        second.data=3;
        first.next =second;   //将质数3的节点放到第一个节点地址域
        second.next=null;
        //-----------------------质数为5的节点
        Node third=new Node();
        third.data=5;
        second.next=third;
        third.next=null;
    }
  }
  //浏览节点方法
  public void scan()  
  {
    //需要判断，如果节点不为空，则输出节点的数据域里的内容
    current=Start;
    int i=0;
    while(current!=null)
    {
      Console.WriteLine("第{0}节点的数据为：{1}",i+1,current.data);
      current=current.next;
      i++;
    }
  }
  public static void Main(string[]args)
  {
      LinkedListInsert list=new LinkedListInsert();
      list.insert();
      list.scan();
  }
}