Cod sursa(job #1249161)

Utilizator danielmaxim95FMI Maxim Daniel danielmaxim95 Data 26 octombrie 2014 17:00:53
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <cstdio>

using namespace std;

struct nod{
    unsigned long int val;
    nod *next;
};

struct lista{
    nod *prim=NULL;
    nod *ultim=NULL;
    }l[255];

int numarcifre(unsigned long int x)
{
    int k=0;
    do
    {
        x>>=1;
        k++;
    }
    while(x);
    return k;
}

void adlista(unsigned long int x, int k)
{
    nod *p=new nod;
    p->val=x;
    p->next=NULL;
    if (l[k].prim==NULL)
    {
        l[k].prim=p;
        l[k].ultim=p;
    }
    else
    {

        l[k].ultim->next=p;
        l[k].ultim=p;

    }
}

void populeaza(unsigned long int v[])
{
    unsigned long int j=0;
    for(int k=0;k<=255;k++)
        if((l[k].prim==l[k].ultim)&&(l[k].prim!=NULL))
        {
            v[j]=l[k].prim->val;j++;
            delete l[k].prim;
            l[k].prim=NULL;
            l[k].ultim=NULL;
        }
        else
            if(l[k].prim!=NULL)
            {
                nod *p=new nod;
                while(l[k].prim!=NULL)
                {
                    p=l[k].prim;
                    v[j]=p->val;j++;
                    delete l[k].prim;
                    l[k].prim=p->next;
                }
                l[k].ultim=NULL;
            }
}

int main()
{
    FILE *f;
    unsigned long int i,h,nc,m,v[10000000],n,a,b,c;
    f=fopen("radix.in","r");
    fscanf(f,"%u %u %u %u",&n,&a,&b,&c);
    fclose(f);
    m=0;
    v[0]=b;
    for(i=0;i<n;i++)
    {
        v[i]=(a*v[i-1]+b)%c;
        if(v[i]>m)m=v[i];
    }

    nc=numarcifre(m);

    for(h=0;h<nc;h+=8)
    {
        for(i=0;i<n;i++)
            adlista(v[i],(v[i]>>h)&255);
        populeaza(v);
    }

    f=fopen("radix.out","w");
    for(i=0;i<n;i+=10)
        fprintf(f,"%ld ",v[i]);
    fclose(f);

    return 0;
}