www.pudn.com > paixusuanfa.rar > sort.cpp

/************************************************/ 
/* 第113页 习题18 */ 
/* 排序表是带头结点的单链表时的选择排序方法 */  
/************************************************/  
#include "stdio.h" 
#include 
#include 
int count ; 
struct node { 
int data; 
struct node *next; 
}; 
typedef struct node NODE; 
void select_sort(NODE*head,int n); 
void create_chain(NODE *head); 
 
void main() 
{  
int a[]={503,87,512,61,908,170,897,275,653,426},n; 
NODE *head,*p; 
head=(NODE*)malloc(sizeof(int)); 
head->next=NULL; 
create_chain(head); 
n=10; 
count=0; 
 
//int a[100],i; 
// printf("Enter a[i]\n"); 
// for(i=0;inext; 
printf("\nBefore sorted\n"); 
while(p!=NULL) 
{printf(" %d ",p->data);p=p->next;} 
//printf("\n count=%d\n",count); 
select_sort(head,n);/* 调用选择排序函数 */ 
p=head->next; 
printf("\nAfter 1sorted\n"); 
 
while(p!=NULL) 
{printf(" %d ",p->data);p=p->next;} 
//printf("\n count=%d\n",count); 
getchar(); 
} 
 
/************************************************/ 
/* 单链表的选择排序 */  
/************************************************/ 
void select_sort(NODE *head,int n) 
{ int t; 
NODE *p,*q,*tmp; 
q=head->next; 
if(q->next!=NULL) 
{ 
while(q->next!=NULL)/* n-1次循环 */ 
{  
tmp=q; 
p=q->next; 
while(p!=NULL)  
{ 
if(tmp->data>p->data) tmp=p; 
p=p->next; 
} 
t=tmp->data; 
tmp->data=q->data; 
q->data=t; 
q=q->next; 
} 
} 
} 
/************************************************/ 
/* 由数组建立单链表 */  
/************************************************/ 
void create_chain(NODE *head) 
{ 
NODE *p;  
int a[]={503,87,512,61,908,170,897,275,653,426},n,i; 
n=10 ; 
 
 
for(i=n-1;i>=0;i--) 
{ 
p=(NODE*)malloc(sizeof(int)); 
p->next=head->next;  
p->data=a[i]; 
head->next=p; 
} 
 
}