数据结构实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告总”。
浙江师范大学
实 验 报 告
学 院： 数理与信息工程学院 专 业： 计算机科学与技术 姓 名： 杨富生 学 号： 201531910137 课程名称： 数据结构 指导教师： 钟发荣 实验时间： 2016-06-15
2016年6月15日
实验一
1.实验要求
1.1 掌握数据结构中线性表的基本概念。
1.2 熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。
2.实验内容
2.1 编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。
#include typedef int elemtype;#define maxsize 10 int del(int A[],int n,elemtype x,elemtype y){ int i=0,k=0;while(i=x&&A[i]
A[i-k]=A[i];i++;} return(n-k);} void main(){ int i,j;int a[maxsize];printf(“输入%d个数:n”,maxsize);for(i=0;i
scanf(“%d,”,&a[i]);
j=del(a,maxsize,1,3);
printf(“输出删除后剩下的数:n”);
for(i=0;i
“n,a[i]);}
2.2 试写一个算法，在无头结点的动态单链表上实现线性表插入操作INSERT(L,i,b)。
void Insert(Linklist &L,int i,elemtype x){ if(!L){
} L=(Linklist)malloc(sizeof(Lnode));(*L).data=x;(*L).next=NULL;} else { if(i==1){
s=(Linklist)malloc(sizeof(Lnode));
s->data=x;s->next=L;L=s;} else {
p=L;j=1;
while(p&&j
{j++;p=p->next;}
if(p||j>i-1)
return error;
s=(Linklist)malloc(sizeof(Lnode));
s->data=x;s->next=p->next;p->next=s;} } 2.3 生成两个多项式PA和PB，求他们的和，输出“和多项式”。typedef struct node {int exp;float coef;struct node *next;}polynode;polynode *polyadd(polynode *pa,polynode *pb){ polynode *p,*q,*pre,*r;float x;p=pa->next;q=pb->next;pre=pa;while((p!=NULL)&&(q!=NULL))
if(p->exp>q->exp)
{
r=q->next;
q->next=p;
pre->next=q;
pre=q;
q=r;
}
}
else if(p->exp==q->exp){
x=p->coef+q->coef;
if(x!=0)
{p->coef=x;
s=p;
}
else
{pre->next=p->next;
free(p);
}
p=pre->next;
r=p;
q=q->next;
free(r);} else
if(p->expexp)
{
pre=p;
p=p->next;
}
if(q!=NULL)
pre->next=q;
free(pb);2.4 设计一个统计选票的算法，输出每个候选人的得票结果。
typedef int elemtype typedef struct linknode { elemtype data;struct linknode *next;}nodetype;nodetype *create(){ elemtype d;nodetype h=NULL,*s,*t;int i=1;printf(”建立单链表:n“);while(1){
printf(”输入第%d个结点数据域“,i);
scanf(”%d“,&d);
if(d==0)break;
if(i==1)
{
h=(nodetype *)malloc(sizeof(nodetype));
h->data=d;h->next=NULL;t=h;
}
else
{
s=(nodetype *)malloc(sizeof(nodetype));
s->data=d;s->next=NULL;t->next=s;
t=s;
}
i++;} return h;}
void sat(nodetype *h,int a[]){ nodetype *p=h;while(p!=NULL){
a[p->data]++;
p=p->next;} } void main(){ int a[N+1],i;for(i=0;i
a[i]=0;nodetype *head;head=create();sat(head,a);printf(”候选人:“);for(i=1;i
printf(”%3d“,a[i]);printf(”n“);}
3.实验心得体会
线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。
实验二
1.实验要求
1.1 了解栈和队列的特性，以便灵活运用。1.2 熟练掌握栈和有关队列的各种操作和应用。
2.实验内容
2.1 设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。#include #include #include #define NULL 0 typedef struct list { char str;struct list *next;}list;void push(char,list *);int pop(char.list *);void deal(char *str);main(void){char str[20];printf(”n请输入一个算式:n“);gets(str);deal(str);printf(”正确!“);getchar();return 0;} void deal(char *str){list *L;L=(list *)malloc(sizeof(list));if(!L){ printf(”错误!“);exit(-2);} L->next=NULL;while(*str){ if(*str=='('||*str=='['||*str=='{')
push(*str,L);else
if(*str==')'||*str==']'||*str=='}')
if(pop(*str,L))
{puts(”错误,请检查!“);
puts(”按回车键退出“);
getchar();exit(-2);
}
str++;} if(L->next){puts(”错误,请检查!“);puts(”按任意键退出“);getchar();exit(-2);} } void push(char c,list *L){list *p;p=(list *)malloc(sizeof(list));if(!p){ printf(”错误!“);exit(-2);} p->str=c;p->next=L->next;L->next=p;} #define check(s)if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);} int pop(char c,list *L){ list *p;if(L->next==NULL)return 1;switch(c){ case')':check('(')break;case']':check('[')break;case'}':check('{')break;} return 1;
实验三
1.实验要求
1.1 掌握二叉树，二叉树排序数的概念和存储方法。1.2 掌握二叉树的遍历算法。
1.3 熟练掌握编写实现树的各种运算的算法。2.实验内容
2.1 编写程序，求二叉树的结点数和叶子数。#include #include struct node{ char data;struct node *lchild,*rchild;}bnode;typedef struct node *blink;blink creat(){ blink bt;char ch;ch=getchar();if(ch==' ')return(NULL);else {
bt=(struct node *)malloc(sizeof(bnode));
bt->data=ch;
bt->lchild=creat();
bt->rchild=creat();} return bt;} int n=0,n1=0;void preorder(blink bt){ if(bt){
n++;
if(bt->lchild==NULL&&bt->rchild==NULL)
n1++;
preorder(bt->lchild);
preorder(bt->rchild);} } void main(){
} blink root;root=creat();preorder(root);printf(”此二叉数的接点数有:%dn“,n);printf(”此二叉数的叶子数有:%dn“,n1);2.2 编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。int get_deep(bitree T,int x){ if(T->data==x){ printf(”%dn“,get_deep(T));exit 1;} else { if(T->lchild)get_deep(T->lchild,x);if(T->rchild)get_deep(T->rchild,x);} int get_depth(bitree T){ if(!T)return 0;else { m=get_depth(T->lchild);n=get_depth(T->rchild);return(m>n?m:n)+1;} } 2.3 编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。#include #include struct node{ char data;struct node *lchild,*rchild;}bnode;typedef struct node *blink;blink creat(){ blink bt;char ch;ch=getchar();if(ch==' ')return(NULL);9 else { bt=(struct node *)malloc(sizeof(bnode));bt->data=ch;bt->lchild=creat();bt->rchild=creat();} return bt;} void preorder(blink bt){ if(bt){ printf(”%c“,bt->data);preorder(bt->lchild);preorder(bt->rchild);} } void inorder(blink bt){ if(bt){
inorder(bt->lchild);printf(”%c“,bt->data);inorder(bt->rchild);} } void postorder(blink bt){ if(bt){ postorder(bt->lchild);postorder(bt->rchild);printf(”%c“,bt->data);} } int max(int x,int y){ if(x>y)return x;else
return y;} int depth(blink bt){ if(bt)return 1+max(depth(bt->lchild),depth(bt->rchild));else return 0;} void main(){ blink root;root=creat();printf(”n“);printf(”按先序排列:“);preorder(root);printf(”n“);printf(”按中序排列:“);inorder(root);printf(”n“);printf(”按后序排列:“);postorder(root);printf(”n“);printf(”此二叉数的深度是:“);printf(”depth=%dn“,depth(root));} 3.实验心得体会
通过本章学习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。
#include #include #define len sizeof(struct node)#define null 0 typedef struct node{ int data;int ltag,rtag;struct node *lchild,*rchild;}Treenode;Treenode *pre=null;Treenode *creat(){ Treenode *bt;int n;scanf(”%d“,&n);if(n!=0){
bt=(Treenode *)malloc(len);
bt->data=n;bt->ltag=0;bt->rtag=0;
bt->lchild=creat();
bt->rchild=creat();} else bt=null;return bt;} void preorder1(Treenode *t){ if(t!=null){
printf(”%4d“,t->data);
preorder1(t->lchild);
preorder1(t->rchild);} } void preorder2(Treenode *t){ if(t!=null){
preorder2(t->lchild);
printf(”%4d“,t->data);
preorder2(t->rchild);} } void preorder3(Treenode *t){ if(t!=null){
preorder3(t->lchild);
preorder3(t->rchild);
printf(”%4d“,t->data);} } void InThread(Treenode *T){ Treenode *p;p=T;if(p){ InThread(p->lchild);if(!p->lchild){ p->ltag=1;p->lchild=pre;} if(!pre->rchild){ pre->rtag=1;pre->rchild=p;} pre=p;InThread(p->rchild);} } Treenode *inorderthreading(Treenode *T){ Treenode *Thre;Thre=(Treenode *)malloc(sizeof(Treenode)Thre->lchild=T;Thre->rchild=Thre;pre=Thre;InThread(T);pre->rtag=1;pre->rchild=Thre;Thre->rchild=pre;return Thre;} void InThrTravel(Treenode *Thre){ Treenode *p;p=Thre->lchild;while(p!=Thre){ while(p->ltag==0)p=p->lchild;printf(”%4d“,p->data);while(p->rtag==1 && p->rchild!=Thre){ p=p->rchild;printf(”%4d“,p->data);} p=p->rchild;}printf(”n“);} void main(){ Treenode *tree;int i;printf(”建立二叉树:n“);tree=creat();printf(”请选择遍历二叉树的方法:nn1.先根序遍历.n2.中根序遍历.n3.后根序遍历.n“);scanf(”%d“,&i);while(i>3 && i
scanf(”%d“,&i);} switch(i){ case 1:preorder1(tree);break;case 2:preorder2(tree);break;case 3:preorder3(tree);break;} printf(”n中根序线索遍历:n“);tree=inorderthreading(tree);InThrTravel(tree)
实验四
#include #include #define null 0 #define n 4 #define m 2*n-1 typedef struct { int weight;int parent,llink,rlink;}node;typedef struct { int start;char bits[n+1];}codetype;typedef struct { char c;codetype code;}element;node tree[m+1];void inithafumantree(node tree[]){ int i;for(i=0;i
tree[i].parent=0;
tree[i].llink=0;
tree[i].rlink=0;} } void inputweight(node tree[]){ int i;printf(”请输入各结点的权值:n“);for(i=1;i
printf(”第%d个结点的权值:“,i);
scanf(”%d“,&tree[i].weight);} } void select(int pre,int *min1,int *min2){ int i;*min1=*min2 = 0;for(i=1;i= tree[i].weight){ *min2 = *min1;*min1 = i;} else if(tree[*min2].weight>tree[i].weight)*min2=i;} } } void sethuftree(node tree[m+1]){ int i,x1,x2;printf(”构造哈夫曼树.nn“);inithafumantree(tree);inputweight(tree);for(i=n+1;i
select(i-1,&x1,&x2);
tree[x1].parent=i;
tree[x2].parent=i;
tree[i].llink=x1;
tree[i].rlink=x2;
tree[i].weight=tree[x1].weight+tree[x2].weight;} void encode(node tree[],element table[]){ int i,s,f;codetype c;for(i=1;i
table[i].c=tree[i].weight;
c.start=n+1;s=i;
while(f=tree[s].parent)
{ c.bits[--c.start]=(s==tree[f].llink)?'0':'1';s=f;}
table[i].code=c;} void main(){ int i;element table[n+1];sethuftree(tree);encode(tree,table);printf(”n输出Huffman编码n“);for(i=1;i
实验五
#include #include #define MAX 1000 #define MAXN 100 typedef struct{ char vexs[MAXN];int edges[MAXN][MAXN];int n,e;}MGraph;void createmgraph(MGraph *g){ int i,j,k,w;char Node='a';printf(”nPlease input n:“);scanf(”%d“,&g->n);printf(”Please input e:“);scanf(”%d“,&g->e);for(j=0;jn;j++)g->vexs[j]=Node++;for(i=0;in;i++)
for(j=0;jn;j++)
if(i==j)g->edges[i][j]=0;
else g->edges[i][j]=MAX;
for(k=0;ke;k++){
printf(”Input i,j,w:(eg.0,1,5)n“);
scanf(”%d,%d,%d“,&i,&j,&w);
g->edges[i][j]=w;
printf(”nThe graph is: nn“);
printf(”t “);
for(k=0;kn;k++){
printf(”%3c“,g->vexs[k]);
if(k==g->n-1)printf(”nn“);
}
for(i=0;in;i++){
printf(”t%c “,g->vexs[i]);
for(j=0;jn;j++)
if(g->edges[i][j]==MAX)printf(”%3c“,MAX-923);
else printf(”%3d“,g->edges[i][j]);
printf(”n“);
} void main(){ MGraph *g;g=(MGraph *)malloc(sizeof(MGraph));createmgraph(g);getchar();}
实验六
1.实验要求
1.1 熟悉图的各种存储方法。
1.2 掌握遍历图的递归和非递归的算法。1.3 理解图的有关算法。
2.实验内容
2.1 写出将一个无向图的邻接矩阵转换成邻接表的算法。void mattolist(int a[][],adjlist b[],int n)
{ for(i=0;i
for(i=0;i
for(j=n-1;j>=0;j--)
if(a[i][j]!=0)
{p=(arcnodetp *)malloc(sizeof(arcnodetp));
p->adjvex=j;
p->nextare=b[i].firstare;
b[i].firstarc=p;
} }
2.2 以邻接表作存储结构，给出拓扑排序算法的实现。typedef struct vexnode { VertexType vertex;int in;ArecNodeTp * fristarc;}AdjList[vnum];typedef struct graph { AdjList adjlist;int vexnum,arcnum;}GraphTp;Top_Sort(GraphTp g){ LstackTp *p;int m,i,v;initStack(S);for(i=0;i if(g.adjlist[i].in==0)/*if(w的入度==0)*/ push(S,&v);/*w入S栈*/ } } m=0;whlie(!EmptyStack(S)){ Pop(S,&v)//S出栈->v printf(”%d“,v);/*输出v*/ m++;p=g.adjlist[i].fristarc;/*p=图g中顶点v的第一个邻接点*/ while(p!=NULL){//p存在(g.adjlist[p->adjvex].in)--;/*p的入度--*/ if(g.adjlist[p->adjvex].in==0)/*if(p的入度==0)*/ Push(S,p->adjvex);/*p入S栈*/ p=p->nextarc;/*p=图g中的顶点v的下一个邻接点*/ } } if(m 实验七 #include #include #define NULL 0 #define maxsize 100 typedef struct node { int data;struct node *left,*right;}dnode;int n=0;void sort(dnode *t,int c)//将c插入到二叉排序树中 { dnode *p;if(c>=t->data) if(t->right==NULL) { p=(dnode *)malloc(sizeof(dnode)); p->data=c; p->left=NULL;p->right=NULL; t->right=p; } else sort(t->right,c);if(cdata) if(t->left==NULL) { p=(dnode *)malloc(sizeof(dnode)); p->data=c;p->left=NULL;p->right=NULL;t->left=p; } else sort(t->left,c)dnode *creat(){ dnode *ht;int x;ht=(dnode *)malloc(sizeof(dnode));printf(”创建二叉排序树(以0结束输入):“);scanf(”%d“,&x);ht->data=x;n++;ht->left=NULL;ht->right=NULL;scanf(”%d“,&x);while(x>0){ sort(ht,x);n++; scanf(”%d“,&x);} return ht;} int find(dnode *b,int x,dnode *a[]){ dnode *stack[maxsize],*p;int top;a[1]=NULL; if(b!=NULL){ top=1;stack[top]=b;while(top>0){ p=stack[top];top--;if(p->left->data==x || p->right->data==x)a[1]=p;if(p->data==x){a[0]=p;return 1;} if(p->right!=NULL){ top++;stack[top]=p->right;} if(p->left!=NULL){ top++;stack[top]=p->left;} } } a[0]=p;} dnode *delet(dnode *t){ dnode *p,*q,*s,*f,*a[2];int flag=0,x;p=(dnode *)malloc(sizeof(dnode));f=(dnode *)malloc(sizeof(dnode));printf(”请输入要删除的结点:“);scanf(”%d“,&x);find(t,x,a);p=a[0];f=a[1];if(p==NULL){printf(”NO FIND!n“);exit(0);} if(p->left==NULL)s=p->right;else if(t->right=NULL)s=p->left;else{ q=p;s=p->left;while(s->right!=NULL) {q=s;s=s->right;} if(q==p)q->left=s->left; else q->right=s->left;p->data=s->data;free(s);flag=1;if(flag==0){ if(f==NULL)t=s;else if(f->left==p)f->left=s; else f->right=s;} return t;} void inorder(dnode *t){ if(t!=NULL){ inorder(t->left);printf(”%4d“,t->data);inorder(t->right);} } void main(){ dnode *h;h=creat();printf(”中序遍历二叉排序树:“);inorder(h);printf(”n“);h=delet(h); inorder(h);printf(”n“);} 实验八 1.实验要求 1.1 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。1.2 能运用线性表的查找方法解决实际问题。2.实验内容 2.1 编写一个算法，利用二分查找算法在一个有序表中插入一个元素X，并保持表的有序性。 #include #include #define MAXNUM 20 int input(int *);/*输入数据*/ int search(int *,int,int);/*查找插入位置*/ void plug(int *,int,int);/*插入数据*/ void main(void){ int data[MAXNUM],m;int insert=1;m=input(data);printf(”Input the insert num:“);scanf(”%d“,data);insert=search(data,1,m);/*返回插入位置*/ plug(data,insert,m);for(insert=1;insert printf(”%3d“,*(data+insert));getch();} /*********************************************************/ int input(int *data){ int i,m;printf(”nInput the max num:“);scanf(”%d“,&m);printf(”input datan“);for(i=1;i scanf(”%d“,data+i);return m;} /**********************************************************/ int search(int *data,int low,int high)/*递归查找插入位置*/ { int mid;if(low>high)return low;/*没有找到插入数据，返回low*/ else{ mid=(low+high)/2; if(*(data+mid)==*data)retun mid;/*找到插入数据，返回mid*/ else if(*(data+mid) else if(*()data+mid)>*data)} search(data,low,high);} /**********************************************************/ void plug(int *data,int insert,int m){ int i;for(i=m;i>insert;i--) *(data+i+1)=*(data+i);*(data+insert)=*data } 2.2 根据给定的数据表，先建立索引表，然后进行分块查找。 #include #include #include #definr N 18 /*元素个数*/ #definr Blocknum 3 /*分块数*/ typedef struct indexterm { int key;/*最大关键字*/ int addr;/*块的起始地址*/ }index;/*索引表数据类型*/ index * CreateList(int data[],int n)/*建索引表*/ { index *p;int m,j,k;m=n/BlockNum;/*分为BlockNum块，每块有m个元素*/ p=(index *)malloc(BlockNum *sizeof(index));for(k=0;k (p+k)->key=dat a[m*k]; (p+k)->addr=m*k; for(j=m*k;j if(data[j]>(p+k)->key) (p+k)->key=data[j];/*块的最大关键字*/ } return p;} int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分块查找*/ { int low=0,high=m-1,mid,i;int b=n/m;/*每块有b个元素*/ while(low mid=(low+high)/2; if((list+mid)->key>=k) high=mid+1; else low=mid+1;} if(low for(i=(list+low)->addr;iadder+b-1&&rectab[i]!=k;i++); if(iaddr+b-1) return i; else return-1;} return-1;} void main(){ int record[N]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};int key;index *list;printf(”please input key:n“);scanf(”%d“,&key);list=CreateList(record,N);printf(”data postion id %dn",BlockSearch(list,record,N,BlockNum,key));} 3.实验心得体会 通过本章的学习，对排序有较高层次的理解与认识，从平时的练习中可以看出排序是数据处理中经常用到的重要运算。有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能用效率较低的顺序查找法。
