shuju5.cpp

实现了对于链式结构的冒泡法

// shuju5.cpp : 定义控制台应用程序的入口点。
// Description	:	实现 自动生成数据& 用户插入数据
//					     冒泡法，插入法，选择法
//						 附加计算程序运行时间
//					visual c++ 2008 通过
/////////////////////////////////////////

#include "stdafx.h"
#include <stdio.h>
#include <windows.h>
#include <time.h>
#define NULL 0

struct stu
{
	int id;
	char name[20];
	double mark;
	struct stu *ahead;
	struct stu *next;
}*head;

const int c_max = 10000;
int n = 0;		// 记录学生总人数

//

void creat()		// 用户插入数据用函数
{

	char goon = 'g';

	while ( goon != 'e')
	{ 
		n++;

		struct stu *p_stu = NULL;
		p_stu = (struct stu *)malloc( sizeof( struct stu));
		p_stu->ahead = NULL;

		printf("Please input the student\'s name:");
		scanf_s("%s", &p_stu->name, 20);		// 末尾参数代表最大读入个数
		putchar('\n');

		printf("Please input the student\'s id:");
		scanf_s("%d", &p_stu->id);
		putchar('\n');

		printf("Please input the student\'s mark:");
		scanf_s("%lf", &p_stu->mark);		// 牢记：double要用%lf
		putchar('\n');

		if ( n == 1) 
			p_stu->next = NULL;
		else 
		{
			// 头部插入
			p_stu->next = head;
			head->ahead = p_stu;
		}
		head = p_stu;
		head->ahead = NULL;
		
		printf("Do you want to input another one?(if not input 0)");
		scanf_s("%c", &goon);

		putchar('\n');
	}
}

//

void auto_creat()
{ 
	int i = 0;
	struct stu *p1, *p2;
	p2 = p1 = ( struct stu *)malloc( sizeof( struct stu));
	
	// 自动生成人数
	head = NULL;
	n = 0;
	for ( i = 0; i != c_max; i++)
	{
	    n++;
		p1->id = 100001 + i;
		p1->mark = rand() % 101;
		p1->name[0] = 's';
	    p1->name[1] = 'u';
		p1->name[2] = 'i';
		p1->name[3] = 'j';
		p1->name[4] = 'i';
		int j = 5;
		for ( ; j != 20; j++) 
			p1->name[j] = '\0';
		
		if ( i == 0) 	
			p1->next = NULL;
		else
		{
			p1->next = p2;
			p2->ahead = p1;
			p2 = p1;
		}

		head = p1;
		head->ahead = NULL;
		
		if ( i != c_max - 1) 
			p1 = ( struct stu *)malloc( sizeof( struct stu));
	}
}

//

// 插入法
void insrt_sort()
{	
	struct stu *unsort = head->next;
	head->next = NULL;
	
	while ( unsort != NULL)
	{
		struct stu *p_temp = unsort, *p1 = head, *p2 = head;
		
		// unsort 向后移
		unsort = unsort->next;

		// 找出p_temp应该插入位置
		while ( ( p1 != NULL) && ( p1->mark < p_temp->mark))
		{
			p2 = p1;
			p1 = p1->next;
		}
		
		// 插入
		if ( p1 == head)
		{
			p_temp->next = p1;
			p1->ahead = p_temp;
			head = p_temp;
		}
		else
		{
			p2->next = p_temp;
			p_temp->ahead = p2;
			p_temp->next = p1;
			
			if ( p1 != NULL)
				p1->ahead = p_temp;
		}
	}
}

//

// 选择法
void selct_sort()
{
	struct stu *unsort = head;
	head = NULL;
	
	while ( unsort !=  NULL)
	{
		struct stu *p = unsort, *max = unsort;
		
		// 对全队扫描 把最大的放到max
		while ( p != NULL)
		{
			if ( p->mark > max->mark)
				max = p;
			
			p = p->next;
		}
		
		// 将max指向的项从 unsort 中剔除
		if( max == unsort)
		{
			unsort = unsort->next;

			if ( unsort != NULL)
				unsort->ahead = NULL;
		}
		else
		{
			( max->ahead)->next = max->next;
			
			if ( max->next != NULL)
				( max->next)->ahead = max->ahead;
		}

		// max可以直接从头插入
		if ( head == NULL)
		{
			head = max;
			head->ahead = head->next = NULL;
		}
		else
		{
			head->ahead = max;
			max->next = head;
			
			head = max;
			head->ahead = NULL;
		}
	}

}

//

// 冒泡法
void bubl_sort()
{
	// i 控制循环范围 flag判断是否已经有序
	int i = n - 1;
	bool flag = 1;

	while ( ( i > 0) && ( flag == true))
	{
		flag = false;

		struct stu *p1 = head->next, *p2 = head;
		
		int j = 0;
		for ( ; j != i; j++)
		{
			if( p1->mark > p2->mark)
			{
				if ( p2 != head) 
				{
					struct stu *p3 = p2->ahead, *p4 = p1->next;
				
					// 连接p1 p3
					p3->next = p1;
					p1->ahead = p3;
					
					// 连接 p2 p1
					p2->ahead = p1;
					p1->next = p2;
					
					// p4 不为空 连接 p4 p2
					if ( p4 != NULL)
					{
						p4->ahead = p2;
						p2->next = p4;
					}
					else 
						p2->next = NULL;

					// p1 移向下一位
					p1 = p4;
				}
				else if ( p1->next != NULL)
				{
					struct stu *p4 = p1->next;
					
					// 连接 p4 p2
					p2->next = p4;
					p4->ahead = p2;

					// 连接 p1 p2
					p2->ahead = p1;
					p1->next = p2;

					// p1 为头指针
					p1->ahead = NULL;
					head = p1;
					
					// p1 移向下一位
					p1 = p4;
				}
				else // 只要数据多于两个就不会满足此条件
				{
					// p1 为头指针
					head = p1;
					p1->ahead = NULL;
					
					// 连接 p1 p2
					p1->next = p2;
					p2->ahead = p1;
					
					
					p2->next =NULL;
					p1 = NULL;
				}

				// 已经进行交换
				flag = true;
			}
			else
			{
				p2 = p1;
				p1 = p1->next;
			}		
		}

		// 已对全队进行过一趟交换 已将范围内最小值放到最底
		i--;
	}
}

//

// 列出学生信息
void list()
{
	struct stu *p;
	p = head;
	
	while(p != NULL)
	{
		printf("stu id:%d\n",p->id);
		printf("stu name:%s\n",p->name);
		printf("stu mark:%.1f\n",p->mark);
		p = p->next;
	}
}

//

int _tmain(int argc, _TCHAR* argv[])
{
//	creat();
	clock_t start,finish;
    double totaltime;
	char key;
	
	while(1)
	 {
		system("cls");
		fflush(stdin);
		
		printf("What can i do for you?\n总共一万个学生，可以对比排序时间\n");
		printf("\n1,自动生成学生数据(input a)");
		printf("\n2,自行输入学生数据(input c)");
		printf("\n3,列出学生信息    (input l)");
		printf("\n4,冒泡法排序      (input c)");
		printf("\n5,插入法排序      (input i)");
		printf("\n5,选择法排序      (input i)");
		printf("\n6,离开            (input e)\n");

		key = getchar();
		
		if(key == 'a') auto_creat();
		
		if(key == 'c') creat();
		
		if(key == 'l') list();
		
		if(key == 's') 
		{
			start = clock();
			selct_sort();
			finish = clock();
			totaltime = ( double)( finish - start)/1000;
			printf("totaltime:%f\n", totaltime);
		}

		if(key == 'i') 
		{
			start = clock();
			insrt_sort();
			finish = clock();
			totaltime = ( double)( finish - start)/1000;
			printf("totaltime:%f\n", totaltime);
		}
		
		if(key == 'b') 
		{
			start = clock();
			bubl_sort();
			finish = clock();
			totaltime = ( double)( finish - start)/1000;
			printf("totaltime:%f\n", totaltime);
		}
		
		if(key == 'e') break;
		
		system("pause");
	}
	return 0;

}