数据结构报告.docx

计算机科学与技术学院 课 程 设 计 报 告课程名称： 数 据 结 构 专 业： 软 件 工 程 班 级： 2010级1001班 学 号： 201013138026 姓 名： 邓仕军 指导老师： 袁 嵩 仓库管理系统【问题描述】使用链表实现一个仓库管理系统，仓库商品的属性包括(商品编号，商品名称，商品数量)，借助计算机来完成如下功能：（1）入库：可以录入商品信息，包括：商品编号，商品名称，商品数量，商品价格；（2）出库：可以删除一定数量的指定商品名称的商品，商品不够给出提示；（3）修改：修改指定商品编号或者商品名称的价格；（4）删除：可以删除指定商品编号、商品名称的商品记录；（5）查询：可以查询所有商品信息；或指定商品编号、商品名称的商品信息；（6）排序：可以根据价格或数量对商品进行排序，并显示排序结果；【基本要求】实现问题描述中所有需求；从文件中读取数据；【设计方案】设计方案方案编号内容优点缺点一程序启动读文件关闭写文件1)文件读写只一次,减少对存储设备的访问（空间复杂度）；2)没有频繁的堆存数设备访问，加快了需求实现响应速度（时间复杂度）；1）整个数据加载在内存中,对内存要求高；2）一次读入，整个程序一直用在开始指定的存储结构，整个数据在内存中，就不能适时的选择算法，对对应的要求可能无法选择最优的算法，如果要在内存中临时转变存储结构，要么费时（一次转换少量）， 要么费内存（空间复杂度）3）突发的程序终止，丢失数据问题；二随时读取文件1）可以对相应的要求可以选择最适合的算法；2）对内存要求较低；1）频繁的访问存储设备；2）响应慢；三定位在文件中实现需求对内存要求很低，只需加载少量的数据更频繁的访问存储设备，响应更慢分析：1）多用户同时访问，需要响应速度快，能够及时的完成请求(时间复杂度)；2）频繁的读取存储设备，缩短使用周期，要维护和修补其造成的不良后果难度更大；3）较高的内存要求，在一定程度容易满足(空间复杂度)；结果：选择方案一,以双向链表作存储结构并附折中处理办法：a. 哈希表存指针，弥补查询效率（时间复杂度）不足，与链表结合，又可以提高删除效率(双向链表删除效率低主要是要先查找)；b. 在有更新后立即写入文件；系统架构图【实现】〖整体规划〗★ 设计思路1、使用双向链表存储所有结点，哈希表仅仅存储结点指针：双向链表可以快速增、删、改、排序，哈希表的查新效率高，可以结合二中节后的优点，同时一定顶程度上减少对内存的开销；2、表层应用由java完成，数据操作由CPP完成；★ 说明a.底层数据结构：执行数据的增删改查操作和存储；b.用户图形界面：将用户的请求转化分解为对底层的基本操作的组合，将处理结果显示在图形界面上；c.由于项目的出发点是数据结构，故而本程序中不使用java中“屏蔽数据结构”的集合,只使用数组；〖逻辑结构〗typedef struct Commodity {IdType id;NameType name;AmountType amount;PriceType price;Commodity *prior,*next; }CommNode,*CommLinkList;typedef Commodity ElemType;struct HashTable { CommLinkList *elem; // ElemType** int count; // 当前数据元素个数 int size;//当前HashTable的大小 double loadFactor;//负载因子，以此可以控制查询效率 };〖存储结构〗〖XML文档存储结构〗 commodity id=1001 name=口香糖 amount=8801 price=10.1121 /〖步骤〗①搭建开发环境a.导入开发包：dom4jbeanUtils相关文档资源包b.创建组织程序的包 cn.xiaodeng.domain :javabean cn.xiaodeng.dao cn.xiaodeng.dao.impl: 数据访问对象(Data Acess Object) cn.xiaodeng.app.controller :处理请求 cn.xiaodeng.app.UI : 给用户提供界面 cn.xiaodeng.utils :工具 cn.xiaodeng.exception :异常处理 junit.test c.创建代表数据库的 xml 文件②编程实现1、读取数据，建双向链表、哈希表：ElemType InsertAscend(CommLinkList L,ElemType e) 按非降序排列的线性表L已存在，在L中按非降序插入新的数据元e，返回其引用，取地址插入hashTable//产生一个字符串哈希码值，算法来自网上收录资料jint Ha