2023年数据结构实验报告全集

数据结构实验报告全集实验一线性表基本操作和简朴程序.实验目的a(1)掌握使用Visua1C++6.0上机调试程序的基本方法;a(2)掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。.实验规定1。)认真阅读和掌握和本实验相关的教材内容。(2)认真阅读和掌握本章相关内容的程序。(3)上机运营程序。(4)保存和打印出程序的运营结果，并结合程序进行分析。(5)按照你对线性表的操作需要，重新改写主程序并运营，打印出文献清单和运营结果实验代码:1)头文献模块ttincludeiostream.h>//头文献动态分派内存空间动态分派内存空间动态分派内存空间ttinclude<ma11oc.h>〃库头文献typedefintelemtype;//定义数据域的类型typedefstruct1inknode//定义结点类型动态分派内存空间elemtypedata;//定义数据域structlinknode*next;〃定义结点指针}nodetype;voidmain()nodetype*head;〃定义节点指针变量head=create();〃创建一个单链表disp(head)；〃输出单链表cout<<“单链表长度：“<<len(head)«endl；ins(head,2,0);〃在第二个节点之后插入以0为元素的节点disp(head);//输出新链表de1(head,2);〃删除第二个节点disp(head);//^^fr^}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)分析问题的规定，编写和调试完毕程序。保存和打印出程序的运营结果，并分析程序的运营结果。3•实验内容a运用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否对的配对的程序。具体完毕如下：(1)定义栈的顺序存取结构。(2)分别定义顺序栈的基本操作(初始化栈、判栈空否、入栈、出栈等)。(3)定义一个函数用来判断算术表达式中包含圆括号、方括号是否对的配对。其中，括号配对共有四种情况:左右括号配对顺序不对的;右括号多于左括号；左括号多于右括号;左右括号匹配对的。设计一个测试主函数进行测试。对程序的运营结果进行分析。实验代码：ftinclude<stdio.h>A#defineMaxSize100typedefstruct{aintdata[MaxSize]；ainttop;}SqStack；voidInitStack(SqStack*st)//初始化栈a{ast->top=-1;}^intStackEmpty(SqStack*st)〃判断栈为空a{return(st->top==11)；printf(〃栈上溢voidPush(SqStack*st,intx)〃元素进栈if(st—>top==MaxSize~l)aprintf(〃栈上溢出！\n〃）；{ast->top++；st->data[st—>top]=x；a出！\n〃）；{aqStack*st)〃退栈(if(st->top==-l)Aprintf(〃栈下溢出\n〃);elsest->top一;}intGettop(SqStack*st)〃获得栈顶元素if(st—>top==-1)a{aprintf("栈空\n〃);return0;}aelsereturnst—>data[st—>top];}AvoidDisplay(SqStack*st)//打印栈里元素{ainti;printf(〃栈中元素：〃)；afor(i=st—>top;i>=0;--i”printf(n%dn,st->data[i]);printf(〃\n")；)intmain()〃测试]SqStackL；aSqStack*st=&L；aInitStack(st)；aprintf(〃栈空：%d\n〃，StackEmpty(st));for(inti=l;i<10;++i)

Push(st,i)；aDisp1ay(st)；printf(H退一次栈\nPush(st,i)；aDisp1ay(st)；printf(H退一次栈\n);Pop(st)；aprintf(〃栈顶元素:%d\n〃，Gettop(st));Pop(st)Display(st)；实验结果:.•元次元元空牡一顶牡.•元次元元空牡一顶牡残废根戋废ynasserp76543254321tocontinue实验三串的基本操作和简程序.实验目的掌握串基木操作：初始化、联接、替换、子串等运算在堆分派存储储结构上的程序设计方法。.实验规定1。）认真阅读和掌握和本实验相关的教材内容。（2）认真阅读和掌握本章相关内容的算法并设计程序序。（3）上机运营程序。(4)保存和打印出程序的运营结果，并结合程序进行分析。实验代码:Windude<stdio.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)for(i=0；i<t.1ength;i++)s.data[i]=t.data[i];s.length=t.1ength;printf(〃字符串复制成功了\n〃)；)//判断字符串是否相等voidStrEqual(SqStrings,SqStringt)(inti,same=l;if(s.1ength!=t.length)same=0;else(for(i=0;i<s.length；i++)if(s.data[i]!=t.data[i])(same=0;break;if(same==0)printf("这两个字符串不相等\n〃)；e1seprintf(〃这两个字符串相等\n〃)；}〃字符串的长度voidStrLength(SqStrings){printf("此字符串长度为:％d\n”，s.1ength)；}〃合并字符串SqStringConcat(SqStrings,SqStringt)(SqStringstr；inti;str.length=s.1ength+t.length;for(i=0；i<s.length；i++)str.data[i]=s.data[i];for(i=0;i<t.length;i++)str.data[s.Iength+i]=t.dataEi];returnstr;}〃求子字符串voidSubStr(SqStrings,inti,intj)SqStringstr;intk;str.length=0;if(i<=0||i>s.length||0IIi+j-l>s.1ength)printf(〃子字符串复制失败\n〃)；for(k=i-1;k<i+j-l；k++)str.data[k—i+l]=s.data[k]；str.length=j;printf("子字符串复制成功长度为：%d\n\j);printf("下面输出此子字符串：\n");for(i=0；i<j；i++)printf('%c”,str.dataEi]);printf(”\n")；)//插入字符串SqStringInserStr(SqStringsi,inti,SqStrings2)intj；SqStringstr;str.1ength=0；if(i<=01|i>s1.length+1)(printf("字符串插入失败\n〃);returnstr;)for(j=0;j<i-l；j++)str.data[j]=sl.data[j]；for(j=0;j<s2.1ength；j++)str.data[i—l+j]=s2.data[j]；for(j=i-l;j<s1.length;j++)str.data[s2.length+j]=sl.data[j]；str.Iength=sl.Iength+s2.length;printf("插入字符串成功长度为:％d\n",str.length)；returnstr;)〃删除字符串SqStringDeleStr(SqStrings,inti,intj){intk;SqStringstr；2）创建单链表nodetype*create()//建立单链表，由用户输入各结点data域之值,〃以0表达输入结束(e1emtyped;〃定义数据元素dnodetype*h=NULL,*s,*t;〃定义结点指针inti=l;cout<V”建立一个单链表“VVend1;while(l)(cout«〃输入第"v<i<<〃结点data域值：〃；cin»d；..if(d==0)break;//以0表达输入结束if(i==l)//建立第一个结点h=(nodetype*)mal1oc(sizeof(nodetyPe));〃表达指针hstr.1ength=O;if(i<=0||i>s.length||i+j>s.1ength+1)(printf("字符串删除失败\n");returnstr;)for(k=0;k<i-l；k++)str.data[k]=s.data[k];for(k=i+j-1;k<s.length;k++)str.data[k—j]=s.data[k];str.length=s.1ength-j;printf(〃删除子字符串成功剩余长度为：％d\n〃,str,length);returnstr;)〃替换字符串voidRepStr(SqStrings,inti,intj,SqStringt)(intk;SqStringstr;str.1ength=0;if(i<=0I|i>s.1ength||i+j-1>s.length)printf（〃字符串替换失败了\n〃）；for(k=0;k<i—1;k++)str.data[k]=s.data[k];for(k=O;k<t.Iength;k++)str.data[i+k—l]=t.data[k];for(k=i+j-l；k<s.Iength;k++)str.data[t.1ength+k-j]=s.data[k];str.Iength=s.1ength-j+t.1ength；Printf(〃替换字符串成功新字符串长度为：％d\n〃，str.length))//字符串的输出voidDispStr(SqStrings)inti；if(s.1ength>0)(printf(〃下面输出这个字符串\n”)；for(i=0；i<s.Iength；i++)printf("%c",s.data[i]);printf(^Xn”)；elseprintf(〃目前空字符串无法输出\n〃)；►voidmain()(SqStrings;chara口={"wenxian1iangn);〃字符串常量aStrAssign(s,a)；DispStr(s);StrLength(s);SqStringsl,s2,t;//si是待复制的字符串变量printf(n请输入一个字符串t:\n〃)；seanf("%sn,t.data);StrAssign(t,t.data);StrCopy(sl,t);〃复制字符串StrLength(si);DispStr(si);Printf(〃下面判断字符串s1和字符串s是否相等\n〃);StrEqua1(s,s1);printf(〃下面将字符串si和字符串s合并一起\n”)；SqStringstr;str=Concat(s,si);〃合并字符串DispStr(str);StrLength(str)；SubStr(str,22,7);//求子字符串str=DeleStr(str,15,4);〃删除字符串DispStr(str)；StrLength(str);printf(“请插入一个字符串s2\n");scanf(n%sH,s2.data);StrAssign(s2,s2.data);str=InserStr(str,15,s2);〃插入字符串DispStr(str)；StrLength(str);printf(〃顺序字符串的基本运算到此结束了\n〃)；实验结果:-口c<"E:\VC6EN\C0D0U\ISDEV98\BIli\Debug\Textl.exe*4L出an串7串了：符功为字成瞿这等相是S串符字一并合S串符和等字电为长$:SI相和符ab,・败功符串不si字ng为失成字符子字—这{此g复率g断.{X千出anffi吕ffitti一一共弓72序g1S功符ef..串成字ng为符*ia度字符这san串一输Xi父ef串■非判个将输xi^J^<子输Xi攵56

面n字输cd符字面cd面两面面2XX子面烫除面n字插34下世此请a嚣下lab下这下下R7e此子子下此请g•E:\VC6EM\C0IM01i\ISDEV98\BIB\Debug\Textl.exe4?e2f9此nu^1:7e至t1wr56票on17S2警3424运c:串长符12..本to为符功字ng为基y度字成个iamske长个长串y串一7符出an串符an符A56字输Xi符字S字插34入面n停es匕青2雨Fe匕页*实验四编程建立二叉树,对树进行插入删除及遍历的程序1.实验目的(1)进一步掌握指针变量的用途和程序设计方法。(2)掌握二叉树的结构特性，以及链式存储结构的特点及程序设计方法。掌握构造二叉树的基本方法。(4)掌握二叉树遍历算法的设计方法。.实验规定(1)认真阅读和掌握和本实验相关的教材内容。(2)掌握一个实际二叉树的创建方法。(3)掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。.实验内容1。)定义二叉链存储结构。(2)设计二叉树的基本操作(初始化一棵带头结点的二叉树、左结点插入、右结点插入、中序遍历二叉树等)。(3)按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。(4)编写测试主函数并上机运营。打印出运营结果，并结合程序运营结果进行分析。实验代码：Winc1ude<iostream.h>typedefstructbitnode(chardata;structbitnode*1chiId,*rchiId；}binode,*bitree•voidereatebitree(bitree*T){charch;cin»ch；if(ch==,O')“*T)=NULL;e1se{K*T)=newbitnode;fi(*T)->data=ch；ereatebitree(&(*T)—>lchild)；ocreatebitree(&(*T)->rchiId);voidinorderout(bitreeT){if(T){^inorderout(T->lchild)；6cout<<T->data«endl；inorderout(T->rchild)5})voidposterder(bitreeT){if(T){»postorder(T->lchild)；postorder(T->rchi1d);。cout«T->data<<end1；intcountleaf(bitreebt){if(!bt)fireturn0;if(bt->lchild==NULL&&bt->rchi1dNULL)return1;(bt->lchi1d)+countle(bt->lchi1d)+countlevoidmain(){bitreebt;createbitree(&bt)inorderout(bt);cout«z//z«endl;postorder(bt);countleaf(bt);c、E:\VC6EN\C0D0N\lSDEV98\BIli\Debug\Textl.exe|ABD0G000CE00F00DECFbFbPressanykeytocontinue实验五建立有序表并进行折半查找1.实验目的掌握递归算法求解问题的基本思想和程序实现方法。2a,实验规定1。)认真阅读和掌握本实验的算法思想。(2)编写和调试完毕程序。(3)保存和打印程序的运营结果，并对运营结果进行分析。3,实验内容(1)分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。(2)编写程序实现：在保存于数组的1000个有序数据元素中查找数据元素x是否存在。数据元素X要包含两种情况：一种是数据元素X包含在数组中；另一种是数据元素X不包含在数组中(3)数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。(4)根据两种方法的实际运营时间，进行两种方法时间效率的分析对比。实验代码：#inc1ude<stdio.h>#include<stdlib.h>#defineMAX_LENGTH100typedefintKeyType;typedefstruct(。intkey;}E1emType;typedefstruct〃。号单元空出(〃。号单元空出ElemTypeelem[MAX_LENGTH];n11ength;}SSTable;intSearch_Bin(SSTableST,KeyTypekey)(ntlow,high,mid;olow=1;high=ST.length；while(1ow<=high)mid=(1ow+high)/2;h->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«”输出一个单链表:〃V<end1«M。if(key==ST.elem[mid].key)o。returnmid;else。if(key<ST.elem[mid].key)eghigh=mid-1;oelsegolow=mid+1;)return0;)voidmain()(inti,resuIt;SSTab1eST;KeyTypekey;printf(”pleaseinputlength:11);oscanf(“%d"，&ST.1ength)；ofor(i=l;i<=ST.1ength;i++)(printf(npleaseinputST.e1em:n);。scanf("%d",&ST.elem[i]);oprintf("pleaseinputkeyword:")；oscanf("％d"，&key);result=Search_Bin(ST,key)；

Af(result==O)^printf(nDon*tfind\nn)；。eIse叩rintf(HFindthekey,thepositionis%d\n"，resu1t);)实验结果:c\"E:\VC6EK\C0D0N\ISDEV98\BIH\Debug\Text1.ezerindthekey,thepositionis4pleaseinputlength：5pleaseinputST.elen：lpleaseinputST.elen：2pleaseinputST.elen：3pleaseinputST.elen：4pleaseinputST.elen：5pleaseinputkeyword：4Pressanykeytocontinue实验六建立一组记录并进行插入排序.实验目的(1)掌握插入排序算法的思想。(2)掌握顺序队列下插入排序算法的程序设计方法。.实验规定(1)认真阅读和掌握教材中插入排序算法的思想。(3)编写基于顺序队列的插入排序排序算法并上机实现。.实验内容(1)编写基于顺序队列的插入排序函数。(2)设计一个测试主函数，实现对基于顺序队列结构的插入排序算法的测试。(3)分析程序的运营结果。实验代码：#include<stdio.h>#include<stdIib.h>#defineMAXSIZE100typedefstruct{intkey；}sortkey;typedefstruct{sortkeye1em[MAXSIZE];intlength;}sorte1em；voidInsertSort(sortelem*p){inti,j；for(i=2；i<=p->length;i++){if(p->elem[i].keyvp—〉elem[i-1].key)/*小于时，需将elem[i]插入有序表*/p—>elem[O].key=p->elem[i].key；/*为统一算法设立监测*/for(j=i-l;p->elem[O].key<p->elem[j].key;j--)P->e1e+.key=p->elem[j].key;/*记录后移*/p->elem[j+l].key=p->elem[0].key;/*插入到对的位置*/)})voidmain(){sorte1em*p;inti;intb[6]={45,23,54,6,4,46};p=(sortelem*)malloc(sizeof(sorte1em));p->length=O;for(i=l;i<7;i++){P->e1em[i].key=b[i—1]；p->length++；}InsertSort(p);for(i=1;i<7;i++){printf("%d",p->eIem[i].key);system("pause")；}实验结果：N:\VC6EH\C0Q0H\ISDEV98\BIR\Debug\Text1.exe4623454654字短任意盥禄续.・・Pressanykeytocontinue.实验七建立一组记录并进行快速排序.实验目的(1)掌握快速排序算法的思想。(2)掌握顺序队列下快速排序算法的程序设计方法。.实验规定(1)认真阅读和掌握教材中快速排序算法的思想。(3)编写基于顺序队列的快速排序排序算法并上机实现。3,实验内容(1)编写基于顺序队列的快速排序函数。(2)设计一个测试主函数，实现对基于顺序队列结构的快速排序算法的测试。(3)分析程序的运营结果。实验代码：#include<iostream.h>voidquick_sort(inta[],intlow,inthigh)inti,j,pivot；if(1ow<high){pivot=a[low];i=low;j=high;while(i<j){〃从顶端开始比较值，假如小于标准值，停止while(i<j&&a[j]>=pivot){j;}〃将比pivot小的元素移到低端，下标加加if(i<J)a[i++]=a[j];//从底端开始比较值，假如大于标准值，停止

while(i<j&&a[i]<=pivot){i++；}//将比pivot大的元素移到顶端，下标减减if(i<j)a[j-]=a[i];}//pivot移动到最终位置a[i]=pivot;〃对左区间进行递归排序quick_sort(a,Iow,i-1)；//对右区间进行递归排序quick_sort(a,i+1,high);}}voidprint_array(inta[],intn){for(inti=0；i<n;i++){cout<<a[i]<<"，"；}}intmain(){intdata[9]={54,38,96,23,15,72,60,45,83)；quick_sort(data,0,8);print_array(data,9)；return0；}实验结果:c：＜"E:\VC6EH\C0H01i\ISDEV98\BIII\Debug\Text1.exe*15,23,38-45,54,60,72,83」96「Pressanykeytocontinueif(p==N