搜索
北京科技大学计算机与通信工程学院实验报告实验名称：数据结构上机实验学生姓名：专业：计算机科学与技术班级：学号：指导教师：实验成绩：________________________________实验地点：实验时间：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[])//后缀表达式