数据结构实验报告全集

数据结构实验报告全集实验一线性表基本操作和简单程序1．实验目的（1）掌握使用VisualC++6.0上机调试程序的基本方法；（2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。2．实验要求（1）认真阅读和掌握和本实验相关的教材内容。（2）认真阅读和掌握本章相关内容的程序。（3）上机运行程序。（4）保存和打印出程序的运行结果，并结合程序进行分析。（5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果实验代码：1）头文件模块#includeiostream.h//头文件#includemalloc.h//库头文件-----动态分配内存空间typedefintelemtype;//定义数据域的类型typedefstructlinknode//定义结点类型{elemtypedata;//定义数据域structlinknode*next;//定义结点指针}nodetype;2）创建单链表nodetype*create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束{elemtyped;//定义数据元素dnodetype*h=NULL,*s,*t;//定义结点指针inti=1;cout建立一个单链表endl;while(1){cout输入第i结点data域值：;cind;if(d==0)break;//以0表示输入结束if(i==1)//建立第一个结点{h=(nodetype*)malloc(sizeof(nodetype));//表示指针hh-data=d;h-next=NULL;t=h;//h是头指针}else//建立其余结点{s=(nodetype*)malloc(sizeof(nodetype));s-data=d;s-next=NULL;t-next=s;t=s;//t始终指向生成的单链表的最后一个节点}i++;}returnh;}3）输出单链表中的元素voiddisp(nodetype*h)//输出由h指向的单链表的所有data域之值{nodetype*p=h;cout输出一个单链表:endl;if(p==NULL)cout空表;while(p!=NULL){coutp-data;p=p-next;}coutendl;}4）计算单链表的长度intlen(nodetype*h)//返回单链表的长度{inti=0;nodetype*p=h;while(p!=NULL){p=p-next;i++;}returni;}5）寻找第i个节点nodetype*find(nodetype*h,inti)//返回第i个节点的指针{nodetype*p=h;intj=1;if(ilen(h)||i=0)returnNULL;//i上溢或下溢celse{while(p!=NULL&&j1)//查找第i个节点，并由p指向该节点{j++;p=p-next;}returnp;}}6）单链表的插入操作nodetype*ins(nodetype*h,inti,elemtypex)//在单链表head中第i个节点//（i=0）之后插入一个data域为x的节点{nodetype*p,*s;s=(nodetype*)malloc(sizeof(nodetype));//创建节点ss-data=x;s-next=NULL;if(i==0)//i=0:s作为该单链表的第一个节点{s-next=h;h=s;}else{p=find(h,i);//查找第i个节点，并由p指向该节点if(p!=NULL){s-next=p-next;p-next=s;}returnh;}}7）单链表的删除操作nodetype*del(nodetype*h,inti)//删除第i个节点{nodetype*p=h,*s;intj=1;if(i==1)//删除第1个节点{h=h-next;free(p);}else{p=find(h,i-1);//查找第i-1个节点，并由p指向该节点if(p!=NULL&&p-next!=NULL){s=p-next;//s指向要删除的节点p-next=s-next;free(s);}elsecout输入i的值不正确endl;}returnh;}8）释放节点空间voiddispose(nodetype*h)//释放单链表的所有节点占用的空间{nodetype*pa=h,*pb;if(pa!=NULL){pb=pa-next;if(pb==NULL)//只有一个节点的情况free(pa);else{while(pb!=NULL)//有两个及以上节点的情况{free(pa);pa=pb;pb=pb-next;}free(pa);}}}9)主程序模块:#includeslink.h//包含头文件slinkvoidmain(){nodetype*head;//定义节点指针变量head=create();//创建一个单链表disp(head);//输出单链表cout单链表长度:len(head)endl;ins(head,2,0);//在第二个节点之后插入以0为元素的节点disp(head);//输出新链表del(head,2);//删除第二个节点disp(head);//输出新链表}5．实验结果建立一个单链表：输入第1结点data域值：1输入第2结点data域值：2输入第3结点data域值：3输入第4结点data域值：4输入第5结点data域值：5输入第6结点data域值：6输入第7结点data域值：7输入第8结点data域值：8输入第9结点data域值：9输入第10结点data域值0：输出一个单链表：123456789单链表长度：9输出一个单链表：1023456789输出一个单链表：12345678实验二顺序栈的实现1.实验目的掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。2.实验要求（1）认真阅读和掌握和本实验相关的教材内容。（2）分析问题的要求，编写和调试完成程序。（3）保存和打印出程序的运行结果，并分析程序的运行结果。3.实验内容利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下：（1）定义栈的顺序存取结构。（2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。（3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。（4）设计一个测试主函数进行测试。（5）对程序的运行结果进行分析。实验代码：#includestdio.h#defineMaxSize100typedefstruct{intdata[MaxSize];inttop;}SqStack;voidInitStack(SqStack*st)//初始化栈{st-top=-1;}intStackEmpty(SqStack*st)//判断栈为空{return(st-top==-1);}voidPush(SqStack*st,intx)//元素进栈{if(st-top==MaxSize-1)printf(栈上溢出!\n);else{st-top++;st-data[st-top]=x;}}voidPop(SqStack*st)//退栈{if(st-top==-1)printf(栈下溢出\n);elsest-top--;}intGettop(SqStack*st)//获得栈顶元素{if(st-top==-1){printf(栈空\n);return0;}elsereturnst-data[st-top];}voidDisplay(SqStack*st)//打印栈里元素{inti;printf(栈中元素：);for(i=st-top;i=0;--i)printf(%d,st-data[i]);printf(\n);}intmain()//测试{SqStackL;SqStack*st=&L;InitStack(st);printf(栈空：%d\n,StackEmpty(st));for(inti=1;i10;++i)Push(st,i);Display(st);printf(退一次栈\n);Pop(st);printf(栈顶元素:%d\n,Gettop(st));Pop(st);Display(st);return0;}实验结果：实验三串的基本操作和简程序1．实验目的掌握串基本操作：初始化、联接、替换、子串等运算在堆分配存储储结构上的程序设计方法。2．实验要求（1）认真阅读和掌握和本实验相关的教材内容。（2）认真阅读和掌握本章相关内容的算法并设计程序序。（3）上机运行程序。（4）保存和打印出程序的运行结果，并结合程序进行分析。实验代码：#includestdio.h#defineMaxSize50typedefstruct{chardata[MaxSize];//存放字符串intlength;//字符串长度}SqString;//将一个字符串常量赋给串svoidStrAssign(SqString&s,charcstr[]){inti;for(i=0;cstr[i]!='\0';i++)//这个'\0'代表字符串结束标志,编译系统自动加上的s.data[i]=cstr[i];s.length=i;}//字符串的复制voidStrCopy(SqString&s,SqStringt){inti;for(i=0;it.length;i++)s.data[i]=t.data[i];s.length=t.length;printf(字符串复制成功了\n);}//判断字符串是否相等voidStrEqual(SqStrings,SqStringt){inti,same=1;if(s.length!=t.length)same=0;else{for(i=0;is.length;i++)if(s.data[i]!=t.data[i]){same=0;break;}}if(same==0)printf(这两个字符串不相等\n);elseprintf(这两个字符串相等\n);}//字符串的长度voidStrLength(SqStrings){printf(此字符串长度为：%d\n,s.length);}//合并字符串SqStringConcat(SqStrings,SqStringt){SqStringstr;inti;str.length=s.length+t.length;for(i=0;is.length;i++)str.data[i]=s.data[i];for(i=0;it.length;i++)str.data[s.length+i]=t.data[i];returnstr;}//求子字符串voidSubStr(SqStrings,inti,intj){SqStringstr;intk;str.length=0;if(i=0||is.length||j0||i+j-1s.length)printf(子字符串复制失败\n);for(k=i-1;ki+j-1;k++)str.data[k-i+1]=s.data[k];str.length=j;printf(子字符串复制成功长度为：%d\n,j);printf(下面输出此子字符串：\n);for(i=0;ij;i++)printf(%c,str.data[i]);printf(\n);}//插入字符串SqStringInserStr(SqStrings1,inti,SqStrings2){intj;SqStringstr;str.length=0;if(i=0||