北科大--数据结构上机实验报告

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

北京科技大学计算机与通信工程学院实验报告实验名称:数据结构上机实验学生姓名:专业:计算机科学与技术班级:学号:指导教师:实验成绩:________________________________实验地点:实验时间:2015年____6___月一、实验目的与实验要求1实验目的(1)加深对常用数据结构和算法设计基本思路、思考方法及其适用场合的理解,并能运用于解决实际问题;(2)能根据特定问题需求,分析建立计算模型(包括逻辑结构和物理结构)、设计算法和程序,并在设计中综合考虑多种因素,对结果的有效性进行分析;(3)训练分析问题、解决问题的能力以及自主学习与程序设计实践能力;(4)形成将非数值型问题抽象为计算模型到算法设计、程序实现、结果有效性分析的能力。2实验要求(1)由于在有限的实验课内学时难以较好完成所有实验内容,因此要求在实验课前自主完成部分实验或实验的部分内容;(2)对于每个实验都要针对问题进行分析,设计出有效的数据结构、算法和程序,对实现结果的正确性进行测试,给出测试用例和结果,分析算法的时间复杂度、空间复杂度、有效性和不足,在算法设计和实现过程中体现创新意识,并能综合考虑时空权衡、用户的友好性、程序的模块化和扩展性等;(3)完成的每个实验需要在实验课内经指导教师现场检查、查看程序代码,回答指导教师提出的问题,以确认实验实际完成的质量;(4)在实验报告中体现问题分析、算法思路、算法描述、程序实现和验证、算法和结果的有效性分析。二、实验设备(环境)及要求Win7、C语言、Dev-C++三、实验内容、步骤与结果分析1实验1:链表的应用1.1实验内容输入数据(设为整型)建立单链表,并求相邻两节点data值之和为最大的第一节点。1.2主要步骤1.2.1问题分析与算法思路①采用单链表结构。②新建链表:每输入一个整数数据,建立一个新节点。循环操作直到输入结束符结束输入。③利用一个调用函数求两节点data值之和为最大的第一节点:假设,设一个int类型的变量s=0,读取链表中第一个节点的数据以及它的第二个节点的数据,并计算它们之和a,再计算第二个节点数据和第三个节点数据之和b,如果ab,则s=a;反之,则s=b。利用if语句和while语句实现。④每当输入一个数据,程序会判断输入的时候输入的数据是否是整数,如果不是整数,要求重新输入。1.2.2算法描述typedefintdatatype;//设当前数据元素为整型typedefstructnode//节点类型{datatypedata;//节点的数据域structnode*next;//节点的后继指针域}Linknode,*Link;LinkCreatelist()//创建单链表的算法{inta;LinkH,P,r;//H,P,r分别为表头,新节点和表尾节点指针H=(Link)malloc(sizeof(Linknode));//建立头节点r=H;scanf(“%d”,&a);//输入一个数据while(a!=0){P=(Link)malloc(sizeof(Linknode));//申请新节点P-data=a;//存入数据r-next=P;//新节点链入表尾r=P;scanf(“%d”,&a);//输入下一个数据}r-next=NULL;//将尾节点的指针域置空return(H);//返回已创建的头节点}LinkAdjmax(LinkH)//求链表中相邻两节点data值之和为最大的第一节点的指针的算法{Linkp,p1,q;inti,j;p=p1=H-next;if(p1==NULL)return(p1);//表空返回q=p-next;if(q==NULL)return(p1);//表长=1时返回i=p-data+q-data;//相邻两节点data值之和while(q-next){p=q;q=q-next;//取下一对相邻节点的指针j=p-data+q-data;if(ji){p1=p;i=j;//取和为最大的第一节点指针}}return(p1);}1.2.3程序实现#includestdio.h#includestdlib.htypedefintdatatype;//设当前数据元素为整型typedefstructnode//节点类型{datatypedata;//节点的数据域structnode*next;//节点的后继指针域}Linknode,*Link;//linknode为节点说明符,link为节点指针说明符LinkCreatelist()//创建单链表的算法{inta,c;floatb;LinkH,P,r;//H,P,r分别为表头,新节点和表尾节点指针H=(Link)malloc(sizeof(Linknode));//建立头节点r=H;do{c=(fflush(stdin),scanf(%f,&b));//printf(%d,c);//判断输入的是否是整数a=(int)b;if(c!=1||a!=b||a-32768||a32767)printf(非法输入!请重新输入!\n);}while(c!=1||a!=b||a-32768||a32767);while(a!=0){P=(Link)malloc(sizeof(Linknode));//申请新节点P-data=a;//存入数据r-next=P;//新节点链入表尾r=P;do{c=(fflush(stdin),scanf(%f,&b));//判断输入的是否是整数a=(int)b;if(c!=1||a!=b||a-32768||a32767)printf(非法输入!请重新输入!\n);}while(c!=1||a!=b||a-32768||a32767);}r-next=NULL;//将尾节点的指针域置空return(H);//返回已创建的头节点}LinkAdjmax(LinkH)//求链表中相邻两节点data值之和为最大的第一节点的指针的算法{Linkp,p1,q;inti,j;p=p1=H-next;if(p1==NULL)return(p1);//表空返回q=p-next;if(q==NULL)return(p1);//表长=1时返回i=p-data+q-data;//相邻两节点data值之和while(q-next){p=q;q=q-next;//取下一对相邻节点的指针j=p-data+q-data;if(ji){p1=p;i=j;//取和为最大的第一节点指针}}return(p1);}voidmain()//主函数{LinkA,B,p,q;inta,b;do{printf(请输入一组整数(以0为结束符,数之间回车):\n);p=A=Createlist();//创建新链表B=Adjmax(A);//求链表中相邻两节点data值之和为最大的第一节点的指针a=(int)(B-data);//取第一节点的data值printf(第一节点的data值为:%d\n,a);while(p-next)//释放链表空间{q=p;p=p-next;free(q);}free(p);printf(是否继续输入下一组整数:是:1,否:0\n);scanf(%d,&b);}while(b);}1.3结果分析①输入的数组为:26473,输出结果:第一节点为4。结果是正确的。②输入的数组为:4521456421454230,输出结果:第一节点为21。结果是正确的。③输入的数组为:457235647012241214524,输出结果:第一节点为70。结果是正确的。1.3.1测试如图所示,只要输入的数据不是整数(字符或小数),或者输入的整数不在[32768,32767]这个范围,程序会用非法输入!请重新输入!提示用户,直到用户输入正确的数据。1.3.2算法和结果的有效性分析时间复杂度:O(n)空间复杂度:不复杂有效性:算法正确,算法易读、易编码和易于调试不足:每个数据输入之间只能用回车区分。2实验2:栈的应用2.1实验内容设操作数:0,1,2,……,8,9(可扩充);运算符:+,-,*,/,(,),#(#号为结束)。输入中缀表达式,将其转换成后缀表达式,然后计算,输出结果。例如:输入中缀表达式5+(4-2)*3#,将其转换成后缀表达式:542-3*+#,然后计算,本例结果为11。2.2主要步骤2.2.1问题分析与算法思路①利用栈来写程序。②首先要获得中缀表达式,再利用一个调用函数是中缀表达式变为后缀表达式。再用一个函数求后缀表达式的值。③利用一个调用函数取判断中缀表达式的合法性。2.2.2算法描述typedefstructnode{chardata;structnode*next;}snode,*slink;typedefstructnode1{intdata;structnode1*next;}snode1,*slink1;voidClearstack(slinks)//置栈空{s=NULL;}intEmptystack(slinks)//判断栈是否为空{if(s==NULL)return(1);//栈空返回1elsereturn(0);//栈非空返回0}charGetstop(slinks)//取栈顶元素{if(s!=NULL)return(s-data);return(0);}voidPush(slink*s,charx)//元素x进栈{slinkp;p=(slink)malloc(sizeof(snode));//生成进栈p节点p-data=x;//存入新元素p-next=*s;//p节点作为新的栈顶链入*s=p;}charPop(slink*s)//出栈{charx;slinkp;if(Emptystack(*s))return(-1);//栈空,返回-1else{x=(*s)-data;p=*s;*s=(*s)-next;free(p);return(x);//成功}}intPrecede(charx,chary)//比较x是否大于y{inta,b;switch(x){case'#':case'(':a=0;break;case'+':case'-':a=1;break;case'*':case'/':a=2;break;}switch(y){case'+':case'-':b=1;break;case'*':case'/':b=2;break;case'(':b=3;break;}if(a=b)return(1);elsereturn(0);}voidMid_post(charE[],charB[])//中缀表达式B到后缀表达式E的转换{inti=0,j=0;charx;inta;slinks=NULL;//置空栈Clearstack(s);Push(&s,'#');//结束符入栈do{x=B[i++];//扫描当前表达式分量xswitch(x){case'':break;case'#':{while(!Emptystack(s)){E[j++]='';//栈非空时E[j++]=Pop(&s);}}break;case')':{while(Getstop(s)!='('){E[j++]='';E[j++]=Pop(&s);}//反复出栈直到遇到'('Pop(&s);//退掉'('}break;case'+':case'-':case'*':case'/':case'(':{while(Precede(Getstop(s),x))//栈顶运算符(Q1)与x比较{E[j++]='';E[j++]=Pop(&s);//Q1=x时,输出栈顶符兵退栈}//E[j++]='';Push(&s,x);//Q1x时,x进栈E[j++]='';}break;default:E[j++]=x;//操作数直接输出}}while(x!='#');E[j]='\0';Clearstack(s);}intEcount(charE[])//后缀表达式

1 / 39
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功