火车装箱

现有一批火车车厢需要按照每节车厢中所含货物数量进行连接发车

要求：

  • 其中每节车厢中包含两种元素 车厢号：TrainNum 以及所装载货物数量：GoodsNum；
  • 其中每节车厢以前车厢 -> 后车厢 的形式进行连接；
  • 按照每节车厢的GoodsNum的降序进行连接；

  • 自定义一个TrainCabin数据结构

    1
    2
    3
    4
    5
    struct TrainCabin{
    //TODO structure your struct
    };

  • 写出一个函数

    1
    2
    TrainCabin* AssembleTraninCabin(TrainCabin* TrainList);
    //选择你认为时间复杂度最小的算法进行编码

返回值为已按照以上要求排好序后的火车链表

输入

  • 第一个值为TrainNum
  • 第二个值为GoodsNum
  • 中间以|分割
  • 输入-1 以结束输入

Input：

1 | 3
2 | 5
3 | 7
4 | 2
5 | 0
-1

输出

  • 在控制台中打印排好序的火车列
  • 按照以下示例格式

Output：

| 3 | 7 | -> | 2 | 5 | -> | 1 | 3 | -> | 4 | 2 | -> | 5 | 0 |

题解

非常基础的一道考察数据抽象、数据结构构造、排序算法、单向链表的简单题…但今天的现场情况不容乐观

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream.h>
#include<stdlib.h>
typedef struct TrainCabin
{
	int TrainNum;
	int GoodsNum;
	struct TrainCabin *next;
}TrainCabin;
TrainCabin* AssembleTraninCabin(TrainCabin *TrainList)
{
	TrainCabin *i=TrainList;
	TrainCabin *j;
	TrainCabin *temp=(TrainCabin*)malloc(sizeof(TrainCabin));
	temp->next=NULL;
	while(i!=NULL)
	{
		j=i->next;
		while(j!=NULL)
		{
			if((*i).GoodsNum>(*j).GoodsNum)
			{
				(*temp).TrainNum=(*i).TrainNum;
				(*temp).GoodsNum=(*i).GoodsNum;
				(*i).TrainNum=(*j).TrainNum;
				(*i).GoodsNum=(*j).GoodsNum;
				(*j).TrainNum=(*temp).TrainNum;
				(*j).GoodsNum=(*temp).GoodsNum;
			}
			j=j->next;
		}
		i=i->next;
	}
	return TrainList;
}
void display(const TrainCabin *TrainList)
{
	while(TrainList->next!=NULL)
	{
		cout<<"|"<<(*TrainList).TrainNum<<"|"<<(*TrainList).GoodsNum<<"| -> ";
		TrainList=TrainList->next;
	}
	cout<<"|"<<(*TrainList).TrainNum<<"|"<<(*TrainList).GoodsNum<<"|"<<endl;
}
int main()
{
	int TrainNum=0,GoodsNum=0;
	TrainCabin *frist,*last;
	TrainCabin *temp;
	frist=(TrainCabin*)malloc(sizeof(TrainCabin));
	frist->next=NULL;
	last=frist;
	char input;
	while(1)
	{
		cin>>TrainNum;
		if(TrainNum==-1)
			break;
		cin>>input;
		cin>>GoodsNum;
		temp=(TrainCabin*)malloc(sizeof(TrainCabin));
		temp->TrainNum=TrainNum;
		temp->GoodsNum=GoodsNum;
		temp->next=NULL;
		last->next=temp;
		last=temp;
	}
	TrainCabin *result=AssembleTraninCabin((*frist).next);
	display(result);
	return 0;
}