/* list.h

*/
typedef  int EntryType;
typedef  int Position;
typedef struct EntryNode{
    EntryType  key;
    struct EntryNode *next ;
} ListNode;

typedef struct list{
    ListNode * head ;
    Position count;
}List;
void initialList(List *list);
void InsertList(Position p ,EntryType x ,List *list);
void deleteNode(Position p ,List *list);
ListNode * MakeListNode (EntryType x);
void SetPosition(Position p ,List *list,ListNode**current);
void permuation (int n,int number ,List *list);
void show(List *list);
int ListEmpty(list);
----------------------------------------------------------------------

/* list.c

*/
#include<stdio.h>
#include<stdlib.h>
#include"list.h"
void initialList(List *list)
{
    list->count=0;
    list->head=NULL;
}
void deleteNode(Position p , List *list)
{

    ListNode * current ;
   if(ListEmpty(list))
      printf(" it is empty\n");
  else
    {
        if(p == 0)
    {//    printf(" delete the head  %d \n" ,list->head->key);
        list->head= list->head->next;
         
    }
    else{
         SetPosition(p-1 ,list,&current);
       //printf(" delete the key %d " ,current->next->key);
    //    printf(" hello \n");
    
        current->next = current->next->next;
        
    }
    list->count--;
    }

}
void InsertList(Position p,EntryType x, List *list )
{
    int i =0;
    ListNode *current;
    ListNode *newnode;
    if(p<0 || p>list->count)
        printf(" %d is error the either too big or too small \n",p);
    else {
          
        newnode = MakeListNode(x);
        if(p==0)
        {
            newnode->next = list->head;
            list->head = newnode;
        }
        else
        {
            SetPosition(p-1,list,&current);
            newnode->next = current->next ;
            current->next = newnode ;
        }    
        list->count++;
    }


}
ListNode* MakeListNode(EntryType x)
{
    ListNode *p  =(ListNode *) malloc (sizeof(ListNode));
    if(p)
    {
        p->key =x ;
        p->next= NULL;
    }
    else
        printf(" No space for addtional node can be obtained \n");
    return p ;
}
void SetPosition (Position p ,List *list ,ListNode **current)
{
     int i = 0 ;
     ListNode * q;
     if(p<0 || p >list->count)
        printf(" not correct position \n");
     else
     {
         q = list->head;
         for(i = 1 ;i <= p ; i++)
             q = q->next ;
         *current = q;        
     }
    
/*/     else {
//         if(p == 0 )
//             q = list->head;
//          else
          {
             for(i = 1 ;i < p ;i++)
                 q = q ->next ;
          }
         *current = q ;
     }
//*/

}
    
void permuation(int c,int number ,List *list)
{
    int n = 0;

    for(n=0;n<number;n++)   // number need check
    {
         if(n>list->count)        
        {
        //    printf(" empty the list no place to insert \n");
            break    ;
        }
    //    printf("insert %d \n",n);
     InsertList(n ,c ,list);
    
     if(c == number)
        show(list);
     else
     {
        // printf(" starting the recurse %d  ...\n",c);
         permuation(c+1,number,list);
        // printf(" finishing the recurse %d ...\n",c);
     }
     // printf(" delete the %d \n",n);
       deleteNode(n ,list);
        
     //  printf(" choose another place \n");
    }
}
void show(List *list)
{
    ListNode *p = list->head;
    while(p)
    {
        printf("%3d",p->key);
        p=p->next;
    }
    putchar('\n');
//    printf("successful \n");
}
int ListEmpty(List list)
{
    if(list.count == 0)
    {
    //    printf("enmpty list \n");
        return 1;
    }
    else return 0;
}


---------------------------------------------------------------------
/*
perm.c
*/
#include<stdio.h>
#include"list.h"
main()
{
    int number =0;
    List list ;
    initialList(&list);
    if(ListEmpty(list))
        printf(" this is an empty list \n");
    printf(" please enter the number you want to permuate \n");
    scanf("%d",&number);

    permuation(1,number,&list);
    return 0;
}



-----------------------------------------------------------------------

而数组可以避免过多的插入。

#define MAX 20
void Permute(int ,int ,int[]);
void ProcessPermutation(int []);
void show (int []);
#include<stdio.h>
int main()
{
    int degree;
    int perm[MAX+1];
    for(degree =0 ;degree< MAX;degree++)
        perm[degree]=-1;
    printf("Number of the element to permuate?");
    scanf("%d",&degree);
    if(degree<1||degree>MAX)
        printf(" the number must be right ");
    else
    {
        perm[0]=0;
        Permute(1, degree,perm);
    }
    getch();
    return 0;

}

void Permute( int newentry,int degree, int *perm)
{
    int current = 0;
    do{
        printf("do before change perm[newentry] is %d perm[current] is %d\n ",    perm[newentry],perm[current]);
        perm[newentry] = perm[current];  //
        //  newentry->next = current ->next ;
        // newentry  = current->
        //  current->next = newentry ;   insert   newentry after  the current
        // current->entry  = newentry->entry  ;
        perm[current]= newentry;
        printf(" after change perm[newentry] is %d perm[current] is %d \n",perm[newentry],perm[current]);
        if(newentry == degree)
        {   
            show(perm);
            printf(" process the permuatation| ");
            ProcessPermutation(perm);
            putchar('\n');
        }
        else
        {   printf( " before the recurse the perm\n");
            show(perm);
            Permute(newentry+1,degree,perm);
            printf(" recurse \n");
        }
    //    show(perm);
    //    printf("the perm[newentry] is %d and the  perm[current] is %d ",perm[newentry],perm[current]);
    printf(" \nnewentry is %d " ,newentry);
        perm[current]= perm[newentry];  // before it is perm[current] = newentry
            printf(" the current is %d ",current);
        current= perm[current];  // the next one ?
        //     current->next =  newentry ->next ;
        //     current= current->next ;
    printf("after the recycle\n");
    show(perm);
    printf(" the current is %d \n",current);
    }while(current!=0);
}
void ProcessPermutation(int *perm)
{
    int current = 0;
    while(perm[current]!=0)
    {
        printf("%3d",perm[current]);
        current= perm[current];
    }
    putchar('\n');
}

void show(int *perm)
{
    int i= 0;
    int j = sizeof(perm)/sizeof(int);
    for(i=0;perm[i]!=-1;i++)
        printf("%3d",perm[i]);
    putchar('\n');
}

有些注释是错的。。。忘记删了。