排课系统论文

1、 摘 要 i 摘 要 排课问题是所有教育行业都要面对的问题，尤其针对中学纷繁复杂的课程和专业， 一直没有很好解决方法。但这又是每个学校在每个学期都会碰到的必修课。本文在相 关理论的指导下，在分析以往一些排课软件的基础上，提出一种排课系统的设计方法， 对一些具体的问题给出相应解决方案。希望对于相关部门有所帮助。此系统主要被分 为三个部分：界面的设计、排课算法的设计、以及报表的自动生成。纵观全局，我们 确定用 visual basic 语言作为程序设计语言以及运用 sqlserver2005 数据库作为后 台的数据库支持。 关键词：关键词：排课、排课系统、设计、中学 abstract ii abs

2、tract course arranging problem is a problem which working in the development of education is facing. especially, there is no a good solution for this matter of the college. however, it is also a necessary administration task for every school in every semester. this essay, with the correlative theory

3、s guidance, on the basis of analyzing some courses-arraying software, proposes a design method of commonly used courses arraying information system in college, and solves some of the certain problems. hoping it is useful for the relative department. the system consist of three parts: the interface d

4、esign, the algorithm of course timetable system, and printing the tables. on the whole, we decided to use vb computer language to design and sqlserver2005 data base to support. key words: courses arranging; courses arrangement management system; design; college 学院工学学士学位论文 摘要 1 目 录 摘 要 .i abstract .i

5、i 第一章 引言 .1 第二章 可行性研究 .2 2.1 系统目标及任务.2 2.2 开发工具的选择和介绍.2 2.3 对现有的排课系统的分析.4 2.4 系统的逻辑模型.5 2.4.1 系统结构图.5 2.4.2 系统流程图.5 2.4.3 数据字典.6 2.5 系统的可行性.7 2.5.1 经济可行性分析.7 2.5.2 操作可行性分析.7 2.5.3 技术可行性分析.8 2.6 成本效益分析.8 第三章 需求分析 .9 3.1 系统的运行环境要求.9 3.1.1 硬件要求.9 3.1.2 软件要求.9 3.2 系统的功能要求.9 3.3 系统的性能要求.10 3.3.1 e-r图.11

6、第四章 总体设计 .12 4.1 模块设计.12 学院工学学士学位论文 摘要 2 4.2 功能分解.13 4.3 数据库设计.13 4.3.1 定义属性表.13 4.4 排课系统总构架.18 第五章 详细设计及代码设计 .19 5.1 用户界面设计.19 5.1.1 简单易用和个性化需求.19 5.1.2 对数据的查询.19 5.1.3 系统菜单功能.19 5.2 详细设计.21 5.2.1 创建系统主界面.21 5.2.2“条件设置”模块.24 5.2.2“课表管理”模块.29 5.2.3“系统管理”模块.32 第六章 测试 .57 6.1 排课系统功能测试.57 6.2 排课系统课表合理性

7、测试.57 6.3 该系统的不足和改进方案.57 第七章 总结 .59 致谢 .60 参考文献 .61 第一章 引言 第 1 页 共 50 页 第一章 引言 随着信息技术的飞速发展，各个行业的信息化势在必行。正所谓“科学技术是第一 生产力”，科技的进步大大地提高了生产率。然而，在中学这个知识密集的地方，如何 才能提高办学效率，更好地完成教学任务，跟上社会发展步伐，这是一个摆在教学工 作者面前的一个迫切的问题。应用信息化来改造传统的教学管理模式是一个重要途径。 近几年来，随着各中学办公自动化工作的推进，教务管理自动化也被摆上了日程。 在教务工作中占有很大比重的一项就是每学期的课程排定工作。由于教

8、工、教室和设 备的相对紧张，如何进行合理地安排和分配，从而充分利用教学资源是我们不得不面 对的问题。而人工进行排课不仅任务重，效率低，而且易出错，难于维护，想要排出 一张各方面都满意的课表非常困难。并且随着中学规模的扩大手工排课的难度和工作 量呈几何级数增长。 排课系统正是为了减轻教务人员的工作量，实现教务工作自动化，解决排课这一 老大难问题的教务办公软件。尤其针对中学的排课一直都没有很好的解决方法，但是 此问题又是每个学校在每个学期都会碰到的必要行政作业。本文在相关理论的指导下， 在分析以往一些排课软件的基础上，提出一个中学通用排课系统的设计方法，并对一 些具体的问题给出相应解决方案。但是，

9、由于技术、经验的有限和数据量过大，目前 我们很难做出一个满足所有需要的排课系统。因为它不仅要考虑到教室冲突问题和教 师冲突问题，还要考虑到分段课、单双周课时的资源利用问题；另外由于中学的教学 特点，还要处理合班课、分班课、体育课与选修课等特殊课程。针对这些问题，在此 专门对数据库设计作了一些探索，并于架构的选择和模块的划分上经过精心调整，在 菜单的设计上也体现了人性化的操作。该设计贴近用户需求，功能完整，架构合理， 并用大量的框图模型体现了系统的规划。 本软件使用 microsoft basic 6.0 进行编写和 sqlserver2005 数据库相连接。数据 库的特点：1.实现数据共享 2

10、.实现数据独立 3.减少了数据冗余度 4.避免了数据不一致 性 5.加强了对数据的保护。一个数据库应用系统通常是由数据库和应用程序两部分组 成，它们是在数据库管理系统支持下设计和开发出来的。 第二章 可行性研究 第 2 页 共 50 页 第二章 可行性研究 2.1 系统目标及任务 本软件主要是适用于高等学校教务部门的办公软件，运用此软件，可以免去工作 人员繁忙而枯燥的手工排课过程，直接通过计算机进行排课。我的任务是完成排课系 统的界面设计以及排课后报表的生成。 2.2 开发工具的选择和介绍 针对目前世界上流行的大量软件和开发工具，经过认真分析其优缺点，结合排课 系统的需要和目前的硬件环境，我们

11、选用微软 windows 平台下的 visual basic 6.0（简写为 vb6.0）作为软件开发工具和 sqlserver2005 数据库进行连接。 作为数据库系统的开发，visual basic 是一个非常理想选择。visual basic 是一种可 视化的、面对对象和条用事件驱动方式的结构化高级程序设计，可用于开发 windows 环境下的应用程序。它简单易学、效率高，且功能强大，可以与 windows 的专业开发 工具 sdk 相媲美，而且程序开发人员不必具有 c/c+编程基础。在 visual basic 环境 下，利用事件驱动的编程机制、新颖易用的可视化设计工具，使用 wind

12、ows 内部的应 用程序接口(api)函数，以及动态链接库(dll)、动态数据交换(dde)、对象的链接与嵌 入(ole)、开放式数据访问(odbc)等技术，可以高效、快速地开发出 windows 环境下 功能强大、图形界面丰富的应用软件系统。总的来说，visual basic 具有以下特点： 1、可视化编程、可视化编程 用传统程序设计语言设计程序时，都是通过编写程序代码来设计用户界面，在设 计过程中看不到界面的实际显示效果，必须编译后运行程序才能观察。如果对界面的 效果不满意，还要回到程序中修改。有时候，这种编程-编译-修改的操作可能要反复多 次，大大影响了软件开发效率。visual bas

13、ic 提供了可视化设计工具，把 windows 界面 设计的复杂性“封装”起来，开发人员不必为界面设计而编写大量程序代码。只需要按 设计要求的屏幕布局，用系统提供的工具，在屏幕上画出各种“部件”，即图形对象， 并设置这些图形对象的属性。visual basic 自动产生界面设计代码，程序设计人员只需 要编写实现程序功能的那部分代码，从而可以大大提高程序设计的效率。 第二章 可行性研究 第 3 页 共 50 页 2、面向对象的程序设计、面向对象的程序设计 4.0 版 以后的 visual basic 支持面向对象的程序设计，但它与一般的面向对象的程 序设计语言(c+)不完全相同。在一般的面向对象

14、程序设计语言中，对象由程序代码和 数据组成，是抽象的概念；而 visual basic 则是应用面向对象的程序设计方法(oop)， 把程序和数据封装起来作为一个对象，并为每个对象赋予应有的属性，使对象成为实 在的东西。在设计对象时，不必编写建立和描述每个对象的程序代码，而是用工具画 在界面上，visual basic 自动生成对象的程序代码并封装起来。每个对象以图形方式显 示在界面上，都是可视的。 3、结构化程序设计语言、结构化程序设计语言 visual basic 是在 basic 语言的基础上发展起来的，具有高级程序设计语言的语句 结构，接近于自然语言和人类的逻辑思维方式。visual b

15、asic 语句简单易懂，其编辑器 支持彩色代码，可自动进行语法错误检查，同时具有功能强大且使用灵活的调试器和 编译器。visual basic 是解释型语言，在输入代码的同时，解释系统将高级语言分解翻 译成计算机可以识别的机器指令，并判断每个语句的语法错误。在设计 visual basic 程 序的过程中，随时可以运行程序，而在整个程序设计好之后，可以编译生成可执行文 件(.exe)，脱离 visual basic 环境，直接在 windows 环境下运行。 4、事件驱动编程机制、事件驱动编程机制 visual basic 通过事件来执行对象的操作。一个对象可能会产生多个事件，每个事 件都可以

16、通过一段程序来响应。例如，命令按钮是一个对象，当用户单击该按钮时， 将产生一个“单击”(click)事件，而在产生该事件时将执行一段程序，用来实现指定的 操作。 在用 visual basic 设计大型应用软件时，不必建立具有明显开始和结束的程序，而 是编写若干个微小的子程序，即过程。这些过程分别面向不同的对象，由用户操作引 发某个事件来驱动完成某种特定的功能，或者由事件驱动程序调用通用过程来执行指 定的操作，这样可以方便编程人员，提高效率。 5、访问数据库、访问数据库 visual basic 具有强大的数据库管理功能，利用数据控件和数据库管理窗口，可以 直接建立或处理 sqlserver2

17、005 数据库，并提供了强大的数据存储功能。visual basic 提供开放式数据连接，即 odbc 功能，可通过直接访问或建立连接的方式使用并 操作后台大型网络数据库，如 sql server，oracle 等。在应用程序中，可以使用结构 第二章 可行性研究 第 4 页 共 50 页 化查询语言 sql 数据标准，直接访问服务器上的数据库。 6、对象的链接与嵌入、对象的链接与嵌入(ole) 对象的链接与嵌入(ole)将每个应用程序都看作是一个对象(object)，将不同的对象 链接(link)起来，再嵌入(embed)某个应用程序中，从而可以得到具有声音、影像、图像、 动画、文字等各种信息

18、的集合式的文件。ole 技术是 microsoft 公司对象技术的战略， 它把多个应用程序合为一体，将每个应用程序看作是一个对象进行链接和嵌入，是一 种应用程序一体化的技术。利用 ole 技术，可以方便地建立复合式文档(compound document)，这种文档由来自多个不同应用程序的对象组成，文档中的每个对象都与原 来的应用程序相联系，并可执行与原来应用程序完全相同的操作。 7、动态链接库、动态链接库(dll) visual basic 是一种高级程序设计语言，不具备低级语言的功能，对访问机器硬件 的操作不太容易实现。但它可以通过动态链接库技术将 c/c+或汇编语言编写的程序 加入到 v

19、isual basic 应用程序中，可以像调用内部函数一样调用其他语言编写的函数。 此外，通过动态链接库，还可以调用 windows 应用程序接口(api)函数，实现 sdk 所 具有的功能。 2.3 对现有的排课系统的分析 随着我国市场经济的快速发展和信息化水平的不断提高，如何利用先进的管理手 段，提高教育单位教学排课管理的水平，是当今社会所面临的一个课题。提高教育管 理水平，必须全方位地提高教育管理意识。只有高标准、高质量的管理才能满足教育 事业的发展需求。面对信息时代的挑战，利用高科技手段来提高教学排课管理无疑是 一条行之有效的途径。在某种意义上，信息与科技在教学管理与现代化建设中显现出

20、 越来越重要的地位。教学排课管理方面的信息化与科学化，已成为现代化生活水平步 入高台阶的重要标志。 有关排课管理系统的软件市面上有不少，教学管理人员也试用过一些，但总觉得 不是很好用，不能完全满足我们的要求，所以都放弃用这些软件了，改为每次输入数 据后，用手工更改数据库存量和安排课程，另外课表也无法用限制条件自动生成.以及 直接导出到 excle 表中，所以，迫切希望有一套完全适合排课管理应用的软件，以减 轻管理人员的工作负担。 另一方面由于这类软件大多数是单机版的，现在也有不少是网络板的，但大部份 第二章 可行性研究 第 5 页 共 50 页 都是在本地网络上运行的。因此系统的开发方向应当是

21、面向网络版的排课管理系统开 发。这点在今后的学习中将不断完善。 2.4 系统的逻辑模型 2.4.1 系统结构图 图 21 系统结构图 chart 2-1 structure system 2.4.2 系统流程图 为了实现管理信息系统的计算机化，仅仅用文字来描述信息的流动和存储还远远 不够，还要进一步调查分析舍去物质流，抽象出信息流，绘制出数据流程图，并对各 种数据的属性和各项处理功能进行详细分析。系统分析的主要成果是系统的逻辑模型。 本系统主要是以数据流图、数据字典和 e-r 图为主要描述工具来勾画系统的概貌。 数据流图（dfd，data flow diagram）是描述数据处理过程的有力工具

22、。数据流图 从数据传递和加工的角度，以图形的方式刻画数据流从输入到输出的移动变换过程。 用户登录身份验证 排课 系统 排课 编辑 自动生成 课表 查询打印 课表 系统数据初 始化 退出系统 帮助 编辑班级 信息编辑教室 信息编辑教师 信息编辑教学 计划 查询班级 课程表 查询教室 课程表 表 查询教师 课程表 第二章 可行性研究 第 6 页 共 50 页 正确用户 读数据 写数据 图 22 系统流程图 chart 2-2 system diagram 2.4.3 数据字典 名字：班级编号 描述：唯一地标识班级库表中一个特定班级的关键域 定义：班级编号=10char 位置：编辑班级信息，课程信息

23、，班级课程，班级课程表 名字：教室编号 描述：唯一地标识教室库表中一个特定教室的关键域 定义：教室编号=10char 位置：编辑教室信息，教室课程表 名字：教师编号 描述：唯一地标识教师库表中一个特定教师的关键域 定义：教师编号=10char 位置：编辑教师信息，班级课程，教师课程表 名字：学院编号 描述：唯一地标识学院库表中一个特定学院的关键域 定义：学院编号=10char 位置：编辑教师信息 用户 登录 功能 模块 的使 用 数据库 第二章 可行性研究 第 7 页 共 50 页 名字：班级课程表 描述：每学期一个确定班级的上课情况信息表 定义：班级课程表=班级名称+课程名称+上课地点 位置

24、：输出到打印机 名字：课程编号 描述：唯一地标识课程库表中一门特定课程的关键域 定义：课程编号=10char 位置：编辑课程信息，班级课程 名字：教室课程表 描述：每学期一个确定教室的上课时间安排情况信息表 定义：教室课程表=教室名称+班级名称 位置：输出到打印机 名称：教师课程表 描述：每学期每个教师的上课情况信息表 定义：教师课程表=教师姓名+课程名称+班级名称+教室名称 位置：输出到打印机 2.5 系统的可行性 2.5.1 经济可行性分析 本系统开发简单但要耗去一定的时间，所用的开发工具和软件都差不多是免费的。 本系统在以后的使用中对于教育办公自动化管理，节省教育人力、物力资源等都有很

25、大的帮助。由此可见，开发此系统在经济上是完全可行的。 第二章 可行性研究 第 8 页 共 50 页 2.5.2 操作可行性分析 如今的计算机已经走进千家万户，硬件成本的下降，导致计算机购买成本的降低. 我的这套系统是利用自己的计算机加微软的集成开发环境 microsoft visual basic6.0 作 为软件的开发平台和 sqlserver2005 数据库连接。使开发出来的系统有直观的用户 界面、有良好的安全性设置、有详细的操作说明书，这样更使各类用户很快地掌握系 统的使用方法和操作，因此在操作上是可行的。 2.5.3 技术可行性分析 从目前 it 业界比较流行的数据库开发、管理软件来看

26、，对于比较简单的中小型数 据库，vb 和 sqlserver2005 的结合无疑是在实际应用中较为成功的一种解决方案。 为用户提供了业界软件开发一直坚持的操作简单的用户界面、完善强大的数据库操作 功能和简洁明了的数据库接口。所以技术实行起来相对会容易。 2.6 成本效益分析 本系统的开发平台和开发工具都是免费提供的，所以不存在经济成本问题。由于 本软件还处于开发初期，所开发出的软件需要不断的修改和维护，就效益而言，它取 代了传统的手工排课方式，节省了人力和时间。如果要创造更高的效益需要对系统进 行更多的优化。 第四章 总体设计 第 9 页 共 50 页 第三章 需求分析 3.1 系统的运行环境

27、要求 3.1.1 硬件要求 1 486/dx66mhz 以上 cpu 2 内存 16m 以上(使用 windows nt 需要 32m 以上内存) 3 硬盘容量 1gb 以上(典型安装需要 128mb 硬盘空间,完全安装须要 147mb 硬盘 空间,外加 microsoft 开发者文档 67mb 硬盘空间) 4 vga 以上分辨率的显示器. 5 一个 cd-rom 驱动器 6 鼠标、打印机 3.1.2 软件要求 1 操作系统应使用 microsoft windows95 及以上版本或者更高版本。 2 安装有 visual basic 语言及 sql server2000 数据库。 3.2 系统

28、的功能要求 利用计算机实现计算机自动排课管理势在必行。对于教育单位来说，利用计算机 支持其高效率完成排课管理的日常事务，是适应现代教学制度要求、推动教学管理走 向科学化、规范化的必要条件；而排课管理是一项琐碎、复杂而又十分细致的工作， 课表信息录入,教师授课安排,限制条件输入,课表的自动生成等管理,一般不允许出错， 如果实行手工操作,须手工填制大量的表格,这就会耗费教育工作人员大量的时间和精力， 计算机进行排课工作的管理，不仅能够保证各项信息准确无误、快速输出，同时计算 机具有手工管理所无法比拟的优点.例如:检索迅速、查找方便、可靠性高、存储量大、 保密性好、寿命长、成本低等。这些优点能够极大

29、地提高排课管理的效率,也是教育的 第四章 总体设计 第 10 页 共 50 页 科学化、正规化管理,与世界接轨的重要条件。 3.3 系统的性能要求 本系统在性能上应达到如下要求： 系统软件运行应该速度快、稳定、可靠，具有很高的健壮性和容错、纠错 能力； 系统软件操作上应简单、方便，界面简洁明了、美观； 系统软件应能具有较高的安全性，对内对外都有严格的身份认证和数据保 密的措施； 系统软件在结构上应具有很好的可扩展性，便于将来的功能扩展和维护； 数据计算准确无误，精确度符合业务的需要。 第四章 总体设计 第 11 页 共 50 页 3.3.1 e-r 图 1.教师 e-r 图 图 31 教师 e

30、-r chart 3-1 the diagram of teachers e-r 2.班级 e-r 图 图 32 班级 e-r chart 3-2 the diagram of class e-r 3.课程 e-r 图 图 33 课程 e-r chart 3-3 the diagram of courses e-r 教师 教师编号姓名职称 班级 学院 班级编号 专业 班级人数 课程 课名学时 课程编号 第四章 总体设计 第 12 页 共 50 页 4.教室 e-r 图 图 3-4 教室 e-r chart 3-4 the diagram of classrooms e-r 第四章 总体设计 4

31、.1 模块设计 模块是软件结构的基础，软件结构的好坏完全由模块的属性体现出来，把软件模 块化的目的是为了降低软件复杂性，使软件设计，测试，调试，维护等工作变得简易， 但随着模块数目的增加，通过接口连接这些模块的工作量也随之增加。从这些特性可 得出如图的一条总的成本（或工作量）曲线，在考虑模块化时，应尽量使模块数接近 于图中的 m，它使得研制成本最小，而且应尽量避免不足的模块化或超量。 图 41 模块与成本关系图 chart 4-1 relation between module and cost 教室名称 容纳人数 教室编号 教室 第四章 总体设计 第 13 页 共 50 页 基于上述原因，在

32、进行总体规划的初步设想中，以中学各种资源和资源的分配为 依据，综合多种相关因素，将该系统划分成以下六个子功能模块：基本信息管理子系 统、用户管理子系统、数据管理子系统、班级课程管理子系统、排课管理子系统、课 表查询子系统。在数据库设计上，遵循“功能分离，数据共享”的原则，将数据库分成 基础数据库及目标数据库两大部分，其中，基础数据库又可分为初始设置信息库、基 本信息库、用户信息库三个功能子库。目标库主要存放系统运行过程中的动态数据， 目标方案等。 4.2 功能分解 基本信息管理子系统功能：班级信息，教室信息和教室信息的添加、保存、编辑 和删除： 1、用户管理子系统功能：用户密码的设置和修改，用

33、户权限的设置，用户重新登 陆； 2、数据管理子系统功能：包括对教室、教师、班级、班级课程和课表数据的保存、 查询、更新、删除； 3、班级课程管理子系统功能：某一确定的学期的教学工作计划，对于班级而言， 每门课程的学时、开始周、结束周以及每门课程的任课教师，该子系统对班级课程进 行管理和完善； 4、排课管理子系统功能：包括自动排课，手动排课两个部分； 5、课表查询子系统功能：对于具体的班级、教师、教室进行课表查询，打印； 4.3 数据库设计 排课管理系统是一项复杂的系统工程，其间需要大量的数据来支撑，从某种程度 上来讲，排课管理系统的设计过程，其实也就是一个规范和完整的数据库设计过程。 经过多年

34、的发展，关系型数据库系统（rdbms）是最成熟的一种数据库管理模式，也 是当前最流行的数据库管理系统。故在此也采用该模式（在加一些关系数据库的介绍） 。 第四章 总体设计 第 14 页 共 50 页 4.3.1 定义属性表 1 班级信息表 表 1 班级信息表 字段名称数据类型可否为空说明 班级名称 nvarchar(50) 主键班级名称 班级人数 int(4) null 本班人数 所在教室 nvarchar(50)not null 班级所在教室 班主任 nvarchar(50)null 班主任姓名 2 课程信息表 表 2 课程信息表 字段名称数据类型可否为空说明 课程名称 nvarchar(5

35、0) 主键课程名称 总节数 int(4)not null 教学节数 每周节数 int(4)not null 每周课程节数 3 信息表 表 3 班级课程信息表 字段名称数据类型可否为空说明 第四章 总体设计 第 15 页 共 50 页 分配 id numxeric(9) 主键标示种子 1 自增 1 班级名称 nvarchar(50) 外键主表为班级信息 课程名称 nvarchar(50) 外键主表为课程信息 总节数 int(4)not null 教学节数 每周节数 int(4)not null 每周课程节数 课程分布 char(14)not null 星期 任课教师 char(6) 外键主表为教

36、师信息 4 教师信息表 表 4 教师信息表 字段名称数据类型可否为空说明 教师编号 char(6) 主键6 位编码 教师姓名 nvarchar(50)not null 教师姓名 所任课程 nvarchar(50) 外键主表为课程信息 电话 nvarchar(50)null 联系电话 邮箱 nvarchar(50)null 联系邮箱 5 时间段信息表 表 5 时间段信息表 字段名称数据类型可否为空说明 第四章 总体设计 第 16 页 共 50 页 节号 char(6) 主键如“第一节” 时间段 nvarchar(50)not null 时间段 备注text（16） null 时间段备注 6 排课

37、信息表 表 6 排课信息表 字段名称数据类型可否为空说明 排课 id numxeric(9) 主键标种子 1 自增 1 班级名称 nvarchar(50) 外键主表为班级信息 节号 char(6) 外键主表为时间段信 息 星期一 nvarchar(50)null 课程名称 星期二 nvarchar(50)null 课程名称 星期三 nvarchar(50)null 课程名称 星期四 nvarchar(50)null 课程名称 星期五 nvarchar(50)null 课程名称 星期六 nvarchar(50)null 课程名称 星期日 nvarchar(50)null 课程名称 7 用户信息表

38、 表 7 用户信息表 第四章 总体设计 第 17 页 共 50 页 字段名称数据类型可否为空说明用户 id 用户 id char(6) 主键6 位的 用户名称 char(10)not null 用户名称 用户类别 char(10)not null 教师、管理人员 密码 char(10)null 密码少于 10 位 电话 nvarchar(50)null 电话 邮箱 nvarchar(50)null 邮箱地址 第四章 总体设计 第 18 页 共 50 页 4.4 排课系统总构架 图 48 系统总架构 chart 4-8 system frame 4.4 回溯算法研究 回溯法(探索与回溯法 )是一

39、种选优搜索法，按选优条件向前搜索，以达到目标。但当探索 到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再 走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 1、回溯法的一般描述 可用回溯法求解的问题 p，通常要能表达为：对于已知的由n 元组（x1，x2，xn） 组成的一个状态空间 e=（x1，x2，xn）xisi ，i=1，2，n，给定关于 n 元组 中的一个分量的一个约束集 d，要求 e 中满足 d 的全部约束条件的所有 n 元组。其中 si 是 分量 xi 的定义域，且 |si| 有限，i=1，2，n。我们称 e 中满足 d 的全部约束条件的

40、任 一 n 元组为问题 p 的一个解。 基本信息录入 资源要求设置 开始排课 优先级高先排 检查排课冲突 生成课表查询课表 打印课表 第四章 总体设计 第 19 页 共 50 页 解问题 p 的最朴素的方法就是枚举法，即对e 中的所有 n 元组逐一地检测其是否满足 d 的全部约束，若满足，则为问题p 的一个解。但显然，其计算量是相当大的。 我们发现，对于许多问题，所给定的约束集d 具有完备性，即 i 元组（x1，x2，xi ）满足 d 中仅涉及到 x1，x2，xi 的所有约束意味着 j（ji）元组（x1，x2，xj） 一定也满足 d 中仅涉及到 x1，x2，xj 的所有约束， i=1，2，n。

41、换句话说，只要存 在 0jn-1，使得（x1，x2，xj）违反 d 中仅涉及到 x1，x2，xj 的约束之一，则以 （x1，x2，xj）为前缀的任何 n 元组（x1，x2，xj，xj+1，xn）一定也违反 d 中仅涉及到 x1，x2，xi 的一个约束， nij。因此，对于约束集 d 具有完备性的问题 p，一旦检测断定某个 j 元组（x1，x2，xj）违反 d 中仅涉及 x1，x2，xj 的一个约 束，就可以肯定，以（ x1，x2，xj）为前缀的任何 n 元组（x1，x2，xj，xj+1， ，xn）都不会是问题 p 的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题， 利用这类问题的上

42、述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题 p 的 n 元组的状态空间 e 表示成一棵高为 n 的带权有序树 t，把在 e 中求问题 p 的所有解转化为在 t 中搜索问题 p 的所有解。树 t 类似于检索树，它可以这样 构造： 设 si 中的元素可排成 xi(1) ，xi(2) ，xi(mi-1) ，|si| =mi，i=1，2，n。从根 开始，让 t 的第 i 层的每一个结点都有 mi 个儿子。这 mi 个儿子到它们的双亲的边，按从左 到右的次序，分别带权 xi+1(1) ，xi+1(2) ，xi+1(mi) ，i=0，1，2，n-1。照这种 构造方式， e 中的一个 n 元

43、组（x1，x2，xn）对应于 t 中的一个叶子结点， t 的根到这 个叶子结点的路径上依次的 n 条边的权分别为 x1，x2，xn，反之亦然。另外，对于任意 的 0in-1，e 中 n 元组（x1，x2，xn）的一个前缀 i 元组（x1，x2，xi）对应于 t 中的一个非叶子结点， t 的根到这个非叶子结点的路径上依次的i 条边的权分别为 x1，x2 ，xi，反之亦然。特别， e 中的任意一个 n 元组的空前缀（），对应于 t 的根。 因而，在 e 中寻找问题 p 的一个解等价于在 t 中搜索一个叶子结点，要求从t 的根到 该叶子结点的路径上依次的 n 条边相应带的 n 个权 x1，x2，xn

44、 满足约束集 d 的全部约 束。在 t 中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深 入，即依次搜索满足约束条件的前缀1 元组（x1i） 、前缀 2 元组（x1，x2） 、，前缀 i 元 组（x1，x2，xi） ，直到 i=n 为止。 在回溯法中，上述引入的树被称为问题p 的状态空间树；树 t 上任意一个结点被称为问 题 p 的状态结点；树 t 上的任意一个叶子结点被称为问题p 的一个解状态结点；树 t 上满 第四章 总体设计 第 20 页 共 50 页 足约束集 d 的全部约束的任意一个叶子结点 被称为问题 p 的一个回答状态结点，它对应 于 问题 p 的一个解

45、 第五章 详细设计 第 21 页 共 50 页 第五章 详细设计及代码设计 5.1 用户界面设计 随着视窗操作系统的全面推广和流行，如今 gui 已经成为业界用户接口的一个标 准。在本系统的设计过程中，也按照 gui 的设计原则来设计用户接口，给用户提供一 个友好的人机交互界面。具体来说，将按照以下几点原则来设计。 5.1.1 简单易用和个性化需求 无论什么系统，面向什么使用者，都应该以简单易用而不显枯燥为标准。本系统 使用图形化的用户界面，整个界面功能键的设定和窗体布局，完全具有独特统一的风 格。 5.1.2 对数据的查询 查询是信息系统中不可缺少的功能。本系统设计的是一种可对任意指定的表、

46、按 所有字段进行的查询。查询的结果，在本系统中用数据窗口对象显示输出。对于查询 的结果，用户也可以根据自己的需求，选择显示的字段和设计自己的视图。当然，系 统下一步应该提供的功能就是根据查询结果，生成各式各类的报表。 5.1.3 系统菜单功能 在实际的系统设计中,菜单可分为两种类型,即下拉式菜单和弹出式菜单,下拉式菜单 系统中,一般有一个主菜单,其中包括若干个选择项.主菜单单的每一项又可下拉出下一级 子菜单.这样用一个个的窗口的形式弹出在屏幕上,它是通过菜单编辑器建立,其步骤如下： 1)选取要建立菜单的窗体 2)从“工具”菜单中,选取“菜单编辑器”建立如下图所示的系统主菜单： 第五章 详细设计

47、 第 22 页 共 50 页 图 51 菜单编辑 chart 5-1 menu edit 基本信息输入 基本信息输入菜单是让录入员输入和修改课程信息、班级信息、教师信息、 教室信息基本数据，数据管理包括课程、班级、教师、教室、课表数据的查询， 打印。 班级信息中包括班级编号、班级名称、班级人数以及添加、保存、查询、编 辑、删除等功能。如下为班级信息的界面： 排课系统是用来自动生成课表并管理课表文档的系统。本系统主要用于 满足中小学的排课要求，排课条件有班级信息，课程信息、教师信息和教学时间 信息。一个完善的排课系统的任务主要包括以下几项： 条件设置： 主要负责管理班级信息、课程信息、教师信息和

48、教学时间信息。 课表设置：主要负责进行课表安排、课表调整和查询打印。 系统管理：主要负责用户管理、密码维护和重新登录。 第五章 详细设计 第 23 页 共 50 页 5.2 详细设计 5.2.1 创建系统主界面 5.2.1.1 建立工程 打开 vb6.0,选择“文件”/“新建工程”命令，弹出“新建工程”对话框，选中 “标准 exe”图标，单击“确定”按钮，建立一个“标准 exe”工程。在项目的属性 面板中，将项目的“name”属性值改为“排课” 。 5.2.1.2 创建系统主窗体 1) 主窗体界面 在项目资源管理器中为项目添加一个 mdi 窗体作为系统主窗体，将其“name”和 “captio

49、n”属性改为“排课系统” 。系统主窗体如图 2 所示，其主要控件的属性如表 8 所示 表 8 主窗体属性设置 控件属性属性值 name 排课系统 caption 排课系统 startupposition0-manual 排课系统 windowstate0-normal 第五章 详细设计 第 24 页 共 50 页 图 2 系统主窗体 2) 主窗体菜单 在菜单编辑器对话框中编辑菜单项。系统的菜单结构如表 9 所示。 表 9 菜单结构 一级菜单二级菜单一级菜单二级菜单 班级设置课表安排 课程设置课表调整 教师设置 条件设置 时间设置 课表管理 查询打印 用户管理系统管理 密码维护 第五章 详细设计

50、 第 25 页 共 50 页 重新登录 3) 程序代码的设计 主窗体运行时需要调用 setright 过程，该过程将根据不同的用户类型来设置系 统的使用权限。当用户单击工具栏中的图片按钮时，将触发 toolbar _buttonclick 事件。单击不同的图片按钮将进入不同的系统界面，单击不同的菜 单时将进入不同的界面，其代码参考附录。 5.2.1.3 创建公用模块 为了能够对数据库访问进行集中处理，需要创建一个专门访问数据库的公用模块。 在项目资源管理器中为项目添加一个模块，并将其保存为 operateda tebase.bas。 1) operatedatebase.bas operate

51、datebase.bas 公用模块主要用于对数据库进行操作，包括 5 个函数： getconnstr()as string 函数，返回连接字符串，用来设置数据库连接字符串。 openconn（byref conn as adodb. connection）as boolean 函数，返回布尔值， 用来打开数据库连接。 executesol（byval sql as string ,byref msg as string）函数，用来执行 sql 语句。 selectsol（byval sql as string ,byref msg as string）as adodb. recordset 函

52、数，返回 recordset，用来执行查询语句。 第五章 详细设计 第 26 页 共 50 页 batchselectsol（byval sql as string ,byref msg as string）as adodb. recordset 函数，返回 recordset，用来执行批处理。 2) publicvar.bas 为了实现小全局变量 ，另外创建一个全局变量模块 publicvar.bas。主要有 4 个 全局变量，如下所示： loginsucceeded 全局变量，用来保存用户登录是否成功的标志。 userid 全局变量，用来保存用户 id。 user-type 全局变量，用来

53、保存用户类型。 connectionstring 全局变量，用来保存数据库连接字符串。 5.2.2“条件设置”模块 第五章 详细设计 第 27 页 共 50 页 “条件设置”模块主要包括以下功能模块： (1)班级设置：负责维护班级信息，主要提供增加、修改、删除和查询功能。 (2)课程设置：负责维护课程信息，同时进行班级课程分配。 (3)教师设置：主要负责维护教师的基本信息和授课信息。 (4)时间设置：主要负责学校每天的教学时间安排。 5.2.2.1“班级设置”模块的实现 班级设置模块负责维护班级信息，主要提供增加、修改、删除和查询功能。为了 实现这些功能，需要如下控件： (1)1 个 list

54、view 控件，显示班级图片。 (2)1 个 imagelist 控件，装载图片。 (3)4 个 textbox 控件。 (4)6 个 commandbutton 控件：5 个用来维护信息的按钮，分别是添加、修改、 删除、保存和取消按钮，1 个用来退出系统的退出按钮。 其主要的控件属性如表 10 所示。 第五章 详细设计 第 28 页 共 50 页 表 10 “班级设置”窗体主要控件属性表 控件属性属性值 name a 班级设置a 班级设置 caption 班级设置 txt(0)maxlength50 运行窗体时将触发 lode 事件。在 lode 事件中，首先需要调用 lodedata 过程

55、初始化班级 listview,然后调用 showdate 过程显示数据。当用户单击 listview 控件中的班级图标时，将触发 listview_click 事件，当用户单击保存按钮 时，将触发 cmdsave_click 事件。在保存数据之前，需要调用 checkdate 函数对数据 进行合法性检查；返回值为真时表示合法，返回值为假时表示数据非法。同时，需要 调用 setdate 过程来设置数据。其代码参考附录。 5.2.2.2“课程设置”模块的实现 课程设置模块主要负责维护课程信息，同时进行班级课程分配，它包括两个窗体， 一个是课程设置窗体，另一个是班级课程信息窗体，为了实现这些功能信息

56、，需要如 下控件： 1) 课程设置窗体 一个 dategrid 控件，显示课程信息列表。 3 个 textbox 控件。 11 个 commandbutton 控件：4 个用来控制光标移动的按钮，分别用于移到第一条、 上一条、下一条和最后一条记录；5 个用来维护信息的按钮，分别是添加、修改、 第五章 详细设计 第 29 页 共 50 页 删除、保存和取消按钮；1 个班级课程按钮；1 个用来退出系统的退出按钮。 其主要的控件属性值如表 11 所示。 表 11 “课程设置”窗体主要控件属性表 控件属性属性值 name a 课程设置a 课程设置（form） caption 课程设置 dategrid

57、1(dategrid)caption 课程信息列表 2) 班级课程信息窗体 5 个 combobox 控件。 第五章 详细设计 第 30 页 共 50 页 1 个 dategrid 控件，显示班级课程信息列表。 2 个 textbox 控件，显示总节数和每周节数。 10 个 commandbutton 控件：4 个用来控制光标移动的按钮，分别用于移到第一条、 上一条、下一条和最后一条记录；5 个用来维护信息的按钮，分别是添加、修改、 删除、保存和取消按钮；1 个用来退出系统的退出按钮。 其主要的控件属性值如表 12 所示。 表 12“班级课程设置”窗体主要控件属性表 控件属性属性值 a 班级课

58、程设置 name a 班级课程设置 第五章 详细设计 第 31 页 共 50 页 （form） caption 班级课程设置 dategrid1(dategrid)caption 班级课程信息列表 在课程设置窗体中，运行课程设置窗体将运行窗体时将触发 lode 事件。 在 lode 事件中，首先需要调用 lodedata 如果记录存在，则需要调用 showdate 过 程显示数据。当用户单击保存按钮时，将触发 cmdsave_click 事件。在保存数据之 前，需要调用 checkdate 函数对数据进行合法性检查；返回值为真时表示合法，返回 值为假时表示数据非法。同时，需要调用 setdat

59、e 过程来设置数据。 在班级课程信息窗体中，运行班级课程信息窗体将触发 lode 事件。在 lode 事件中，首先需要初始化班级 combobox、课程 combobox、课程分布 combobox， 然后调用调用 lodedata 过程装载数据,如果数据存在，则需要调用 showdate 过程 显示数据。当用户单击保存按钮时，其运行结果同上。 其代码参考附录。 5.2.2.3“教师设置”模块的实现 教师设置模块主要负责维护教师的基本信息和授课信息，进行增加、修改、 删除和查询功能，为了实现这些功能信息，需要如下控件： (1)1 个 listview,控件，显示教师图标。 (2)1 个 ima

60、gelist 控件，装载图片。 (3)4 个 textbox 控件。 (4)1 个 combobox 控件，显示课程名称。 (5)6 个 commandbutton 控件：5 个用来维护信息的按钮，分别是添加、修改、 第五章 详细设计 第 32 页 共 50 页 删除、保存和取消按钮，1 个用来退出系统的退出按钮。 其主要的控件属性如表 13 所示。 表 13“教师设置”窗体主要控件属性 控件属性属性值 name a 教师设置a 教师设置 caption 教师设置 txtid(textbox 教师 标号) maxlength6 运行窗体时将触发 lode 事件。在 lode 事件中，首先需要初