约瑟夫环1.txt

数据结构学习用到的一些程序！！里面有二叉树相关的几个

#include <stdio.h> 
#include <stdlib.h> 

/* to test something about LIST data structure 
2005.9.26 */ 
struct list 
{ 
 int data; 
 int key; 
 struct list* nextPtr; 
}; 
typedef struct list List; 
typedef List* ListPtr; 

ListPtr insert(ListPtr*,int); 
void constructList(ListPtr*,int); 
void print(ListPtr,int); 
void distroy(ListPtr); 
void maintain(ListPtr,int); 

int main() 
{ 
 int n; 
 ListPtr sPtr; 
 sPtr=NULL; 
 printf("\ninput n:"); 
 scanf("%d",&n); 
 constructList(&sPtr,n); 
 print(sPtr,n); 
 #if 1 
 maintain(sPtr,n); 
 #endif 
 getchar(); 
 return 0; 
} 


ListPtr insert(ListPtr* sPtr,int value) 
{ 
 ListPtr currentPtr,previousPtr,newPtr; 
 static int i=1; 
 newPtr=(ListPtr)malloc(sizeof(ListPtr)); 
 currentPtr->nextPtr=NULL; 
 if(newPtr!=NULL) 
 { 
newPtr->data=i; 
newPtr->key=value; 
newPtr->nextPtr=NULL; 
currentPtr=*sPtr; 
 previousPtr=NULL; 
 while(currentPtr!=NULL) 
 { 
 previousPtr=currentPtr; 
 currentPtr=currentPtr->nextPtr; 
 } 
 if(previousPtr==NULL){ 
 *sPtr=newPtr; 
 i++; 
 return *sPtr; 
}else{ 
 previousPtr->nextPtr=newPtr; 
 i++; 
 return newPtr; 
 } 
 }else{ 
 printf("can't malloc \n"); 
 } 



} 


void constructList(ListPtr* sPtr,int n) 
{ 
 int i; 
 int key; 
 ListPtr currentPtr; 

 currentPtr=NULL; 
 for(i=0;i<n;i++) 
 { 
 printf("input key of %d:",i+1); 
 scanf("%d",&key); 
 currentPtr=insert(sPtr,key); 
 } 
 currentPtr->nextPtr=*sPtr; 

} 

void print(ListPtr sPtr,int n) 
{ 
 int i; 
 printf("List is:"); 
 for(i=0;i<n;i++) 
 { 
 printf("%d with",sPtr->data); 
 printf(" %d ->",sPtr->key); 
 sPtr=sPtr->nextPtr; 
 } 
 printf("\n"); 
} 


void distroy(ListPtr sPtr) 
{ 
 ListPtr tempPtr; 
 while(sPtr!=NULL) 
 { 
 tempPtr=sPtr; 
 sPtr=sPtr->nextPtr; 
 free(tempPtr); 

 } 
 printf("free success!\n"); 
} 


void maintain(ListPtr sPtr,int n) 
{ 
 int m,length,posit; 
 ListPtr currentPtr,previousPtr,tempPtr; 

 length=n; 
 currentPtr=previousPtr=sPtr; 
 printf("input the first KEY:"); 
 scanf("%d",&m); 

 while(length>=1) 
 { 
 posit=m-2; 
 if(posit==-1) 
 { 
 m=currentPtr->key; 
 printf("%d--",currentPtr->data); 
 currentPtr=previousPtr=currentPtr->nextPtr; 


 }else{ 

 while(posit) 
 { 

 currentPtr=currentPtr->nextPtr; 
 posit--; 
 } 
 previousPtr=currentPtr; 
 tempPtr=currentPtr->nextPtr; 
 m=tempPtr->key; 
 printf("%d--",tempPtr->data); 
 currentPtr=tempPtr->nextPtr; 
 previousPtr->nextPtr=currentPtr; 
 length--; 

 } 
 } 
 printf("\n"); 

}