数据结构实习报告文档格式.docx
- 文档编号:8609555
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:9
- 大小:20.81KB
数据结构实习报告文档格式.docx
《数据结构实习报告文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构实习报告文档格式.docx(9页珍藏版)》请在冰点文库上搜索。
姓名:
学号:
完成日期:
一、需求分析1.本演示程序中,利用单向循环链表存储结构存储约瑟夫环数据(即n个人的编号和密码)。
2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示"
提示信息"
之后,由用户在键盘上输入演示程序中需要输入的数据,运算结果显示在其后。
3.程序执行的命令包括:
1)构造单向循环链表;
2)4.测试数据m的初值为20;
n=7,7个人的密码依次为:
3,1,7,2,4,8,4,首先m值为6(正确的出列顺序为6,1,4,7,2,1,3,5)。
二、概要设计1.单向循环链表的抽象数据类型定义为:
ADTList{数据对象:
D={ai|ai∈正整数,I=1,2,.,n,n≥0}数据关系:
R1={ai-1,ai|,ai-1,ai∈D,I=1,2,.,n}基本操作:
InitList(&
L)操作结果:
构造一个空的线性表L。
ListInsert(&
L,i,e)初始条件:
线性表L已存在,1≤i≤ListLength(L)+1.操作结果:
在L中第i个位置之前插入新的数据无素e,L长度加1。
ListDelete(&
L,i,&
e)初始条件:
线性表L存在非空,1≤i≤ListLength(L).操作结果:
删除L的第i个元素,并用e返回其值,L长度减1。
2.程序包含四个模块:
1)主程序模块:
voidmain(){.
第二篇:
数据结构第六次作业p134
——11411203张玉
24.
template
voidSeqQueue:
:
EnQueue(constT&
x){//插入函数
if(IsFull()==true){
maxSize=2*maxSize;
elements[rear]=x;
rear=(rear+1)%maxSize;
}
};
boolSeqQueue:
DeQueue(constT&
x){//删除函数if(IsEmpty()==true)returnfalse;
if(rearmaxSize=maxSize/2;
x=elements[front];
front=(front+1)%maxSize;
returntrue;
29.
//利用优先级队列实现栈和队列
#include
templateclassPQueue;
//前视的类定义
templateclassStack;
templateclassQueue;
//优先级队列结点类的定义template
classPQueueNode
{
friendclassPQueue;
//PQueue类作为友元类定义friendclassStack;
friendclassQueue;
public:
PQueueNode(T&
value,intnewpriority,PQueueNodepriority(newpriority),link(next){}//构造函数*next):
data(value),
virtualTGetData(){returndata;
}//取得结点数据
virtualintGetPriority(){returnpriority;
}//取得结点优先级
virtualPQueueNode*GetLink(){returnlink;
}//取得下一结点地址
virtualvoidSetData(T&
value){data=value;
}//修改结点数据
virtualvoidSetPriority(intnewpriority){priority=newpriority;
}//修改结点优先级
virtualvoidSetLink(PQueueNode*next){link=next;
}//修改指向下一结点的指针private:
Tdata;
//数据
intpriority;
//优先级
PQueueNode*link;
//链指针
//优先级队列的类定义
classPQueue
friendclassStack;
PQueue():
front(NULL),rear(NULL){}//构造函数
virtual~PQueue(){MakeEmpty();
}//析构函数
virtualvoidInsert(T&
value,intnewpriority);
//插入新元素value到队尾virtualTRemove();
//删除队头元素并返回virtualTGet();
//读取队头元素的值virtualvoidMakeEmpty();
//置空队列
virtualintIsEmpty(){returnfront==NULL;
}//判队列空否private:
PQueueNode*front,*rear;
//队头指针,队尾指针
template
voidPQueue:
MakeEmpty()
//将优先级队列置空
PQueueNode*q;
while(front!
=NULL)//链不空时,删去链中所有结点
//循链逐个删除
q=front;
front=front->
link;
deleteq;
rear=NULL;
//队尾指针置空
}template
Insert(T&
value,intnewpriority)
//插入函数
PQueueNode*q=newPQueueNode(value,newpriority,NULL);
if(IsEmpty())
front=rear=q;
//队列空时新结点为第一个结点
else
PQueueNode*p=front,*pr=NULL;
//寻觅q的插入位置
while(p!
=NULL&
&
p->
priority>
=newpriority)//队列中按优先级从大到小链接{
pr=p;
p=p->
if(pr==NULL)
//插入在队头位置
q->
link=front;
front=q;
link=p;
pr->
link=q;
//插入在队列中部或尾部
if(pr==rear)
rear=q;
//删除队头元素并返回
TPQueue:
Remove()
if(IsEmpty())
returnNULL;
PQueueNode*q=front;
//将队头结点从链中摘下
T&
retvalue=q->
data;
if(front==NULL)
returnretvalue;
//读取队头元素的值
Get()
returnfront->
//
(1)栈的定义与实现
classStack:
publicPQueue
//栈类定义
Stack():
PQueue(){}//构造函数
voidInsert(T&
value);
//插入新元素value到队尾
voidStack:
value)
PQueueNode*q=newPQueueNode(value,0,NULL);
if(IsEmpty())front=rear=q;
//栈空时新结点为第一个结点
//插入在前端
}//--------------------------Queue//
(2)队列的定义与实现
classQueue:
//队列类定义
Queue():
PQueue(){}//构造函数
//插入新元素value到队尾
voidQueue:
rear=rear->
//插入在队尾位置
voidmain(){
StackaStack;
QueueaQueue;
intn=1;
aStack.Insert(n);
aQueue.Insert(n);
第三篇:
附件:
实习报告格式,如下:
数据结构实习报告
班级:
姓名:
xxx(20121514101)
指导教师:
日期:
题目
一、问题描述(把你所选的题目及要求说一下)
二、概要设计(抽象数据类型定义)
三、详细设计(主要算法和函数间的调用关系)
四、调试分析(调式过程中浮现的问题及如何改正)
五、心得体味(组内成员的分工及实习期间的体味)
六、用户手册(系统的使用办法介绍)
可参照习题集上的实习报告格式。
第四篇:
13软件二班
殷健学号:
1345536225
子集和数问题
1:
问题描述
子集和数问题1:
子集和问题的为〈W,c〉。
其中,W={w1,w2,...,wn}是一个正整数的集合,子集和数问题判定是否存在W的一个子集W1,使得∑W1=c∑W(02:
问题分析
程序中设计了函数voidcomputeSumofSub(ints,intk,intr),其意义是从第k项开始,假如s(已经决策的和数)和w[k](当前元素)之和为和数,就把结果输出来,否则假如s与,w[k],w[k+1]之和小于和数,则调用computeSumofsub(s+w[k],k+1,r-w[k]),意为挑选此结点的左分支,再推断s和后面所有元素之和是否不小于M(所有的加起来都小,必然无解),并且s+w[k+1]M,也是无解),若条件符合即调用computeSumofSub(s,k+1,r-w[k]),即挑选当前结点的右分支。
算法展示:
#includeusingnamespacestd;
#include#include#defineM50classSumOfSub{private:
intw[M];
intm;
intx[M];
SumOfSub(inta[],intb,intn){
for(inti=0;
i=m&
s+w[k+1]};
voidmain(){intsum=0;
srand((unsigned)time(NULL));
i}coutcout}cout>
m;
sum=m*sum;
cout复杂性分析:
对于不同的输入结果,算法的执行次数有所不同,最好情况是n,最坏情况是n*2^n。
尽管差异很大,但当n很大时,对某些输入而言,回溯法仍可在短时光内求解。
其它说明:
按书中所讲的约束条件,程序中所有变量都是整型,输入的各元素要从小到大输入,而且不能有重复的元素。
若是想要无序输入,可以程序中加入程序1.c的归并排序算法,对输入的数组排序即可。
拓展一
问题描述:
子集和数问题拓展一:
子集和问题的为〈W,c,p〉。
其中,W={w1,w2,...,wn}是一个正整数的集合,子集和数问题判定是否存在W的一个子集W1,使得∑W1=c∑W(0问题分析:
增加一个数组p,使得p的每个元素与w对应元素关系为pi=Wi+10;
最后结果W子集中元素个数越多,则p和最大,但也可以将每个符合条件子集对应P集合的元素和计算出做个比较,然后输出最大的再对应原W子集。
算法演示
intp[M];
intm;
intN[M];
intmax;
intj;
max=0;
j=0;
iw[i]=a[i];
p[i]=a[i]+10;
m=b;
x[0]=n;
}voidcomputeSumOfSub(ints,intk,intr){x[k]=1;
if(s+w[k]==m){printResult(k);
cout}elseif(s+w[k]+w[k+1]=m&
s+w[k+1]intS=0;
inti;
coutfor(i=0;
iS=S+p[i];
cout}
coutcoutif(S>
max){
max=S;
intJ=0;
for(i=0;
iif(x[i]==1){
N[J]=w[i];
J++;
j=J;
}}voidspecial(){
coutfor(inti=0;
icout}
iw[i]=rand();
if(w[i]==0){
w[i]=rand();
sum=sum+w[i];
}coutcout>
coutr+=w[i];
}sumOfSputeSumOfSub(0,0,r);
sumOfSub.special();
}运行结果
复杂性分析
拓展二
问题描述
子集和问题的为〈W,c,P〉。
其中,W={w1,w2,...,wn}是一个正整数的集合,子集和数问题判定是否存在W的一个子集W1,使得∑W1=c∑W(0问题分析
增加一个数组随机数组P,每个符合条件子集对应P集合的元素和计算出做个比较,然后输出最大的再对应原W子集。
intN[M];
j=0;
p[i]=rand();
coutm=b;
运行结果
第五篇:
一、概述软件开辟的流程
二、回忆C语言的基本语法:
1、常量(类型)
2、变量(类型、定义)
3、表达式(例子:
三位数的拆分)
4、操纵语句(if条件语句,例子:
饿了吗?
for循环语句,例子:
做好事问题求解)
5、数组(例子:
猜数字游戏)
三、学生成绩计算系统
做好事问题求解:
某学校为表扬好人好事需核实一件事,老师寻了A、B、C、D三个学生,A说:
“不是我。
”。
B说:
“是C。
C说:
“是D。
D说:
“C胡说”。
这四个人中三个人说了实话。
请问:
这件好事是谁做的?
#include"
Stdio.h"
Conio.h"
voidmain(void){charthisman;
/*定义变量用来保存做好事的人*/intsum=0;
/*求和变量*//*循环枚举做好事的人*/for(thisman='
A'
;
thisman}getch();
}猜数字:
在计算机上设置一个没有重复数字的4位数,不能让猜得人知道。
猜的人就可以开始猜。
每猜一个数字,出数者就要依据这个数字给出几A几B,其中A前面的数字表示位置正确的数的个数,而B前的数字表示数字正确而位置不对的数的个数。
如正确答案为5234,而猜的人猜5346,则是1A2B,其中有一个5的位置对了,记为1A,而3和4这两个数字对了,而位置没对,因此记为2B,合起来就是1A2B。
接着猜的人再依据出题者的几A几B继续猜,直到猜中为止。
次数限制:
有的时候,这个游戏有推测次数上的限制。
依据计算机测算,这个游戏,假如以最严谨的计算,任何数字可以在7次之内猜出。
而有些地方把次数限制为6次或更少,则会导致有些数可能猜不出来。
而有些地方考虑到人的逻辑思维难以达到计算机的那么严谨,故设置为8次甚至10次。
也有的没有次数上的限制。
我们今天要做的这个游戏就是设定次数为8次。
voidguess(intb[])/*猜数字游戏举行猜数的函数,采纳数组作为参数*/{inti=0,j=0,s=0,x=0,k1=0,k2=0;
/*i、j、s用于举行循环,x用记录猜
数的次数,k1用于记录位置相同且数相同的数字个数、k2记录数相同的数字个数*/inta[4];
while
(1){x++;
printf("
di%dcishuru:
"
x);
scanf("
%d"
&
j);
/*输入要猜的数放在变量j中*/for(i=3;
i>
=0;
i--)/*将输入的4位数举行拆分放到数组a中*/{a[i]=j%10;
j=j/10;
}for(i=0;
i=0;
i--)/*将四位数拆分并
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实习 报告