学步园

要求：从文件fin中读取数据，每行的格式如"王明 85"，代表"姓名 成绩"，具体有多少行不确定。按成绩从大到小排序，将结果写入文件fout.

/*
	功能：从文件fin中读取"name grade"，并按照grade从大到小排序
	经验：操作vector也可以像操作普通数组一样操作(使用下标)，前提是没有结点的删除或增加
*/
#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

typedef struct
{
	char name[20];
	int grade;
}Node;


vector<Node>::iterator searchMax(vector<Node> &v)		// 返回vector中grade最大的结点
{
	vector<Node>::iterator ret = (vector<Node>::iterator)NULL;
	if(v.size() > 0)
	{
		ret = v.begin();
		for(vector<Node>::iterator it = ret + 1; it != v.end(); it++)
		{
			if(ret->grade < it->grade)
				ret = it;
		}
	}

	return ret;
}

void display(vector<Node> &v)
{
	for(vector<Node>::iterator it = v.begin(); it != v.end(); it++)
	{
		printf("%d ", it->grade);
	}
	printf("\n");
}

void swap(Node * p1, Node *p2)		// 交换两个结点的值
{
	Node t;
	t = *p1;
	*p1 = *p2;
	*p2 = t;
}

void bubbleSort(vector<Node> &v)	// vector像使用普通数组一样使用
{
	int i, j, len;
	int flag;
	len = v.size();
	for(i = 0; i < len; i++)
	{
		flag = 0;
	 	for(j = 0; j < len - i - 1; j++)
		{
			if(v[j].grade < v[j+1].grade)
			{
				flag = 1;
				swap(&v[j], &v[j+1]);	// 交换两结点值
			}
		}
		if(!flag)						// 本轮未交换过元素值，表明已有序
			break;
		display(v);
		printf("*****************************************\n");
	}
}

void writeVector(FILE *fout, vector<Node> &v)
{
	for(vector<Node>::iterator it = v.begin(); it != v.end(); it++)
	{
		fprintf(fout, "%s %d\n", it->name, it->grade);
	}
}

int main(int argc, char **argv)
{
	char fin[] = "a.txt";
	char fout[] = "a_out.txt";
	FILE *fp1, *fp2;
	vector<Node> v;

	fp1 = fopen(fin, "r");
	fp2 = fopen(fout, "w");
	if(fp1 == NULL || fp2 == NULL)
	{
		printf("Open file error!\n");
		return 1;
	}

	// 从文件读取数据
	Node node;
	while(fscanf(fp1, "%s %d\n", node.name, &node.grade) == 2)
		v.push_back(node);
	fclose(fp1);
	display(v);		// 显示读取的数据

	// 方法一：调用bubbleSort()
	printf("----------------------------------------------------\n");	
	bubbleSort(v);
	printf("====================================================\n");
	display(v);
	writeVector(fp2, v);

	// 方法二：通过searchMax()
/*	vector<Node>::iterator max = (vector<Node>::iterator)NULL;
	while(v.size() > 0)
	{
		max = searchMax(v);
		if(max == (vector<Node>::iterator)NULL)
			break;
		fprintf(fp2, "%s %d\n", max->name, max->grade);
		v.erase(max);
	}*/
	fclose(fp2);

	return 0;
}

结论：对vector排序，可像操作数组一样方便的操作。前提是没有结点的增、删。

========================================================================

另附：整数数组选择排序算法：

void disp(int a[], int len)
{
        int i = 0;
        for(; i < len; i++)
        {
                printf("%d ", a[i]);
        }
        printf("\n");
}

void selectSort(int a[], int len)       // 选择排序
{
        int i, j, k, t;
        for(i = 0; i < len; i++)
        {
                k = i;
                for(j = i+1; j < len; j++)
                {
                        if(a[j] > a[k])
                                k = j;                          // k指向最大值
                }
                if(k != i)
                {
                        t = a[i];
                        a[i] = a[k];
                        a[k] = t;
                }
                else
                        continue;
                for(j = 0; j < i; j++)
                        printf("|  ");
                disp(a+i, len-i);
        }
}