太原理工大学数据结构实验报告

本科实验报告课程名称：数据结构B实验项目：线性结构、树形结构、图结构、查找、排序实验地点：专业班级：学号：学生姓名：指导教师：2013年1月13日线性结构一、实验目的和要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。二、实验内容和原理习题[问题描述]设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。[输入]顺序表的长度，初始化顺序表数据，插入数据X。[输出]已建立顺序表，输出插入X后的顺序表。[存储结构]采用顺序存储结构[算法的基本思想]建立顺序表（用数组的形式实现）。在表中从后往前查找要插入元素的位置，直到查找到第一个比X小的数，并从表的最后一元素依次后移，把要插入元素插入搜查找位置。三、主要仪器设备使用的计算机惠普：硬件配置Win7、软件环境win-TC四、操作方法与实验步骤[习题源程序]#includestdio.h#defineMAXSIZE100#defineRIGHT1#defineERROR0typedefintElemType;typedefstruct{ElemTypeelem[MAXSIZE];intlast;}SeqList;voidInitlist(SeqList*L){L-last=-1;}voidputseqList(SeqList*L,intn){inti;for(i=0;in;i++)scanf(%d,&(L-elem[i]));L-last=L-last+n;}intLenList(SeqList*L){intLen;Len=L-last+1;returnLen;}intPositionList(SeqList*L,intX){intj;for(j=0;j=L-last;j++)if(XL-elem[j])returnj+1;return(L-last+1);}intInsList(SeqList*L,inti,inte){intk;if((i1)||(iL-last+2)){printf(thepositioniswrong);return(ERROR);}if(L-last=MAXSIZE-1){printf(thelistisfull);return(ERROR);}for(k=L-last;k=i-1;k--)L-elem[k+1]=L-elem[k];L-elem[i-1]=e;L-last++;return(RIGHT);}intOutputSeqList(SeqList*L){inti;for(i=0;i=L-last;i++)printf(%d,,L-elem[i]);return(L-elem[i]);}voidmain(){ints,c;SeqListL;Initlist(&L);printf(pleaseinputthelength:);scanf(%d,&s);printf(pleaseinputthelist:);putseqList(&L,s);LenList(&L);printf(Pleaseinputanelementtoinsert:);scanf(%d,&c);InsList(&L,PositionList(&L,c),c);OutputSeqList(&L);printf(\n);getch();}五、实验数据记录和处理六、实验结果与分析此程序的优点是算法简单，易于实现。但是由于采用的是顺序存储的形式，导致算法的时间性能和空间性能不是很好，而且本程序的的健壮性不是很好，对空间不够的情况没有很人性化的提出解决方案。七、讨论、心得改进思想：#defineLIST_INIT_SIZE100typedefstruct{int*elem;intlength;intlistsize;}sqlist;voidcreat_sqlist(sqlist*p){inti,l;p-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!p-elem){printf(OVERFLOW);exit(1);}printf(Pleaseinputlength:\n);scanf(%d,&l);p-length=l;p-listsize=LIST_INIT_SIZE;printf(Inputsqlist:\n);for(i=0;ip-length;i++)scanf(%d,&p-elem[i]);for(i=0;ip-length;i++)printf(%d,p-elem[i]);printf(\n);}这是对顺序表构造的部分改进，同时可以将数据的存储改成链表的形式。心得体会：通过本次试验让我对顺序表有了更深层次的了解，同时也对顺序表和链表的区别有了自己的见解。树形结构一、实验目的和要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。二、实验内容和原理习题[问题描述]编写递归算法，计算二叉树中叶子结点的数目。[输入]一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD..EH...CF.I..G..。ABCDEFGHI[输出]二叉树中叶子结点的个数[存储结构]采用二叉链表存储。[算法的基本思想]求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。三、主要仪器设备使用的计算机惠普：硬件配置Win7、软件环境win-TC四、操作方法与实验步骤[习题源程序]#includestdio.hstructBiTree{chardata;structBiTree*lchild;structBiTree*rchild;};structBiTree*CreatBiTree(){charx;structBiTree*p;scanf(%c,&x);if(x!='.'){p=(structBiTree*)malloc(sizeof(structBiTree));p-data=x;p-lchild=CreatBiTree();p-rchild=CreatBiTree();}elsep=NULL;returnp;}intLeafNum(structBiTree*T){if(!T)return0;elseif(!T-lchild&&!T-rchild)return1;elsereturnLeafNum(T-lchild)+LeafNum(T-rchild);}intmain(){intnum;structBiTree*T;printf(Pleaseinputthetree(pre):¥n);T=CreatBiTree();while(T==NULL){printf(empoty,again:¥n);T=CreatBiTree();}num=LeafNum(T);printf(¥nthesumofleafis:%d¥n,num);getch();}五、实验数据记录和处理六、实验结果与分析实验程序采用了二叉链表作为存储结构方便了递归函数的进行。此外由于数的定义采用了递归的形式，所以关于数的构造、遍历、以及其他运算采用递归形式，使得程序的可阅读性增强。七、讨论、心得改进思想：voidCountLeaf(BitreeT,int&cout){if(T){if((!T-lchild)&&(!T-rchild))count++;}CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);}采用C++的引用形式，可以对叶子结点的程序上进行修正，使其看起来更为简练。心得体会：通过实验操作，了解到了数的递归定义的优点，以及对于程序算法上的思想指导。同时，也对数的不同存储形式有了了解。图结构一、实验目的和要求熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。二、实验内容和原理习题【问题描述】试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径（i≠j）。【输入】图的顶点个数N，以及以V1、V2、V3、V4为弧尾的所有的弧，并以-1结束。还有你要判断是否连通的两个顶点。【输出】若A到B无路径，则输出“不是连通的”,否则输出A到B路径上各顶点。【存储结构】图采用邻接矩阵的方式存储。【算法的基本思想】采用深度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,...,VAK,访问遍之后,若没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,...,VA1M，再访问与VA2邻接顶点...，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。实现时采用队列记录被访问过的顶点。每次访问与队头顶点相邻接的顶点，然后将队头顶点从队列中删去。若队空，则说明到不存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来，以便输出时回溯。三、主要仪器设备使用的计算机惠普：硬件配置Win7、软件环境win-TC四、操作方法与实验步骤[习题源程序]#includestdio.hintn;structVNode{intposition;structVNode*next;};structArcNode{intmark;structVNode*first;};voidDFS(structArcNode*v,structArcNode*w){structVNode*L;w-mark=1;L=w-first;while(L!=NULL){if((v+(L-position))-mark==0){DFS(v,(v+L-position));}L=L-next;}}intmain(){inti,j,k;intkey1,key2;intnum=0;structArcNode*p;structVNode*temp;structVNode*flag;printf(youxiangtudedingdian:\n);scanf(%d,&n);while(n1){printf(shurucuowu,again:\n);scanf(%d,&n);}p=(structArcNode*)malloc(n*sizeof(structArcNode));for(i=0;in;i++){printf(shuruV%d\n,i+1);scanf(%d,&k);if(k==-1){p[i].mark=0;p[i].first=NULL;}else{temp=(structVNode*)malloc(sizeof(structVNode));temp-position=k;temp-next=NULL;p[i].first=temp;p[i].mark=0;flag=temp;scanf(%d,&k);while(k!=-1){temp=(structVNode*)malloc(sizeof(structVNode));temp-position=k;temp-next=NULL;flag-next=temp;flag=temp;scanf(%d,&k);}}}printf(shuruliangdiandeweizi:\n);printf(\n);scanf(%d%d,&key1,&key2);DFS(p,(p+key1));if(p[key2].mark==1){printf(V%d\V%d\n,key1+1,key2+1);}else{p[key1].mark=0;DFS(p,(p+key2));if(p[