第一篇：数据结构实习报告
数据结构实习报告
班级：13软件二班
姓名：殷健 学号：1345536225
子集和数问题
1：问题描述
子集和数问题1：子集和问题的为〈W,c〉。其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W(0 程序中设计了函数void computeSumofSub(int s,int k,int r)，其意义是从第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（由于输入的数据要求是从小到大且无重复元素，所以若s+w[k+1]）>M，也是无解），若条件符合即调用computeSumofSub(s,k+1,r-w[k])，即选择当前结点的右分支。 算法展示： #include int m;int x[M];public: SumOfSub(int a[], int b, int n){ for(int i=0;i };void main(){ int sum=0;int w[M];srand((unsigned)time(NULL)); for(int i=0;i } cout<<“随机数组为：”;cout< cout<<“符合条件的子集为:”;for(int i=0;i<=k;i++){ } cout< } 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子集。 算法演示 #include int N[M];int max;int j;public: SumOfSub(int a[], int b, int n){ max=0;j=0; for(int i=0;i w[i]=a[i]; p[i]=a[i]+10; } m = b; x[0]=n;} void computeSumOfSub(int s, int k, int r){ x[k] = 1;if(s+w[k] == m){ printResult(k);cout<<“ ”; } else if(s+w[k]+w[k+1] <= m){ computeSumOfSub(s+w[k],k+1,r-w[k]);} if(s+r-w[k]>=m&&s+w[k+1]<= m){ x[k] = 0;computeSumOfSub(s, k+1, r-w[k]);} } void printResult(int k){ int S=0;int i; cout<<“符合条件的子集为:”; for(i=0;i<=k;i++){ if(x[i] == 1){ S=S+p[i]; cout< } cout<<“p和为:”< cout< if(S>max){ max=S; int J=0; for(i=0;i<=k;i++){ if(x[i]==1){ N[J]=w[i]; J++; } } j=J; } } void special(){ cout< for(int i=0;i cout< } cout< for(int i=0;i w[i]=rand(); if(w[i]==0){ w[i]=rand(); } sum=sum+w[i];} cout<<“随机数组为：”;for(i=0;i cout< r += w[i];} sumOfSub.computeSumOfSub(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子集。 算法演示 #include int x[M];int N[M];int max;int j;public: SumOfSub(int a[], int b, int n){ max=0; j=0; cout<<“随机数组p为:”; for(int i=0;i w[i]=a[i]; p[i]=rand(); cout< } cout< m = b; x[0]=n;} void computeSumOfSub(int s, int k, int r){ x[k] = 1;if(s+w[k] == m){ printResult(k);cout<<“ ”; } else if(s+w[k]+w[k+1] <= m){ computeSumOfSub(s+w[k],k+1,r-w[k]);} if(s+r-w[k]>=m&&s+w[k+1]<= m){ x[k] = 0;computeSumOfSub(s, k+1, r-w[k]);} } void printResult(int k){ int S=0;int i; cout<<“符合条件的子集为:”; for(i=0;i<=k;i++){ if(x[i] == 1){ S=S+p[i]; cout< } cout<<“p和为:”< cout< if(S>max){ max=S; int J=0; for(i=0;i<=k;i++){ if(x[i]==1){ N[J]=w[i]; J++; } } j=J; } } void special(){ cout< for(int i=0;i cout< } cout< for(int i=0;i w[i]=rand(); if(w[i]==0){ w[i]=rand(); } sum=sum+w[i];} cout<<“随机数组w为：”;for(i=0;i cout< r += w[i];} sumOfSub.computeSumOfSub(0, 0, r); sumOfSub.special();} 运行结果 复杂性分析 对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时间内求解。 数据结构课程设计的实习报告怎么写呀，请求做过课设的同学发一篇范文过来谢谢-_-规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容： 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.单向循环链表的抽象数据类型定义为：ADT List{数据对象：D={ai|ai∈正整数，I=1，2，.，n,n≥0}数据关系：R1={ai-1，ai|，ai-1，ai∈D,I=1，2，.，n}基本操作：Init List(&L)操作结果：构造一个空的线性表L。List Insert(&L,i,e)初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据无素e，L长度加1。List Delete(&L,i,&e)初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。2.程序包含四个模块：1)主程序模块：void main(){. 数据结构第六次作业p134 ——11411203张玉 24.template void SeqQueue if(IsFull()==true){ maxSize=2*maxSize; elements[rear]=x; rear=(rear+1)%maxSize; } elements[rear]=x; rear=(rear+1)%maxSize; }; template bool SeqQueue if(rear<=maxSize/4){ maxSize=maxSize/2; x=elements[front]; front=(front+1)%maxSize; } x=elements[front]; front=(front+1)%maxSize; return true; }; 29.// 利用优先级队列实现栈和队列 #include template template template class PQueueNode { friend class PQueue friend class Queue public: PQueueNode(T &value, int newpriority, PQueueNode virtual int GetPriority(){ return priority;}//取得结点优先级 virtual PQueueNode virtual void SetData(T& value){ data = value;}//修改结点数据 virtual void SetPriority(int newpriority){ priority = newpriority;} //修改结点优先级 virtual void SetLink(PQueueNode T data;//数据 int priority;//优先级 PQueueNode }; //优先级队列的类定义 template class PQueue { friend class Stack friend class Queue public: PQueue():front(NULL), rear(NULL){}//构造函数 virtual ~PQueue(){ MakeEmpty();}//析构函数 virtual void Insert(T &value, int newpriority);//插入新元素value到队尾 virtual T Remove();//删除队头元素并返回 virtual T Get();//读取队头元素的值 virtual void MakeEmpty();//置空队列 virtual int IsEmpty(){ return front == NULL;}//判队列空否private: PQueueNode };template void PQueue { //将优先级队列置空 PQueueNode while(front!= NULL)//链不空时, 删去链中所有结点 { //循链逐个删除 q = front; front = front->link; delete q; } rear = NULL;//队尾指针置空 }template void PQueue { //插入函数 PQueueNode front = rear = q;//队列空时新结点为第一个结点 else { PQueueNode 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 T PQueue { if(IsEmpty()) return NULL;PQueueNode front = front->link;//将队头结点从链中摘下 T &retvalue = q->data; delete q; if(front == NULL) rear = NULL;return retvalue; } //读取队头元素的值 template T PQueue if(IsEmpty()) return NULL; else return front->data; } //(1)栈的定义与实现 template class Stack:public PQueue { //栈类定义 public: Stack():PQueue void Insert(T & value);//插入新元素value到队尾 };template void Stack { //插入函数 PQueueNode else { //插入在前端 q->link = front; front = q; } }//--------------------------Queue //(2)队列的定义与实现 template class Queue:public PQueue { //队列类定义 public: Queue():PQueue void Insert(T & value);//插入新元素value到队尾 };template void Queue { //插入函数 PQueueNode if(IsEmpty()) front = rear = q;//队列空时新结点为第一个结点 else rear = rear->link = q;//插入在队尾位置 void main(){ Stack int n = 1; aStack.Insert(n);aQueue.Insert(n);} 附件： 实习报告格式，如下： 数据结构实习报告 班级： 姓名： xxx（20121514101） xxx（20121514101） xxx（20121514101） 指导教师： 日期： 题目 一、问题描述（把你所选的题目及要求说一下） 二、概要设计（抽象数据类型定义） 三、详细设计（主要算法和函数间的调用关系） 四、调试分析（调式过程中出现的问题及如何改正） 五、心得体会（组内成员的分工及实习期间的体会） 六、用户手册（系统的使用方法介绍） 可参照习题集上的实习报告格式。 一、概述软件开发的流程 二、回顾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” void main(void){ char thisman;/*定义变量用来保存做好事的人*/ int sum=0;/*求和变量*/ /*循环枚举做好事的人*/ for(thisman='A';thisman<='D';thisman++){ /*对四个人所说的话进行求和，真话为1，假话为0*/ sum=(thisman!='A')+(thisman=='C')+(thisman=='D')+(thisman!='D');/*判断和是否为3，真话3，假话1*/ if(sum==3){ /*找到做好事的人，输出*/ printf(“thisman is %cn”,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” void guess(int b[])/*猜数字游戏进行猜数的函数，采用数组作为参数*/ { int i=0,j=0,s=0,x=0,k1=0,k2=0;/*i、j、s用于进行循环，x用记录猜 数的次数，k1用于记录位置相同且数相同的数字个数、k2记录数相同的数字个数*/ int a[4];while(1){ x++;printf(“di %d ci shu ru:”,x);scanf(“%d”,&j);/*输入要猜的数放在变量j中*/ for(i=3;i>=0;i--)/*将输入的4位数进行拆分放到数组a中*/ { a[i]=j%10;j=j/10;} for(i=0;i<4;i++)/*比较位置和数字都一致的*/ { if(a[i]==b[i])k1++;} for(i=0;i<4;i++)/*只比较数字相同不管位置*/ { for(s=0;s<4;s++)if(a[i]==b[s])k2++;} printf(“%dA%dBn”,k1,k2);if(x==8)/*如果已经猜了8次还没有猜对那么就要提示并推出这一轮游戏*/ { printf(“your time over back menun”);break;} if(k1==4&&k2==4)/*猜对了数字，提示胜利*/ { printf(“win!”);break;} k1=0;/*将计数变量清零*/ k2=0;} } void set_num()/*设置被猜的数子*/ { printf(“input number:”);scanf(“%d”,&num);/*输入被猜的数字，存放在变量num中*/ for(i=3;i>=0;i--)/*将四位数拆分并按高低位存放在数组b中*/ { b[i]=num%10;num=num/10;} printf(“ok press any key”);getch();/*等待*/ clrscr();/*清屏*/ } int main(void){ int b[4],num,i,ch=0;while(1)/*条件为1的无限循环作为软件运行的主体，等待退出命令*/ { printf(“****menu****n”);printf(“set number input 1n”);printf(“guess number input 2n”);printf(“exit input 3n”);printf(“input your select items:”);scanf(“%d”,&ch);if(ch==1)/*选择变量为1调用设置被猜数字函数*/ { set_num();} if(ch==2)/*选择变量为2调用猜数游戏过程函数*/ { guess(b);} if(ch==3)/*选择变量为3退出循环结束游戏*/ { break;} } getch();return 0;}第二篇：数据结构实习报告
第三篇：数据结构实习报告
第四篇：数据结构实习报告
第五篇：数据结构实习报告
点击咨询 