#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10

struct node
{
    int num;
    struct node *next;
};
struct stud
{
    char name[10];
    int num;
}sw[5],sr[5],*pw,*pr;

void selectsort(int *);
void bubblesort(int *);
void quicksort(int *,int,int);
void InsertSort(int *,int );
int BinSearch(int *,int,int,int);
struct node * creat(int);
void reverse(struct node *);
struct node *merge(struct node *,struct node*);
struct node * circle(int);
int select(struct node *,int ,int );
void WordCount(char str[]);


int main()
{
    int i,j;
    int a[10]={3,2,5,4,1,8,9,7,6,0};

    for(i=0;i<SIZE;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    //bubblesort(a);
    //selectsort(a);
    //quicksort(a,0,SIZE-1);
    InsertSort(a,SIZE);

    for(j=0;j<SIZE;j++)
    {
       printf("%d ",a[j]);
    }
    int x;
    printf("\nPlease input the number you want to find:");
    scanf("%d",&x);
    int pos=BinSearch(a,0,SIZE-1,x);
    printf("The position of %d is: %d\n",x,pos+1);


    //**************************

    struct node *cir;
    int c,king;
    printf("The total of circle:");
    scanf("%d",&c);
    cir=circle(c);
    king=select(cir,c,3);
    printf("The king is:%d\n",king);



    //**************************
    struct node *p,*q,*m;
    int n,mm;
    printf("Please input the total node you want:");
    scanf("%d",&n);
    p=creat(n);
    printf("Please input the total node you want:");
    scanf("%d",&mm);
    q=creat(mm);

    /*
    p=p->next;
    while(p)
    {
        printf("%d ",p->num);
        p=p->next;
    }*/
    //printf("\nafter reverse:\n");
    //q=creat(n);
    //reverse(p);
    m=merge(p,q);
    printf("\nafter reverse:\n");
    m=m->next;
    while(m)
    {
        printf("%d ",m->num);
        m=m->next;
    }
    /*
    p=p->next;
    while(p)
    {
        printf("%d ",p->num);
        p=p->next;
    }
    */

    //

    FILE *fp;
    if((fp=fopen("d:\\st.dat","wb+"))==NULL)
    {
        printf("Cannot open!\n");
        return ;
    }
    pw=sw;
    pr=sr;
    printf("Please input data:name num\n");
    for(i=0;i<5;i++)
    {
        scanf("%s%d",sw[i].name,&sw[i].num);
    }
    fwrite(pw,sizeof(struct stud),5,fp);
    rewind(fp);
    fread(pr,sizeof(struct stud),5,fp);
    for(i=0;i<5;i++)
        printf("%s %d",sw[i].name,sw[i].num);


    return 0;
}
void selectsort(int a[])
{
    int i,j,key,temp;
    for(i=0;i<SIZE-1;i++)
    {
        key=i;
        for(j=i+1;j<SIZE;j++)
        {
            if(a[key]>a[j])
                key=j;
        }
        if(key!=i)
        {
            temp=a[key];
            a[key]=a[i];
            a[i]=temp;
        }
    }
}

void bubblesort(int *a)
{
    int i,j,temp;
    for(i=0;i<SIZE-1;i++)
    {
        for(j=0;j<SIZE-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

void quicksort(int *a,int l,int r)
{
    int i=l,j=r,key=a[l];
    if(l>=r)
        return ;
    while(i<j)
    {
        while(i<j&&a[j]>=key)
            j--;
        a[i]=a[j];
        while(i<j&&a[i]<=key)
            i++;
        a[j]=a[i];
    }
    a[i]=key;
    quicksort(a,l,i-1);
    quicksort(a,i+1,r);
}

int BinSearch(int *a,int s,int t,int key)
{
    int low=s,high=t,mid;
    if(s<=t)
    {
        mid=(low+high)/2;
        if(a[mid]==key)
            return mid;
        else if(a[mid]>key)
            return BinSearch(a,low,mid-1,key);
        else
            return BinSearch(a,mid+1,high,key);
    }
    return -1;
}

struct node * creat(int n)
{
    int i;
    struct node *head,*p,*tail;
    head=(struct node *)malloc(sizeof(struct node));
    head->next=NULL;
    tail=head;
    for(i=0;i<n;i++)
    {
        p=(struct node *)malloc(sizeof(struct node));
        scanf("%d",&p->num);
        p->next=NULL;
        tail->next=p;
        tail=p;
    }
    return head;

}
void reverse(struct node *head)
{
    struct node *p,*q;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        q=(struct node *)malloc(sizeof(struct node));
        q->num=p->num;
        q->next=head->next;
        head->next=q;
        p=p->next;
    }
}

struct node *merge(struct node *head1,struct node *head2)
{
    struct node *h1,*h2,*tail;
    h1=head1->next;
    h2=head2->next;
    tail=head1;
    head2->next=NULL;
    while(h1&&h2)
    {
        if(h1->num<h2->num)
        {
            tail->next=h1;
            tail=h1;
            h1=h1->next;
        }
        else
        {
            tail->next=h2;
            tail=h2;
            h2=h2->next;
        }
    }
    if(h1)
        tail->next=h1;
    else
        tail->next=h2;
    return head1;
}

struct node * circle(int n)
{
    struct node *p,*head,*tail;
    int i;
    head=(struct node *)malloc(sizeof(struct node));
    tail=head;
    head->next=NULL;
    scanf("%d",&head->num);
    for(i=2;i<=n;i++)
    {
        p=(struct node *)malloc(sizeof(struct node));
        scanf("%d",&p->num);
        p->next=NULL;
        tail->next=p;
        tail=p;
    }
    p->next=head;
    return head;
}

int select(struct node *head,int n,int m)
{
    struct node *p,*q;
    int i=0,count=0;
    //p=head->next;
    q=head;
    while(q->next!=head)
        q=q->next;
    while(count<n-1)
    {
        i++;
        p=q->next;
        if(i%m==0)
        {
            printf("%3d ",p->num);
            q->next=p->next;
            count++;
        }
        else
            q=p;
    }
    printf("\n");
    return q->num;
}

void InsertSort(int a[],int length)
{
    int i,j,key;
    //length=strlen(a);
    for(i=1;i<length;i++)
    {
        key=a[i];
        for(j=i-1;j>=0;j--)
        {
            if(a[j]>key)
                a[j+1]=a[j];
            else
                break;
        }

        a[j+1]=key;
    }
}
void WordCount(char str[])
{
    int i,word=0,num=0;
    for(i=0;str[i]!=‘\0‘;i++)
    {
        if(str[i]==‘ ‘)
            word=0;
        else if(word==0)
        {
            num++;
            word=1;
        }
    }
    printf("Total Number:%d\n",num);

}