算法导论笔记：K路归并6.5-9

直接放代码，太烂了。

#include <stdio.h>
#include <stdlib.h>

typedef struct slist
{
    int val;
    struct slist* next;
} list_t;

list_t* makeList(int* base,int length);
list_t* makeNode(int data);
list_t* partition(list_t* start,list_t* end);
void quicksort(list_t* begin,list_t* end);
list_t* merge(list_t* heap[]);
void max_heapify(list_t* heap[],int start,int end);
list_t* heap_minimun(list_t* heap[]);
void print(list_t* fun) /*打印函数*/
{
    int i=1;
    while(fun!=NULL)
    {
        /*printf("%d:%d %p\n",i,current->a,current);*/
        printf("%d:%d \n",i,fun->val);
        fun=fun->next;
        i++;
        /*printf("%p",current);*/

    }
}
int main(void)
{
    int link_1[10]={10,63,9,5,4,7,8,91,10,2};
    int link_2[5]={21,13,6,9,23};
    int link_3[4]={12,13,17,1};
    list_t* head1=makeList(link_1,10);
    print(head1);
    list_t* head2=makeList(link_2,5);
    print(head2);
    list_t* head3=makeList(link_3,4);
    print(head3);
    list_t* heap[3]={head1,head2,head3};
    list_t* result=merge(heap);
    print(result);

    return 0;
}

void min_heapify(list_t* heap[],int start,int end)
{
    int dad=start;
    int son=2*dad+1;
    while(son<=end)
    {
        if(son+1<=end&&heap[son]->val>=heap[son+1]->val)
            son++;
        if(heap[dad]->val<=heap[son]->val)
            return;
        else
        {
            list_t* p=heap[dad];
            heap[dad]=heap[son];
            heap[son]=p;
        }
    }
}

list_t* heap_minimun(list_t* heap[])
{
    list_t* result=heap[0];
    heap[0]=heap[0]->next;
    if(heap[0]==NULL)
    {
        int i;
        for(i=1;i<3;i++)
        {
            if(heap[i]==NULL)
            {
                list_t* temp=heap[i-1];
                heap[i-1]=heap[0];
                heap[0]=temp;
                break;
            }
        }
        if(i==3)
        {
            list_t* temp=heap[i-1];
            heap[i-1]=heap[0];
            heap[0]=temp;
        }
    }
    return result;
}

list_t* merge(list_t* heap[])
{
    for(int i=3/2-1;i>=0;i--)
        min_heapify(heap,i,2);
    /*for(int i=0;i<3;i++)
    {
        printf("%d",heap[i]->val);
    }*/
    list_t* merge=NULL,*p=NULL;

    while(1)
    {
        /*for(int i=0;i<3;i++)
        {
            printf("%d\n",heap[i]->val);
        }*/
        if(merge==NULL)
        {
            merge=heap_minimun(heap);
            p=merge;
        }
        else
        {
            p->next=heap_minimun(heap);
            p=p->next;
        }
        if(heap[0]==NULL)
            break;
        for(int j=1;j<3;j++)
        {
            if(heap[j]==NULL)
            {
                min_heapify(heap,0,j-1);
                break;
            }
        }
        if(heap[2]!=NULL)
            min_heapify(heap,0,2);
    }
    /*  for(int j=0;j<3;j++)
        {
            if(heap[j]->next!=NULL)
            {
                heap[j]=heap[j]->next;
                min_heapify(heap,j,2);
                break;
            }
        }*/

    return merge;
}

list_t* Partition(list_t* head,list_t* end)
{
    if(head==NULL)
        return NULL;
    list_t*p=head,*q=head->next;
    int temp;
    while(q!=end)
    {
        if(q->val<head->val)
        {
            p=p->next;
            temp=p->val;
            p->val=q->val;
            q->val=temp;
        }
        q=q->next;
    }
    temp=head->val;
    head->val=p->val;
    p->val=temp;
    return p;
}

void quicksort(list_t* begin,list_t* end)
{
    if(begin!=end)
    {
        list_t* partition=Partition(begin,end);
        quicksort(begin,partition);
        quicksort(partition->next,end);
    }
}

list_t* makeList(int* base,int length)
{
    if(length==0)
        return NULL;
    list_t* head=NULL,*next=NULL,*new=NULL;
    for(int i=0;i<length;i++)
    {
        if(head==NULL)
        {
            head=makeNode(base[0]);
            next=head;
        }
        else
        {
            new=makeNode(base[i]);
            next->next=new;
            next=next->next;
        }
    }
    list_t* begin=head;
    quicksort(begin,new->next);
    return head;
}

list_t* makeNode(int data)
{
    list_t* p=(list_t*)malloc(sizeof(list_t));
    p->val=data;
    p->next=NULL;
    return p;
}