《数据结构》期中作业

1北京邮电大学远程教育计算机科学与技术专业《数据结构》实验指导书实验一线性表的插入和删除一、实验目的1、掌握用TurboC上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、实验内容线性表基本操作的实现当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。程序实现：typedefNull0;typedefintdatatype;#definemaxsize1024;typedefstruct{datatypedata[maxsize];intlast;}sequenlist;intinsert(L,x,i)sequenlist*L;inti;{intj;if((*L).last==maxsize-1){printf(“overflow”);returnNull;2}elseif((i1)‖(i(*L).last+1){printf(“error”);returnNull;}else{for(j=(*L).last;j=i-1;j--)(*L).data[j+1]=(*L).data[j];(*L).data[i-1]=x;(*L).last=(*L).last+1;}return(1);}intdelete(L,i)sequenlist*L;inti;{intj;if((i1)‖(i(*L).last+1)){printf(“error”);returnNull;}else{for(j=i,j=(*L).last;j++)(*L).data[j-1]=(*L).data[j];(*L).data--;}return(1);}3voidcreatlist(){sequenlist*L;intn,i,j;printf(“请输入n个数据\n”);scanf(“%d”,&n);for(i=0;in;i++){printf(“data[%d]=”,i);scanf(“%d”,(*L).data[i]);}(*L).last=n-1;printf(“\n”);}printout(L)sequenlist*L;{inti;for(i=0;i(*L).last;i++){printf(“data[%d]=”,i);printf(“%d”,(*L).data[i]);}}main(){sequenlist*L;charcmd;inti,t;clscr();printf(“i,I…..插入\n”);printf(“d,D…..删除\n”);4printf(“q,Q……退出\n”);do{do{cmd=getchar();}while((cmd!=‘d’)‖(cmd!=‘D’)‖(cmd!=‘q’)‖(cmd!=‘Q’)‖(cmd!=‘i’)‖(cmd!=‘I’));switch(cmd){case‘i’,‘I’;scanf(&x);scanf(&i);insert(L,x,i);printout(L);break;case‘d’,‘D’;scanf(&i);delete(L,i);printout(L);break;}}while((cmd!=‘q’)&&(cmd!=‘Q’));}实验二二叉树的操作一、实验目的1、进一步掌握指针变量、动态变量的含义；2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；53、掌握用指针类型描述、访问和处理二叉树的运算。二、实验内容已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法。算法思想：本算法要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。程序实现：#defineM100#defineNull0typedefstructnode{intdata;stuuctnode*lchild,*rchild;}bitree;bitree*que[M];intfront=0,rear=0;bitree*creat(){bitree*t;intx;scanf(“%d”,&x);if(x==0)t=Null;else{t=malloc(sizeof(bitree));t→data=x;t→lchild=creat();t→rchild=creat();}returnt;6}voidinorder(t)bitree*t;{if(t!=Null){inorder(t→lchild);printf(“%4d”,t→data);inorder(t→rchild);}}voidenqueue(t)bitree*t;{if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=t;}}bitree*delqueue(){if(front==rear)returnNull;front=(front+1)%M;return(que[front]);}voidlevorder(t)bitree*t;{bitree*p;7if(t!=Null){enqueue(t);while(front!=rear){p=delqueue();printf(“%4d”,p→data);if(p→lchild!=Null)enqueue(p→lchild);if(p→rchild!=Null)enqueue(p→rchild);}}}main(){bitree*root;printf(“\n”);root=creat();inorder(root);printf(“\n”);levorder(root);}实验三图的操作一、实验目的1、掌握图的基本存储方法；2、掌握有关图的操作算法并用高级语言实现；3、熟练掌握图的两种搜索路径的遍历方法。二、实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区8域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。算法思想：下面是R、W、Floyd求每对顶点之间最短路径算法的C语言程序，程序中矩阵A用来进行n次迭代，矩阵P用来记录路径，P[i][j]为迭代过程中当前已经求得的从顶点i到顶点j的最短路径上最后被插入的那个顶点。算法实现：typedefstructnode{intno;floatwgt;structnode*next;}edgenode;typedefstruct{charvtx;edgenode*link;}vexnode;typedefvexnodeGraph[n];voidFloyd(GraphG,floatA[n][n],intp[n][n]){inti,j,k;for(i=0;in;i++)for(j=0;jn;j++){A[i][j]=G[i][j];P[i][j]=-1;}for(k=0;kn;k++)for(i=0;in;i++)for(j=0;jn;j++)9if(A[i][k]+A[k][j]A[i][j]){P[i][j]=k;A[i][j]=A[i][k]+A[k][j];}}实验四排序一、实验目的1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验内容统计成绩[问题描述]给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；（2）按名次列出每个学生的姓名与分数。[基本要求]学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。[算法实现]下面给出的是用直接选择排序算法实现的C语言程序。#definen30typedefstructstudent{charname[8];intscore;10}studentR[n];main(){intnum,i,j,max,temp;printf(“\n请输入学生成绩:\n”);for(i=0;in;i++){printf(“姓名:”);scanf(“%s”,&stu[i].name);scanf(“%4d”,&stu[i].score);}num=1;for(i=0;in;i++){max=i;for(j=i+1;jn;j++)if(R[j].scoreR[max].score)max=j;if(max!=i){temp=R[max];R[max]=R[i];R[i]=temp;}if((i0)&&(R[i].scoreR[i-1].score))num=num+1;printf(“%4d%s%4d”,num,R[i].name,R[i].score);}}11实验五查找一、实验目的1、掌握查找的不同方法，并能用高级语言实现查找算法；2、熟练掌握二叉树的构造和查找方法。二、实验内容设计一个读入一串整数构成一棵二叉排序树的算法。[实现提示]二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。[算法实现]typedefstructnode{intkey;intother;structnode*lchild,*rchild;}bstnode;voidinorder(t)bstnode*t;{if(t!=Null){inorder(t→lchild);printf(“%4d”,t→key);inorder(t→rchild);}}bstnode*insertbst(t,s)bstnode*s,*t;{bstnode*f,*p;p=t;12while(p!=Null){f=p;if(s→key==p→key)returnt;if(s→keyp→key)p=p→lchild;elsep=p→rchild;}if(t==Null)returns;if(s→keyf→key)f→lchild=s;elsef→rchild=s;returnt;}bstnode*creatord(){bstnode*t,*s;intkey;t=Null;scanf(“%d”,&key);while(key!=0){s=malloc(sizeof(bitree));s→key=key;s→lchild=Null;s→rchild=Null;scanf(“%d”,&data);s→other=data;t=insertbst(t,s);scanf(“%d”,&key);}returnt;13}main(){bstnode*root;root=creatord();inorder(root);}注：实验一，实验二和实验四为必做实验。