sort.cpp

操作系统排序算法

/************************************************/
/* 第113页 习题18 */
/* 排序表是带头结点的单链表时的选择排序方法 */ 
/************************************************/ 
#include "stdio.h"
#include<io.h>
#include<malloc.h>
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;i<N;i++)
// scanf("%d",&a[i]);
p=head->next;
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;
}

}