直接放代码,太烂了。
#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;
}