沈阳工程学院课程设计报告 第一章问题分析
第一章 问题分析
1.1 引言
数据结构的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。
在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上，通过思考，和大量的阅读，来构造一个完整的程序。请记住：重要的是学会编程，而不是背语法。
程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课程设计主要是学习程序设计的方法，进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上，学好基本功。
通过本次课程设计，相信我们一定能加强对数据结构这门课程的学习，尤其在动手实践上会有很大的进步。
1.2 背景
在人们日常的火车订票和退票中，有大量的数据和信息需要存储和处理，通常纸质的档案不容易保存和使用，在查询，订票，退票上有很大的困难，浪费大量的时间和人力也不一定能够取得很好的效果，为了方便人们订票，开发一个火车售票系统迫在眉睫 。
1.3 分析
1.3.1 火车售票系统
两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条路线的情况登录在一张线性表上，由于路线基本不变，可采用顺序存储结构，并按车次有序或按终点站名有序。每条路线是这张表上的一个记录，包含上述8个域，其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。用
1
沈阳工程学院课程设计报告 第一章问题分析
队列来进行客户信息的存储。编辑用户使用菜单，内容包括：列车基本信息管理，列车基本信息查询，订票管理，退票管理。
火车售票系统分为四个大模块，分别为列车基本信息管理，列车基本信息查询，订票管理，退票管理。
⑴ 列车基本信息管理 输入火车的车次号。在循环中，如果火车的车次号不存在的话，创建新结点并依次输入火车的信息，该车次号的信息输入完毕，保存到文件中，结束输入；如果火车的车次号存在的话，重新输入，重复上述过程，单链表创建完毕。
⑵ 列车基本信息查询 列车基本信息查询是在已有的火车订票系统中按地点、按车次、按车线查找到火车信息，并将其显示在屏幕上。通过移动指针找到与输入相同的地点、车次、车线，并将该地点、车次、车线所对应的火车的信息输出。
⑶ 订票管理 根据查询功能查找出所要订购的车票信息，输入所要订购的车票信息。先判断链表是否为空，若为空，显示“没有任何记录”；若不为空，输入车票的数量，看有没有火车票，若没有火车票，输出没有火车票，否则对该结点进行订票操作。
⑷ 退票管理 根据查询功能查找出所要退票的车票信息，先判断链表是否为空，若为空，返回主菜单；若不为空，看是否过期，若过期，输出退票失败，否则对该结点进行退票操作。 主函数是程序的入口，采用模块化设计。通过一定的入口可以进行列车基本信息管理、列车基本信息查询、订票管理、退票管理。
2
沈阳工程学院课程设计报告 第一章问题分析
开始 主菜单 功能选择 Y 1? Y 录入班次信息 2? Y 浏览班次信息 3? 查询行车路线 选择查询 Y N 1? Y 按班次查询 2? 按终点查询 Y 3? Y 4? 售票与退票管理系统 选择 Y 5? 1? Y 订票系统 2? 退出 3? 退票系统 Y 结束 3
沈阳工程学院课程设计报告 第三章系统分析与设计
第二章 原理与运行环境
2.1 数据结构理论
2.1.1 火车售票系统数据结构理论
链接方式存储的线性表简称为链表。 链表是一种动态存储结构，所占用的存储空间在程序的执行过程中得到，当线性表需要增加一个结点时，要为该结点向系统申请一个存储空间。当线性表删除一个结点时，要将已删除的结点的存储空间释放，归还给系统。 每个存储结点不仅包含有所存储元素本身的信息（称之为数据域），而且包含所有元素之间逻辑关系的信息，即前驱结点包含有后继结点的地址信息（这称为指针域），这样可以通过前驱结点的指针域方便地找到后继结点的位置，提高数据查找速度。
队列是一种先进后出的线性表，它只允许在表的一端进行插入，而在另一端进行删除元素。以队列的链式表示和实现为例。一个链队列需要两个分别指向队头和队尾的指针才能唯一确定。首先给链队列添加一个头结点，并且令头指针指向头结点。链队列的操作即为单链表的插入和删除的特殊情况，只是尚需修改尾指针或头指针。一般情况下，删除队列头元素时仅需修改头结点中的指针，但当队列中最后一个元素被删除后，队列尾指针也丢失了，因此，需要对队尾指针重新赋值（指向头结点）。
火车售票系统应用数据结构的知识有：链式线性表存储结构和队列。线性表的链式存储结构的特点：是用一组任意的存储单元存储线性表的数据元素，结点的一个域表示元素本身，另一个是能指示其后继的指针，用来表示线性表数据元素的逻辑关系。顺序表的可随机存取特点。我们将任务分成多个最简化的模块，增强了可读性和简单性，同时为日后的编写，调试，维护提供了极大地方便。队列的特点是：它只允许在表的一端进行插入，而在另一端进行删除元素。
在火车售票系统中，我们把列车和客户分别作为一个结点，该结点类型为结构体型，结构体中的域表示列车和客户的属性。每个结点除了存放属性外，还存放指向后继结点的指针。
列车基本信息管理：存储是将一个车次信息作为一个结点以链式存储在文件中。
列车基本信息查询：在已有的火车售票系统中按地点，按车次，按车线查找到列车信息，并将其显示在屏幕上。
订票管理：在原有的火车售票系统中查找到要订购的车次信息，并将该车次所在的结点输出。
退票管理：根据查询功能查找出所要退票的车票信息，然后退票处理。
2.2 运行环境
本程序的运行环境为Microsoft Visual C++。
开始→程序→Microsoft Visual C++，创建工程名称，如图2-1所示。
4
沈阳工程学院课程设计报告 第三章系统分析与设计
图2.1创建工程名
在工程中选定文件类型，选择C++ Source File，其界面如图2.2。
图2.2文件类型
新建完环境和文件类型之后，进入输入代码的界面，即工程环境，如下图2.3。
5