單連結清單的轉置、排序操作

   該代碼主要是針對對連結清單操作不是很熟悉的朋友，也是自己在面試當中經常 碰到的程式設計問題,是以利用業餘時間寫下了此練習性質的程式。以下是源代碼：

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct st{ 
    char name[10];
    int score;
    struct st *next;
};
void print(struct st*);
/*連結清單頭節點的初始化*/
struct st *init()
{
    struct st *head;
    head =malloc(sizeof(struct st));
    head->score =-1;
    memset(head->name,0x00,sizeof(head->name));
    head->next=NULL;
    if (head ==NULL)
        return NULL;
    else 
        return head;
}
/*插入節點，尾節點的插入,時間複雜度o(n)*/
int pushlist(struct st *ptr,char *name,int score)
{
    struct st *e,*ep;
    ep =e =ptr;
    if (e->score==-1)
    {   
        memcpy(e->name,name,strlen(name));
        e->score =score;
        return 0;
    }   
    while (e!=NULL)
    {
        ep =e;
        e =e->next;
    }
    e =malloc(sizeof(struct st));
    if (e==NULL)
    {
        return -1;
    }
    memcpy(e->name,name,strlen(name));
    e->score =score;
    ep->next =e;
    e->next=NULL;
    return 0;


}
/*插入節點，尾節點的插入,時間複雜度o(1)*/
struct st **pushListTail(struct st *ptr,struct st **next,char *name,int score)
{
    struct st *e; 
    e =ptr;
    if (e->score==-1)
    {   
        memcpy(e->name,name,strlen(name));
        e->score =score;
        next =&(ptr->next);//儲存一級指針的位址。
        return next;
    }   
    e =malloc(sizeof(struct st));
    memcpy(e->name,name,strlen(name));
    e->score =score;
    e->next =NULL;
    *next =e; 
    next =&(e->next);
    return next;
    
}

/*轉置函數*/
void reverse(struct st **ptr)
{
    struct st *p=*ptr;
    struct st *q=NULL;
    struct st *r;
    while (p)
    {
        r =p->next;
        p ->next=q;
        q =p;
        p =r;
    }
    *ptr =q;


}
/*轉置函數 use 遞歸*/
struct st *reverseFordigui(struct st *ptr)
{
    if (ptr==NULL || ptr->next==NULL){
        return ptr;
    }   
    struct st *newhead =reverseFordigui(ptr->next);
    ptr->next->next =ptr;
    ptr->next=NULL;
    return newhead;

}

/*找到節點的最小值*/
struct st * findmin(struct st *ptr)
{
    struct st *cur=ptr;
    struct st *tmp;
    struct st *min =cur;
    for (cur=ptr;cur!=NULL;cur =cur->next)
    {
        if (cur->score < min->score)
        {
            min =cur;
        }


    }
    return min;
}
/*釋放單個節點*/
struct st *freeNode(struct st *tmp,struct st *head)
{
    struct st *cur,*p=head;
    if (tmp ==head)
    {
        p =(head)->next;
        free(head);
        head =NULL;
        head =p;
        return head;
    }
    for (cur =(head)->next;cur!=NULL;cur =cur->next)
    {
        if (cur ==tmp)
        {
            p->next=cur->next;
            free(cur);
            cur =NULL;
            return head;
        }
        p =p->next;
    }
    if (cur==NULL)
    {
        printf("NULL is");
        return NULL;
    }
}
/*将最小值插入到新建立頭内*/
struct st *sort(struct st *ptr)
{
    struct st *cur=ptr;
    struct st *tmp;
    struct st *head=ptr;
    struct st *e,*ep;
    int i=0;
    struct st *newhead=init();
    e=ep =newhead;
    while (1)
    {


        tmp =findmin(head);
        if (e ->score ==-1)
        {
            memcpy(e->name ,tmp->name,strlen(tmp->name));
            e->name[strlen(tmp->name)]='\0';
            e->score=tmp->score;
            head =freeNode(tmp,head);
            if (head ==NULL)
                break;
            continue;
        }
        while (e)
        {
            ep =e;
            e =e->next;
        }
        e =malloc(sizeof(struct st));
        memcpy(e->name ,tmp->name,strlen(tmp->name));
        e->name[strlen(tmp->name)]='\0';
        e->score=tmp->score;
        ep->next =e;
        e->next =NULL;
        head =freeNode(tmp,head);
        if (head ==NULL)
            break;
    }
    return newhead;
}
/*周遊整個連結清單*/
void print(struct st *ptr)
{
    struct st *cur;
    for (cur=ptr;cur!=NULL;cur=cur->next)
    {
        printf("name:%s,score:%d\n",cur->name,cur->score);
    }
}
/*釋放整個連結清單*/
void myfree(struct st *ptr)
{
    struct st *after;
    struct st *cur=ptr;
    for (cur=ptr;cur!=NULL;cur=after)
    {
        after =cur->next;
        free(cur);
        cur=NULL;
    }
}
/*簡單的測試*/
int main()
{
    struct st *head,**next;
    struct st *me;
    struct st *sorthead;
    head =init();
    char name[10];
    int value;
    int i;
    for (i=0;i<10;i++){
        value =rand()%100;
        sprintf(name,"同學%d",value);
        name[strlen(name)]='\0';
        pushlist(head,name,value);
        //next =pushListTail(head,next,name,value);//調用方式二。
    }
    printf("------ before reverse--------\n");
    print(head);
    printf("------ reverse after--------\n");
    reverse(&head);
    print(head);
    printf("-------sort -------------\n");
    sorthead=sort(head);
    print(sorthead);
    myfree(sorthead);
}