[数据结构与算法]2020软专高级程序语言T4

写出一个结构体，要求是一个单链表，里面装的是学生的学号、姓名、成绩还要把这个链表按照成绩由低到高排序。

以上得到的单链表设为单链表1。

读取一个文件里面的学生成绩等信息放到单链表2中。

将单链表1和单链表2归并排序。

#include<stdio.h>
#include<algorithm>
using namespace std;

typedef struct Student
{
	int xh;
	char name[20];
	int score;
	Student* next;
}*stu;

/*
创建结构体链表结点时用 stu xxx =(stu)malloc(sizeof(Student));
定义一个结构体链表结点指针时用  stu xxx;
*/ 

stu build1()//通过手动输入的方式建立第一个链表 
{
	stu head=(stu)malloc(sizeof(Student)); 
	int n=5;
	stu p1;
	p1=head;
	while(n--)
	{
		printf("请输入第%d个学生的信息：\n",5-n); 
		stu p=(stu)malloc(sizeof(Student));
		scanf("%d %s %d",&p->xh,&p->name,&p->score);
		p1->next=p;//head头结点不存信息，从head的下一个结点存信息 
		p1=p1->next;
	}
	p1->next=NULL;
	return head;
}

stu build2()//通过文件读入的形式建立第二个链表 
{
	stu head=(stu)malloc(sizeof(Student));
	stu p1=head;//定义尾插指针 
	
	//文件操作 
	FILE *fp;//定义文件指针 
	fp=fopen("original.txt","r");//只读打开文件，要么写绝对路径地址，要么将文件放入程序同目录 
	if(fp==NULL)//判断文件打开状态 
	{
		printf("FILE OPEN ERROR文件打开错误\n");
	}
	
	while(!feof(fp))//文件没有结束就继续读取文件 
	{
		stu p=(stu)malloc(sizeof(Student));
		fscanf(fp,"%d %s %d",&p->xh,&p->name,&p->score);
		p1->next=p;//尾插加入链表 
		p1=p1->next;
	}
	p1->next=NULL;//添加链表尾 
	return head;
}

void sort(stu head)//对第一个链表进行冒泡排序 
{
	printf("**********开始冒泡排序*******\n"); 
	
	stu p,q;
	p=head->next;
	while(p!=NULL)
	{
		q=p->next;
		while(q!=NULL)
		{
			if(p->score>q->score)
			{
				Student tmp;//先整体交换 
				tmp=*p;
				*p=*q;
				*q=tmp;
				tmp.next=p->next;//再更改next指针 
				p->next=q->next;
				q->next=tmp.next;
			}
			q=q->next;
		}
		p=p->next;
	}
}

stu merge(stu head1,stu head2)//对两个链表归并排序形成一个新的有序链表 
{
	stu p=head1->next;
	stu q=head2->next;
	
	stu newhead=(stu)malloc(sizeof(Student));//建立新链表的头结点 
	newhead->next=NULL;
	stu k=newhead;
	while(p!=NULL&&q!=NULL)
	{
		if(p->score<=q->score)//p所指的元素成绩低，将p接入新链表 
		{
			k->next=p;
			k=k->next;
			p=p->next;
		}
		else//否则将q接入新链表 
		{
			k->next=q;
			k=k->next;
			q=q->next;
		}
	}
	if(q!=NULL) 
	{
		k->next=q;
	}
	if(p!=NULL)
	{
		k->next=p;
	}
	return newhead;
}

void print(stu head)
{
	printf("******该链表中的学生输出如下******\n");
	stu p=head->next;
	while(p!=NULL)
	{
		printf("%d %s %d\n",p->xh,p->name,p->score);
		p=p->next;
	}
	printf("******该链表中的学生输出完毕******\n");
}

int main()
{
	stu head1=build1();
	stu head2=build2();
	sort(head1);
	print(head1);
	print(head2);
	stu newhead=merge(head1,head2);
	print(newhead);
	return 0;
}

/*
1 haha 100
2 heihei 200
3 dd 189
4 gg 50
5 aa 11
*/

/*
original.txt内容
191273 aaa 59
104046 bbb 78
104946 ccc 60
123129 ddd 84
345897 eee 96
345345 fff 51
346425 ggg 70
436525 hhh 65
345325 iii 89 
*/