数据结构报告Word格式.docx
《数据结构报告Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构报告Word格式.docx（43页珍藏版）》请在冰点文库上搜索。
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文档存储结构〗
<
commodityid="
1001"
name="
口香糖"
amount="
8801"
price="
10.1121"
/>
〖步骤〗
搭建开发环境
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->
exchange=1;
//有交换
p->
next=temp->
temp->
prior=p;
//先将结点从链表上摘下
next=p;
prior->
next=temp;
//将temp插到p结点前
prior=p->
prior;
prior=temp;
}
elsep=p->
}//无交换，指针后移
tail=p;
p=tail->
//准备向上起泡
while（exchange&
&
p->
prior!
=head）{
//向上（左）起泡，一趟有一最小元素冒出
if（p->
amount<
amount）{/
temp=p->
//有交换
p->
prior=temp->
temp->
temp->
next=p->
}
elsep=p->
}
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（c<
H.size）
p=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
5、增加、修改：
/*
增加：
现在哈希表中查找，如果要增加元素不存在，探测，插入，
否则插入失败
修改：
现在哈希表中查找，再进行修改，涉及到的主要函数代码在前面
已经给出，不在重复给出
*/
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）
查（建立在查的基础上）：
排序：
最好n
，（实质就是快速排序）
【总结及提升】
1.处理装填因子的时候抛出异常更好；
2.因为存的是地址的地址，故而先检验该地址是否为空；
3.是否正负或者整数，不应该有底部CPP空值，CPP需要做的只是操作安全上的维护，管理数据即可，因为它可能服务的的对象并不仅仅是这个系统，而其他系统对数据的现实意义的要求可能又不一样，如果在底层处理数据的现实意义（用户自定义约束）会极大限制程序的灵活性，故而用户自定义的约束留到表层去处理；
4.各个函数之间的“耦合性”；
5.题目最底层的抽象就是增删改查，没有其它的，用户的一切要求都可以有这些操作组合而成，因而不能将“表层”的要求影响到底层，底层应该追求最合理的的分离和抽象，这样程序上层组合的灵活性就越大；
6.本地方法虽是CPP实现，但它并不是最底层，最分离的方法，它介于表层和底层之间，有分离和组合的共同特征，可以涉及少数的自定义约束，最底层的就是：
数据结构，数据操作，约束条件（不带与需求相关色彩的抽象约束条件）；
7.为了在局部提高程序的执行效率，在底层采用了几个“分离度低”、“耦合度高”、
“不择手段”的方法，主要表现在：
返回、传入相关指针引用（不安全）如：
ElemType*DeleteHash（HashTable&
H,ElemTypee）；
简单的增加int参数区分重载，如：
H,ElemTypee,inttag）（代码复用性低、耦合度高、针对性太强）；
教学计划安排
学校每学期开设的课程是有先后顺序的，如开设《数据结构》课程之前，必须开设《离散数学》和《程序设计基础》。
给定课程先后顺序如下图所示，选择物理存储方式，存储该课程关系图。
编程实现拓扑排序算法，合理安排开设各门课程的先后顺序。
点信息用一条单向链表储存，每个顶点又是一个“头结点”，依附于每个顶点的是它的先修课：
依附于该顶点的众多结点中，如果某个结点的入度变为零，则该顶点的入度减一，直至该顶点的入度为零，它所依附的结点入度也减一......直至判定完毕。
在顶点信息链表中，每个顶点又是一个“头结点”，依附于每个顶点的是它的先修课，那么就应该注意到在逻辑上是：
现实意义就是：
一门课的先修课都被选修了，这门课也就可以选修了，而同时它也可能作为其它课程的先修课，因而它的选修也进一步影响到以它作为先修课的课程。
单从数据结构和时间复杂度上看，完全没必要这么做，但是，在现实中，一个老师往往更了解选修自己教授的这门课需要哪些预备知识（先修课），而不是这门课会作为哪些课程的先修课。
执行拓扑排序；
//课程结构体
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;
1、读取数据，建双顶点信息表、建有向图
将”#C1012#C5652#”形式的记录中课程编号提取出来，建有向图
说明：
除处理”#”外，其它算法思想来源于教材
voidCreateALG（ALGraph&
G）{
G.vexnum=ListLength（G.vertices）;
AdjListp=G.vertices->
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;
}
G.arcnum++;
index=0;
delete[]pnum;
pnum=newchar[NUMLENGTH];
}else{
pnum[index++]=*pnums;
pnums++;
if（q==NULL）{//假如"
##"
q就不会被实例化，这是q是空的
firstarc=NULL;
}else{
q->
nextarc=NULL;
p=p->
delete[]pnum;
2、求入度
voidFindInDegree（ALGraphG）{
AdjListp=G.vertices->
while（p）{
p->
indegree=0;
p=p->
p=G.vertices->
while（p）{
ArcNode*q=p->
firstarc;
while（q）{
indegree++;
q=q->
nextarc;
3、拓扑排序
StatusTopologicalSort（ALGraphG,jobjectArray&
arrayObjectData）{
FindInDegree（G）;
//入度为零的顶点的地址入栈
while（S.empty（）==false）{
//弹栈，假设其课程编号为NUM
++count;
//遍历，所有先修课程包含NUM的课程入度减一
if（count<
G.vexnum）{
//图有会路
returnERROR;
升级会员 