还剩21页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
武倨利拉大学Wuhan Universityof ScienceTechnoloqv计算机科学与技术学院实验报告课程名称数据结构专业计算机科学与技术班级级班20221学号202213137024姓名镇方权指导老师邱奕敏Node*st;//st容量足够大static intlength=0;static int num=0;void createBiTreeBiTreeT{char ch;scanf级c〃,ch;if ch=#T=NULL;else{if!T=BiTNode*mallocsizeofBiTNode printferror;T-data=ch;//生成根结点createBiTreeT-lchild;//构造左子树createBiTree T-rchiId;//构造右子树void PreOrderBiTreebt//先序遍历二叉树,填写静态链表的“下标”和data域if btst[++num].data=bt-data;st[num].row=num;PreOrder bt-lchild;PreOrderbt-rchild;}int Locatechar x|〃在静态链表中查二叉树结点的下标int i;for i=l;i=num;i++if st[i].data==xreturn i;BiTree LevelOrderLocatePBiTreeroot,charx{int front,rear;BiTree queue[MAXSIZE],p;p=root;请输入二叉树各结点的值:ABCItltDEItttttFttGItitrclji Idfront=rear=0;if p{queue[rear++]=p;while frontrearp=queue[front++];ifp-data==xreturn p;if p-lchildqueue[rear++]=p-lchild;ifp-rchildqueue[rear++]=p-rchild;void DynaToSTBiTree t{int i;BiTree p;st[i].lchild=0;〃无左孩子,其Ichild域填0PreOrder t;fori=1;i=num;i++st[i].rchild=0;〃无右孩子,其rchild域填0p二LevelOrderLocatePt,st[i].data;if p-lchildst[i].Ichild=Locate p-lchild-data;elseif p-rchildst[i].rchild=Locatep-rchild-data;elseint main{BiTree t;printf(〃请输入二叉树各结点的值:\n〃);createBiTreet;nodeNumt;st=Node*mallocsizeofstruct Node*length;DynaToSTt;show st;return0;标F data Ichild1A22B33C04D55E06F0二叉树的建立是按照先序遍历的方式递归的建立
4.实验体味的,因此在输入二叉树的节点中的值时,要注意#字符的个数实验四
1.实验题目设无向图G有n个点e条边,编写算法建立G的邻接表,并按照深度优先搜索输出顶点,要求该算法时间复杂性为0n+e,且除邻接表本身所占空间之外只用0D辅助空间
2.程序核心代码struct edgenode〃表结点{int endver;edgenode*edgenext;:struct vexnode〃头结点char vertex;edgenode*edgelink;;struct Graph〃无向图vexnode adjlists[Max_Ver_Num];int vexnum,arcnum;;void CreatAdjListGraph*Gint i,j,k;edgenode*pl;edgenode*p2;cout〈”请输入无向图的顶点数和边数:,,«endl;cinG-vexnumG-arcnum;coutendl;cout〃开始输入顶点表/z«endl;for i=l;i=G-vexnum;i++{cinG-adjlists[i].vertex;G-adjlists[i].edgelink=NULL;coutendl;cout〈〃开始输入边表信息〃endl;coutendl;for k=l;k=G-arcnum;k++{cout〈〃请输入边Vi,Vj〉对应的顶点序号〃;cinij;coutendl;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;void DFSGraph*G,int i,int visited[]{coutG-adjlists[i].vertex,z〃;visited[i]=l;edgenode*p=new edgenode;p=G-adjlists[i].edgelink;if G-adjlists[i].edgelink!visited[p-endver]DFS G,p-endver,visited;void DFStraversalGraph*G,char ccout«〃该图的深度优先遍历结果为:〃endl;int visited[Max_Ver_Num];for int i=l;i=G-vexnum;i++|visited[i]=O;for int i=l;i=G-vexnum;i++if G-adjlists[i].vertex==cDFS G,i,visited;break;forint i=l;i=G-vexnum;i++{if visited[i]=ODFS G,i,visited;coutendl;}〃主程序int mainGraph*G二new Graph;CreatAdjList G;PrintGaph G;char Vi;cout〈”请输入开始遍历的顶点endl;cinVi;DFStraversalG,Vi;coutendl;return0;}
4.实验体味在输入边表关系时,要注意因为是无向图,所以有两次建立边表的过程,不需要重复输入实验五
1.实验题目二叉排序树采用二叉链表存储写一个算法,删除结点值是X的结点要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长注可不考虑被删除的结点是根的情况
2.程序核心代码typedef struct BiTNode{ElemType data;struct BiTNode*lchild,*rchild;}BiTNode,*BiTree;static BiTree head;〃建二叉排序树BiTree createBSTBiTreehead,int number{BiTree p;p=BiTreemallocsizeofBiTNode;p-data=number;p-lchild=p-rchild=NULL;if head==NULL{return p;else|if p-datahead-data head-lchild=createBSThead-lchiId,number;else head-rchild=createBSThead-rchiId,number;return head;〃求的双亲PBiTree searchParentBiTreehead,BiTree pifhead-lchild=p||head-rchild==p||head-p||head==NULL returnhead;elseif p-datahead-datareturn searchParenthead-lchild,p;elsereturn searchParenthead-rchild,p;//删除二叉排序树中结点Pbool DeleteBiTreep{BiTree q,s;q=BiTreemalloc sizeofBiTNode;s=BiTreemallocsizeofBiTNode;if!p-rchild!p-lchild//删除的节点是叶子节点q=searchParenthead,p;ifq-Ichiid==p q-lchild=NULL;else q-rchild=NULL;else if!p-rchild{〃左子树不为空,右子树为空searchParenthead,p-lchild=p-lchild;free p;else if!p-lchild{〃右子树不为空,左子树为空searchParenthead,p-rchild=p-rchild;freep;else//摆布子树都不为空q二P;s=p-lchild;whiles-rchild{q=s;s=s-rchiId;p-data=s-data;ifq!=p q-rchild=s-lchild;else q-lchild=s-lchild;delete s;}return true;}bool deleteBSTBiTree Head,int number{if!Head returnfalse;else{if Head-data二二number returnDelete Head;else ifnumberHead-data returndeleteBSTHead-lchild,number;else returndeleteBSTHead-rchiId,number;〃主程序int main{BiTree Head;printf〃建立一棵二叉排序树,请输入你要建树的所有数以作为结束标志!\n〃;Head=NULL;int number,n;scanf〃%d〃,number;while number!=-l|Head=createBSTHead,number;scanf〃%d〃,number;head=Head;printf〃中序遍历二叉排序树为\n〃;printBST Head;printf〃\n〃;printf〃请输入要删除的结点〃;scanf〃%d〃,n;if deleteBSTHead,n printf〃删除成功!\n〃;else printf〃删除失败!\n;printf〃删除之后的二叉排序树中序遍历为\n〃;printBSTHead;printf〃\n〃;return0;实验一
1.实验题目设有两个无头结点的单链表,头指针分别为链中有数据域链域ha,hb,data,两链表的数据都按递增序存放,现要求将表归到表中,且归并后next,hb haha仍递增序,归并中表中已有的数据若中也有,则中的数据不归并到ha hbhb ha中,的链表在算法中不允许破坏hb
2.程序核心代码struct LNodeint data;struct LNode*next;};typedef struct LNode*LinkList;LinkList UnionLinkList ha,LinkList hbLinkList head=LNode*mallocsizeofLNode;head-next=ha;LNode*pa,*pb,*pTmp;pa=ha-next;pb=hb-next;pTmp=ha;whilepapb{ifpa-datapb-data{pTmp=pa;pa=pa-next;else ifpa-datapb-data{LNode*Lr=LNode*mallocsizeofLNode;Lr-data=pb-data;Lr-next=pa;pTmp-next=Lr;pTmp二Lr;pb=pb-next;else
4.实验体味二叉排序树的删除要注意分类讨论,删除的节点p为叶子节点时,不能简单的直接删除p,而要找到p的双亲节点,令双亲节点指向p的指针为NULL即可pTmp=pa;pa=pa-next;pb=pb-next;ifpa{pTmp-next=pa;else{whilepb{LNode*Lr二LNode*mallocsizeofLNode;Lr-data=pb-data;pTmp-next=Lr;pTmp=Lr;pb=pb-next;pTmp-next=NULL;freehead;return ha;int ListinsertLinkListL,inti,int e{int j=0;LinkList p=L,s;whilepji~l{p=p-next;j++;}if!p|ji-l return0;s=LinkListmallocsizeof structLNode;/*生成新结点*/s-data=e;/*插入L中*/s-next=p-next;p-next=s;return1;int main{LinkList ha,hb;intn,i;int data;InitListha;printf〃请输入ha中数据的个数〃;scanf〃%d〃,n;printf〃请挨次输入ha中的数据\n〃;forint i=1;i=n;i++scanf〃%d〃,data;Listinsert ha,i,data;printf〃ha二〃;LinkList p=ha-next;while p{printf/z%d〃,p-data;p=p-next;printf〃\n〃;InitListhb;printf〃请输入hb中数据的个数〃;scanf n;printf〃请挨次输入hb中的数据\n〃;for i=1;i=n;i++|scanf〃%d〃,Mata;Listinsert hb,i,data;printf〃hb=〃;p=hb-next;while pprintfz/%d/z,p-data;p=p-next;printf〃\n〃;printf Chb归并到ha后,新的ha=;p=Union ha,hb-next;while p{printf/z%d〃,p-〉data;p=p-next;printf〃\n〃;systempause;return0;数据结构实验日回口,・c\E:\24\\Debug\erge.exe请根次输入申的数据■ha
16924.ha=16924■请输入中数堂的个数hb3■请根次输入申的数据■hb・2615hb=2615■1归并到后,新的hb haha=l2691524请按任意键继续.一■
4.实验总结要注意归并时若ha表中已有的数据若hb中也有,贝ij hb中的数据不归并到ha中,hb的链表在算法中不允许破坏实验二
1.实验题目结合书上第页的例子一元多项式相加,采用链式存储结构,将两个线性41链表表示的一元多项式相加,并输出
2.程序核心代码typedef structLNode{intdata;〃存储系数int flag;〃存储对应幕数structLNode*next;}LNode;〃建立带头结点的单链表,n项多项式void CreateListLNode**L,int nLNode*p;inti=0;*L=LNode*malloc sizeofLNode;*L-next=NULL;for i=0;in;++i{p二LNode*malloc sizeofLNode;scanf〃%d%d〃,p-data,p-flag;p-next=*L-next;*L-next=p;//插入链表}//多项式LI与L2对应项相加得到新的L2void PolyoAddLNode**L1,LNode**L2{int ck;LNode*p,*q;p二NULL;q=NULL;q=*Ll-next;while q{ck=0;p=*L2-next;whilepif q-flag==p-flag{ck=1;break;p=p-next;if ck==1//同类项合并p-data+=q-data;q=q-next;else〃否则,直接将非同类项插到L2最前面{*Ll-next=q-next;q-next=*L2-next;*L2-next=q;q=*Ll-next;int main{int m=0;LNode*pl,*p2;pl=NULL;p2二NULL;printf〃设定多项式A的项数\n;scanf〃%d〃,m;printf〃请输入多项式A的系数及对应位嘉次\n〃;CreateListpl,m;printf〃A〃;PolyoPrintpl;printf设定多项式B的项数\n;scanf级d〃,m;printf”请输入多项式B的系数及对应位哥次\n〃;CreateListp2,m;printf〃B〃;PolyoPrintp2;PolyoAdd pl,p2;printf〃相加后的;PolyoPrintp2;systempause;return0;八数据结构实验一元多项式相加\•••\24\\Debug\番输入多项式的系数及对应位幕次A203132多项式为A3*x^2*3*x^l+2*x0设定多项式的项数B2请输入多项式的系数及对应位幕次B3021多项式为B2*x^l+3*x^0相加后的多项式为3*x^2*5*xl*5*x^0请按任意至继续.・•
4.实验总结合并多项式是指相同指数的项的系数相加,比较两个链表的节点的指数的大小,作为指针挪移的条件,同事合并的过程中应消除系数项为零的节点实验三
1.实验题目二叉树的动态二叉链表结构中的每一个结点有三个字段data,Ichi Id,rchildo其中指针Ichild下标dataIchildrchild1A262B343C004D505E006F077G00和rchild的类型为bitreeo静态二叉链表是用数组作为存储空间,每一个数组元素存储二叉树的一个结点,也有三个字段data,Ichild,rchildo所不同的是,Ichild和rdhild为integer型,分别用于存储摆布孩子的下标,如果没有摆布孩子,则相应的值为Oo例如,二叉树的静态二叉链表如上图所示编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表并写出其调用形式和有关的类型描述其中n为一个确定的整数
2.程序核心代码typedef structBiTNodechar data;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedef structNode〃静态链表结点结构{char data;〃结点数据int row,Ichild,rchild;〃下标,摆布孩子}Node;。