数据结构与算法（C语言实现） 7-8.查找和排序算法的综合应用

实验七-八查找和排序算法的综合应用

一、实验目的

1．理解排序和查找的概念和意义；

2. 掌握顺序查找、折半查找、直接插入排序，改进的冒泡排序、快速排序等算法。

二、实验内容

有n（n至少为100）个学生记录，每个学生记录包含姓名、性别、班号（班号为1001—1030之间）。现编写程序实现以下功能：

（1）利用文件输入学生记录；

（2）分别按班号或姓名采用顺序查找或折半查找算法实现查找指定学生记录并输出，若未找到则输出“查无此人”信息；

（3）按班号和性别有序输出，即先按班号输出，同一个班的学生按性别输出。

头文件及宏定义：

#include 
#include 
#include 
#include 
#define MAX 1500
#define TRUE -1
#define FALSE -2
#define by_name 1
#define by_class 2

typedef int Status;
typedef struct Student
{
    char name[10];
    char sex[5];
    char class[15];
}Student;
typedef struct
{
    Student *data;
    int length;
}*StudentList;

Status getFileFlag=FALSE;

子函数声明：

Status getFileList(StudentList);//文件读取信息表
void display(StudentList,int*,char*);//输出查找内容
void Quicktsort(StudentList,int,int);//快速排序
void Insertsort(StudentList);//直接插入排序
void Selectsort(StudentList);//选择排序
void BubbleSort_plus(StudentList);//冒泡排序改进
void Sexsort(StudentList);//选择排序（性别）
void Namesort(StudentList);//选择排序（姓名） 
int *Sq_Search(StudentList,char*,Status,Status);//顺序查找 返回序号数组
int *Binary_Search(StudentList,char*,Status,Status);//二分查找 返回序号数组

子函数主体：

Status getFileList(StudentList L)
{
    FILE *fp;
    int i=0;
    if(getFileFlag==FALSE)
    {
    	getFileFlag=TRUE;
		srand(time(NULL));
		fp=fopen("学生信息输入文件.txt","w");
		char *name[60]={"赵","钱","孙","李","周","吴","郑","王","冯","陈",
			             "楮","卫","蒋","沈","韩","杨","朱","秦","尤","许",
			              "何","吕","施","张","孔","曹","严","华","金","魏",
			             "陶","姜","戚","谢","邹","喻","柏","水","窦","章",
			             "云","苏","潘","葛","奚","范","彭","郎","鲁","韦",
			             "昌","马","苗","凤","花","方","俞","任","袁","柳"}; 
		char *sex[2]={"男","女"};
		for(int i=0;i=1001&&temp<=1030)
					break;
			}
			itoa(temp,class_temp,10);
			fputs(class_temp,fp);
			fputc('t',fp);
			strcpy(fullname_temp,name[rand()%60]);
			strcpy(lastname_temp,name[rand()%60]);
			strcat(fullname_temp,lastname_temp);
			fputs(fullname_temp,fp);
			fputc('t',fp);
			strcpy(sex_temp,sex[rand()%2]);
			fputs(sex_temp,fp);	
			if(i!=MAX-1)		
				fputc('n',fp);
		}
		fclose(fp);
		printf("已将示例文件"学生信息输入文件.txt"放入程序目录!n");
		printf("注意：数据间为TAB键！末行不可出现无关字符！n");
		printf("可修改文件内容后继续操作！n");
		system("pause");
	}
    
    if((fp=fopen("学生信息输入文件.txt","r"))==NULL)
    {
        fclose(fp);
        return FALSE;
    }
    while(!feof(fp))
    {
        fscanf(fp,"%st%st%s",L->data[i].class,L->data[i].name,L->data[i].sex);//班号 姓名 性别
        //printf("%s %s %sn",L->data[i].class,L->data[i].name,L->data[i].sex);
        i++;
    }
    (*L).length=i;

    fclose(fp);
    return TRUE;
}

void display(StudentList L,int *temp,char *key)
{
    if(temp[0]==TRUE)
        for (int i = temp[1]; i <= temp[2]; i++)
            if(!strcmp(L->data[i].class,key)||!strcmp(L->data[i].name,key))
                printf("%s %s %sn",L->data[i].class,L->data[i].name,L->data[i].sex);
    if(temp[0]==FALSE)
        printf("查无此人！n");
}

void Sexsort(StudentList L)
{
    int i,j;
    for(i=0;ilength;i++)
    {
        for(j=i+1;jlength;j++)
        {
            if(!strcmp(L->data[i].class,L->data[j].class)&& !strcmp(L->data[i].sex,"女")&&!strcmp(L->data[j].sex,"男"))
            {
                Student student=L->data[i];
                L->data[i]=L->data[j];
                L->data[j]=student;
            }
        }
    }
}

void Namesort(StudentList L)
{
	int i,j;
	for(i=0;ilength;i++)
	{
		for(j=i+1;jlength;j++)
		{
			if(strcmp(L->data[i].name,L->data[j].name)>0)
			{
				Student student=L->data[i];
				L->data[i]=L->data[j];
				L->data[j]=student;
			}
		}
	} 					            		           	        
}	    

void Quicktsort(StudentList L,int first,int last)
{
    if(first>last)
        return;
    int i=first,j=last;
    Student standard=L->data[i];
    while (i!=j)
    {
        while ((strcmp(L->data[j].class,standard.class)>=0)&&idata[i].class,standard.class)<=0)&&idata[i];
            L->data[i]=L->data[j];
            L->data[j]=temp;
        }
    }
    L->data[first]=L->data[i];
    L->data[i]=standard;

    Quicktsort(L,first,i-1);
    Quicktsort(L,i+1,last);

    Sexsort(L);
}

void Insertsort(StudentList L)
{
    int i,j;
    for (i = 1; i < L->length; i++)
    {
        if(strcmp(L->data[i-1].class,L->data[i].class)>0)
        {
            Student temp_1=L->data[i];
            for (j = i-1;strcmp(L->data[j].class,temp_1.class)>0&&j>=0; j--)
            {
                Student temp_2=L->data[j];
                L->data[j]=L->data[j+1];
                L->data[j+1]=temp_2;
            }
            L->data[j+1]=temp_1;

        }
    }
    Sexsort(L);
}

void Selectsort(StudentList L)
{
    int i,j,k;
    for(i=0;ilength;i++)
    {
        k=i;
        for(j=i+1;jlength;j++)
            if(strcmp(L->data[k].class,L->data[j].class)>0)
                k=j;
        if(k!=i)
        {
            Student temp=L->data[i];
            L->data[i]=L->data[k];
            L->data[k]=temp;
        }
    }
    Sexsort(L);
}

void BubbleSort_plus(StudentList L)
{
    int lastEdge=0,lastEdgetemp=0;
    for(int i=0;ilength-1;i++)
    {
        lastEdge=lastEdgetemp;
        for(int j=L->length-1;j>lastEdge;j--)
        {
            if(strcmp(L->data[j-1].class,L->data[j].class)>0)
            {
                Student temp=L->data[j-1];
                L->data[j-1]=L->data[j];
                L->data[j]=temp;

                lastEdgetemp=j;
            }
        }

        if(lastEdge==lastEdgetemp)
            break;
    }
    Sexsort(L);
}

int *Sq_Search(StudentList L,char* key,Status flag,Status choice)
{
	if(choice==1)
		Insertsort(L);
	else if(choice==2)
		Selectsort(L);
	else if(choice==3)
		Quicktsort(L,0,L->length-1);
	else
		BubbleSort_plus(L);
    
    int *save=(int *)malloc(3*sizeof (int));//0位置为状态 1位置为首位置 2位置为尾位置
    int i=0,j=0;
    for (i = 0; i < 3; i++)
	        save[i]=FALSE;
	if(flag==by_name)
	{
		strcpy(L->data[L->length].name,key);
		while(j!=L->length)
		{
			if(!strcmp(L->data[j].name,key)) 
			{
				save[0]=TRUE;
				if(save[1]==FALSE)
					save[1]=save[2]=j;
				else
					save[2]=j;
			}
			j++;
		}
	}
	else
	{
		strcpy(L->data[L->length].class,key);
		while(j!=L->length)
		{
			if(!strcmp(L->data[j].class,key)) 
			{
				save[0]=TRUE;
				if(save[1]==FALSE)
					save[1]=save[2]=j;
				else
					save[2]=j;
			}
			j++;
		}
	}
    return save;
}

int *Binary_Search(StudentList L,char* key,Status flag,Status choice)
{
	int *save=(int *)malloc(3*sizeof (int));
	    for (int i = 0; i < 3; i++)
	        save[i]=FALSE;
	    int left=0,right=L->length-1,middle;
	if(flag==by_name)
		Namesort(L);
	else
		if(choice==1)
			Insertsort(L);
		else if(choice==2)
			Selectsort(L);
		else if(choice==3)
			Quicktsort(L,0,L->length-1);
		else
			BubbleSort_plus(L);
	
    
    while (left<=right)
    {
    	if(flag==by_name)
    	{
			middle=left+(right-left)/2;
			if(strcmp(L->data[middle].name,key)>0)
			    right=middle-1;
			else if(strcmp(L->data[middle].name,key)<0)
			    left=middle+1;
			else
			{
				save[0]=TRUE;
				break;
			}
		}
		else
		{
			middle=left+(right-left)/2;
			if(strcmp(L->data[middle].class,key)>0)
				right=middle-1;
			else if(strcmp(L->data[middle].class,key)<0)
				left=middle+1;
			else
			{
				save[0]=TRUE;
				break;
			}
		}
    }
    if(save[0]==TRUE)
    {
    	if(flag==by_name)
    	{
			left=right=middle;
			while(left-1>=0&&(!strcmp(L->data[left].name,L->data[left-1].name)))
				left--;
			save[1]=save[2]=left;
			while(right+1<=L->length-1&&(!strcmp(L->data[right].name,L->data[right+1].name)))
				right++;
			save[2]=right;	
		}
		else
		{
			left=right=middle;
			while(left-1>=0&&(!strcmp(L->data[left].class,L->data[left-1].class)))
				left--;
			save[1]=save[2]=left;
			while(right+1<=L->length-1&&(!strcmp(L->data[right].class,L->data[right+1].class)))
				right++;
			save[2]=right;	
		}	
	}
	
    return save;
}

主函数：

int main(void)
{
    StudentList L=(StudentList) malloc(sizeof (StudentList));
    L->data=(Student *) malloc(MAX*sizeof (Student));
    L->length=0;

start:    if(getFileList(L))
			printf("文件读取成功！n");
    else
    {
        printf("文件读取失败！n");
        exit(-1);
    }
    clock_t begin,end;
	char *key=(char *) malloc(MAX*sizeof (char));
	char choice_1,choice_3,choice_4;
	Status choice_2;

a:    printf("|—————请选择———————|n");
	printf("|----------1.顺序查找----------|n");
	printf("|----------2.二分查找----------|n");
	printf("|---Powered by CaptainUniverse_|n");
	printf("|———————★———————|nn");
    fflush(stdin);
	scanf("%c",&choice_1);
	if(choice_1!='1'&&choice_1!='2')
	{
		printf("输入有误！n");
		goto a;
	}
	
b:    printf("|—————请选择———————|n");
	printf("|--------1.直接插入排序--------|n");
	printf("|--------2.选择排序------------|n");
	printf("|--------3.快速排序------------|n");
	printf("|--------4.改进冒泡排序--------|n");
	printf("|---Powered by CaptainUniverse_|n");
	printf("|———————★———————|nn");
	fflush(stdin);
	scanf("%d",&choice_2);
	if(choice_2!=1&&choice_2!=2&&choice_2!=3&&choice_2!=4)
	{
		printf("输入有误！n");
		goto b;
	}
c:    printf("|—————请选择———————|n");
	printf("|----------1.查找班号----------|n");
	printf("|----------2.查找姓名----------|n");
	printf("|---Powered by CaptainUniverse_|n");
	printf("|———————★———————|nn");
	fflush(stdin);
	scanf("%c",&choice_3);
	if(choice_3!='1'&&choice_3!='2')
	{
		printf("输入有误！n");
		goto c;
	}
		
	printf("请输入查找内容:n"); 
	fflush(stdin);
    gets(key);
    
    begin=clock();
    if(choice_1=='1')
    {
		if(choice_3=='1')
			display(L,Sq_Search(L,key,by_class,choice_2),key);
		else if(choice_3=='2')
			display(L,Sq_Search(L,key,by_name,choice_2),key);
	}
	else if(choice_1=='2')
	{
		if(choice_3=='1')
			display(L,Binary_Search(L,key,by_class,choice_2),key);
		else if(choice_3=='2')
		{
			int *temp=Binary_Search(L,key,by_name,choice_2);
			if(temp[0]==TRUE) 
			{
				StudentList L_temp=(StudentList) malloc(sizeof (StudentList));
				L_temp->data=(Student *) malloc((temp[2]-temp[1]+1)*sizeof (Student));
				L_temp->length=temp[2]-temp[1]+1;
				for(int i=0;i<=temp[2]-temp[1];i++)
				L_temp->data[i]=L->data[temp[1]+i];	
				Insertsort(L_temp);
				int a[3]={TRUE,0,temp[2]-temp[1]};
				display(L_temp,a,key);
				}
		}
	}	
	end=clock();
    printf("用时：%g msnn",(double)(end-begin));
d:    printf("是否继续操作：n");
    printf("1.继续n");
    printf("2.退出n");
    fflush(stdin);
    scanf("%c",&choice_4);
    if(choice_4=='1')
    	goto start;
    else if(choice_4=='2')
    {
    	printf("感谢您的使用！再见！n");
		exit(0);
	}	
	else
	{
		printf("输入有误！n");
		goto d;
	}
}

写在最后：

2022.6.9 21：54

getFileList()函数写的太难看了第一次写随机生成数据文件等我有思路再改改

用了四种排序：直接插入排序、选择排序、快速排序、改进冒泡排序，两种查找：顺序查找、二分查找

每次操作后会显示过程所用时间更直观比较出不同数据、排序法、查找法的时间效率

数据结构与算法（C语言实现） 7-8.查找和排序算法的综合应用

C/C++/C#相关栏目本月热门文章