冒泡排序 选择排序 快速排序
//数据结构 描述数据的组织方式 往往什么样的数据结构 决定了使用什么样的算法

//链表
//单向链表

//所谓的指向 就是存储了人家的地址
typedef struct _Node
{
    int data;
    struct _Node * next;
}Node;//节点

Node * creatList();//创建
void insertList(Node *head ,int data);//插入
void travereList(Node * head);//遍历
int lenList(Node *head);//长度
Node *searchList(Node *head,int find);//查找
void deleteList(Node *head,Node *pfind);//删除
void popSortList(Node *head);//排序
void reverseList(Node *head);//逆置
void destroyList(Node *head);//销毁

//带有头节点的链表  创建空链表
Node * creatList()
{
    Node *head = (Node *)malloc(sizeof(Node));
    head->next =NULL;
    return head;
}
void insertList(Node *head ,int data)
{
    Node *cur = (Node *)malloc(sizeof(Node));
    cur->data = data;
    cur->next = head->next;
    head->next = cur;
}
void travereList(Node * head)
{
    head = head->next;
    while(head)
    {
        printf("%2d",head->data);
        head = head->next;
    }
}
int lenList(Node *head)
{
    int count = 0;
    head = head->next;
    while(head)
    {
        count++;
        head = head->next;
    }
    return count;
}
Node *searchList(Node *head,int find)
{
    head =head->next;
    while(head)
    {
        if(head->data == find)
            break;
        head = head->next;
    }
    return head;
}
void deleteList(Node *head,Node *pfind)
{
    while(head->next != pfind)
        head =head->next;
    head->next =pfind->next;
    free(pfind);
      //
      if(pfind->next ==NULL)
      {
        while(head->next != pfind)
            head =head->next;
        head->next =pfind->next;
        free(pfind);
    }
    else//换数据
    {
        pfind->data = pfind->next->data;
        Node * t = pfind->next;
        pfind->next = t->next;
        free(t);
    }

}
void popSortList(Node *head)
{
    //交换数据
    Node * p,*q;
    int len = lenList(head);
        for(int i = 0 ;i<len-1 ;i++)
    {
        p= head->next;
        q = p->next;
        for(int j=0;j<len-1-i;j++)
        {
            if(p->data >q->data)
            {
                //两者交换
                p->data ^= q->data;
                q->data ^= p->data;
                p->data ^= q->data;
            }
            p = p->next;
            q = p->next;
        }
    }
      //交换指针
            Node *p,*q,*pre;
      int len = lenList(head);
      for(int i = 0;i<len-1;i++)
     {
        pre = head;
            p = head->next;
            q = p->next;
            for(int j= 0;j<len-1-i;j++)
            {
                if(p->data >q->data)
                {
                 pre->next = q;
                     p->next = q->next;
                     q->next =p;
                     
                    pre =q;
                     q= p->next;
                    continue;
                }
                pre =pre->next;
                p = p->next;
                                q  = q->next;
            }
     }  
}
void reverseList(Node *head)
{
     Node *h = head->next;
     head->next = NULL;
     Node *t;
     while(h)
     {
        t=h->next;
        h->next = head->next;
        head->next = h;
        h=t;
     }
}
void destroyList(Node *head)
{
     Node *t;
     while(head)
    {
        t= head->next;
        free(head);
        head = t;
    }
}
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int main
{
      Node *head = createList();
      srand(time(NULL));
      for(int i =0; i<10;i++)
      {
           insertList(head,rand()%10);
      }
      traverList(head);
      int len = lenList(head);
      printf("\nlen = %d\n",len);
      Node*pfind = searchList(head,8);
      if(pfind != NULL)
      {
        printf("find in the list");
        deleteList(head,pfind);
        travereList(head);
      }
      printf("\nafter sort");
      popSortList(head);
      traverList(head);

      reverseList(head);
      traverList(head);

      destroyList(head);
      return 0;
}