参考资料河南自考数据结构实验报告

河南省高等教育自学考试实验报告册运算机及应用专业（本科段）《数据结构》姓名准考证号所属地市实验地址实验日期2实验总成绩指导教师签名实验单位（实验室）意见主考院校审核意见河南科技大学自学考试办公室2021年9月21日char vertex;edgenode*edgelink;；struct Graph{vexnode adjlists[MaxVerNum]int vexnum;int arcnum;；ertex;G-adjlists[i].edgelink二NULL;cout〃开始输入边表信息〃endl;for k=0;kG-arcnum;k++{cout〃请输入边Vi,Vj对应的极点〃;cinij;pl=new edgenode;pl-endver=j;pl-edgenext=G-adjlists[i].edgelink;G-adjlists[i].edgelink=pl;p2=new edgenode;p2-endver=i;p2-edgenext=G-adjlists[j].edgelink;G-adjlists[j].edgelink二p2;ertex，z〃；visit[i]=l;edgenode*p=new edgenode;p=G-adjlists[i].edgelink;ifG-adjlists[i].edgelink!visit[p-endver]{DFSG,p-endver,visit;}void DFStraversalGraph*G,char c ertex==certex，z〃visit[e]=l;edgenode*p=new edgenode;p=G-adjlists[e].edgelink;if pint m=p-endver;if m==0EnQueueQ,m;while visit[m]=0p=p-edgenext;if p二二NULL break;m=p-endver;EnQueueQ,m;}}void BFStraversalGraph*G,char ccout〈〃该图的广度优先遍历结果为:〃〈endl;int visited[MaxVerNum];for int i=0;iG-vexnum;i++{visited[i]=O;intm;for i=0;iG-vexnum;i++{if G-adjlists[i].vertex二二cm=i;BFS G,i,visited;break;}

五、实验内容功能•随机输入假设干整数成立一个线性表，查找指定节点的位置；•按升序输入假设干整数成立一个有序表查找指定节点的位置；•随机输入假设干整数成立一个二叉排序树，查找指定节点的位置；输入要求先输入表中结点的个数N,然后输入N整数测试数据（略）

六、数据查找

（一）、实验目的把握在线性表上进行顺序查找、二分查找的算法实现和在二叉排序树上的查找算法的实现

（二）、程序清单（）int TSearchSSTable ST,int key{））ey returnmid;ey high=mid-1;ey=key;printf（请输入第％d个数，大于％d\n,n,[i-l].key）;scanf（H%dn,key）;；=i}printf（请输入要查的数:\n）;scanf（n%dn,key）;（）postion=Search_Bin T,key;printf（此数的位置是%d\nn,postion）;

（三）、实验中显现的问题及解决方式随机输入假设干整数成立一个二叉排序树，查找指定节点的位置二叉树查找代码容易犯错实验四排序

一、实验学时2学时

二、实验目的把握对一批记录进行排序的各类算法，包括直接插入排序法、冒泡排序法、直接选择排序法和快速排序法

三、实验原理排序的方式

四、实验设备:本实验在586以上的微机上进行，运行环境为TurboC.

五、实验内容功能•随机输入假设干整数，按直接插入排序法排序并输出；•输入假设干整数，按冒泡排序法排序并输出；•随机输入假设干整数，按直接选择排序法排序并输出；输入要求任意输入N整数测试数据（略）

六、选做题目对快速排序、希尔排序、堆排序进行比较

（一）、实验目的把握对一批记录进行排序的各类算法，包括直接插入排序法、冒泡排序法、直接选择排序法和快速排序法

二、程序清单#include#includeWincludeOttdefine M20/*****把排序之前的数输入到指定文件夹中*****/Void writefilelint*a,int n{FILE*fp;int i;char filename

[10];printf〃请输入要输出的文件名称包括后缀名\n〃;getsfilename;if fp=fopenfilename,zzw，z==NULLfprintf不能打开文件！\n;fprintf〃排序之前*****\n〃;fori=l;i=n;i++fprintf zz%3d/z,a[i];}/*****把用各类排序方式排序后的数输入到指定文件夹中*****/void writefile2int int n{FILE*fp;int i;char filename

[10];fprintf〃请输入要输出的文件名称包括后缀名\n〃;getsfilename;if fp=fopen filename,/zw/z==NULLfprintf不能打开文件！\n;printf〃排序以后*****\n〃;fori=l;i=n;i++printf zz%3d〃，a[i];a

[0]=-l;}void createint*a,int*b,int*n{int i,;srandunsignedtimeNULL;for i=0;in;i++{a[i]=rand;b[i]=a[i];printfz，%8d〃，a[i];}/***1*****插入排序**********/void insertsortint*a,int n{int i,j;for i=2;i〈=n;i++{a

[0]=a[i];for j=i-l;a

[0]a[j];j—a[j+l]=a[j];a[j+l]=a

[0];}}void xiersortint*a,int n{int d

[3]={5,3,1};int i,j,k=0;while k3{for i=d[k]+l;i=n;i++{a

[0]=a[i];forj=i-d[k];j0a[j]a

[0];j=j-d[k]a[j+d[k]]=a[j];a[j+d[k]]=a[O];}k++;}void maopaosortint*a,int n{int i,j,change,t;fori=l;in;i++{change=0;forj=l;j=n-i;j++ifa[j]a[j+l]{t=a[j];aLj]=a[j+l];a[j+l]=t;change=l;}if change==0break;}}void quicksortint*a,int t,int n{int i=t,j=n;while ij{{a

[0]=a[i];whileija[j]a

[0]j-;{a[i]=a[j];i++;}whileija[i]a

[0]i++；ifij{a[j]=a[i];j—;}}a[i]=a[O];quicksort a,1,i-l;quicksort a,i+1,n;}}void jiandansortint*a,intn{int i,j,t;fori=l;in;i++{forj=i+l;j=n;j++ifa[i]a[j]{t=a[i];a[i]=a[j];a[j]=t;void adjustint intlow,int top{int j;a

[0]=a[low];forj=2*low;j=top;j*=2{ifjtopa[j]a[j+Hj++；ifa[j]a

[0]{a[low]=a[j];low=j;a[low]=a

[0];void duisortint*a,int nfori=n/2;i0;i一adjust a,i,n;fori=n;il;一一ia[l]=a[i];{printf〃％5d〃，a[l];adjust a,1,i-l;printf〃贴d〃，a[i];void maininta[M+l],b[M+l],n=0,i;char chi=y,ch2;create a,b,n;while chl==，y「ch]二二，Y，{printf〃\n输入1插入排序〃printf〃\n输入2希尔排序〃printf〃\n输入3冒泡排序〃printf\n输入4快速排序〃printf〃\n输入5简单排序〃printf〃\n输入6堆排序〃；printf〃\n输入C c从头产生随机数〃；printf〃\n输入Nn退出\n〃;

一、实验报告要求1

二、实验一单链表的操作2

三、实验二图的遍历操作6

四、实验三数据查找9

（二）、实验中显现的问题及解决方式随机输入假设干整数模块要注意程序循环的排列，能够让结果按直接选择排序法排序并输出实验报告要求

1、实验报告应包括以下内容1程序清单2实验结果3分析与讨论

2、实验报告应写明实验名称、班号、实验者姓名、学号、将实验报告整理装订好，按指导教师规定的时刻上交大体实验方式本实验环节要求学生能够顺利完成《数据库原理》、《数据结构》、《操作系统》、《面向对象程序设计》及门课程的实验操作实验所用器件、设备的简单介绍所有实验在586以上的微机上进行，运行环境为VFP、C语言、C++语言和windows linux操作系统实验一单链表的操作

一、实验学时2学时

二、实验目的熟悉数据库在链式存储结构下各类算法的实现

三、实验设备:本实验在586以上的微机上进行，运行环境为TurboC语言

四、样例（参看《实践性环节培训与考核大体要求》p2）

五、实验内容功能•成立一个数据域寄存的是字符串的单链表；•输入一个指定的字符串，插入到单链表的指定位置；•删除单链表中制定的字符串；•遍历单链表输入要求输入N个字符串（长度小于6）,成立含有N个节点的单链表，要求输入的字符串不重复测试数据成立时N=5（red,green,yellow,blue,black）插入时orange（在第五个节点以后插入）删除时:blue

（一）、实验目的:}while1;熟悉数据库在链式存储结构下各类算法的实现/iz*£**1**lzlz*lz*1**1*«、、/*1**lzviz*lz*lz*1**lz Ll/\r1*slz%lz%fz%lz%lzslz*lz six%iz*lz*lz//xj%xjx xjxxjxxj%zjx xj%xjx IJWgx✓pxzjx zj%zjxzyx xjs/

（二）、程序清单Listnode*CreateL/Ir1^1r-4-//不不不不不不不不不不不不不不不不不不不L111K1-/1oL不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不/ttinclude#include{int j;ttinclude Listnode*head,*s,*r;#define N5struct node{charhead=Listnodetypedef data

[8];struct node*mallocsizeofListnode;r二*next;}Listnode;head;r-next=NULL;printfa\n请输入%d个字符串”,N;for/*******函数挪用说明*******/j=l;j=N;j++Listnode*CreateL;{priListnode*Getnode;ntf字void TraveLO;符串%d:j;void InsertLO;s=Listnovoid DeleteL;de*malloc/It\C^|~^rT KIX//•I*^rfV/mainsizeofListnode;{int k,j;scanf%s，s-data;Listnode*head,*p;printf“成立单链表:r-next=s;head=CreateL;do{printfn

0.退出\n”）；r-next=NULL;printf〃遍历单链表\n〃）;return head;请选择:printf〃单链表的插入\n〃）;printf〃单链表的删除//zjs#TSXTSzjsztsXlSXgSXjSXTSxTs zTszTsxTsZjSl/IIH1/1zTsZlSzjszjsxTs/void printf〃TraveLListnode*head\n〃）;〃）；{Listnode*p;scanf%d,k;switch kp=head-〉next;;while case0:exit0;pcase1:TravelLhead;break;{printf〃%s〃，p-data;case2:InsertLhead;break;p=p-next;case3:DeleteLhead;二/7z A//xix✓TxxTxxlxrxxixxix✓Tx*Tpi_I/\✓Tx xixzlxTxTxzlx/void InsertLListnode*headchar ch

[8];int k;Listnode*p,*s;printf\n输入要插入的字符串”；scnaf%s,ch;;printfu\n输入要插入的位置;scanf“%d，k;p=Getnodehead,k-1;if p=NULL{printf positionerror!/z;exit0;s=Listnode*mallocsizeofListnode;strcpy s-data,ch;s-next=p-next;p-next=s;/vt**,1*KL*KL*vl*4414*11lvr*.1**,1*KL*KL*%L*KLZ//个个个个个个个个个个个个个个个个个个个个7IIJIJ DTK个个个个个个个个个个个个个个个个个个/void DeleteLListnode*head{char ch

[8];Listnode*p,*q;printf\n输入要删除的字符串;scnaf%s”，ch;;printf\n查找它之前的位置”;p=head;whielp-next{q=p-next;if!strcmpq-data,ch break;P二q；}if p-next{p-next=q-next;freeq;else printfnot found;///ZjSZjSX7SXjXZTSXTXZTSZTSXTSXjSXTXZlSZjSXJSXTS^TS1I*1XTXZrSZTSZTSZTSX7SXjS✓TXZTVZJSZjSZjSZTSZTXZrSZTS/Listnode*GetnodeListnode*head,inti{int j;Listnode*p;p二head;j=0;whilep-nextji{p=p-next;j++；}if i=jreturn p;elsereturn NULL;/xlzsix sixsixsixsixxJxsixx£*s£*fxsixxtx sixsixxlzsixsixlx sixlxsixsixsixxlz//xTx✓Tx✓rxrx✓TxXTX xjxxixxTxXIXxTx xTxxTxxvxxrxxrxxix✓rxxjx XTXxTxxx✓jx xTxxTxxfxxix/

（三）、实验中显现的问题及解决的方式输入N个字符串（长度小于6）,成立含有N个节点的单链表，要求输入的字符串不重复要细心查看实验二图的遍历操作

一、实验学时2学时

二、实验目的采纳邻接矩阵存储方式的无向图的深度优先遍历和广度优先遍历算法的实现

三、实验原理图的大体运算

四、实验设备:本实验在586以上的微机上进行，运行环境为TurboC.

五、实验内容功能•成立一个极点信息是字符的无向图；•输出深度优先遍历的结果；•输出广度优先遍历的结果；输入要求先输入极点数和边数，然后输入极点信息和每条边对应的两个极点的序号测试数据68ABCDEF0103122433445565

六、选做内容编写一个途径遍历算法，求出从北京到哈尔滨途中不通过郑州的所有简单途径，测试数据为教科书中图，起点为北京

七、图的遍历操作

（一）、实验目的采纳邻接矩阵存储方式的无向图的深度优先遍历和广度优先遍历算法的实现

（二）、程序清单ttincludeO#define MaxVerNum50struct edgenode{int endver;int inform;edgenode*edgenext;）；struct vexnode。