全排列的链表,与连续表实现
/* 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,¤t);
//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,¤t);
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",°ree);
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');
}