数据结构报告.docx
《数据结构报告.docx》由会员分享，可在线阅读，更多相关《数据结构报告.docx（43页珍藏版）》请在冰点文库上搜索。
数据结构报告
计算机科学与技术学院
课程设计报告
课程名称：
数据结构
专业：
软件工程
班级：
2010级1001班
学号：
201013138026
姓名：
邓仕军
指导老师：
袁嵩
仓库管理系统
【问题描述】
使用链表实现一个仓库管理系统，仓库商品的属性包括（商品编号，商品名称，商品数量），借助计算机来完成如下功能：
（1）入库：
可以录入商品信息，包括：
商品编号，商品名称，商品数量，商品价格；
（2）出库：
可以删除一定数量的指定商品名称的商品，商品不够给出提示；
（3）修改：
修改指定商品编号或者商品名称的价格；
（4）删除：
可以删除指定商品编号、商品名称的商品记录；
（5）查询：
可以查询所有商品信息；或指定商品编号、商品名称的商品信息；
（6）排序：
可以根据价格或数量对商品进行排序，并显示排序结果；
【基本要求】
1、实现问题描述中所有需求；
2、从文件中读取数据；
【设计方案】
设计方案
方案编号
内容
优点
缺点
一
程序启动读文件
关闭写文件
1）文件读写只一次,减少对存储设备的访问（空间复杂度）；
2）没有频繁的堆存数设备访问，加快了需求实现响应速度（时间复杂度）；
1）整个数据加载在内存中,对内存要求高；
2）一次读入，整个程序一直用在开始指定的存储结构，整个数据在内存中，就不能适时的选择算法，对对应的要求可能无法选择最优的算法，如果要在内存中临时转变存储结构，要么费时（一次转换少量），要么费内存（空间复杂度）
3）突发的程序终止，丢失数据问题；
二
随时读取文件
1）可以对相应的要求可以选择最适合的算法；
2）对内存要求较低；
1）频繁的访问存储设备；
2）响应慢；
三
定位在文件中实现需求
对内存要求很低，只需加载少量的数据
更频繁的访问存储设备，响应更慢
分析：
1）多用户同时访问，需要响应速度快，能够及时的完成请求（时间复杂度）；
2）频繁的读取存储设备，缩短使用周期，要维护和修补其造成的不良后果难度更大；
3）较高的内存要求，在一定程度容易满足（空间复杂度）；
结果：
选择方案一,以双向链表作存储结构并附折中处理办法：
a.哈希表存指针，弥补查询效率（时间复杂度）不足，与链表结合，又可以提高删除效率（双向链表删除效率低主要是要先查找）；
b.在有更新后立即写入文件；
系统架构图
【实现】
〖整体规划〗
★设计思路
1、使用双向链表存储所有结点，哈希表仅仅存储结点指针：
双向链表可以快速增、删、改、排序，哈希表的查新效率高，可以结合二中节后的优点，同时一定顶程度上减少对内存的开销；
2、表层应用由java完成，数据操作由CPP完成；
★说明
a.底层数据结构：
执行数据的增删改查操作和存储；
b.用户图形界面：
将用户的请求转化分解为对底层的基本操作的组合，将处理结果显示在图形界面上；
c.由于项目的出发点是数据结构，故而本程序中不使用java中“屏蔽数据结构”的集合,只使用数组；
〖逻辑结构〗
typedefstructCommodity
{
IdTypeid;
NameTypename;
AmountTypeamount;
PriceTypeprice;
Commodity*prior,*next;
}CommNode,*CommLinkList;
typedefCommodityElemType;
structHashTable
{
CommLinkList*elem;//ElemType**
intcount;//当前数据元素个数
intsize;//当前HashTable的大小
doubleloadFactor;//负载因子，以此可以控制查询效率
};
〖存储结构〗
〖XML文档存储结构〗
〖步骤〗
搭建开发环境
a.导入开发包：
dom4j
beanUtils
相关文档资源包
b.创建组织程序的包
cn.xiaodeng.domain:
javabean
cn.xiaodeng.dao
cn.xiaodeng.dao.impl:
数据访问对象（DataAcessObject）
cn.xiaodeng.app.controller:
处理请求
cn.xiaodeng.app.UI:
给用户提供界面
cn.xiaodeng.utils:
工具
cn.xiaodeng.exception:
异常处理
junit.test
c.创建代表数据库的xml文件
编程实现
1、读取数据，建双向链表、哈希表：
ElemType&InsertAscend（CommLinkList&L,ElemTypee）
按非降序排列的线性表L已存在，在L中按非降序插入新的数据元e，返回其引用，取地址插入hashTable
//产生一个字符串哈希码值，算法来自网上收录资料
jintHashCode（char*key）{
unsignedinthash=1315423911;
while（*key）
{
hash^=（（hash<<5）+（int）（*key++）+（hash>>2））;
}
return（hash&0x7FFFFFFF）;
}
//根据hashCode，确定该插入元素的位置
intindexFor（inthashCode,intlength）{
returnhashCode&（length-1）;
}
intcollision（intp,intd,intsize）//线性探测再散列
{//开放定址法处理冲突
returnp=（p+d）%size;
}
StatusInsertHash（HashTable&H,ElemType&e,inttag）
{
if（/*e已经存在*/）{
//返回重复
}
elseif（/*探测次数<表长*实际负载因子*/）{
//插入，返回正常
}
else{
//重建哈希表
}
//返回错误;
}
boolReadXml（stringszFileName,CommLinkList&L,HashTable&H）{
//初始化工作
while（/*文件没有读完*/）{
//读取一个记录，初始化相关变量
InsertHash（H,InsertAscend（L,commodity）,1）;
//文件读取标记下移
}
}
2、双向链表排序：
//以数量排序为例
JNIEXPORTjobjectArrayJNICALLJava_cn_xiaodeng_dao_utils_DataProcessUtils_sortByAmount
（JNIEnv*env,jclass_j_class）{
//初始化
intexchange=1;tail=dataL;
while（exchange）{
p=head->next;
exchange=0;
while（p->next!
=tail）{
if（p->amount>p->next->amount）{
//交换两结点指针，涉及6条链
temp=p->next;
exchange=1;//有交换
p->next=temp->next;
temp->next->prior=p;//先将结点从链表上摘下
temp->next=p;
p->prior->next=temp;//将temp插到p结点前
temp->prior=p->prior;
p->prior=temp;
}
elsep=p->next;
}//无交换，指针后移
tail=p;p=tail->prior;//准备向上起泡
while（exchange&&p->prior!
=head）{
//向上（左）起泡，一趟有一最小元素冒出
if（p->amountprior->amount）{/
temp=p->prior;
exchange=1;//有交换
p->prior=temp->prior;
temp->prior->next=p;
temp->prior=p;
p->next->prior=temp;
temp->next=p->next;
p->next=temp;
}
elsep=p->prior;
}
head=p;//准备向下起泡
}//while（exchange）
}
3、删除：
//以按id删除为例
CommoditySTATU_VAR;
Commodity*DELKEY=&STATU_VAR;
//标志该位置被删除过元素哈希表中的删除
CommLinkList&DeleteHash（HashTable&H,KeyTypeK）{
//"删除"Hash表中的元素e，并返回其指针的引用，不具通用性,前提//是已有函数确定e必定在Hash表中存在
intp;
Find（H,K,p）;//寻找
//前提是e必定存在，故在这里不作判断
ElemType*s=H.elem[p];
H.elem[p]=DELKEY;
//设置数量标志为DELKEY（-1），表明该元素已被删除,但是删除
//点的释放工作并不在这里进行，而是由链表去做
H.count--;//哈希表当前长度减一
returns;
}
jobjectArrayDeleteById（jstringid）{
if（!
Search（hashTable,id））{
returnNULL;
//在哈希表中查找，没找到，说明删除的元素不存在，返回空
}
CommLinkListdete_com=DeleteHash（hashTable,id）;
ListDelete（dataL,dete_com）;//双向链表中删除
//其它处理
}
4、查找：
//以按id查找为例
ElemType*Search（HashTableH,KeyTypeK）
{
//在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指
//示待查数据元素在表中位置,并返回SUCCESS;否则,返回UNSUCCESS
intc=0;
intp=indexFor（Hash（K）,H.size）;//求得哈希地址
while（（H.elem[p]||H.elem[p]==DELKEY）&&
!
Equals（K,H.elem[p]->id））{
//H.elem[p]==DELKEY标志的被删除过
{//该位置中填有记录．并且关键字不相等
c++;
if（cp=collision（p,c,H.size）;//求得下一探查地址p
else
returnNULL;//查找不成功（H.elem[p].id==NULLKEY）
}
if（H.elem[p]&&Equals（K,H.elem[p]->id））
returnH.elem[p];//查找成功，p返回待查数据元素位置
else
returnNULL;//查找不成功（H.elem[p].id==NULLKEY）
}
5、增加、修改：
//以按id查找为例
/*
增加：
现在哈希表中查找，如果要增加元素不存在，探测，插入，
否则插入失败
修改：
现在哈希表中查找，再进行修改，涉及到的主要函数代码在前面
已经给出，不在重复给出
*/
6、数据交互（javaC++）：
//以其中一个函数为例
java本地方法：
publicstaticnativeObject[]deleteById（Stringid）;
//C++实现方法
JNIEXPORTjobjectArrayJNICALLJava_cn_xiaodeng_dao_utils_DataProcessUtils_deleteById
（JNIEnv*env,jclass_j_class,jstringid）{
//实现代码
}
注：
在java与C++交互中涉及到数据转换，相关函数不在此处给出
【运行结果展示】
1.主界面
2.排序（以数量从高到低为例）
3.按范围查找：
（以价格为例）
4.查找：
（按名称、编号查找）
5.按名称、编号删除，添加
6.修改：
【算法评估】
增：
直接插在表头或尾O
（1），指定位置或者按顺序（升、降）表O（n）；
删：
改进后
（建立在查的基础上）
改（建立在查的基础上）：
按id：
按名称：
O（n）
查（建立在查的基础上）：
按id：
按名称：
O（n）
排序：
最好n
，（实质就是快速排序）
【总结及提升】
1.处理装填因子的时候抛出异常更好；
2.因为存的是地址的地址，故而先检验该地址是否为空；
3.是否正负或者整数，不应该有底部CPP空值，CPP需要做的只是操作安全上的维护，管理数据即可，因为它可能服务的的对象并不仅仅是这个系统，而其他系统对数据的现实意义的要求可能又不一样，如果在底层处理数据的现实意义（用户自定义约束）会极大限制程序的灵活性，故而用户自定义的约束留到表层去处理；
4.各个函数之间的“耦合性”；
5.题目最底层的抽象就是增删改查，没有其它的，用户的一切要求都可以有这些操作组合而成，因而不能将“表层”的要求影响到底层，底层应该追求最合理的的分离和抽象，这样程序上层组合的灵活性就越大；
6.本地方法虽是CPP实现，但它并不是最底层，最分离的方法，它介于表层和底层之间，有分离和组合的共同特征，可以涉及少数的自定义约束，最底层的就是：
数据结构，数据操作，约束条件（不带与需求相关色彩的抽象约束条件）；
7.为了在局部提高程序的执行效率，在底层采用了几个“分离度低”、“耦合度高”、
“不择手段”的方法，主要表现在：
返回、传入相关指针引用（不安全）如：
ElemType*DeleteHash（HashTable&H,ElemTypee）；简单的增加int参数区分重载，如：
CommLinkList&DeleteHash（HashTable&H,ElemTypee,inttag）（代码复用性低、耦合度高、针对性太强）；
教学计划安排
【问题描述】
学校每学期开设的课程是有先后顺序的，如开设《数据结构》课程之前，必须开设《离散数学》和《程序设计基础》。
给定课程先后顺序如下图所示，选择物理存储方式，存储该课程关系图。
编程实现拓扑排序算法，合理安排开设各门课程的先后顺序。
【基本要求】
1、实现问题描述中所有需求；
2、从文件中读取数据；
【设计方案】
点信息用一条单向链表储存，每个顶点又是一个“头结点”，依附于每个顶点的是它的先修课：
依附于该顶点的众多结点中，如果某个结点的入度变为零，则该顶点的入度减一，直至该顶点的入度为零，它所依附的结点入度也减一......直至判定完毕。
系统架构图
【实现】
〖整体规划〗
★设计思路
在顶点信息链表中，每个顶点又是一个“头结点”，依附于每个顶点的是它的先修课，那么就应该注意到在逻辑上是：
依附于该顶点的众多结点中，如果某个结点的入度变为零，则该顶点的入度减一，直至该顶点的入度为零，它所依附的结点入度也减一......直至判定完毕。
现实意义就是：
一门课的先修课都被选修了，这门课也就可以选修了，而同时它也可能作为其它课程的先修课，因而它的选修也进一步影响到以它作为先修课的课程。
单从数据结构和时间复杂度上看，完全没必要这么做，但是，在现实中，一个老师往往更了解选修自己教授的这门课需要哪些预备知识（先修课），而不是这门课会作为哪些课程的先修课。
★说明
a.底层数据结构：
执行拓扑排序；
b.用户图形界面：
将用户的请求转化分解为对底层的基本操作的组合，将处理结果显示在图形界面上；
〖逻辑结构〗
//课程结构体
typedefstructVertexType{
jstringnum;
jstringname;
jstringpnum;//先修课程号
}VertexType;
structVNode;//前向声明
typedefstructArcNode{
VNode*adjvex;//该弧所指向的顶点的指针
ArcNode*nextarc;//指向下一条弧的指针
}ArcNode;//表结点
typedefstructVNode
{
VertexTypedata;//顶点信息
ArcNode*firstarc;
//第一个表结点的地址,指向第一条依附该顶点的弧的指针
VNode*next;
intindegree;
}*AdjList;//头结点
typedefstructALG
{
AdjListvertices;
jintvexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
〖存储结构〗
〖步骤〗
搭建开发环境
a.导入开发包：
dom4j
beanUtils
相关文档资源包
b.创建组织程序的包
cn.xiaodeng.domain:
javabean
cn.xiaodeng.dao
cn.xiaodeng.dao.impl:
数据访问对象（DataAcessObject）
cn.xiaodeng.app.controller:
处理请求
cn.xiaodeng.app.UI:
给用户提供界面
cn.xiaodeng.utils:
工具
cn.xiaodeng.exception:
异常处理
junit.test
c.创建代表数据库的xml文件
编程实现
1、读取数据，建双顶点信息表、建有向图
将”#C1012#C5652#”形式的记录中课程编号提取出来，建有向图
说明：
除处理”#”外，其它算法思想来源于教材
voidCreateALG（ALGraph&G）{
G.vexnum=ListLength（G.vertices）;
AdjListp=G.vertices->next;
while（p）{
ArcNode*q=NULL;//必须显式的置NULL
boolisFisrt=true;
char*pnums=JstringToCharP（p->data.pnum）;
char*pnum=newchar[NUMLENGTH];
intindex=0;
while（*pnums）{
if（*pnums=='#'）{
if（index>0）{
pnum[index]='\0';
jstringjsnum=CharPToJstring（pnum）;
ArcNode*arc=（ArcNode*）malloc（sizeof（ArcNode））;arc->adjvex=LocateElem（G.vertices,jsnum）;
if（isFisrt==true）{
p->firstarc=arc;
q=arc;
isFisrt=false;
}else{
q->nextarc=arc;
q=arc;
}
G.arcnum++;
index=0;
delete[]pnum;
pnum=newchar[NUMLENGTH];
}
}else{
pnum[index++]=*pnums;
}
pnums++;
}
if（q==NULL）{//假如"##"q就不会被实例化，这是q是空的
p->firstarc=NULL;
}else{
q->nextarc=NULL;
}
p=p->next;
delete[]pnum;
}
}
2、求入度
voidFindInDegree（ALGraphG）{
AdjListp=G.vertices->next;
while（p）{
p->indegree=0;
p=p->next;
}
p=G.vertices->next;
while（p）{
ArcNode*q=p->firstarc;
while（q）{
p->indegree++;
q=q->nextarc;
}
p=p->next;
}
p=G.vertices->next;
}
3、拓扑排序
StatusTopologicalSort（ALGraphG,jobjectArray&arrayObjectData）{
//初始化
FindInDegree（G）;
//入度为零的顶点的地址入栈
while（S.empty（）==false）{
//弹栈，假设其课程编号为NUM
++count;
//遍历，所有先修课程包含NUM的课程入度减一
}
if（count//图有会路
returnERROR;
升级会员 