数据结构实习题答案

通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。

要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为： 1、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定： （1）输入的形式和输出值的范围； （2）输出的形式；

（3）程序所能达到的功能；

（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。 2、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。 3、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。 4、调试分析：

（1）调试过程中所遇到的问题及解决方法； （2）算法的时空分析； （3）经验与体会。

5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。

6、测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。

实验一、线性表的基本操作

一、目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

二、内容 （题目）

三、分析过程 四、设计过程 五、实现 六、测试

七、性能分析

范例：

1． 约瑟夫环 #define NULL 0 typedef struct Node {

int bianhao;

int mima;

struct Node *next; } Node;

Node *CreatFromTail(int n) {

Node *l,*r,*s; int i,mima;

l=(Node *)malloc(sizeof(Node)); l->next=NULL; r=l;

printf(\"input other mima\\n\"); for(i=1;i<=n;i++) {

scanf(\"%d\

s=(Node *)malloc(sizeof(Node)); s->bianhao=i; s->mima=mima; r->next=s; r=s; }

r->next=l->next; return l; }

DeleNode(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%d\\n \ m=q->mima; free(q); }

return; }

main() {

Node *l;

int m,n;

printf(\"input number of people and the first mima\\n\"); scanf(\"%d,%d\ l=CreatFromTail(n); DeleNode(m,n,l); }

2． 回文判断 方法1：

#include \"stdio.h\" main() {

char a[100],c; int len; int i,j,top; i=0;

while((c=getchar())!='@') { a[i]=c; i++; }

for(j=0;jwhile(top>=0) { if (a[top]!=a[j]) { printf(\"is not\"); return; } top--; j++; }

printf(\"is\"); }

方法2：

#include \"stdio.h\" #define TRUE 1 #define FALSE 0

#define stacksize 100 #define queuesize 100 typedef struct

{

char elem[queuesize]; int front,rear; } sequeue;

typedef struct {

char elem[stacksize]; int top; } seqstack;

int EnterQueue(sequeue *q,char x) {

if((q->rear+1)%queuesize==q->front) return(FALSE); q->elem[q->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->elem[q->front];

q->front=(q->front+1)%queuesize; return(x); }

int push(seqstack *s,char x) {

if(s->top==stacksize-1) return(FALSE); s->top++;

s->elem[s->top]=x; }

char pop(seqstack *s) {

char x;

if(s->top==-1) return(FALSE); else {

x=s->elem[s->top]; s->top--; return(x);

} }

main() {

char c;

int len1=0,len2=0; seqstack *s; sequeue *q; char x1,x2;

q=(sequeue*)malloc(sizeof(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\"); else { while(s->top>=0) { x1=pop(s); x2=delete(q); if(x1!=x2) { printf(\"is not\"); return;} } printf(\"is\"); } }

3． 串操作（92页实习题1） 方法1：

#include \"stdio.h\" main() {

char s[100],t[100],r[100],c; int i,j,k,m,len1,len2,len3; gets(s); gets(t); len1=0;

while(s[len1]!='\\0') len1++;

len2=0;

while(t[len2]!='\\0') len2++;

len3=0; i=0; k=0; while(ij=0;

while((jif (j>=len2) { r[len3]=s[i]; m=0; while ((mfor(k=0;k方法2：

#include \"string.h\" #define Maxlen 100 typedef struct{ char ch[Maxlen]; int len; } SString;

concat(SString *s, SString t) {

int i,flag;

if (s->len+t.len<=Maxlen) { for(i=s->len;ilen+t.len;i++) s->ch[i]=t.ch[i-s->len]; s->len+=t.len; flag=1; }

else if (s->lenlen;is->ch[i]=t.ch[i-s->len]; s->len=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;isub->ch[i]=s.ch[i+pos]; sub->ch[i]='\\0'; sub->len=len; return 1; } }

equal(SString s,SString t) {

int i;

if (s.len!=t.len) return 0; else {

for(i=0;iStrIndex(SString s,int pos ,SString t) {

int i,j;

if (t.len==0)return 0; i=pos;

j=0;

while(iif (s.ch[i]==t.ch[j]){i++;j++; } else {i=i-j+1;j=0;} if (j>=t.len) return(i-j); else return 0; }

main() {

SString s,t,x,r={\"\

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);

/* SubString(sub1,s,1,1); concat(&r,*sub1); SubString(sub1,s,2,1); concat(&r,*sub1);

printf(\"%s\\n\ printf(\"%s\\n\

i=0;

while(ij=0;

SubString(sub1,s,i,1); SubString(sub2,t,j,1);

while((jif (j>=t.len) { concat(&r,*sub1); } i++; }

r.len=strlen(r.ch); for(k=0;kSubString(sub3,r,k,1);

printf(\"%s %d\\n\ }

printf(\"%s\\n\}󰀀

4．151页实习题1 #include \"stdio.h\" #define NULL 0

typedef struct BiNode {

char data;

struct BiNode *Lchild,*Rchild; } 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\ preorder(root->Lchild); preorder(root->Rchild); } }

void midorder(BiNode *root) {

if (root!=NULL) {

midorder(root->Lchild); printf(\"%c\ midorder(root->Rchild); } }

void sucorder(BiNode *root) {

if (root!=NULL) {

sucorder(root->Lchild); sucorder(root->Rchild); printf(\"%c\ } }

main( ) {

BiNode *root; root=NULL;

root=creatBiTree(); printf(\"\\nxianxu:\\n\"); preorder(root);

printf(\"\\nzhongxu:\\n\"); midorder(root);

printf(\"\\nhouxu:\\n\"); sucorder(root); }󰀀

#include #include

#define MAX_VERTEX_NUM #define INFINITY 32768 #define True 1 #define False 0

/*#define Error -1 */ #define Ok 1

/*假设顶点数据为整型*/ typedef struct

10 /*最多顶点个数*/ /*最大权值，即：无穷大*/ /*出错*/ {

int vexs[MAX_VERTEX_NUM]; /*顶点向量*/ int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /*邻接矩阵*/ int vexnum,arcnum; /*图的顶点数和弧数*/

}AdjMatrix; /*（Adjacency Matrix Graph）*/ int visited[MAX_VERTEX_NUM]; /*访问标志数组*/

int CreateDN(AdjMatrix *G) /*创建一个有向网,且顶点递增存储*/ { int i,j,k,weight,v1,v2;

printf(\"Please input graph's arcnum and vexnum:\");

scanf(\"%d,%d\ /*输入图的顶点数和弧数*/ for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) G->arcs[i][j]=INFINITY;

printf(\"Please input vertex:0,1,2,……\"); for(i=0;ivexnum;i++) G->vexs[i]=i;

/* scanf(\"%d\ 输入图的顶点*/

printf(\"Please input graph's arcs:arcs_tail,arcs_head and weight\"); for(k=0;karcnum;k++)

{scanf(\"%d,%d,%d\输入一条弧的顶点及权值*/ /* i=LocateVex_M(G,v1); j=LocateVex_M(G,v2); */

G->arcs[v1][v2]=weight; /*建立弧*/ }

return(Ok); }

void DepthFirstSearch(AdjMatrix g,int v0) /* 深度优先搜索邻接矩阵 */ { int vj;

printf(\"%5d\ for(vj=0;vjif (!visited[vj] && g.arcs[v0][vj]!=INFINITY) DepthFirstSearch(g,vj); } /* DepthFirstSearch */

void TraverseGraph(AdjMatrix g) /* 对图g进行深度优先搜索 */ { int vi;

for(vi=0;vimain()

{ AdjMatrix graph; int i,j; CreateDN(&graph);

for(i=0;iTraverseGraph(graph); }

××××××××××××××××××××××× #include #include

#define M 10 /* 此头函数请不要删除 */ typedef struct {

char name[15]; int score; } student;

void CreatTable(student stu[M+1],int n)/* create student's grade table*/ {

int i;

for(i=1;i<=n;i++) {

printf(\"please input the student's name\\n\"); scanf(\"%s\

printf(\"please input the student's score\\n\"); scanf(\"%d\ } }

void Inssort(student stud[M+1],int n)/*insert sort*/ {

int i,j; for(i=2;i<=n;i++) {

stud[0]=stud[i]; j=i-1; while(stud[0].scorestud[j+1]=stud[j];

j=j-1; } stud[j+1]=stud[0]; }

}/*end Inssort*/

void Bubblesort(student stud[M+1],int n) {

student stu; int i,j=1;

for(j=1;jfor(i=1;i<=n-j;i++)

if(stud[i].scorestu=stud[i];

stud[i]=stud[i+1]; stud[i+1]=stu; } }

void print(student stu[M+1],int n) {

int i=1,j=0;

printf(\" %-15s \ printf(\" %-5d\ printf(\" %-5d\\n\

i++;

while(i<=n) {

if(stu[i].score==stu[i-1].score) {

j++;

printf(\" %-15s \ printf(\" %-5d\ printf(\" %-5d\\n\

} else {

j=0;

printf(\" %-15s \

printf(\" %-5d\ printf(\" %-5d\\n\

} i++; } }

main() {

int n;

student table[M+1];

printf(\"Please input the student's number:\\n\"); scanf(\"%d\ CreatTable(table,n); Inssort(table,n); print(table,n);

printf(\"*************************\\n\"); Bubblesort(table,n); print(table,n); getch(); }

××××××××××××××××××××××××××

#include #include

#define max_st_num 40 typedef struct {char name[15]; int flag; }sname;

typedef sname htable;

void create(htable ht[],int st_num) { char name[15]; int i=0,d,j;

for(i=0;i<=st_num;i++) ht[i].flag=0;

for(i=0;i{ printf(\"Please input %d student's name:\\n\ scanf(\"%s\ d=name[0]%13; if(ht[d].flag==1) for(j=1;j<=13;j++) {d=(d+j)%13;

if(ht[d].flag==0)break; }

ht[d].flag=1;

strcpy(ht[d].name,name); } }

int hashsearch(htable ht[],char name[]) { int d0,d,i;

d0=(name[0]%13);

if(ht[d0].flag==0)return(-1);

else if((strcmp(ht[d0].name,name))==0)return(d0); else

{ for(i=1;i<13;i++) { d=(d0+i)%13; if(strcmp(ht[d].name,name)==0)return(d); } return(-1); } }

main()

{htable student[max_st_num]; char name[15]; int addr,stunum; char ch='y';

printf(\"Create the student name hash table\\n\"); printf(\"Input student's number:\\n\"); scanf(\"%d\ create(student,stunum); while((ch=='y')||(ch=='Y'))

{ printf(\"Please input the finding student's name:\\n \"); scanf(\"%s\

addr=hashsearch(student,name);

if(addr!=-1)printf(\"the student's locate %d\\n\ else

printf(\"The student isn't in table\\n\");

printf(\"Continue search other student,please input 'y'\\n\"); ch=getchar();

ch=getchar(); } }󰀀

实验一目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验二目的：

1． 掌握栈和队列的概念，定义以及基本操作。 2． 掌握串的定义及基本操作。

实验三目的：

了解非线性数据结构树的存储表示特征及遍历的次序与二叉树的存储结构之间的关系，掌握二叉树的建立、遍历以及其它的一些基本操作。

实验四目的：

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。

实验五目的：

掌握基于线性表的查找、基于书的查找以及哈希查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。

试验六目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。