数据结构之链表

//Linklist.h
  typedef struct Node{
      int data;    //数据域
      struct Node * next;  //指针域
  }ListNode , * Linklist;   //ListNode 结点类型,Linklist 指向结点的指针类型

/*Linklist h; 定义头指针*/ /*ListNode *p; 定义指向某结点的指针,两者类型相同*/

单链表

• 1.初始化空表，建立头结点
  Linklist initll(){
  Linklist h;
  h = (Linklist)malloc(sizeof(ListNode));
  if(h!=NULL)
  h->next = NULL;
  else
  printf("分配空间失败！\n");
  return h;
  }

• 2.建立单链表
  int Inpll(Linklist h,int n){ //形参：头指针，结点个数

        ListNode *p,*tail;
        int i;
  
        tail = h;
  
        for(i=0;i<n;i++)
        {
          p=(ListNode * )malloc(sizeof(ListNode));
          scanf("%d",&(p->data));   
          p->next = NULL;
  
          tail -> next = p;
          tail = p;    //tail 永远抓住最后一个结点
        }
  
        return 1;
    }
  

• 3.往非递减有序的单链表中插入一个结点后，链表仍有序
  void Insll(Linklist h,int x){
  ListNode p,q,*temp;

        q =(Linklist)malloc(sizeof(ListNode));  
        q->data=x;
    
        if(h->next==NULL)  //原链表为空
        {
            h->next=q;
            q->next=NULL;
            return;
        }
  
        for(p=h->next,temp=h;p!=NULL;temp=p,p=p->next)
        {   
            if(p->data>=x){         
                q->next = p;  //q的指针域指向当前结点
                temp->next = q;  //前一个结点的指针域指向q
                break;
            }
            else if(p->next==NULL)  //x比原链表中所有结点的值都大,需把q放在最后
            {  
            p->next=q;
              q->next=NULL;
              break;
            }
        }
        
    }
  

• 4.遍历单链表
  int trall(Linklist h){
  ListNode * p;

          if(h->next==NULL)  //空表不遍历
            return 0;
  
          for(p=h->next;p!=NULL;p=p->next){
              printf("%d\t",p->data);
          }
          printf("\n");
          return 1;
    }
  

单循环链表

  ***  特点：最后一个结点的指针域永远指向头结点 ***

• 1.建立带头结点的单循环链表

    int ReInpll(Linklist h,int n){  
         ListNode *p,*tail;
         int i;
  
         /*h->next=NULL;       //不带头结点创建单循环链表
         scanf("%d",&(h->data));*/
        
         tail = h;   
         for(i=0;i<n;i++)
        {
          p=(ListNode * )malloc(sizeof(ListNode));
          scanf("%d",&(p->data));   
          p->next = NULL;
          tail -> next = p;
          tail = p;  //tail 永远抓住最后一个结点
        }
        p->next=h;  //最后一个结点的指针域指向头指针
        return 1;
    }
  

• 2.删除单循环链表中所有值为x的元素
  void DelX_LL( Linklist h, int x){
  ListNode p,q;
  q=h;

        for(p=q->next;p!=h;p=q->next){  
            if(p->data==x){
            q->next=p->next;
            free(p);        //回收被删除的结点      
            continue;  //不再执行下面的语句
             }
            q=q->next;
        }       
    }
  

• 3.遍历单循环链表
  int traRell(Linklist h){

      ListNode * p;
  
      if(h->next == h)  //空表不遍历
          return 0;
  
      for(p=h->next;p!=h;p=p->next){
          printf("%d\t",p->data);
      }
      printf("\n");
      return 1;
    }
  

单链表和单循环链表的区别

• 1.** 尾结点的指针域 **
  单链表的尾结点的指针域指向NULL；
  单循环链表的尾结点的指针域指向头结点。

• 2.** 判断链表为空的条件 **
  判断单链表（带头结点）是否为空,是判断头结点的指针域是否为空。

if(head->next==NULL)

 判断单循环链表（带头结点）是否为空,是判断头结点的指针域是否指向自身。

if(h->next == head)

• 3.** 循环的条件 **
  在算法中，
  单链表的循环条件是：

p != NULL; //p结点不为空

或者
> p->next != NULL; //p结点的指针域不为空

单循环链表的循环条件是：

p != head; //p结点不等于头指针