还剩37页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构实验报告全集实验一线性表基本操作和简朴程序.实验目的a1掌握使用Visua1C++
6.0上机调试程序的基本方法;a2掌握线性表的基本操作初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法.实验规定1认真阅读和掌握和本实验相关的教材内容2认真阅读和掌握本章相关内容的程序3上机运营程序4保存和打印出程序的运营结果,并结合程序进行分析5按照你对线性表的操作需要,重新改写主程序并运营,打印出文献清单和运营结果实验代码:1头文献模块ttincludeiostream.h//头文献ttincludema11oc.h〃库头文献typedefintelemtype;//定义数据域的类型typedefstruct1inknode//定义结点类型elemtypedata;//定义数据域structlinknode*next;〃定义结点指针}nodetype;voidmainnodetype*head;〃定义节点指针变量head=create;〃创建一个单链表disphead;〃输出单链表cout“单链表长度“lenhead«endl;inshead20;〃在第二个节点之后插入以0为元素的节点disphead;//输出新链表de1head2;〃删除第二个节点disphead;//^^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定义一个函数用来判断算术表达式中包含圆括号、方括号是否对的配对其中,括号配对共有四种情况:左右括号配对顺序不对的;右括号多于左括号;左括号多于右括号;左右括号匹配对的设计一个测试主函数进行测试对程序的运营结果进行分析实验代码ftincludestdio.hA#defineMaxSize100typedefstruct{aintdata[MaxSize];ainttop;}SqStack;voidInitStackSqStack*st//初始化栈a{ast-top=-1;}^intStackEmptySqStack*st〃判断栈为空a{returnst-top==11;voidPushSqStack*stintx〃元素进栈ifst—top==MaxSize~last-top++;st-data[st—top]=x;a}a}avoidPopSqStack*st〃退栈ifst-top==-lAprintf〃栈下溢出\n〃;elsest-top一;}intGettopSqStack*st〃获得栈顶元素ifst—top==-1a{aprintf栈空\n〃;return0;}aelsereturnst—data[st—top];}AvoidDisplaySqStack*st//打印栈里元素{ainti;printf〃栈中元素〃;afori=st—top;i=0;--i”printfn%dnst-data[i];printf〃\n;intmain〃测试]SqStackL;aSqStack*st=L;aInitStackst;aprintf〃栈空%d\n〃,StackEmptyst;forinti=l;i10;++ireturn0;实验结果::\VC6EN\C0D0N\ISDEV98\BIR\Debug\Text
1.exe76543254321tocontinue实验三串的基本操作和简程序.实验目的掌握串基木操作初始化、联接、替换、子串等运算在堆分派存储储结构上的程序设计方法.实验规定1)认真阅读和掌握和本实验相关的教材内容
(2)认真阅读和掌握本章相关内容的算法并设计程序序
(3)上机运营程序4保存和打印出程序的运营结果,并结合程序进行分析实验代码:Windudestdio.h#defineMaxSize50typedefstruct{chardata[MaxSize];//存放字符串intlength;//字符串长度}SqString;〃将一个字符串常量赋给串svoidStrAssignSqStringscharcstr[]{inti;fori=0;cstr[i]!=\0;i++〃这个,\0代表字符串结束标志,编译系统自动加上的s.data[i]=cstr[i];s.length=i;〃字符串的复制voidStrCopySqStringsSqStringtfori=0;it.1ength;i++s.data[i]=t.data[i];s.length=t.1ength;printf〃字符串复制成功了\n〃;//判断字符串是否相等voidStrEqualSqStringsSqStringtintisame=l;ifs.1ength!=t.lengthsame=0;elsefori=0;is.length;i++ifs.data[i]!=t.data[i]same=0;break;ifsame==0printf这两个字符串不相等\n〃;e1seprintf〃这两个字符串相等\n〃;}〃字符串的长度voidStrLengthSqStrings{printf此字符串长度为:%d\n”,s.1ength;}〃合并字符串SqStringConcatSqStringsSqStringtSqStringstr;inti;str.length=s.1ength+t.length;fori=0;is.length;i++str.data[i]=s.data[i];fori=0;it.length;i++str.data[s.Iength+i]=t.dataEi];returnstr;}〃求子字符串voidSubStrSqStringsintiintjSqStringstr;intk;str.length=0;ifi=0||is.length||0IIi+j-ls.1engthprintf〃子字符串复制失败\n〃;fork=i-1;ki+j-l;k++str.data[k—i+l]=s.data[k];str.length=j;printf子字符串复制成功长度为%d\n\j;printf下面输出此子字符串\n;fori=0;ij;i++printf%c”str.dataEi];printf”\n;//插入字符串SqStringInserStrSqStringsiintiSqStrings2intj;SqStringstr;str.1ength=0;ifi=01|is
1.length+1printf字符串插入失败\n〃;returnstr;forj=0;ji-l;j++str.data[j]=sl.data[j];forj=0;js
2.1ength;j++str.data[i—l+j]=s
2.data[j];forj=i-l;js
1.length;j++str.data[s
2.length+j]=sl.data[j];str.Iength=sl.Iength+s
2.length;printf插入字符串成功长度为:%d\nstr.length;returnstr;〃删除字符串SqStringDeleStrSqStringsintiintj{intk;SqStringstr;2)创建单链表nodetype*create//建立单链表,由用户输入各结点data域之值〃以0表达输入结束e1emtyped;〃定义数据元素dnodetype*h=NULL*s*t;〃定义结点指针inti=l;coutV”建立一个单链表“VVend1;whilelcout«〃输入第vi〃结点data域值〃;cin»d;..ifd==0break;//以0表达输入结束ifi==l//建立第一个结点h=nodetype*mal1ocsizeofnodetyPe;〃表达指针hstr.1ength=O;ifi=0||is.length||i+js.1ength+1printf字符串删除失败\n;returnstr;fork=0;ki-l;k++str.data[k]=s.data[k];fork=i+j-1;ks.length;k++str.data[k—j]=s.data[k];str.length=s.1ength-j;printf〃删除子字符串成功剩余长度为%d\n〃strlength;returnstr;〃替换字符串voidRepStrSqStringsintiintjSqStringtintk;SqStringstr;str.1ength=0;ifi=0I|is.1ength||i+j-1s.lengthprintf(〃字符串替换失败了\n〃);fork=0;ki—1;k++str.data[k]=s.data[k];fork=O;kt.Iength;k++str.data[i+k—l]=t.data[k];fork=i+j-l;ks.Iength;k++str.data[t.1ength+k-j]=s.data[k];str.Iength=s.1ength-j+t.1ength;Printf〃替换字符串成功新字符串长度为%d\n〃,str.length//字符串的输出voidDispStrSqStringsinti;ifs.1ength0printf〃下面输出这个字符串\n”;fori=0;is.Iength;i++printf%cs.data[i];printf^Xn”;elseprintf〃目前空字符串无法输出\n〃;►voidmainSqStrings;chara口={wenxian1iangn;〃字符串常量aStrAssignsa;DispStrs;StrLengths;SqStringsls2t;//si是待复制的字符串变量printfn请输入一个字符串t:\n〃;seanf%snt.data;StrAssigntt.data;StrCopyslt;〃复制字符串StrLengthsi;DispStrsi;Printf〃下面判断字符串s1和字符串s是否相等\n〃;StrEqua1ss1;printf〃下面将字符串si和字符串s合并一起\n”;SqStringstr;str=Concatssi;〃合并字符串DispStrstr;StrLengthstr;SubStrstr227;//求子字符串str=DeleStrstr154;〃删除字符串DispStrstr;StrLengthstr;printf“请插入一个字符串s2\n;scanfn%sHs
2.data;StrAssigns2s
2.data;str=InserStrstr15s2;〃插入字符串DispStrstr;StrLengthstr;printf〃顺序字符串的基本运算到此结束了\n〃;实验结果:-口cE:\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.exe4e2f9此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编写测试主函数并上机运营打印出运营结果,并结合程序运营结果进行分析实验代码Winc1udeiostream.htypedefstructbitnodechardata;structbitnode*1chiId*rchiId;}binode*bitree•voidereatebitreebitree*T{charch;cin»ch;ifch==O“*T=NULL;e1se{K*T=newbitnode;fi*T-data=ch;ereatebitree*T—lchild;ocreatebitree*T-rchiId;voidinorderoutbitreeT{ifT{^inorderoutT-lchild;6coutT-data«endl;inorderoutT-rchild5}voidposterderbitreeT{ifT{»postorderT-lchild;postorderT-rchi1d;cout«T-dataend1;intcountleafbitreebt{if!btfireturn0;ifbt-lchild==NULLbt-rchi1dNULLreturn1;returncountleafafbt-rchild;}voidmain{bitreebt;createbitreebtinorderoutbt;cout«z//z«endl;postorderbt;countleafbt;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根据两种方法的实际运营时间,进行两种方法时间效率的分析对比实验代码#inc1udestdio.h#includestdlib.h#defineMAX_LENGTH100typedefintKeyType;typedefstructintkey;}E1emType;typedefstructElemTypeelem[MAX_LENGTH];n11ength;}SSTable;intSearch_BinSSTableSTKeyTypekeyntlowhighmid;olow=1;high=ST.length;while1ow=highmid=1ow+high/2;h-data=d;h-next=NULL;t=h;//h是头指针else//建立其余结点s=nodetype*mallocsizeofnodetype;s-data=d;s-next=NULL;t-next=s;t=s;//t始终指向生成的单链表的最后一个节点i++;returnh;3输出单链表中的元素voiddispnodetype*h//输出由h指向的单链表的所有data域之值nodetype*p=h;cout«”输出一个单链表:〃Vend1«Mifkey==ST.elem[mid].keyoreturnmid;elseifkeyST.elem[mid].keyeghigh=mid-1;oelsegolow=mid+1;return0;voidmainintiresuIt;SSTab1eST;KeyTypekey;printf”pleaseinputlength:11;oscanf“%d,ST.1ength;ofori=l;i=ST.1ength;i++printfnpleaseinputST.e1em:n;scanf%dST.elem[i];oprintfpleaseinputkeyword:;oscanf%d,key;result=Search_BinSTkey;Afresult==O^printfnDon*tfind\nn;eIse叩rintfHFindthekeythepositionis%d\n,resu1t;实验结果:c\E:\VC6EK\C0D0N\ISDEV98\BIH\Debug\Text
1.ezerindthekeythepositionis4Pressanykeytocontinue实验六建立一组记录并进行插入排序.实验目的1掌握插入排序算法的思想2掌握顺序队列下插入排序算法的程序设计方法.实验规定1认真阅读和掌握教材中插入排序算法的思想3编写基于顺序队列的插入排序排序算法并上机实现.实验内容1编写基于顺序队列的插入排序函数2设计一个测试主函数,实现对基于顺序队列结构的插入排序算法的测试3分析程序的运营结果实验代码#includestdio.h#includestdIib.h#defineMAXSIZE100typedefstruct{intkey;}sortkey;typedefstruct{sortkeye1em[MAXSIZE];intlength;}sorte1em;voidInsertSortsortelem*p{intij;fori=2;i=p-length;i++{ifp-elem[i].keyvp—〉elem[i-1].key/*小于时,需将elem[i]插入有序表*/p—elem[O].key=p-elem[i].key;/*为统一算法设立监测*/forj=i-l;p-elem[O].keyp-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]={4523546446};p=sortelem*mallocsizeofsorte1em;p-length=O;fori=l;i7;i++{P-e1em[i].key=b[i—1];p-length++;}InsertSortp;fori=1;i7;i++{printf%dp-eIem[i].key;systempause;}实验结果N:\VC6EH\C0Q0H\ISDEV98\BIR\Debug\Text
1.exe4623454654字短任意盥禄续.・・Pressanykeytocontinue.实验七建立一组记录并进行快速排序.实验目的1掌握快速排序算法的思想2掌握顺序队列下快速排序算法的程序设计方法.实验规定1认真阅读和掌握教材中快速排序算法的思想3编写基于顺序队列的快速排序排序算法并上机实现3实验内容1编写基于顺序队列的快速排序函数2设计一个测试主函数,实现对基于顺序队列结构的快速排序算法的测试3分析程序的运营结果实验代码#includeiostream.hvoidquick_sortinta[]intlowinthighintijpivot;if1owhigh{pivot=a[low];i=low;j=high;whileij{〃从顶端开始比较值,假如小于标准值,停止whileija[j]=pivot{j;}〃将比pivot小的元素移到低端,下标加加ifiJa[i++]=a[j];//从底端开始比较值,假如大于标准值,停止whileija[i]=pivot{i++;}//将比pivot大的元素移到顶端,下标减减ifija[j-]=a[i];}//pivot移动到最终位置a[i]=pivot;〃对左区间进行递归排序quick_sortaIowi-1;//对右区间进行递归排序quick_sortai+1high;}}voidprint_arrayinta[]intn{forinti=0;in;i++{couta[i],;}}intmain{intdata
[9]={543896231572604583;quick_sortdata08;print_arraydata9;return0;}实验结果:c<E:\VC6EH\C0H01i\ISDEV98\BIII\Debug\Text
1.exe*152338-4554607283」96「Pressanykeytocontinueifp==NULLcout«”空表”;whilep!=NULLcout«p—data;p=p-next;}cout«endl;}4计算单链表的长度intlennodetype*h〃返回单链表的长度inti=0;nodetype*p=h;whilep!=NULL.p=p-next;i++;returni;5寻找第i个节点nodetype*findnodetype*hinti〃返回第i个节点的指针nodetype*p=h;intj=l;ifilenh||i=0returnNULL;//i上溢或下溢ce1sewhilep!NULLjVl〃查找第i个节点,并由p指向该节点j++;p=p-next;returnp;6)单链表的插入操作nodetype*insnodetype*hintielemtypex//在单链表head中第i个节点//i=0之后插入一个data域为x的节点nodetype*p*s;s=nodetype*ma11ocsizeofnodetype;//仓J建节点ss-data=x;s—next=NULL;ifi==0//i=0:s作为该单链表的第一个节点s-next=h;h=s;}else{p=findhi;//查找第i个节点,并由p指向该节点ifp!=NULLs—next=p—next;p-next=s;returnh;7单链表的删除操作nodetype*delnodetype*hinti//删除第i个节点{nodetype*p=h*s;intj=1ifi==l〃删除第1个节点h=h-next;freep;elseP=findhiT;〃查找第iT个节点,并由p指向该节点.ifp!=NULLp-next!=NULLS=p—next;〃s指向要删除的节点p-next=s-next;frees;}e1secoutn输入i的值不对的“Xendl;returnh;8释放节点空间Voiddisposenodetype*h〃释放单链表的所有节点占用的空间nodetype*pa=h*pb;ifpa!=NULLpb=pa—next;ifpb=NULL//只有一个节点的情况freepa;elsewhilepb!=NULL〃有两个及以上节点的情况freepa;pa=pb;pb=pb-next;}freepa;}9主程序模块#inc1udenslink.h〃包含头文献siinkpleaseinputlength5pleaseinputST.elen lpleaseinputST.elen2pleaseinputST.elen3pleaseinputST.elen4pleaseinputST.elen5pleaseinputkeyword4。