尾插法创建链表、选择排序

解题思路:

注意事项:

参考代码:

#include <stdio.h>
#include <malloc.h>

typedef struct student
{
	int id;
	int score;
	struct student* next;
}Stu, * stu;

stu creat(int n)
{
	stu head = (stu)malloc(sizeof(Stu));
	if (head==NULL)
	{
		return NULL;
	}
	stu r = head;
	stu s;
	//尾插法
	for (int i = 0; i < n; i++)
	{
		s = (stu)malloc(sizeof(Stu));
		if (s==NULL)
		{
			return NULL;
		}
		scanf("%d%d", &s->id, &s->score);
		r->next = s;
		r = s;
		s->next = NULL;
	}
	return head;
}

void output(stu head)
{
	head = head->next;
	stu p;
	while (head!= NULL)
	{
		printf("%d %d\n", head->id, head->score);
		p = head;
		head = head->next;
		free(p);
	}	
}

stu connect(stu head1, stu head2)
{
	stu p = head1;//指向头结点
	while (p->next)//指向尾结点
	{
		p = p->next;
	}
	p->next = head2->next;//链表1连接链表2
	return head1;
}

void sort(stu head)
{
	
	stu rear = head;//创建一个指向头结点的指针
	//选择排序法
	while (rear->next)
	{
		//查找最小值
		stu q = rear->next;
		stu per = rear;//指向q的前驱结点
		stu min = rear->next;
		stu permin = rear;//指向最小值的前驱结点
		while (q)
		{
			if (q->id < min->id)
			{
				min = q;
				permin = per;
			}
			per = q;
			q = q->next;
		}
		//将最小值插入合适的位置
		permin->next = min->next;
		min->next = rear->next;
		rear->next = min;
		//
		rear = rear->next;
	}
}

int main()
{
	int n = 0, m = 0;
	scanf("%d%d", &n, &m);
	stu head1 = NULL;
	stu head2 = NULL;
	stu head3 = NULL;
	head1=creat(n);
	head2=creat(m);	
	head3 = connect(head1, head2);
	sort(head3);
	output(head3);
	return 0;
}