Ascending order in linked list in c

问题:

I am trying to do ascending order in linked list through change of links and addresses rather than value

struct node
{
    char name[30];
    int percent;
    struct node *link;
};

int main
{
    clrscr();
    randomize();
    struct node *st;
    st=NULL;
    for(int i=0;i<7;i++)
        append(&st,random(101)); //Assigning random values to structure node->percent

    display(st);
    AscMarks(&st); //Changing the order of links and addresses to arrange them in ascending order
    printf("\nAscending order list...\n");
    display(st);
    getch();
    return 0;
}

/*Adds a node at the end of a linked list */
void append(struct node **q,int per)
{
    struct node *temp,*r;
    temp=*q;
    /* If the list is empty , create first node */
    if(temp==NULL)
    {
        temp=(node*)malloc(sizeof(struct node));
        temp->percent=per;
        getName(temp->name);
        temp->link=NULL;
        *q=temp;
    }
    else
    {

        while(temp->link!=NULL)
            temp=temp->link;

        r=(struct node*)malloc(sizeof(struct node));
        r->percent=per;
        getName(r->name);
        r->link=NULL;
        temp->link=r;
    }
}

/*Displays the contents of the linked list */
void display(struct node *q)
{
    while(q!=NULL)
    {
        printf("%d\t%s\n",q->percent,q->name);
        q=q->link;
    }
}

void getName(char *c)
{
    for(int i=0;i<30;i++)
    {
        if(i==10||i==20)
            *(c+i)=' ';
        else
            *(c+i)=(char)((random(26)+97));
    }
    *(c+i+1)='\0';
}

/*To change the links and addresses in order to arrange the percent in ascending order */
void AscMarks(struct node **q)
{
    struct node *temp,*temp1,*r;
    temp=*q;
    //  r=q;
    for(int i=0;i<7;i++,temp=temp->link)
    {       temp1=temp->link;
        for(int j=i+1;j<7;j++,temp1=temp1->link)
        {
            if(temp->percent>temp1->percent)
            {
                r=*q;
                while(r->link!=temp1)
                {
                    r=r->link;
                }
                r->link=temp1->link;

                temp1->link=temp;
                temp=temp1;

            }
        }
        if(i==0)
            *q=temp;
    }

    temp->link=NULL;
    /*
       while(r!=NULL)
       {
       printf("\n%d",r->percent);
       r=r->link;
       } */
}

Ascending order (AscMarks) is not giving results as expected and I am unable to see what's my fault in the code Please help

回答1:

You are not establishing link between the smallest address to the second smallest address and so on ... i have got that through node variable "*s" by s->link=temp& giving the address of last sorted value (temp) to s..through s=temp.. And in "j" loop after each time , temp->percent> temp1->percent .. you have done temp1-link=temp, it makes the address of temp1, the address of starting temp... means in short ... the number of tries of "j" will be too less to compare all the addresses ... as most of it will repeat ... so for it you should do j=i;

 void AscMarks(struct node **q)
      {
          struct node *temp,*temp1,*r,*s;
        temp=*q;
        //  r=q;
        for(int i=0;i<7;i++,temp=temp->link)
        {       temp1=temp->link;
            for(int j=i+1;j<7;j++,temp1=temp1->link)
            {
                if(temp->percent>temp1->percent)
                {
                    r=*q;
                    while(r->link!=temp1)
                    {
                        r=r->link;
                    }
                    r->link=temp1->link;
                    j=i;//resetting the value of j
                    temp1->link=temp;
                    temp=temp1;
                    if(i!=0)
                           s-link=temp; //establishing link between 
                           //this sorted address(in this loop) to the
                           //last sorted address                                                            

                }
            }
        if(i==0)
            *q=temp;
        s=temp;//giving it the address of structure which have the last
               //sorted value      
}

temp->link=NULL; //No need to do this
    /*
       while(r!=NULL)
       {
       printf("\n%d",r->percent);
       r=r->link;
       } */
}