sada.cpp

一条最短路径的有效算法,希望大家多来交流,多来引用

#include<iostream.h>
#include"stdio.h"
#include"stdlib.h"
#define maxsize 20
typedef int keytype;

typedef struct
{
	int f;
}datatype;

typedef struct 
{
	datatype data;
	keytype key;
}node;



//快速排序

int partition(node r[], int n, int low, int high)
{ 
	keytype pivotkey;
	r[0] = r[low];
	pivotkey = r[low].key;
	while(low < high)
	{
		while(low<high && r[high].key >= pivotkey)
			-- high;
		r[low]=r[high];
		while(low<high && r[low].key <= pivotkey)
			++ low;
		r[high]=r[low];
	}
	r[low] = r[0];
	return low;
}


void qsort(node r[], int n, int low, int high)
{
	keytype pivotloc;
	if(low < high)
	{
		pivotloc = partition(r, n, low, high);
		qsort(r, n, low,pivotloc - 1);
		qsort(r, n, pivotloc + 1, high);
	}
}


void Quicksort(node r[], int n)
{
	qsort(r, n, 1,n);
}


void main()
{
	node r[20];
	int size = 1;
	cout<<endl;
	cout<<"请输入要排序的元素(当输入#时结束):";
	cout<<endl;
	
	size = 0;
	int d;
	cin>>d;
	while(d != 0)
	{
		r[++ size].data.f = d;
		r[size].key = d;
		cin>>d;
	}
	
	cout<<"快速排序为:"<<endl;
	Quicksort(r, size);
	for(int i = 1; i <= size; i ++)
	{cout<<r[i].key<<"  ";}
	cout<<endl;
}