课程设计(数据结构)all.doc

浙江工商大学课程授课提纲2009 / 2010学年 第一学期课程信息课程名称课程设计（数据结构）开课班级课程类型专业必修课学分1周学时17总学时17教学周第20周教室实验时间周一周五全天教学安排课程17课时教师主讲教师电子信箱答疑时间周一 周五答疑地点教材指定教材： “数据结构”（C语言版） 严蔚敏 吴伟民 编著 清华大学出版社参考书目：1、FUNDAMENTALS OF DATA STRUCTURES IN C Robert Kruse /C.L. Tonda / Bruce Leung2、“数据结构”（第三版）-使用C语言 朱战立 刘天时 编著 西安交通大学出版社考试安排课程设计结束时，现场检查程序和文档。教学目的见附录1课程要求见附录3周数时数教学内容20 17见附录2附录1一、 实验目的数据结构是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成在学习结束时完成一个较综合的实验。通过本课程的课程设计，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、 实验要求 问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。 数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案(必须连同算法一起考虑)，确定主要的数据结构及全程变量。对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。 算法设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，相当于C语言的过程或函数设计。 测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。 上机调试对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。三、 实习报告内容 问题描述： 包括目标、任务、条件和约束的描述。 设计： 数据结构设计和核心算法设计描述； 主控及功能模块层次结构； 主要功能模块的输入、处理(算法框架描述)和输出； 功能模块之间的调用与被调用关系等。 测试： 测试范例，测试结果，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。 使用说明和作业小结： 使用说明主要描述如何使用你的程序以及使用时的主要事项； 在小结中说明程序的改进思想、经验和体会，并回答教师布置的讨论题。整理一份程序清单及运行示例的结果。 将以上各项文字材料及程序清单等装订成册，形成一个完整的报告。附录22008级数据结构课程设计题目及基本要求如下：一系统类（一）运动会分数统计系统【问题描述】参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）【基本要求】（1）可以输入各个项目的前三名或前五名的成绩；（2）能统计各学校总分，（3）可以按学校编号或名称、学校总分、男女团体总分排序输出；（4）可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。（5）数据存入文件并能随时查询 （6）规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文提示，各学校分数为整型。界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（二）文章编辑系统【问题描述】输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；【基本要求】（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构可以使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；（三）宿舍管理查询系统【问题描述】为宿舍管理人员编写一个宿舍管理查询系统。【基本要求】（1）采用交互工作方式（2）建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)（3）查询菜单: (用二分查找实现以下操作)A.按姓名查询 B.按学号查询 C.按房号查询（4）保存任一查询结果到文件中（四）学生成绩管理系统【问题描述】现有学生成绩信息文件1（1.txt），内容如下姓名 学号 语文 数学 英语 张明明 01 67 78 82李成友 02 78 91 88张辉灿 03 68 82 56王露 04 56 45 77陈东明 05 67 38 47. . . . 学生成绩信息文件2（2.txt）,内容如下:姓名 学号 语文 数学 英语 陈果 31 57 68 82李华明 32 88 90 68张明东 33 48 42 56李明国 34 50 45 87陈道亮 35 47 58 77. . . . 【基本要求】（1）实现对两个文件数据进行合并，生成新文件3.txt（2）抽取出三科成绩中有补考的学生并保存在一个新文件4.txt（3）对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)（4）要求使用结构体,链或数组等实现上述要求.（5）其它功能：学生成绩信息的插入、删除、查找、追加、读入、显示、保存、拷贝、排序（五）通讯录管理系统【问题描述】编写一个通讯录管理系统。本系统应完成一下几方面的功能：1)输入信息enter();2)显示信息display( );3)查找以姓名作为关键字 search( );4)删除信息delete( );5)存盘save ( );6)装入load( ) ;【基本要求】1)每条信息至少包含 ：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项2)作为一个完整的系统，应具有友好的界面和较强的容错能力（六）哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 7）实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。【进一步要求】1)译码功能；2)显示哈夫曼树；3)界面设计的优化。（七）图书管理系统【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1)每种书的登记内容包括书号、书名、著作者、现存量和库存量；2)对书号建立索引表（线性表）以提高查找效率；3)系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。（八）散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步要求】1)设计不同的散列函数，比较冲突率；2)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。二游戏类（一）走迷宫游戏【问题描述】程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。【基本要求】1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2)迷宫的墙足够结实，老鼠不能穿墙而过；3)正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4)添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5)找出走出迷宫的所有路径，以及最短路径。利用序列化功能实现迷宫地图文件的存盘和读出等功能（二）利用栈求表达式的值，可供小学生作业，并能给出分数。【问题描述】建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。（四）编写一个五子棋的游戏程序。【问题描述】实现人与机对下的功能。【基本要求】1、要有棋盘；2、设计输、赢判断规则函数；3、给出下棋过程三、图类问题（一）地图着色问题【问题描述】已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。（二）学校超市选址问题（带权有向图的中心点）【问题描述】对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。（三）教学计划编制问题【问题描述】大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。【基本要求】（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。【测试数据】学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5语言的设计和分析C3，C4C6计算机原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1【实现提示】可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。（四）选址问题【问题描述】华联万家福超市要在某地建立一所地区级中央配送中心，要求该配送中心能够覆盖该地区五个连锁分店，分店的坐标及每月的销售量数据如下表所示，要求求出一个理论上的配送中心的位置。【测试数据一】位置坐标月销售量（TEU）连锁一分店（325，75）1200连锁二分店（400，150）250连锁三分店（450，350）450连锁四分店（350，400）350连锁五分店（25，450）450【测试数据二】位置坐标月销售量（TEU）连锁一分店（1，2）300连锁二分店（7，4）500连锁三分店（3，1）200连锁四分店（5，5）100连锁五分店（2，6）600四综合类问题（一）散列法的实验研究【问题描述】散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。（二）排序综合问题【问题描述】利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。【基本要求】1)至少采用五种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。（三）压缩器/解压器【问题描述】为了节省存储空间，常常需要把文本文件采用压缩编码的方式储存。例如：一个包含1000个x的字符串和2000个y的字符串的文本文件在不压缩时占用的空间为3002字节（每个x或每个y占用一个字节，两个字节用来表示串的结尾）。同样是这个文件，采用游程长度编码（run-length coding），可以存储为字符串1000x2000y，仅为10个字母，占用12个字节。若采用二进制表示游程长度（1000和2000）可以进一步节约空间。如果每个游程长度占用2个字节，则可以表示的最大游程长度为2*pow(16)，这样，上例中的字符串只需要用8个字节来存储。当要读取编码文件时，需要对其进行解码。由压缩器（compressor）对文件进行编码，由解压器（decompressor）进行解码。（1）长度-游程编码的压缩/解压；+（2）LZW压缩/解压（散列）；（1）长度-游程编码的压缩/解压；+（3）霍夫曼编码压缩/解压 (霍夫曼树) 【基本要求】要求选用二种压缩/解压策略实现压缩/解压器（1）为必选。输入的为本文文件（.txt），输出的为一种自定义的文件（.nz）。考虑当构成文本的字符集合为a,b,c,z,0,1,2,9时，请用实例测试你的压缩/解压器。你的压缩器会不会出现抖动？（压缩后的文本比原来的还要大）。扩充构成文本的字符集合以便使它适应更一般的情况。【实现提示】LZW：由Lempel、Ziv和Welch这三位科学家所开发的技术。该方法把文本的字符串映射为编码，首先，为该文本中所有可能出现的字母分别分配一个代码。例如：要压缩的对象是aaabbbbbbbaabaaba，由a和b组成。为a分配代码0,为b分配代码1。字符串和编码的关系被存储在字典中。字典如下：Key 01234567CodeAbAaaabbbbbbbbbaaaba LZW压缩器不断的在输入文件中寻找在字典中出现的最长的前缀p,并输出其相应的代码。若输入文件的下一个字符为c，则为pc分配下一个代码，并插入字典，这种策略称为LZW规则。相反，在解压时，编码表由压缩文件重新构造，LZW原则使这种重建成为可能。 如上例子，压缩时，文件中第一个在字典中出现的最长前缀是a, 输出其编码0,然后为字符串aa分配代码2，并插入到字典中。余下的字符串在字典中出现的最长前缀是aa,输出aa的对应代码2，同时为字符串aab分配代码3并将其插入到字典中。依次类推，由此，输出0214537 解压时，要输入代码，然后用代码所表示的文本来替换这些代码。代码到文本的映射可按下面的方法重建：首先把分配给单一字母的代码插入到字典中。象前面一样，字典的入口为key-code对。然而此时是根据给定的代码（key）去寻找相应的入口（而不是根据文本Code）。压缩文件中的第一个代码对应于单一的字母，因此可以由该字母代替。对于压缩文件中的其他代码p,要考虑两种情况：1）在字典中；2）不在字典中。在1）情况下，找到p对应的文本text(p)输出。并且，根据压缩原理可知，若在压缩文件中代码q写在p之前且text(q)是与q对应的文本，则压缩器会为文本text(q)（其后紧跟fc(p)，text(p)的第一个字符）分配一新代码。因此在字典中插入序偶（下一个代码，text(q)fc(p)）。 情况2）时，只有在当前文本段形如text(q)text(q)fc(q)且text(p)=text(q)fc(q)时才会发生。相应的压缩文件段是qp。在压缩过程中，为text(q)fc(q)分配的代码为p。在解压过程中，在用text(q)代替q后，又遇到代码p。然而，此时字典中没有与p对应的文本。因为这种情况只在解压文本段为text(p)text(q)fc(q)时才发生，因此可以对p解码。当遇到一个没有定义代码文本对的代码p时，p对应的文本为text(q)fc(q)，其中q为p前面的代码。如上例子：首先，初始化字典，在其中插入(0,a),(1,b)。压缩的第一个代码为0,则用a代替之。下一个代码2未定义，因为前一个代码为0，且text(0)=a,fc(0)=a,则text(2)=text(0)fc(0)=aa。因此用aa代替2,并把(2,aa)插入字典中。下个代码1由b来替换，并把(3,text(2)fc(1)=(3,aab)插入字典中。依次类推，得解压结果。霍夫曼编码：根据不同符号在文本中出现的不同的频率来进行压缩编码。假设文本是由a,u,x,z组成的字符串，若这个字符串的长度为1000，每个字符用一个字节来存储，共需1000个字节（即8000位）的空间。如果每个字符用2位二进制来编码（00=a,01=x,10=u,11=z），则用2000位二进制即可以表示1000个字符。此外，还需要一定的空间来存放编码表，可以采用如下格式来存储：符号个数：代码1，符号1，代码2，符号2，符号个数及每个符号分别用8位二进制来表示，每个代码需要占用log2(符号个数)位二进制。因此，上例中，代码表需占用5*8+4*2=48位，压缩比为8000/2048=3.9 。利用这种编码方法，字符串aaxuaxz的压缩码为二进制串00000110000111，每个字符的编码具有相同的位数（两位）。从左到右依次从位串中取出两位，通过查编码表边可以获得原字符串，这是解压缩过程。我们利用霍夫曼编码来实现压缩，必须：1） 必须获得不同字符的频率。2） 建立具有最小加权外部路径的二叉数（即霍夫曼树），树的外部结点用字符串中的字符表示，外部结点的权重（weight）即为该字符出现的频率。3） 遍历从根到外部结点的路径得到每个字符的编码。4） 使用字符的编码来代替字符串中的字符。为了方便解码，需要保存字符代码映射表或每个字符的频率表（在保存信息为频率表的情况下，解码需要重构霍夫曼数以获得相应的编码表）。构造霍夫曼树：首先从仅含一个外部结点的二叉树集合开始，每个外部结点代表字符串的一个不同的字符，其权重等于该字符的频率。此后不断的从集合中选择两棵具有最小权重的二叉树，并把它们合并成一棵新的二叉树，合并方法是把这两棵二叉树分别作为左右子树，然后增加一个新的根结点。新二叉树的权重为两棵子树的权重之和。这个过程一直可以持续到仅剩下一棵树为止。二叉树的集合可以使用有序表 /优先队列（基于队列/基于堆）实现。编码：构造完毕霍夫曼树后，可以对从根开始到外部结点（叶子）的路径进行编码，方法是向左孩子移动时取0，向右孩子移动时取1。【选作内容】对于策略2）我们用这种方法修改它：每当压缩/解压1024*x个字节后，重新初始化代码表。取文本长度为100K到200K之间，x=10，20，30，40和50。测试修改后的程序，请给出你的结论：采用那种x值比较好？对于霍夫曼编码：当文本中的字符出现的频率差别很大时，我们可以通过使用变长的编码来降低每个位串的长度。但是，怎样对使用变长编码的位串解码呢？我们可以发现：在得到的霍夫曼编码中，没有任何一个代码是另一个代码的前缀。因此与编码向匹配的实际的字符是唯一的。请用实现这样的变长策略，并验证它。（四）LL语法分析器【问题描述】语法分析器的功能是识别单词符号序列是否是给定文法的正确句子（程序）。LL分析法是实现上述功能的一种编译方面的算法。根据下列的例子实现LL语法分析法。【基本要求】给定文法：ETE E+TE| TFT T*FT| F(E)|i（1）求出的first集合内容FIRST(F)= (，i FIRST(T)=*, FIRST(T)=FIRST(F)-= (，i FIRST(E)=+, FIRST(E)= FIRST(T)-=(，i （2）求出follow集合的内容FOLLOW(E)=#, ) FOLLOW(E)=#, ) FOLLOW(T)=+, ), # FOLLOW(T)= FOLLOW(T)= +,),# FOLLOW(F)=*, + , ), # （3）构造分析表ETi+*()#EETTFETEETEE+TEETFTTFTTT*FTTFiF(E)（4）分析过程（判断句子i+i*i是否能有上述文法推导出来）1212步骤 符号栈 读入符号剩余符号串 使用规则1. E i+i*i# 2. ET i+i*i# E:=TE3. ETF i+i*i# T:=FT4. ET i i+i*i# F:= i5. ET + i*i# (出栈，读下一个符号）6. E i*i# T:= 7. ET+ i*i# E:=+TE12128.ET i *i# 9.ETF i *i# T:=FT10.ET i i *i# F:= i11.ET * i# 12.ETF* * i# T:=*FT13.ETF i # 14.ET i i # F:= i15.ET # 16.E # T:= 17. # E:= 结论：这个句子能由上述文法推导出来。（6）判断句子：（i+i）*i是否能由上述文法推导出来。五路径问题（一）最短路径问题【问题描述】有九个城市，其公路路网如下图所示，弧旁数字是该段公路的长度，有一批货物从城市x运往城市y，问走那条路最短，路线是怎么样的。【基本要求】用两种以上求解最短路径的方法，并比较这几种算法的性能。而且城市和公路要求能够添加。【测试数据一】【测试数据二】【测试数据三】公路路网系统自动生成（二）全国铁路运输网最佳经由问题【问题描述】这是上海铁路局目前仍在使用的行包托运软件中的一部分内部算法。该题目采用1995年年底我国铁路运输网的真实数据进行编程和运行验证。铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。【基本要求】（1） 查询某站所属的铁路线（2） 要求具备新增铁路线的管理功能（3） 要求具备新增车站的管理功能（4） 针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序（三）全国交通咨询模拟【问题描述】处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。【测试数据】徐州397乌鲁木齐哈尔滨长春沈阳天津郑州西安兰州成都上海昆明贵阳株州福州柳州广州深圳南宁189221611456681100967639907349676511242305704651622367409255607675140呼和浩特北京137674西宁大连534842武汉825南昌672【实现提示】（1）对全国城市交通图和班车时刻表及飞机航班表的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对于从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息。（2）以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。六、指派问题（一）指派问题【问题描述】有四批货物等待运走，这四批货物记做A、B、C、D，需要四量卡车来运输，这四辆卡车记做甲、乙、丙、丁。这四辆卡车运输这些货物需要不同的时间