数据结构实习报告.docx
《数据结构实习报告.docx》由会员分享，可在线阅读，更多相关《数据结构实习报告.docx（9页珍藏版）》请在冰点文库上搜索。
数据结构实习报告
数据结构实习报告
时间：
2020年08月03日编稿：
作者三
第一篇：
数据结构实习报告
数据结构课程设计的实习报告怎么写呀，请求做过课设的同学发一篇范文过来感谢-_-规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：
1、需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?
明确规定：
（1）输入的形式和输入值的范围；
（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：
包括正确地输入及其输出结果和含有错误的输入及其输出结果，数据结构实习报告。
2、概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。
3、详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法（伪码算法达到的详细程度建议为：
按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；画出函数的调用关系图。
4、调试分析内容包括：
（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回忆讨论和分析；
（2）算法的时空分析（包括基本操作和其他算法的时光复杂度和空间复杂度的分析）和改进思想；（3）经验和体味等，实习报告《数据结构实习报告》。
5、用户使用说明说明如何使用你编写的程序，详细列出每一步操作步骤。
6、测试结果列出你的测试结果，包括输入和输出。
这里的测试数据应该完整和严格，最好多于需求分析中所列。
7、附录题目：
约瑟夫-实习报告尺寸：
约瑟夫-实习报告.doc名目：
一、需求分析
二、概要设计
三、程序具体设计及函数调用关系
四、调试分析
五、测试结果原文：
实习报告题目：
约瑟夫（Joseph）问题的一种描述是：
编号为1，2，.，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至年有人全部出列为止。
试设计一个程序求出出列顺序。
班级：
姓名：
学号：
完成日期：
一、需求分析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;
}
elements[rear]=x;
rear=（rear+1）%maxSize;
};
template
boolSeqQueue:
:
DeQueue（constT&x）{//删除函数if（IsEmpty（）==true）returnfalse;
if（rearmaxSize=maxSize/2;
x=elements[front];
front=（front+1）%maxSize;
}
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;//链指针
};
//优先级队列的类定义
template
classPQueue
{
friendclassStack;
friendclassQueue;
public:
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
voidPQueue:
:
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->link;
}
if（pr==NULL）
{
//插入在队头位置
q->link=front;
front=q;
}
else
{
q->link=p;
pr->link=q;//插入在队列中部或尾部
if（pr==rear）
rear=q;
}
}
}
//删除队头元素并返回
template
TPQueue:
:
Remove（）
{
if（IsEmpty（））
returnNULL;PQueueNode*q=front;
front=front->link;//将队头结点从链中摘下
T&retvalue=q->data;
deleteq;
if（front==NULL）
rear=NULL;returnretvalue;
}
//读取队头元素的值
template
TPQueue:
:
Get（）
if（IsEmpty（））
returnNULL;
else
returnfront->data;
}
//
（1）栈的定义与实现
template
classStack:
publicPQueue
{
//栈类定义
public:
Stack（）:
PQueue（）{}//构造函数
voidInsert（T&value）;//插入新元素value到队尾
};template
voidStack:
:
Insert（T&value）
{
//插入函数
PQueueNode*q=newPQueueNode（value,0,NULL）;if（IsEmpty（））front=rear=q;//栈空时新结点为第一个结点
else
{
//插入在前端
q->link=front;
front=q;
}
}//--------------------------Queue//
（2）队列的定义与实现
template
classQueue:
publicPQueue
{
//队列类定义
public:
Queue（）:
PQueue（）{}//构造函数
voidInsert（T&value）;//插入新元素value到队尾
};template
voidQueue:
:
Insert（T&value）
{
//插入函数
PQueueNode*q=newPQueueNode（value,0,NULL）;
if（IsEmpty（））
front=rear=q;//队列空时新结点为第一个结点
else
rear=rear->link=q;//插入在队尾位置
voidmain（）{
StackaStack;QueueaQueue;
intn=1;
aStack.Insert（n）;aQueue.Insert（n）;}
第三篇：
数据结构实习报告
附件：
实习报告格式，如下：
数据结构实习报告
班级：
姓名：
xxx（20121514101）
xxx（20121514101）
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];public:
SumOfSub（inta[],intb,intn）{
for（inti=0;i=m&&s+w[k+1]};voidmain（）{intsum=0;intw[M];srand（（unsigned）time（NULL））;
for（inti=0;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子集。
算法演示
#includeusingnamespacestd;#include#include#defineM50classSumOfSub{private:
intw[M];intp[M];intm;intx[M];
intN[M];intmax;intj;public:
SumOfSub（inta[],intb,intn）{
max=0;j=0;
for（inti=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}
coutfor（inti=0;iw[i]=rand（）;
if（w[i]==0）{
w[i]=rand（）;
}
sum=sum+w[i];}coutcout>m;sum=m*sum;coutr+=w[i];}sumOfSputeSumOfSub（0,0,r）;
sumOfSub.special（）;}运行结果
复杂性分析
对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。
尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时光内求解。
拓展二
问题描述
子集和数问题拓展一：
子集和问题的为〈W,c，P〉。
其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W（0问题分析
增加一个数组随机数组P，每个符合条件子集对应P集合的元素和计算出做个比较，然后输出最大的再对应原W子集。
算法演示
#includeusingnamespacestd;#include#include#defineM50classSumOfSub{private:
intw[M];intp[M];intm;
intx[M];intN[M];intmax;intj;public:
SumOfSub（inta[],intb,intn）{
max=0;
j=0;
coutfor（inti=0;iw[i]=a[i];
p[i]=rand（）;
cout}
coutm=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}
coutfor（inti=0;iw[i]=rand（）;
if（w[i]==0）{
w[i]=rand（）;
}
sum=sum+w[i];}coutcout>m;sum=m*sum;coutr+=w[i];}sumOfSputeSumOfSub（0,0,r）;
sumOfSub.special（）;}
运行结果
复杂性分析
对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。
尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时光内求解。
第五篇：
数据结构实习报告
一、概述软件开辟的流程
二、回忆C语言的基本语法：
1、常量（类型）
2、变量（类型、定义）
3、表达式（例子：
三位数的拆分）
4、操纵语句（if条件语句，例子：
饿了吗？
for循环语句，例子：
做好事问题求解）
5、数组（例子：
猜数字游戏）
三、学生成绩计算系统
做好事问题求解：
某学校为表扬好人好事需核实一件事，老师寻了A、B、C、D三个学生，A说：
“不是我。
”。
B说：
“是C。
”。
C说：
“是D。
”。
D说：
“C胡说”。
这四个人中三个人说了实话。
请问：
这件好事是谁做的？
#include"Stdio.h"#include"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次。
#include"Stdio.h"#include"Conio.h"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--）/*将四位数拆分并
升级会员 