求用直接插入法对一个链表进行升序排列的程序

发布网友 发布时间：2022-04-23 02:06

我来回答

共1个回答

热心网友 时间：2023-10-11 02:30

#include "stdio.h"
struct student
{

int number;
int score;
struct student *next;
struct student *before; /*由于要排序，所以要建立双向链表 */
}*Head_A,*Rear_A,*Head_B,*Rear_B,*p,*p1;

void main()
{
int i,j,Length_A,Length_B,Length_Z;
printf("此程序是把a,b两个链表合并并按学号升序排列.\n");
printf("a,b两个链表中的结点包括学号、成绩。\n");
printf("先分别输入两个链表的长度.\n");

printf("请输入a链表的长度:"); /*输入链表a*/
scanf("%d",&Length_A);

printf("请输入a链表结点中的学号和成绩\n");
printf(" 学号 成绩\n");
for(i=1;i<=Length_A;i++)
{
p=(struct student*)malloc(sizeof(struct student));
printf("请输入第%d个同学的学号和成绩:",i);
scanf("%d%d",&p->number,&p->score);
p->next=NULL;
if(i==1) {Head_A=p;Rear_A=p;p->before=NULL;}
else {p->before=Rear_A;Rear_A->next=p;Rear_A=p;}
}
printf("现在将输出a链表.\n"); /*输出链表a*/
printf(" 学号 成绩\n");
p=Head_A;
for(i=1;i<=Length_A;i++)
{
printf("第%d个同学:%d %d\n",i,p->number,p->score);
p=p->next;
}
printf("请输入b链表的长度:"); /*输入链表b*/
scanf("%d",&Length_B);

printf("请输入b链表结点中的学号和成绩\n");
printf(" 学号 成绩\n");
for(i=1;i<=Length_B;i++)
{
printf("第%d个同学的学号和成绩:",i);
scanf("%d%d",&p->number,&p->score);
p->next=NULL;
if(i==1) {Head_B=p;Rear_B=p;}
else {p->before=Rear_B;Rear_B->next=p;Rear_B=p;}
}
printf("现在将输出b链表.\n"); /*输出链表b*/
printf(" 学号 成绩\n");
p=Head_A;
for(i=1;i<=Length_B;i++)
{
printf("第%d位同学的学号和成绩：%d %d\n",i,p->number,p->score);
p=p->next;
}
printf("现在将a,b链表进行合并\n"); /*合并两链表*/
Rear_A->next=Head_B; /*将b链表的头指针地址赋值给a链表的尾部*/
Rear_A=Head_B;
printf("现在输出合并后的新链表\n"); /*输出新链表*/
Length_Z=Length_A+Length_B; /*长度变为两链表之和*/
p=Head_A;

printf(" 学号 成绩\n");
for(i=1;i<=Length_Z;i++)
{
printf("第%d位同学的学号和成绩:%d %d\n",i,p->number,p->score);
p=p->next;
}
p1=(struct student*)malloc(sizeof(struct student));
printf("现在进行排序工作\n");

for(i=1;i<Length_Z;i++)
{ p=Head_A;
p->before=NULL;
p1=p->next;
for(j=1;j<=Length_Z-i;j++)
{
if(p->number>p->next->number)
{
p1=p->next;
p->next=p1->next;
p1->next->before=p1->before;
p1->next=p1->before;
if(j==1) {p->before=p1;Head_A=p1;p1->before=NULL;}
else {p1->before=p->before;p1->before->next=p1;}
p1=p->next;
}
else {p=p1;p1=p1->next;}
}
}
/*经过上面的程序，已经把顺序排好*/
printf("现在将输出已按升序排列的新链表.\n");
printf(" 学号 成绩\n");
for(i=1;i<=Length_Z;i++)
{
printf("第%d位同学的学号和成绩:%d %d\n",i,p->number,p->score);
p=p->next;
}

}