Bağlantılı listeler kullanarak yığın sıralaması

Question

Kimsenin yığın sıralaması yapmak için bağlantı listelerini kullanıp kullanmadıklarını ve kodları sağlayıp sağlamadıklarını merak ettim. Ben diziler kullanarak heapsort yapmak mümkün olmuştur, ancak bağlantılı listelerinde yapmaya çalışıyorum pratik ve sadece bir ağrı nerede olduğunu biliyorum. Yapacağım bir proje için bağlantılı listeler uygulamak zorundayım, herhangi bir yardım büyük ölçüde takdir edilecektir. Ayrıca

Cevabın C

Answer 1

kullanıyorum "bağlantılı bir listede Yığın uygulamak istemiyoruz."

Heapsort, O(n log n) olduğu ve yerinde olduğu için iyi bir sıralama algoritmasıdır. Ancak, bağlantılı bir listeye sahip olduğunuzda, heapsort artık O(n log n) artık değildir, çünkü bağlantılı bir listede bulunmayan diziye rastgele erişime dayanır. Yani ya yerinizi özniteliğini kaybedersiniz (ancak ağaç benzeri bir yapı tanımlamanız gereken O(n) boşluğudur). Ya da onlar olmadan yapmalısınız, ancak üye araması için bağlantılı listenin O(n) olduğunu unutmayın. Çalışma zamanı karmaşıklığını, baloncuklardan daha kötü olan O(n^2 log n) gibi bir şeye getirir.

Bunun yerine mergesort kullanın. Zaten O(n) bellek ek yük gereksiniminiz var. Sağ 'yığın' tanımına karşısında sinek

Answer 2

//Heap Sort using Linked List 
//This is the raw one 
//This getRoot function will replace the root with number in the last node, after the main prints the largest number in the heap 
//The heapSort function will reconstruct the heap 
//addNode function is as same as in binary search tree 
//Note addNode and heapSort are recursive functions 
//You may wonder about the for loop used in main, this actually tells the depth of the tree (i.e log base2 N) 
//With this value these functions find where to trverse whether left or right(direction), with help of macro GETBIT (0-left,1-right) 


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

#define GETBIT(num,pos) (num >> pos & 1) 

struct node 
{ 
    int data; 
    struct node *left; 
    struct node *right; 
}; 
typedef struct node node; 

int nodes; 
node *first, *tmp, *current; 

void addNode(node *,node *,int); 
void swap(int *, int *); 
void getRoot(node *, int); 
void heapSort(node *); 

int main() 
{ 
    int num; 
    int cont,i,j; 

    while(1)            //It gets number from user if previous value is non zero number 
    { 
     printf("Enter a number\n"); 
     scanf("%d",&num); 
     if(!num)           //i'm using 0 as terminating condition to stop adding nodes 
      break;           //edit this as you wish 

     current = (node *)malloc(sizeof(node)); 
     if(current == 0) 
      return 0; 

     current->data = num; 
     nodes++; 

     for(i=nodes,j=-1; i; i >>= 1,j++); 

     if(first == 0) 
     { 
      first = current; 
      first->left = 0; 
      first->right = 0; 
     } 
     else 
      addNode(first,first,j-1); 

     printf("Need to add more\n"); 

    } 
    printf("Number of nodes added : %d\n",nodes); 

    while(nodes) 
    { 
     printf(" %d -> ",first->data);          //prints the largest number in the heap 

     for(i=nodes,j=-1; i; i >>= 1,j++);         //Updating the height of the tree 
     getRoot(first,j-1); 
     nodes--; 

     heapSort(first); 
    }  

    printf("\n\n"); 
    return 0; 
} 

void swap(int *a,int *b) 
{ 
    *a = *a + *b; 
    *b = *a - *b; 
    *a = *a - *b; 
} 

void addNode(node *tmp1,node *parent, int pos) 
{ 
    int dirxn = GETBIT(nodes,pos);         // 0 - go left, 1 - go right 

    if(!pos) 
    { 
     if(dirxn) 
      tmp1->right = current; 
     else 
      tmp1->left = current; 

     current->left = 0; 
     current->right = 0; 

     if(current->data > tmp1->data) 
      swap(&current->data, &tmp1->data); 
    } 

    else 
     if(dirxn) 
      addNode(tmp1->right,tmp1,pos-1); 
     else 
      addNode(tmp1->left,tmp1,pos-1); 

    if(tmp1->data > parent->data) 
     swap(&parent->data,&tmp1->data); 
} 

void getRoot(node *tmp,int pos) 
{ 
    int dirxn; 

    if(nodes == 1) 
     return ; 

    while(pos) 
    { 
     dirxn = GETBIT(nodes,pos); 

     if(dirxn) 
      tmp = tmp->right; 
     else 
      tmp = tmp->left; 
     pos--; 
    } 

    dirxn = GETBIT(nodes,pos); 

    if(dirxn) 
    { 
     first->data = tmp->right->data; 
     free(tmp->right); 
     tmp->right = 0; 
    } 
    else 
    { 
     first->data = tmp->left->data; 
     free(tmp->left); 
     tmp->left = 0; 
    } 
} 

void heapSort(node *tmp) 
{ 
    if(!tmp->right && !tmp->left) 
     return; 

    if(!tmp->right) 
    { 
     if(tmp->left->data > tmp->data) 
      swap(&tmp->left->data, &tmp->data); 
    } 
    else 
    { 
     if(tmp->right->data > tmp->left->data) 
     { 
      if(tmp->right->data > tmp->data) 
      { 
       swap(&tmp->right->data, &tmp->data); 
       heapSort(tmp->right); 
      } 
     }   
     else 
     { 
      if(tmp->left->data > tmp->data) 
      { 
       swap(&tmp->left->data, &tmp->data); 
       heapSort(tmp->left); 
      } 
     } 
    } 
} 

Answer 3

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

    typedef struct node 
    { 
      int data; 
      struct node *next; 
    }N; 

void maxheap(N **,int n,int i); 

void display(N **head) 
{ 
     N *temp1=*head; 
     while(temp1!=NULL) 
     { 
       printf("%d ",temp1->data); 
       temp1=temp1->next; 
     } 
} 

int main(int argc,char *argv[]) 
{ 
     N *head=NULL,*temp,*temp1; 
     int a,l,r,n,i; 
     n=0; 

     FILE *fp; 

     fp=fopen(argv[1],"r"); 


     while((a=fscanf(fp,"%d",&l))!=EOF) 
     { 
       temp=(N*)malloc(sizeof(N)); 
       temp->data=l; 
       temp->next=NULL; 

       if(head==NULL) 
       head=temp; 

       else 
       { 
         temp1=head; 
         while(temp1->next!=NULL) 
           temp1=temp1->next; 

         temp1->next=temp; 
       } 
       n++; 
     } 

     display(&head); 
     printf("\nAfter heapifying..\n"); 
     for(i=(n/2)-1;i>=0;i--) 
       maxheap(&head,n,i); 


     temp1=head; 
     while(temp1!=NULL) 
     { 
       printf("%d ",temp1->data); 
       temp1=temp1->next; 
     } 

     printf("\n"); 
} 

void maxheap(N **head,int n,int i) 
{ 
     int larg,l,r,tem,lar; 

     larg=i; 
     l=(2*i)+1; 
     r=(2*i)+2; 

     lar=larg; 
     N *temp=*head; 
     while(lar!=0 && lar<n) 
     { 
       temp=temp->next; 
       lar--; 
     } 

     N *temp1=*head; 
     lar=l; 
     while(lar!=0 && lar<=n) 
     { 
       temp1=temp1->next; 
       lar--; 
     } 


     if(l<n && temp->data<temp1->data) 
     { 
       larg=l; 
       lar=l; 
       temp=*head; 
       while(lar!=0 && lar<n) 
       { 
         temp=temp->next; 
         lar--; 
       } 
     } 

     lar=r; 
     temp1=*head; 
     while(lar!=0 && lar<n) 
     { 
       temp1=temp1->next; 
       lar--; 
     } 



     if(r<n && temp->data<temp1->data) 
     { 
       larg=r; 
       lar=r; 
       temp=*head; 
       while(lar!=0 && lar<=n) 
       { 
         temp=temp->next; 
         lar--; 
       } 
     if(larg!=i) 
     { 
       tem=temp->data; 
       temp->data=temp1->data; 
       temp1->data=tem; 

       maxheap(&(*head),n,larg); 
     } 
} 

// sadece heapify işlev