数据结构实测验完整答案

1、数据结构上机实验的目的和要求通过上机实验加深对课程内容的理解， 增加感性认识， 提高软件设计、 编写及调试程序 的能力。要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为：1、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：（ 1）输入的形式和输出值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。2、概要设计： 说明用到的数据结构定义、 主程序的流程及各程序模块之间的调用关系。3、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。4、调试分析：（1）调试过程中所遇到的问题及解决方法；（2）算

2、法的时空分析；（3）经验与体会。5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。6、测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输入规模的 增长所用算法的实际运行时间的变化。实验一、线性表的基本操作一、目的： 了解和掌握线性表的逻辑结构和链式存储结构， 掌握单链表的基本算法及相关的时间性 能分析。二、内容（题目）三、分析过程四、设计过程五、实现六、测试七、性能分析范例：1 约瑟夫环#define NULL 0typedef struct Nodeint bianhao;int mima;struct Node *next; Node;Node *CreatFr

3、omTail(int n)Node *l,*r,*s;int i,mima;l=(Node *)malloc(sizeof(Node); l->next=NULL;r=l;printf("input other miman"); for(i=1;i<=n;i+) scanf("%d",&mima); s=(Node *)malloc(sizeof(Node); s->bianhao=i;s->mima=mima;r->next=s;r=s; r->next=l->next;return l;DeleNod

4、e(int m,int n,Node *l)int i,j;Node *p,*q;p=l;i=1;while(i<=n) for(j=1;j<=m-1;j+) p=p->next;q=p->next; p->next=q->next;printf("chu dui d ren shi%d, qi mima shi%dn ",q->bianhao,q->mima); i+; m=q->mima;free(q);return;main()Node *l;int m,n;printf("input number of

5、 people and the first miman"); scanf("%d,%d",&n,&m);l=CreatFromTail(n);DeleNode(m,n,l);2 回文判断方法 1：#include "stdio.h"main()char a100,c;int len;int i,j,top;i=0;while(c=getchar()!='')ai=c;i+; for(j=0;j<i;j+) printf("%c",aj);top=i-1;j=0;while(top>

6、=0)if (atop!=aj)printf("is not");return;top-;j+;printf("is");方法 2：#include "stdio.h"#define TRUE 1#define FALSE 0#define stacksize 100#define queuesize 100typedef structchar elemqueuesize;int front,rear; sequeue;typedef structchar elemstacksize;int top; seqstack;int Ent

7、erQueue(sequeue *q,char x)if(q->rear+1)%queuesize=q->front) return(FALSE); q->elemq->rear=x;q->rear=(q->rear+1)%queuesize; return(TRUE);char delete(sequeue *q)char x;if (q->rear=q->front) return(FALSE); x=q->elemq->front;q->front=(q->front+1)%queuesize; return(x);

8、int push(seqstack *s,char x)if(s->top=stacksize-1) return(FALSE); s->top+;s->elems->top=x;char pop(seqstack *s)char x;if(s->top=-1) return(FALSE);else x=s->elems->top; s->top-; return(x);main()char c;int len1=0,len2=0;seqstack *s;sequeue *q;char x1,x2; q=(sequeue*)malloc(size

9、of(sequeue); q->front=q->rear=0;while(c=getchar()!='&')EnterQueue(q,c); len1+;s=(seqstack*)malloc(sizeof(seqstack);s->top=-1;while(c=getchar()!='')push(s,c); len2+;if(len1!=len2) printf("is not");elsewhile(s->top>=0)x1=pop(s); x2=delete(q);if(x1!=x2) prin

10、tf("is not"); return; printf("is");3 串操作( 92 页实习题 1)方法 1：#include "stdio.h"main()char s100,t100,r100,c;int i,j,k,m,len1,len2,len3;gets(s);gets(t);len1=0;while(slen1!='0') len1+;len2=0;while(tlen2!='0') len2+;len3=0;i=0; k=0;while(i<len1)j=0;while(j<

11、;len2)&&(si!=tj)j+;if (j>=len2)rlen3=si;m=0;while (m<len3)&&rm!=rlen3) m+;if (m=len3) printf("%c zai s zhong shou ci chu xian de wei zhi shi %dn",rlen3,i); len3+;i+;for(k=0;k<len3;k+)printf("%c",rk);方法 2：#include "string.h"#define Maxlen 100type

12、def structchar chMaxlen;int len; SString;concat(SString *s, SString t)int i,flag;if (s->len+t.len<=Maxlen)for(i=s->len;i<s->len+t.len;i+)s->chi=t.chi-s->len;s->len+=t.len; flag=1;else if (s->len<Maxlen)for(i=s->len;i<Maxlen;i+) s->chi=t.chi-s->len; s->len

13、=Maxlen; flag=0;else flag=0; return(flag); len(SString s) return(s.len);SubString(SString *sub,SString s,int pos,int len ) int i;if (pos<0|pos>s.len|len<1|len>s.len-pos) sub->len=0; return(0);else for(i=0;i<len;i+) sub->chi=s.chi+pos;sub->chi='0' sub->len=len; retu

14、rn 1;equal(SString s,SString t)int i;if (s.len!=t.len) return 0;elsefor(i=0;i<s.len&&i<t.len;i+) if (s.chi!=t.chi) return 0;return 1;StrIndex(SString s,int pos ,SString t)int i,j;if (t.len=0)return 0; i=pos;j=0;while(i<s.len&&j<t.len)if (s.chi=t.chj)i+;j+; else i=i-j+1;j=

15、0;if (j>=t.len) return(i-j);else return 0;main()SString s,t,x,r="",0;SString *sub1,*sub2,*sub3;int i,j,k; sub1=(SString*)malloc(sizeof(SString); sub2=(SString*)malloc(sizeof(SString); sub3=(SString*)malloc(sizeof(SString); gets(s.ch);s.len=strlen(s.ch);gets(t.ch);t.len=strlen(t.ch);/* S

16、ubString(sub1,s,1,1);concat(&r,*sub1);SubString(sub1,s,2,1); concat(&r,*sub1);printf("%sn",sub1->ch); printf("%sn",r.ch);*/i=0;while(i<s.len)j=0;SubString(sub1,s,i,1);SubString(sub2,t,j,1); while(j<t.len)&&!equal(*sub1,*sub2) j+;SubString(sub2,t,j,1);if (

17、j>=t.len)concat(&r,*sub1);r.len=strlen(r.ch); for(k=0;k<r.len;k+)SubString(sub3,r,k,1); printf("%s %dn", sub3->ch,StrIndex(s,0,*sub3); printf("%sn",r.ch);4 151 页实习题 1 #include "stdio.h" #define NULL 0 typedef struct BiNode char data;struct BiNode *Lchild,*R

18、child; BiNode;BiNode *creatBiTree( )BiNode *bt; char ch; ch=getchar(); if (ch='.') bt=NULL; else bt=(BiNode *)malloc(sizeof(BiNode); bt->data=ch;bt->Lchild=creatBiTree(); bt->Rchild=creatBiTree(); return bt;void preorder(BiNode *root)if (root!=NULL) printf("%c",root->da

19、ta); preorder(root->Lchild); preorder(root->Rchild); void midorder(BiNode *root)if (root!=NULL)midorder(root->Lchild); printf("%c",root->data); midorder(root->Rchild);void sucorder(BiNode *root)if (root!=NULL)sucorder(root->Lchild); sucorder(root->Rchild); printf("

20、;%c",root->data);main( )BiNode *root; root=NULL; root=creatBiTree(); printf("nxianxu:n"); preorder(root); printf("nzhongxu:n"); midorder(root); printf("nhouxu:n");sucorder(root);#include<stdio.h>#include<stdlib.h>#define MAX_VERTEX_NUM#define INFINIT

21、Y 32768#define True 1#define False 0/*#define Error -1 */#define Ok 1/* 假设顶点数据为整型 */ typedef struct10 /* 最多顶点个数 */* 最大权值，即：无穷大 */*出错 */int vexsMAX_VERTEX_NUM; /* 顶点向量 */int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; /* 邻接矩阵 */ int vexnum,arcnum; /* 图的顶点数和弧数 */AdjMatrix; /* ( Adjacency Matrix Graph )*/int vis

22、itedMAX_VERTEX_NUM;/* 访问标志数组 */int CreateDN(AdjMatrix *G) /* 创建一个有向网 ,且顶点递增存储 */ int i,j,k,weight,v1,v2;printf("Please input graph's arcnum and vexnum:");scanf("%d,%d",&G->arcnum,&G->vexnum); /* 输入图的顶点数和弧数 */ for(i=0;i<G->vexnum;i+)for(j=0;j<G->vexnu

23、m;j+)G->arcsij=INFINITY;prin tf("Please in put vertex:0,1,2, ”)；for(i=0;i<G->vexnum;i+)G->vexsi=i；/* scanf("%d",&G->vexsi)；输入图的顶点 */printf("Please input graph's arcs:arcs_tail,arcs_head and weight")；for(k=0；k<G->arcnum；k+)scanf("%d,%d,%d&quo

24、t;,&v1,&v2,&weight)； /* 输入一条弧的顶点及权值 */* i=LocateVex_M(G ,v1)； j=LocateVex_M(G ,v2)； */G->arcsv1v2=weight；/* 建立弧 */return(Ok)；void DepthFirstSearch(AdjMatrix g,int v0) /* 深度优先搜索邻接矩阵 */ int vj；printf("%5d",v0)；visitedv0=True；for(vj=0；vj<g.vexnum；vj+)if (!visitedvj &&

25、; g.arcsv0vj!=INFINITY)DepthFirstSearch(g,vj)； /* DepthFirstSearch */void TraverseGraph(AdjMatrix g) /* 对图 g 进行深度优先搜索 */ int vi；for(vi=0；vi<g.vexnum；vi+) visitedvi=False；/* 访问标志数组初始 */for(vi=0；vi<g.vexnum；vi+) /* 调用深度遍历连通子图的操作 */ if(!visitedvi) DepthFirstSearch(g,vi)；/* TraverseGraph */ main()

26、 AdjMatrix graph; int i,j;CreateDN(&graph);for(i=0;i<graph.vexnum;i+)for(j=0;j<graph.vexnum;j+)printf("%8d",graph.arcsij);printf("n");TraverseGraph(graph);xxxxxxxxxxxxxxxxxxxxxxx#include <conio.h>#include <stdio.h>#define M 10 /* 此头函数请不要删除 */ typedef structc

27、har name15;int score; student;void CreatTable(student stuM+1,int n)/* create student's grade table*/ int i;for(i=1;i<=n;i+) printf("please input the student's namen"); scanf("%s",);printf("please input the student's scoren"); scanf("%d"

28、,&stui.score);void Inssort(student studM+1,int n)/*insert sort*/int i,j; for(i=2;i<=n;i+) stud0=studi; j=i-1; while(stud0.score<studj.score)studj+1=studj;j=j-1;studj+1=stud0;/*end Inssort*/void Bubblesort(student studM+1,int n)student stu;int i,j=1;for(j=1;j<n;j+)for(i=1;i<=n-j;i+) i

29、f(studi.score<studi+1.score)stu=studi;studi=studi+1;studi+1=stu;void print(student stuM+1,int n)int i=1,j=0;printf(" %-15s ",); printf("%-5d",stui.score);printf("%-5dn",i);i+;while(i<=n)if(stui.score=stui-1.score)j+;printf("%-15s ",);pr

30、intf("%-5d",stui.score);printf("%-5dn",i-j);elsej=0;printf("%-15s ",);printf("printf("%-5d",stui.score);%-5dn",i); i+;main()int n;student tableM+1;printf("Please input the student's number:n"); scanf("%d",&n);Crea

31、tTable(table,n);Inssort(table,n);print(table,n);printf("*n");Bubblesort(table,n); print(table,n); getch();xxxxxxxxxxxxxxxxxxxxxxxxxx#include<string.h> #include<stdio.h> #define max_st_num 40 typedef struct char name15;int flag;sname;typedef sname htable; void create(htable ht,i

32、nt st_num) char name15;int i=0,d,j; for(i=0;i<=st_num;i+) hti.flag=0;for(i=0;i<st_num;i+) printf("Please input %d student's name:n",i+1); scanf("%s",name);d=name0%13;if(htd.flag=1)for(j=1;j<=13;j+)d=(d+j)%13;if(htd.flag=0)break;htd.flag=1;strcpy(,name);int hashsearch(htable ht,char name) int d0,d,i;d0=(name0%13);if(htd0.flag=0)return(-1);else if(strcmp(,name)=0)return(d0);else for(i=1;i<13