单链表快速排序和二分查找

快速排序：

#include<stdio.h>//单链表的快速排序。注意要右减在前，左增在后。时刻小心头节点。
#include<stdlib.h>
#include"linklist.c"
static Lnode *p=NULL;
void paixu(linklist l,int left,int right);
void main()
{
    int num[7]={23,34,45,56,76,78,89};
    int *p3=num;
    int length=sizeof(num)/sizeof(int);
 //  static Lnode *p=NULL;//全局变量和局部变量作用域也是个问题
    p=createEmptyList();
    if(p!=NULL)
    {
       insertfromhead(p,p3,length);
    }
    Lnode *p1=NULL;
    p1=p;
    Lnode *p4=NULL;
    p4=p->next;
    int count1=1,count2=0;
    while(p1->next!=NULL)
     {
        p1=p1->next;
        count2++;
     }  
    Lnode *p2=NULL;
    p2=p;
    p2=p2->next;
    paixu(p,count1,count2);
    p4=p->next;
while(p4->next!=NULL)
{
   printf("%d ",p4->value);
   p4=p4->next;

}



}
void paixu(linklist l,int left,int right)
{
 if(right>=left)
 return;
    int i=0;
    int j=0;
    int m=0;
    int n=0;
    int temp;
    int temp1;
    Lnode *p1=p->next;
    Lnode *p2=p1;
    for(;i<left;i++)
    {
        p1=p1->next;
    }   
    temp=p1->value;
    p1=p->next;
    for(;i<right;j++)
    {
        p2=p2->next;
    }
     m=left;
     n=right;
 while(m<n)
 {
     while(p1->value>=temp&&m<n)
     {
        n--;
        p2=p->next;
        for(j=0;j<n;j++)
          p2=p2->next;

     }
     while(p1->value<=temp&&m<n)
     {   
         m++;
         p1=p->next;
        for(i=0;i<m;i++)
            p1=p1->next;
     }
      if(m<n)
      {
         temp1=p1->value;
         p1->value=p2->value;
         p2->value=temp1;
      }

 }
   Lnode *p4=p->next;
  for(i=0;i<left;i++)
  p4=p4->next;
  p4->value=p1->value;
  p1->value=temp;
  paixu(p,left,m-1);
  paixu(p,m+1,right);

}

二分查找

#include<stdio.h>  //单链表二分查找  
#include<stdlib.h> // 千万千万注意p2->next，一到未知就会报错。很难找BUG。
#include"linklist.c"

void maopao(linklist l,size_t length);
int find(int a,linklist l,int left,int right);
int num[6]={23,34,45,56,35,67};
int length=sizeof(num)/sizeof(int);
int count=0;
void main()
{
   int b=45;
   Lnode *p=NULL;
   p=createEmptyList();
   int m=0;
   int n=length-1;    //这里为length，下面的p2->next会到未知而报错。
   if(p!=NULL)
   {
        insertAtTail(p,num,length);
    }
    maopao(p,length);
     find(b,p,m,n);

    if(find(b,p,m,n)!=0)
      printf("查找成功");
    else
      printf("failure");
}

void maopao(linklist l,size_t length)
{
    int i=0;
    int j=0;
    Lnode *p=NULL;
    Lnode *p1=NULL;
    Lnode *p2=NULL;
    p=l;
    p=p->next;
    p1=p;
    p2=p;
    int temp;
    for(i=0;i<length;i++)
    {
        p1=p;
        for(j=0;j<(length-i-1);j++)
        {
            p2=p1->next;
            if(p1->value>p2->value)
            {
                temp=p1->value;
                p1->value=p2->value;
                p2->value=temp;
            }
            p1=p1->next;
    //      printf("%d ",j);
        }
   }
   p1=p;
   for(i=0;i<length;i++)
   {
     printf("%d ",p1->value);
      p1=p1->next;
    }   
}

int find(int a,linklist l,int left,int right)
{   
  //  if(count==1)
//  return 0;
    int i=0;
    Lnode *p=NULL;
    Lnode *p1=NULL;
    Lnode *p2=NULL;
    Lnode *p3=NULL;
    p=l;
    p=p->next;
    printf("%d ",p->value);
    p3=p;
    if(right-left==1)
    {
     p1=p;
     p2=p;
     i=0;
     for(i=0;i<left;i++)
     p1=p1->next;
     for(i=0;i<right;i++)
     p2=p2->next;
     if(a==p1->value||a==p2->value)
     { 
        printf("%d ",left);
         return a;
     }   
      else
      {
         printf("%d %d %d %d",p1->value,left,p2->value,right);
         return 0;
      }  
     }
     p1=p;
     p2=p;
     i=0;
     for(i=0;i<left;i++)
     {
         p1=p1->next;
         printf("\n%d ",i);
     }       
     for(i=0;i<right;i++)
     {
         p2=p2->next;
         printf("\n%d ",i);
     }   
     printf("%d %d %d ",a,p1->value,p2->value);
     if((a<p1->value)||(a>p2->value))
     return 0;
     for(i=0;i<((right+left)/2+1);i++)
     p3=p3->next;
     if(p3->value>=a)
      {
      find(a,l,left,((right+left)/2+1));
        count++;
    }
    else
    {
        find(a,l,((right+left)/2+1),right);
        count++;
  
    }
    
}