城市公交查询系统的设计与实现.doc

西南大学学士学位论文 1 目目 录录 摘要 摘要 3 3 ABSTRACTABSTRACT 4 4 第一章第一章 前言前言 4 4 1 11 1 引言引言 4 4 1 21 2 系统开发背景系统开发背景 5 5 1 2 11 2 1 系统开发的目的系统开发的目的 5 5 1 2 21 2 2 ASPASP 技术技术 6 6 1 2 31 2 3 ASPASP 与数据库访问与数据库访问 7 7 1 2 41 2 4 SQLSQL 语言简介语言简介 8 8 1 2 51 2 5 数据库管理系统数据库管理系统 8 8 第二章第二章 系统分析系统分析 9 9 2 12 1 公交网络分析公交网络分析 9 9 2 1 12 1 1 地理网络的特点地理网络的特点 9 9 2 1 22 1 2 公交网络的特点公交网络的特点 1010 2 1 32 1 3 公交网络的抽象公交网络的抽象 1010 2 1 42 1 4 公交网络的表示公交网络的表示 1111 2 22 2 系统数据流分析系统数据流分析 1313 2 32 3 系统功能分析系统功能分析 1515 第三章第三章 系统设计系统设计 1717 3 13 1 环境设计环境设计 1717 3 23 2 功能设计功能设计 1818 3 2 13 2 1 B SB S 结构设计结构设计 1818 3 2 23 2 2 系统模块设计系统模块设计 1818 3 33 3 数据库设计数据库设计 1919 3 3 13 3 1 概念模型概念模型 1919 3 3 23 3 2 E RE R 图图 2121 3 3 33 3 3 数据库表数据库表 2222 第四章第四章 最短路径算法研究最短路径算法研究 2424 4 14 1 最短路径概念最短路径概念 2424 4 24 2 D DIJKSTRAIJKSTRA算法理论基础算法理论基础 2424 第五章第五章 系统实现系统实现 2525 5 15 1 算法实现算法实现 2525 5 1 15 1 1 交通查询系统的最短路径算法交通查询系统的最短路径算法 2525 5 1 25 1 2 虚拟结点的最短路径算法策略虚拟结点的最短路径算法策略 2525 5 1 35 1 3 系统备忘录系统备忘录 2626 西南大学学士学位论文 2 5 25 2 系统平台系统平台 2727 5 2 15 2 1 互联网信息服务互联网信息服务 IISIIS 2727 5 2 25 2 2 SQLSQL SERVERSERVER 20052005 介绍介绍 2828 5 35 3 公交查询系统功能的实现公交查询系统功能的实现 2929 5 45 4 部分源代码及程序说明部分源代码及程序说明 3030 5 4 15 4 1 代码设计代码设计 3030 5 4 25 4 2 页面实现部分代码页面实现部分代码 3131 5 55 5 系统测试系统测试 3737 第六章第六章 结束语结束语 3838 参考文献参考文献 3838 致谢致谢 3939 西南大学学士学位论文 3 城市公交查询系统的设计与实现城市公交查询系统的设计与实现 摘要 摘要 城市公共交通运输目前仍然是绝人多数出行者的首选方式 也是各地城市政府大力发展的一 种交通方式 如何提供方便 快捷 经济 高效地利用公交线路的方案 方便市民的出行和生活 同 时减少不必要的交通流量 提高交通运输的效率和城市的地位 已是个越来越迫切的现实问题 本 文研究的是基于 B S 结构的城市公交查询的设计与实现 主要内容就是最优路径分析在公共交通中 的应用 文章的结构按照 模型建立 算法研究 系统实现 的思路来组织 在研究公交网络模型 时 详细分析了公交站点的分布情况 并对公交站点进行了合理的抽象 借鉴了虚拟网络的概念来 表示公交网络 传统的 Dijkstra 算法以及相应的改进算法都是基于路程最短 本文使用 Dijkstra 算法来计算最短路径 并引入备忘录存储求得的最短路径信息 以提高查询的效率及灵活性 通过 测试 此算法具有通用性强 速度快 灵活性高等特点 关键词 关键词 公交网络 Dijkstra 算法 备忘录 虚拟结点 Design and Implementation of urban public transportation query system Abstract urban public transport is still the preferred method that most people choose Around the city government is also vigorously develop a mode of transportation How to provide convenient fast economic and efficient use of bus lines of the programe to facilitate the travel and living and to reduce unnecessary traffic flow and improve the efficiency of transport and the city s status is a more pressing practical problems This paper is based on B S structure of the urban public transport for the design and implementation the main content is the optimal path of public transport in the application The article in accordance with the structure of model algorithm the system to achieve the idea to organize Research on public transport in the network model a detailed analysis of the distribution of transit sites and transit sites for a reasonable abstract from the concept of a virtual network to express public transport network The traditional Dijkstra algorithm and the corresponding improvement algorithms are based on the shortest distance the paper Dijkstra algorithm used to calculate the shortest path And the introduction of the Memorandum of storage seek the shortest path information to enhance the efficiency and flexibility of enquiries Pass the test this method is high universality speed flexibility high Key word Public traffic network Dijkstra algorithm Memorandum Hypothesized crunodes 第一章第一章 前前 言言 1 1 引言引言 毕业设计作为任何院校而言都是非常重要的实践性教学环节 是对学生在校期间 所学知识的综合性考察 也为我们今后走向工作岗位打下必要的基础 在本着能真正 西南大学学士学位论文 4 锻炼培养自己分析问题 解决问题能力的前提下 根据自己兴趣爱好和一定的社会经 验 我选择了基于 web 构建的网上公交查询系统这一课题 计算机和互联网的出现和蓬勃发展对人类生活的影响是革命性的 因为它彻底改 变了人们获取信息乃至生活的方式 人们越来越多地在日常生活中频繁地使用到计算机 和互联网 鉴于这种情况 我们开发了一套基于 web 构建的公交查询系统 系统界面简洁友 好 使用方便 自己在设计的过程中无论系统分析 编程语言还是实际动手能力都有 长足的进步 城市公共交通运输以其覆盖面广 经济快捷的特点 日前仍然是绝人多数出行者的 首选方式 也是各地城市政府大力发展的一种交通方式 如果能够提供种一服务 为市民 特别是外来旅游 出差 就医等急需了解本地道路情况的人提供方便 快捷 经济 高效地利用公交线路的方案 将方便他们的出行和生活 同时减少不必要的交通流量 提高 交通运输的效率和城市的地位 这已是个越来越迫切的现实问题 在西方国家 如美国 日本等 在城市公交网络系统上投入了极大的物力 构建了利 用计算机网络和先进的通信系统的智能运输系统 从而实现了大范围全方位的发挥实 时 准确 高效的运输综合管理 使人 车 路密切配合 和谐统一 大大改善了交通环境 等 国内在这方面的起步较晚 但是各地政府都给予了极大的重视 相继建立了网上公交 查询系统 但是效果不甚理想 主要存在以下问题 1 多数查询系统的形式单 覆盖而较小 2 数据存储结构不够合理 不易扩充 不能支持大于两点的查询 3 咨询方式单一 没有充分发挥现有的各种通信资源 4 查询结果不能满足城市交通实时变化 5 大多数系统基于点对点的查询 智能化程度较差 1 2 系统开发背景系统开发背景 1 2 1 系统开发的目的系统开发的目的 公交查询系统开发的目的是为乘客的出行提供准确 及时 优化的公交信息服务 系统向乘客提供公交信息的动态走向 生成出行辅助计划 对乘客的出行进行主动而 合理的引导 较大程度上方便乘客 从而将无序的交通出行变得有序 优化客流分布 提高公交线网的运行效率 同时将该系统投入实际应用也是提高城市形象的一项重要 西南大学学士学位论文 5 举措 该系统的具体开发过程如图 1 1 所示 基础图形数据建立数学模型 逻辑地图 开发系统应用程序 适合公交网络的数据 图 1 1 系统开发过程图 乘客能够对现有的公交站点 公交线路 运营计划进行查询 乘客输入任意出行 起点 终点 系统可在相应的约束条件下 查找搜索出最优公交出行路径和换乘方案 最后反馈给乘客 同时管理人员可根据站点 线路的变更 运营调度计划的调整 及 时更新系统的公交线网 对与公交有关的其他基础数据方便地进行管理和维护 1 2 2 ASP 技术技术 ASP 全称 Active Server Page 中文叫做动态服务器网页 是微软公司开发的基于 Windows NT Server 和 IIS 的服务器端脚本编写环境 ASP 是一种开发动态网页的技术 它既不是一种编程语言 也不是一种开发工具软件 同样也不是一种应用程序 它定 义了动态网页的开发模型 使用 ASP 可以组合 HTML 页 脚本命令和 ActiveX 组件以创 建交互的 Web 页和基于 Web 的功能强大的应用程序 ASP 赖以运行的基础是 Windows Web 服务器 IIS Internet Information Server 运行于 Windows NT 以及 Windows 2000 以后的版本 或者 PWS Personal Web Server 运行于 Windows 98 多用于 ASP 开发 ASP 使用的编程语言是脚本 可以使用 VBScript 和 JavaScript ASP 对开发工具没有特殊要求 因为所有网页都是文本 而 ASP 采用脚本解释执行无须编译器之类的工具 所以 ASP 开发工具实际上只需要一个文 本编译器 ASP 技术原理是将使用不同脚本编程语言所编写的动态页面保存在 Web 服务器内 当用户向 Web 服务器发出访问动态页面的请求时 Web 服务器从硬盘或者内存中接收正 确的 ASP 文件 并将这个文件发送给 ASP 的解释引擎 ASP DLL 解释引擎扫描整个 页面文件 并执行脚本代码以实现不同的功能 如 用 ADO 组件通过 ODBC 访问数据库 西南大学学士学位论文 6 执行算术或逻辑运算等 最后把执行结果返回 Web 服务器 最终 Web 服务器把解释引 擎的执行结果连同页面上的 HTML 内容一同传送到客户端浏览器 虽然客户端用户所接 收的页面与传统页面并没有任何区别 但实际上页面的内容已经经过了服务器处理 完成了动态的个性化设置 ASP 工作原理图如图 1 2 所示 图 1 2 ASP 工作原理示意图 ASP 作为一种服务器端的 script 技术 主要有如下特点 1 与浏览器无关 用户端只要有 HTML 的浏览器 即可浏览 ASP 所设计的网页 内容 ASP 所使用的脚本程序 如 VBScript 或 JavaScript 均在 Web 服务器端执行 用 户端的浏览器可以不具备运行这些脚本的能力 2 ASP 支持多种网络技术 ASP 支持 ODBC 和 OLEDB 的网络数据库 并且可以支 持其他语言 如 C Java Visual Basic 和 Delphi 所建立的服务器对象 3 ASP 源程序不会被传到客户的浏览器中 因而可以避免所写的源程序被他人 窃取 也提高了程序的安全性 可使用服务器端的脚本来产生客户端的脚本 1 2 3 ASP 与数据库访问与数据库访问 要构建一个基于 ASP 技术的 Web 数据库应用程序 需要将 ASP 页面与数据库建立 连接 在 ASP 中 访问数据库是通过使用其他内置组件 ADO ActiveX Data Object ActiveX 数据对象 来实现的 ADO 组件是构建 ASP 数据库应用程序的核心 它可以提 供多种对象进行数据访问 ADO 提供了较高级的数据库应用程序开发接口 ADO 对数据库的存取操作是通过调 用 OLE DB 提供者或者 ODBC 驱动程序访问数据库来实现的 当客户端使用浏览器执行 IIS 中的 ASP 文件时 可以通过 OLEDB 或 ODBC 驱动程序链接到数据库 并执行 SQL 语 句 然后将查询结果以 HTML 格式返回客户端 其示意图如图 1 3 所示 西南大学学士学位论文 7 客户机 Web 服务 器 ADOOLEDB 或 ODBC 数据库 图 1 3 ADO 数据示意图 由图可知 ADO 在 ASP 网页与数据库之间起着链接与传递的作用 也就是把 ADO 中 的对象嵌入到 ASP 程序中 来执行 ASP 网页发出的处理数据库中数据的指令 如增加 数据 删除数据或查找数据等操作 因此可以说 ASP 是依赖于 ADO 来实现数据存取的 而 ADO 又是通过 ASP 把数据传输给客户或把客户端的数据存放在数据库中 ADO 主要是用 Connection Command 和 Recordset 三种对象进行 Web 应用程序设计 实现对数据库的访问 三个对象的作用分别是 Connection 对象主要用于打开或链接 数据库文件 表示对远程数据源的连接 Recordset 对象主要用于存取数据库 表示从 数据源返回的结果集 Command 对象主要的作用是对数据库下达查询指令 可以用来执 行命令和参数化的查询语句 可以用于 SQL 语句和返回结果集的 SQL 查询 1 2 4 SQL 语言简介语言简介 SQL 是英文 Structured Query Language 的缩写 意思是结构化查询语言 SQL 语 言的主要功能是同各种数据库建立联系 进行沟通 按照 ANSI 美国国家标准协会 的规定 SQL 被称为关系型数据库管理系统的标准语言 SQL 语言结构简洁 功能强大 应用广泛 目前 绝大多数流行的关系型数据库管理系统 如企业级数据库管理系统 Oracle SQL Server Sybase Informix 等 小型数据库管理系统 Access Paradox 等都采用了 SQL 语言标准 1 2 5 数据库管理系统数据库管理系统 数据管理指的是如何对数据进行分类 组织 存储 检索及维护 要注意 这里 所说的数据 不仅是指数字 还包括文字 图形 图像 声音等 凡是计算机中用来 描述事物的记灵 统称为数据 数据库技术是计算机应用领域中非常重要的技术 随着计算机应用的不断深入 数据库的重要性日益被人们所认识 它已成为信息管理 办公自动 计算机辅助设计 等方面的重要手段 对一个特定的数据库来说 它是集中 统一地保存 管理着某一个单位或某一领 西南大学学士学位论文 8 域内所有有用信息的系统 这个系统根据数据间的自然联系结构而成 数据较少冗余 且具有较高的数据独立性 能为多种应用服务 因此可以看出 数据库系统是管理数据且为不同应用服务的工具 它所管理的数 据是大量的有关某一方面的信息 需要较长时间的保存 它所提供的数据应该是正确 的 可靠的 高效率的 数据库管理系统简称 DBMS database management system 是专门用于建立和管 理数据库的一套软件 介于应用程序和操作系统之间 DBMS 不仅具有最基本的数据 管理功能 还能保证数据的完整性 安全性 提供多用户的并发控制 当数据库出现 故障时对系统进行恢复 第二章第二章 系统分析系统分析 2 1 公交网络分析公交网络分析 2 1 1 地理网络的特点地理网络的特点 在现实世界中 若干线状要素相互连接成网状结构 资源沿着这个线性网流动 这样构成的一个系统就称为地理网络 如城市中公共汽车沿着道路运行形成公共交通 网络 水库中的水沿排水管流动形成排水管网络 在地理信息系统中 作为空间实体的地理网络与图论中的网络相比有其自身的特 点 1 地理网络作为一种复杂的地理目标 除具有一般网络的边 结点间的拓扑意义 之外 还具有空间定位上的地理意义和目标复合上的层次意义 2 在现实世界中 地理网络目标除了一系列线状设施外 常常还包含一些重要的 点状设施 如交通网络中的车站和河网中的水闸都是不可缺少的点状设施 在进行地 理网络分析时必须考虑它们的表达和对整个网络的影响 而且这些点状设施作为具有 一定地理意义的零维目标依附于线状设施之上 是一种不同于网络的结点的新的点 也就是说点状设施不一定是网络中的结点 3 按照几何形态 空间实体被抽象为点 线 面目标 作为复杂目标的地理网络 的构建是在一定的原子目标基础上复合而成的 弧段是线状目标数据采集 存储的基 本单元 它在构建网络之前并不具有完整的地理意义 通过结构化的组织生成了目标 意义的网络体系 由弧段构建网络的过程表现为分解与合并两个方面 弧段的一部分 作为边参与网络的生成 或者多条弧段合并成一条边参与网络的生成 显然 在线性 西南大学学士学位论文 9 特征的表示中仅仅用弧段来描述线性特征是不够的 为此在地理网络中引入一些新的 概念扩充线性特征的表示方法 如路径 段的概念 2 1 2 公交网络的特点公交网络的特点 城市中公交汽车沿着道路运行 形成的公交线路网是建立在道路网之上 依据道路建立的网络模型并不能直接应用于公交网络 这是因为公交网络与道 路网络相比有它的一些特点 1 连通性 在道路网络模型中 通常是将道路交叉点抽象成一个结点 也就是说该结 点连接着多条路段 路段与路段之间在该结点处具有连通性 但在公交网络中 如果将公交站点视为结点的话 那么同路公交线路在该点的连通性与不同公交线路在 该点的连通性是有差别的 这是因为不同路的公交线在同一站点上的连通是需要换车 而增加时间消耗的 另外多条公交线路虽然可以相交于空间上的同一个点 但是该点 不一定是公交停靠站点 或者不是同时有停靠点 在这种情况下不同公交线路在这一 点也不是连通的 2 公交站点的特性 在公交线路网中 不同的公交线路在行程上一定会有重叠 也就是说不同的线路 上一定会有同名站点 但在公交站点分布的实际情况中 即使是同名站点也存在空间 位置相异的情况 如果将一个公交站点视为一个结点 在进行网络分析时 就要求把 空间上相近的异线站点合理抽象成一个结点 这一点会在后面作详细介绍 3 最短路径的意义 公交乘客出行和汽车司机运货所考虑的因素是不同的 汽车司机运货关心的是如 何选择最近距离 最大程度的省时省油 而公交乘客出行更多考虑的是出门的方便性和 舒适性 所以道路网络中的最短路径和公交线路的最短路径的意义是不同的 道路网 络中的最短路径只要找出两点之间路径距离为最短即可 但是在公交网络中 乘客不 会为了寻找距离最短路径而随意换车 因为从一条线路换乘到另一条线路是费时又费 力的 在很多情况下 换乘另一趟车需要到另一个站台 这就有一段的步行距离 而 且在站台等车也是要消费时间的 所以对于公交乘客来说 最短路径的意义并不在于 路程是否最短 而在于换乘的次数最少 2 1 3 公交网络的抽象公交网络的抽象 西南大学学士学位论文 10 公交站点在公交网络中是非常重要的点状设施 它是网络中拾起或卸下资源的结 点位置 所以在建公交网络模型时 必须考虑它们的表达和对整个网络的影响 在实 际情况中 同一条公交线路上两个方向的站点和不同公交线路上的站点分布情况较为 复杂 所以必须对公交站点进行一定的分析 抽象成网络中的节点 这一点对网络的 拓扑表达是非常重要的 下面将对一些情况分别进行说明 交通网络又是由交通线路交织而成 道路网络的复杂性 决定了交通网络的复杂 性 以交叉路口为结点 以路段为弧 更可抽象出交通网络的网络拓扑结构 以北京某地道路网络为例 如图 2 1 a 所示 在交叉路口及各路段上设置有站 点 则可以抽象出它的拓扑结构图 如图 2 1 b 所示 a b 图 2 1 公交网拓扑结构示意图 将主要街道 高速路抽象成拓扑结构图中的路段 在各个交叉路口之间又分布着 数量 距离不等的站点 这些公交站点有些位于交叉路口附近 而有些则在某路段内 2 1 4 公交网络的表示公交网络的表示 1 几何网络与虚拟网络 网络可以由多个要素类 feature class 构成 例如 在电力网络系统中 输电线路 开关和变压器等要素类型构成了一个电力网络 要素具有几何信息并且可显示 可以 称作几何网络 几乎所有的网络分析工作均是在网络拓扑关系的基础上展开 而拓扑 并不一定完全依赖于几何 网络拓扑也并不一定总是表现为几何拓扑 为了使抽象的 网络更加适合网络分析 许多专家学者提出了虚拟网络 virtual network V net 的概念 特别是在多模式交通网络中研究得较为深入 虚拟网络是真实网络的逻辑抽象 通过覆盖 同一地区的几个相互独立的网络综合而来 它更强调拓扑表达 忽略网络的几何形态 虚拟网络的基本要素由结点 node 单点 point 和联线 lintL 组成 西南大学学士学位论文 11 Point 网络中具有固定坐标的点位 如事件点等 Node 路线的汇合节点 或路线的起终节点 Link 两个节点之间的线形实体 2 用虚拟网络表示的公交网络 城市中公共汽车沿道路运行形成公共交通网络 街道和公交线路是公共交通网络 中两个主要的实体 在同一条道路上可以存在数条公交线路 数条公交线路在并存一 段路程后又分道扬镳 而有时一条公交线路需要经过多条道路 在这里 可以将道路看 成物理形式的几何网络 它是真实道路的真实描述 存储真实地理坐标 而将公交线 路网看成一个虚拟形式的逻辑网络 它建立在道路网络之上 虽然公交网络不同于多 模式网络 但本文借鉴了虚拟网络的概念来表述公交网络模型 本文将虚拟网络的基 本要素重新定义为 结点表示线路的起点或终点 单点表示具有固定坐标的点位 联线表 示两个结点之间的线形实体 根据公交网络的实际情况 又将虚拟网络中的结点和单 点分为两种类型 一种是多条公交线路共享的结点和单点 称为共享结点 shared node SN 和共享单点 shared point SP 另一种是单条线路所独有的结点和单点 称为内 部结点 inter node IN 和内部单点 inter point IP 并将一个虚拟网络表达为一个五元组 V net SN IN SP IP L 图 2 2 所示是一个几何交通网络 图 2 2 几何交通网络 西南大学学士学位论文 12 图 2 2 中的公交网络可以用 2 3 所示的虚拟网络来描述 图 2 3 逻辑交通网络 SN al b1 IN a7 b7 c1 c6 dl d5 SP al b1 a2 b2 a5 c3 c5 d3 IP a3 a4 a6 a7 b3 b4 b5 b6 b7 c1 c2 c4 c6 dl d2 d4 d5 link a1 a7 bl b7 cl c6 dl d5 在虚拟网络中 共享单点 SP 可以精确地表达公交线路的转换 2 22 2 系统数据流分析系统数据流分析 管理员将数据添加到数据库中 用户提交要查询的数据 通过查询算法在数据库 中查找 最后将查询结果反馈给用户 管理员可以根据公交线路改变或车次的增减等 情况来更新数据库 系统数据流图如下 输入数据 查询处理程序 数据库文件 查询结果 输出结果 用户查询 西南大学学士学位论文 13 图 2 4 输入数据 查询处理程序 数据库文件 输出数据 选择查询对象 显示查询结果 管理员查询 输入数据 管理员登陆程 序 管理员更改 输入数据 管理员登陆程序 输入数据更改信息 信息更改程序 数据库文件 图 2 5 2 32 3 系统功能分析系统功能分析 通过以上分析 结合当前 web 技术 学生信息管理系统应该具有的功能如下 西南大学学士学位论文 14 1 查询功能 包括站点查询 站站查询 车次查询等 2 信息修改 包括车次修改 添加站点 添加路线等 3 用户向管理员提出反馈信息的功能 4 管理功能 包括数据库更新 提取反馈信息 发布消息等 综合以上功能分析 系统的结构功能图如下 查询系统 用户查询系统 旅客须知 系统管理 意见反馈 站 点 查 询 站 站 间 查 询 车 次 查 询 系 统 查 询 信 息 更 改 路 线 查 询 车 次 查 询 路 名 查 询 站 点 查 询 意 见 查 询 增 加 站 点 线 路 增 删 车 次 增 删 图 2 6 西南大学学士学位论文 15 第三章第三章 系统设计系统设计 3 13 1 环境设计环境设计 1 硬件环境 1 服务端 服务端的最低配置是由建立站点所需的软件来决定 在最低配置的情况下 服务 端的性能不能完全发挥 因此通常应给服务端配置高性能硬件 系统服务端的配置 处理器 Inter Pentium 4 1 6GHz 或者更高 内存 256M 或者更高 硬盘 80GB 光驱 CD ROM 52X 显卡 SVGA 显卡适配器 2 用户端 因为用户端主要用于浏览和操作数据 所以对客户端的硬件要求不高 只要配 置高于以下配置 处理器 Inter Pentium 166MX 或者更高 内存 128M 或者更高 硬盘 20GB 光驱 CD ROM 32X 显卡 SVGA 显卡适配器 2 软件环境 1 服务器端 操作系统 Windows XP SP2 网络协议 TCP IP Web 服务器 Resin3 1 5 数据库 MySQl 5 0 浏览器 Internet Explore 5 0 以上 西南大学学士学位论文 16 2 用户端 操作系统 Windows XP SP2 网络协议 TCP IP 浏览器 Internet Explore 5 0 以上 3 23 2 功能设计功能设计 3 2 13 2 1 B SB S 结构设计结构设计 B S 结构 Browser Server 浏览器 服务器模式 是 WEB 兴起后的一种网络 结构模式 WEB 浏览器是客户端最主要的应用软件 这种模式统一了客户端 将系统功 能实现的核心部分集中到服务器上 简化了系统的开发 维护和使用 客户机上只要安装一个浏览器 Browser 如 Netscape Navigator 或 Internet Explorer 服务器安装 Oracle Sybase Informix 或 SQL Server 等数据库 浏览器 通过 Web Server 同数据库进行数据交互 B S 最大的优点就是可以在任何地方进行操作而不用安装任何专门的软件 只要有 一台能上网的电脑就能使用 客户端零维护 系统的扩展非常容易 B S 结构的使用越来越多 特别是由需求推动了 AJAX 技术的发展 它的程序也能 在客户端电脑上进行部分处理 从而大大的减轻了服务器的负担 并增加了交互性 能进行局部实时刷新 所以本系统采用基于 B S 模式的系统结构设计 其 B S 结构设计图如图 3 1 客户端浏览器客户端浏览器客户端浏览器 查询信息处理更新信息处理反馈信息处理 Web应用服务器 数据库 应用层 数据层 图 3 1 西南大学学士学位论文 17 3 2 2 系统模块设计系统模块设计 城市公交乘车查询系统 以国际互联网络环境为基础 为广大出行者提供了多渠 道的城市公交查询服务 出行者可以通过 Internet 使用 Web 浏览器访问城市公交查询 网站来得到图形化的查询结果 出行者可以在各个公交客运站或火车站通过触摸屏来查 询道路信息 本系统由 4 个模块组成 1 城市信息管理维护模块 主要实现公交线路 站点和附近单位 建筑物信息的 录人 编辑 更改 维护等操作 这部分信息采用分级管理 以保证数据的安全性 2 地理信息数据库管理模块 该模块由地图数字化软件和空间数据录人软件组成 负责将城市交通地图数字化及导人到系统的数据库中 3 公交咨询查询模块 主要负责对用户提出的查询事务进行处理 并以系统自定 义的数据格式返回到用户端 该模块主要含有 乘车距离最短查询 换车次数最少查询 时间最短路径查询等功能 查询模块的各功能程序采用 ASP SQL 语言编写 以存储过 程形式提供 用户输人起始地点和目的地 输人信息可以是政治机构 景点 商业 场景 文化场所等 4 图形化信息显示模块 负责将地图信息在用户端显示输出 3 3 数据库设计数据库设计 3 3 1 概念模型概念模型 1 基本概念 实体 Entity 客观存在并可相互区别的事物称为实体 实体可以是具体的人 事 物 也 可以是抽象的概念或联系 如一个站点或一条公交线路 属性 Attibute 实体所具有的某一特性称为属性 一个实体可以由若干个属性来刻画 如 道路实体可以由道路编号 道路名称 长度 道路等级等属性组成 实体型 Entity Type 具有相同属性的实体必然具有共同的特征和性质 用实体名及其属性名集 合来抽象和刻画同类实体 称为实体型 例如 站点 站点编号 名称 位置 就是一个实体型 西南大学学士学位论文 18 联系 Relationship 在现实世界中 事物内部以及事物之间是有联系的 这些联系在信息世界 中反映为实体 型 内部的联系和实体 型 之间的联系 实体内部的联系通常是指组成 实体的各属性之间的联系 实体之间的联系通常是指不同实体集之间的联系 两个实体型之间的联系可以分为三类 一对一联系 1 1 如果对于实体集 A 中的第一个实体 实体集 B 中至多有一个 也可以没有 实体与之联系 反之亦然 则称实体集 A 与实体集 B 具有一对一联系 记为 l 1 一对多联系 l n 如果对于实体集 A 中的每一个实体 实体集 B 中有 n 个实体 n 0 与之 有联系 反之 对于实体集 B 是的每一个实体 实体集 A 中至多只有一个实体 与之联系 则称实体集 A 与实体集 B 有一对多联系 记为 1 no 多对多联系 m n 如果对于实体集 A 中的每一个实体 实体集 B 中有 n 个实体 n 4 与之 有联系 反之 对于实体集 B 是的每一个实体 实体集 A 中也有 m 个实体 m 0 与之联系 则称实体集 A 与实体集 B 有多对多联系 记为 m n 比如一条公 交线路上有若干个站点 而一个站台也可以对应多条公交线路 则线路与站台 之间具有多对多联系 2 概念模型的表示方法 实体一联系方法 Entity Relationship Approach 是概念模型中最著名的表示方 法 该方法用 E R 图来描述现实世界的概念模型 在 E R 图中用矩形表 示实体 椭圆表示属性 用菱形表示联系 并用无向边进行连接 在公交信息查询中涉及的实体有 站点属性有站点编号 名称 位置 道路属性有道路编号 名称 长度 公交线路属性有线路编号 名称 长度 运营时间 所属公司 停靠站点数 票 价 平均发车时间 双行线 西南大学学士学位论文 19 这些实体之间的联系如下 一条道路上可以经过多条公交线路 一条公交线路又由多条道路连接而 成 所以道路与公交线路之间具有多对多联系 一条公交线路上包含多个公交站点 一个公交站点往往又是多条线路的停靠点 所以公交线路与站台之间具有多对多的关系 在站点这个实体集内部存在紧邻的联关系 一个站点可能有多个紧邻站 点 在紧邻站点集合中的一个站点可能又与另外的站点具有紧邻关系 因此这 也是多对多关系 3 3 2 E R 图图 下面给出公交查询的 E R 图 图 3 2 图 3 3 和图 3 4 为实体及其属性图 图 3 5 为 实体联系图 将实体的属性用单独的图画出是为了更清晰地表示实体及实体之间的关系 图 3 2 图 3 3 西南大学学士学位论文 20 图 3 4 图 3 5 根据交通查询系统所得到的基本 E R 图 此系统的关系模式如下所示 站点 站点编号 站点名 站点位置 道路 编号 名称 位置 公交路线 编号 名称 长度 所属公司 运营时间 票价 停靠站数 平均发车时间 3 3 3 数据库表数据库表 表 3 1 Sation 表 站点属性表 字段名字段类型字段长度字段说明 St idchar 6站点编号 其中隐含弧段信息 用前三 位表示弧段编号 后三位是站点编号 positionint 2记录站点在弧段的结点序列中的位置 Stat nam e char10站点名称 表 3 1 西南大学学士学位论文 21 表 3 2 Route 表 线路属性表 字段名字段类型字段长度字段说明 Route idChar4公交线路编号 Route nameChar10线路名称 Company Char10所属公司 frequencyInt3发车频率 Start timeTime4早班车发车时间 End timetime4晚班车发车时间 表 3 2 表 4 3 Route st 表 线路 站点表 字段名字段类型字段长度字段说明 Route idChar4公交线路编号 Stat idChar4站点编号 locationchar2记录站点在路径上的位置 表 3 3 表 4 4 Stat Rela 表 站点关系表 字段名字段类型字段长度字段说明 Stat IDChar4站点编号 Adj staChar4具有紧邻关系的站点编号 表 3 4 西南大学学士学位论文 22 第四章第四章 最短路径算法最短路径算法研究研究 4 1 最短路径概念最短路径概念 地理网络的最优路径是指在地理网络中满足某种最优化条件的一条路径 所谓最优化就是对于给定的目标函数和约束条件使目标函数在约束条件下达到 最大值或最小值 最优路径问题一直是计算机科学 运筹学 交通工程学 地理信息科学等 学科的一个研究热点 它是资源分配 路线设计及分析等优化问题的基础 很 多网络相关问题 如最长路径问题 最可靠路径问题 最大容量路径问题 可 达性评价问题和各种路径分配问题均可纳入这个问题的范畴之中 国内外大量 专家学者对此问题进行了深入研究 有很多最优路径问题可以转化为最短路径问题 而且网络最优化的其它许 多问题也都可以转化为最短路径问题或者用最短路径的算法作为其求解的子过 程 最短路径不仅仅指一般地理意义上的距离最短 还可以引申到其它的度量 如时间 费用 线路容量等 相应地 最短路径问题就成为最快路径问题 最 低费用问题等 比如司机用汽车运输货物从 A 城到 B 城 他就会考虑走路程最 短或者时间最少的道路 这里所考虑的是路程最短问题或最快路径问题 又比 如在两地之间铺设煤气管道 则要根据地形 土壤 是否经过江河 泥塘 农 田 公路等各种情况 来选择铺设费用最小的铺设路线 这是考虑费用的最短 路径问题 经典的图论与不断发展完善的计算机数据结构及算法的有效结合使 得新的最短路径算法不断涌现 对于最短路径的求解 狄克斯特拉提出的一个 算法是目前公认的最好的算法 现有的许多文献都对此作了介绍 4 2 Dijkstra 算法理论基础算法理论基础 Dijkstra算法是求解单源最短路径的贪心算法 其基本思想是 以非降次序逐次 生成源点到其它各点的最短路径 设置顶点集合U 一个顶点属于集合U当且仅当从源 到该顶点的最短路径长度已知 初始时 U中仅含有源点 设u是G的某一个顶点 把从 源到u且中间只经过U中顶点的路径称为从源到u的特殊路径 该路径记录在Path中 路 径长度记录在数组dist中 Dijkstra算法每次从V U中取出具有最短特殊路径长度的 顶点u 将u添加到U中 同时对数组dist进行必要的修改 相应地 修改Path 算法结 西南大学学士学位论文 23 束时 Dist中记录了源点到其它各点的最短路径长度 Path中记录相应的路径 算法 过程如下 假设图G V E 用邻接矩阵arcs来表示 arcs i j 表示图中边 vi vj 上的 权值 若 vi vj 不存在 则置arcs i j 为 用计算机上可允许的最大值代替 1 初始设置 U v0 Path i j v0vi 最短路径长度的初值为 Dist i arcs v0 vi vi V U 2 选择u vj 使得Dist vj Min Dist i vi V U 则vj就是当前求得的一条从 v0出发的最短路径的终点 令U U j 3 修改从v0出发到集合V S上任一顶点vk可达的最短路径长度 如果 Dist j arcs j k t min L s a sdist a c L c t L s a sdist a d L d t L s b sdist b c L c t L s b sdist b d L d t 通过获取最短路径长度的过程信息 可找到相应的最短路径 5 1 3 系统备忘录系统备忘录 用户输入起点站和终点站进行查询时 系统接收用户输入的信息并反馈查询结果 对众多查询相同的情况 若系统每次都按照 Dijkstra 算法完成一次搜索 将耗费大量的 时间和空间 因此可以用系统备忘录来存储已得到的查询信息 系统可根据需要设置 西南大学学士学位论文 25 多个备忘录 每个备忘录可以按查询的频率数 最近查询等原则组织 备忘录的数据结构应包括以下几个方面 起点站终点站查询次数线路信息 其中 线路信息即系统反馈的查询结果 可以用文本方式给出具体的行车路线 即经过的站点和换乘站点等 为了将虚拟结点 备忘录的思想用于最短路径算法中 可以在查询系统应用之前 建立两个备忘录 1 和备忘录 2 选出公交线路中所有交叉路口来形成一个只有较少结点 数目的网络拓扑图 再分别求出各个交叉点之间的最短路径即行车路线 并记录在备 忘录 1 中 乘客查询时 如果输入的起点站和终点站恰为交叉点 就可以通过备忘录 1 直接 输出行车线路 若输入的起点站和终点站不是交叉点 首先在备忘录 2 中进行查询 然后调用引入虚拟结点的 Dijkstra 算法搜索 在系统中添加备忘录后 查询流程图 5 2 所 图 5 2 5 2 系统系统平台平台 生成交叉结点的存储结构 求交叉路口间最短路径 并存入备忘录 1 输入查询起点和终点 交叉结点 在备忘录 1 中查找 置为虚拟结点 在备忘录 2 调用优化算法求解 结果存入备忘录 2 并输出 继续查 是 否 否 是 西南大学学士学位论文 26 5 2 1 互联网信息服务互联网信息服务 IIS IIS 是 Internet Information Server 的缩写 它是微软公司主推的网络服务器 最新的版本是 Windows 2000 里面包含的 IIS IIS 与 Windows NT Server 完全集成在 一起 因而用户能够利用 Windows NT Server 和 NTFS NT File System NT 的文件系 统 内置的安全性 建立强大 灵活而安全的 Internet 和 Intranet 站点 它支持 HTTP Hypertext Transfer Protocol 超文本传输协议 FTP File Transfer Protocol 文件传输协议 以及 SMTP 协议 通过使用 CGI 和 ISAPI IIS 可以得到高度 的扩展 IIS 的一个重要特性是支持 ASP IIS3 0 版本以后引入了 ASP 可以很容易的 张贴动态内容和开发基于 web 的应用程序 对于诸如 VBScript Jscript 脚本语言 或者由 Visual Basic Java Visual C 开发的系统 以及现有的 CGI 和 WinCGI 脚本 开发的应用程序 IIS 都提供强大的本地支持 IIS 对系统资源的消耗很少 安装 管 理和配置都相当简单 这是因为 IIS 与 Windows NT Server 网络操作系统紧密地集成 在一起 Windows 2000 的 Professional 版本缺省没有安装 IIS 服务 用户可以通过控制面 板 添加删除程序 添加 Windows 组件按照系统提示来安装就可以了 安装完成后用 户可以通过控制面板 管理工具 Internet 服务管理器来对 IIS 进行管理和配置 5 2 2 SQL SERVER 2005 介绍介绍 SQL Server 2005 是一个全面的 集成的 端到端的数据解决方案 它为企业中的 用户提供了一个安全 可靠和高效的平台用于企业数据管理和商业智能应用 SQL Server 2005 为 IT 专家和信息工作者带来了强大的 熟悉的工具 同时减少了在从移 动设备到企业数据系统的多平台上创建 部署 管理及使用企业数据和分析应用程序 的复杂度 通过全面的功能集 和现有系统的集成性 以及对日常任务的自动化管理 能力 SQL Server 2005 为不同规模的企业提供了一个完整的数据解决方案 SQL Server 2005 数据平台为不同规模的组织提供了以下好处 充分利用数据资产 除了为业务线和分析应用程序提供一个安全可靠的数据库之 外 SQL Server 2005 也使用户能够通过嵌入的功能 如报表 分析和数据挖掘等从他 们的数据中得到更多的价值 提高生产力 通过全面的商业智能功能 和熟悉的微软 Office 系统之类的工具集 成 SQL Server 2005 为组织内信息工作者提供了关键的 及时的商业信息以满足他们 西南大学学士学位论文 27 特定的需求 SQL Server 2005 目标是将商业智能扩展到组织内的所有用户 并且最终 允许组织内所有级别的用户能够基于他们最有价值的资产 数据来做出更好的决策 减少 IT 复杂度 SQL Server 2005 简化了开发