数据结构实验报告

哈尔滨师范大学计算机科学与信息工程学院实验报告手册课程名称：数据结构指导教师：周英专业：物联网工程专业2017年—2018年第一学期姓名：吕嘉辉学号：2016020068年级：2016级班级：02班实验报告填写及打印要求：1、A4纸正反面打印；2、实验报告封面、封面上填写内容必须打印；3、实验报告内容，学生可手写也可打印，可根据内容自行加页；4、指导教师必须手写签名；5、左侧装订。实验报告内容实验题目：线性表及其应用实验目的：掌握线性表的定义、不同存储结构及基本运算。实验要求：约瑟夫(Joseph)问题描述为：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，从第s个人开始从1报数，数到第m的人出列；然后从它在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出列顺序。实验器材：电脑DEVC++实验步骤/程序源代码：#includestdlib.h#includestdio.htypedefstructnode{//定义节点类型(单链表的定义结构）intnum;//用来对每个节点进行编号标序structnode*next;//递归定义}LNode,*Linkls;//}LNode;//typetefLNode*LinkListvoidcreate(intm,Linkls&head){Linklsp;head=(LNode*)malloc(sizeof(LNode));//申请头结点的储存空间head-next=head;//让链表成为一个空的循环链表for(inti=m;i1;i--){if(!(p=(LNode*)malloc(sizeof(LNode))))exit(-1);//申请存储空间p-num=i;p-next=head-next;head-next=p;}head-num=1;}intmain(){intn,i,m,s=1,j=1;LNode*head,*p,*q;printf(请输入开始的总人数n：\n);scanf(%d,&n);printf(请输入从第s个开始的s值：\n);scanf(%d,&s);printf(请输入m的值：\n);scanf(%d,&m);//输入数据create(n,head);//产生一个以head为头结点，有n个元素的循环列表printf(进行一次删除操作：\n);for(i=1,p=head;is;i++)p=p-next;while(n--){for(i=1;im-1;i++)p=p-next;q=p-next;printf(第%d次出局的数：%d\n,j++,q-num);//输出数到得数字，后面进行删除p-next=q-next;p=p-next;free(q);//释放q所指向空间}system(pause);return0;}实验结果分析：实验日期：2017年10月23日成绩评定：□优秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教师签名：年月日实验报告内容实验题目：栈和队列及其应用实验目的：掌握栈和队列的定义、存储结构及基本运算，理解栈与递归的应用。设计一个程序，演示用算符优先法对算术表达式求值的过程。实验要求：为实现算符优先算法求表达式的值，需要建立两个栈，一个是寄存运算符OPTR，一个是寄存操作数或运算结果OPND，先初始化栈，然后边扫描表达式边计算。实验器材：电脑DEVC++实验步骤/程序源代码：/***链栈实现表达式求值***/#includeiostreamusingnamespacestd;constcharoper[7]={'+','-','*','/','(',')','#'};#defineOK1#defineERROR0#defineOVERFLOW-2typedefcharSElemType;typedefintStatus;typedefstructSNode{//链栈的定义格式intdata;structSNode*next;//SNode链栈的名字}SNode,*LinkStack;StatusInitStack(LinkStack&S){//构造一个空栈S=NULL;returnOK;}boolStackEmpty(LinkStackS){//判断链栈是否为空if(!S)returntrue;returnfalse;}StatusPush(LinkStack&S,SElemTypee){//插入元素e，使之成为栈顶元素SNode*p=newSNode;if(!p){returnOVERFLOW;}p-data=e;//插入元素ep-next=S;S=p;returnOK;}StatusPop(LinkStack&S,SElemType&e){//删除栈顶元素SNode*p;if(!S)returnERROR;e=S-data;p=S;S=S-next;deletep;returnOK;}StatusGetTop(LinkStack&S){//返回栈顶元素if(!S)returnERROR;returnS-data;}boolIn(charch){//判断ch是否是运算符for(inti=0;i7;i++){if(ch==oper[i]){returntrue;}}returnfalse;}charPrecede(chartheta1,chartheta2){//判断运算符优先级if((theta1=='('&&theta2==')')||(theta1=='#'&&theta2=='#')){return'=';}elseif(theta1=='('||theta1=='#'||theta2=='('||(theta1=='+'||theta1=='-')&&(theta2=='*'||theta2=='/')){return'';}elsereturn'';}charOperate(charfirst,chartheta,charsecond){//计算两数运算结果switch(theta){case'+':return(first-'0')+(second-'0')+48;case'-':return(first-'0')-(second-'0')+48;case'*':return(first-'0')*(second-'0')+48;case'/':return(first-'0')/(second-'0')+48;}return0;}charEvaluateExpression(){//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈LinkStackOPTR,OPND;charch,theta,a,b,x,top;InitStack(OPND);//初始化OPND栈InitStack(OPTR);//初始化OPTR栈Push(OPTR,'#');//将表达式起始符“#”压入OPTR栈cinch;while(ch!='#'||(GetTop(OPTR)!='#')){//表达式没有扫描完毕或OPTR的栈顶元素不为“#”if(!In(ch)){Push(OPND,ch);cinch;}//ch不是运算符则进OPND栈elseswitch(Precede(GetTop(OPTR),ch)){//比较OPTR的栈顶元素和ch的优先级case'':Push(OPTR,ch);cinch;//当前字符ch压入OPTR栈，读入下一字符chbreak;case'':Pop(OPTR,theta);//弹出OPTR栈顶的运算符Pop(OPND,b);Pop(OPND,a);//弹出OPND栈顶的两个运算数Push(OPND,Operate(a,theta,b));//将运算结果压入OPND栈break;case'='://OPTR的栈顶元素是“(”且ch是“)”Pop(OPTR,x);cinch;//弹出OPTR栈顶的“(”，读入下一字符chbreak;}//switch}//whilereturnGetTop(OPND);//OPND栈顶元素即为表达式求值结果}intmenu(){intc;cout0-9以内的多项式计算endl;cout1.计算endl;cout0.退出\nendl;cout选择：;cinc;returnc;}intmain(){while(1){switch(menu()){case1:{cout请输入要计算的表达式（操作数和结果都在0-9的范围内，以#结束）：endl;charres=EvaluateExpression();//算法3.22表达式求值cout计算结果为res-48endlendl;}break;case0:cout退出成功\nendl;exit(0);default:break;}}return0;}实验结果分析：实验日期：2017年10月30日成绩评定：□优秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教师签名：年月日实验报告内容实验题目：串及其应用实验目的：掌握串的存储及模式匹配等应用。试写一统计某文本中某些字符串的出现次数和位置。实验要求：在主串S中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符要主串S中出现的位置。分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符看其是否相等，相等j下移接着进行比较，不相等i,j下移接着进行比较。实验器材：电脑DEVC++实验步骤/程序源代码：#includeiostreamusingnamespacestd;intBF(string&tag,string&ptn,intpos){inti,j;i=pos;j=0;inttlen=tag.size();intplen=ptn.size();while(itlen&&jplen){if(tag[i]==ptn[j]){++i;++j;}else{i=i-j+1;j=0;}}if(jplen-1)couti-plen+1;elsecout匹配失败;}intmain(){stringtag,ptn;intpos;cout请输入主串;cintag;cout请输入子串；cinptn;cout请输入从第几个字符开始匹配;cinpos;BF(tag,ptn,pos);system(pause);}实验结果分析：实验日期：2017年11月6日成绩评定：□优秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教师签名：年月日实验报告内容实验题目：数组和广义表及其应用实验目的：掌握数组存储矩阵的应用并实现矩阵转置操作。试写一程序实现求已知是n阶矩阵的转置矩阵。实验要求：(1)将矩阵的行列值相互交换；(2)将每个三元组中的i和j相互调换；(3)重排三元组之间的次序便可实现矩阵的转置。实验器材：电脑DEVC++实验步骤/程序源代码：#includestdio.h#definemaxsize10000typedefstruct{inti,j;intv;}trituplenode;typedefstruct{trituplenodedata[maxsize];intm,n,t;}tritupletable;voidinput(tritupletable*a){inti,j,k=0;intx;scanf(%d%d,&a-m,&a-n);for(i=0;ia-m;i++){for(j=0;ja-n;j++){scanf(%d,&x);if(x){a-data[k].i=i;a-data[k].j=j;a-data[k].v=x;k++;}}}a