数据结构报告Word格式.docx
- 文档编号:825719
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:43
- 大小:1.47MB
数据结构报告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;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 报告