《数据结构》实训报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实训报告样本”。
实验一
线性表
1.实验要求
1.1 掌握数据结构中线性表的基本概念。
1.2 熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。1.3 熟练掌握链表的各种操作和应用。2.实验内容
2.1 编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。
2.2 试写一个算法，在无头结点的动态单链表上实现线性表插入操作 2.3 设计一个统计选票的算法，输出每个候选人的得票结果。
3.实验代码
2.1代码：
#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代码：
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
线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。
实验二
栈与队列
1.实验要求
1.1 了解栈和队列的特性，以便灵活运用。1.2 熟练掌握栈和有关队列的各种操作和应用。
2.实验内容
2.1 设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。
3.实验代码
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;
4.实验小结
栈和队列是最基础的一种数据结构之一，为实现其他数据结构的奠定基石。
实验三 树
1.实验要求
1.1 掌握二叉树，二叉树排序数的概念和存储方法。1.2 掌握二叉树的遍历算法。
1.3 熟练掌握编写实现树的各种运算的算法。
2.实验内容
2.1 编写程序，求二叉树的结点数和叶子数。
2.2 编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。2.3 编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。
数据结构实验报告
3.实验代码 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代码：
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);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));4.实验小结
通过本章学习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。
实验四 图
1.实验要求
1.1 熟悉图的各种存储方法。
1.2 掌握遍历图的递归和非递归的算法。1.3 理解图的有关算法。
2.实验内容
2.1 写出将一个无向图的邻接矩阵转换成邻接表的算法。
数据结构实验报告
2.2 以邻接表作存储结构，给出拓扑排序算法的实现。
3.实验代码
2.1代码：
void mattolist(int a[][],adjlist b[],int n)/*n为图的结点个数*/ { for(i=0;i
/*邻接表置空*/ for(i=0;i
/*逐行进行*/
}
2.2代码： typedef struct vexnode {
VertexType vertex;int in;/*增加一个入度域*/ ArecNodeTp * fristarc;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;} }AdjList[vnum];typedef struct graph { AdjList adjlist;int vexnum,arcnum;}GraphTp;Top_Sort(GraphTp g)
数据结构实验报告
{
LstackTp *p;/*建立入度为0的顶点栈S*/ int m,i,v;
initStack(S);
} for(i=0;i
} if(mv 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的下一个邻接点*/ 4.实验小结
通过本章学习实验，对图有了具体的认识。图也是一种非线性的数据结构，这种结构有着广泛的应用，一切具有关系的问题都可以用图来表示。
数据结构实验报告
实验五 查找
1.实验要求
1.1 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。1.2 能运用线性表的查找方法解决实际问题。2.实验内容
2.1 编写一个算法，利用二分查找算法在一个有序表中插入一个元素X，并保持表的有序性。
2.2 根据给定的数据表，先建立索引表，然后进行分块查找。3.实验代码
2.1代码：
#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;ihigh)return low;/*没有找到插入数据，返回low*/ else{
} 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);mid=(low+high)/2;if(*(data+mid)==*data)retun mid;/*找到插入数据，返回mid*/ else if(*(data+mid)*data)*(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
} return p;} int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分块查找*/ { int low=0,high=m-1,mid,i;(p+k)->key=dat a[m*k];(p+k)->addr=m*k;for(j=m*k;j(p+k)->key)(p+k)->key=data[j];/*块的最大关键字*/
数据结构实验报告
int b=n/m;/*每块有b个元素*/ while(low
} if(lowaddr;iadder+b-1&&rectab[i]!=k;i++);
} 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));} if(iaddr+b-1)return i;mid=(low+high)/2;if((list+mid)->key>=k)high=mid+1;else low=mid+1;else return-1;4.实验小结
通过本章的学习，对排序有较高层次的理解与认识，从平时的练习中可以看出排序是数据处理中经常用到的重要运算。有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能用效率较低的顺序查找法。
北京联合大学实训报告课程（项目）名称： 数据结构 学 院： 专 业： 班 级： 学 号：姓 名： 成 绩：2012年 6 月 21 日数据结构实训任务一一、任务与目的： 1、用顺序表表示两个无序集合A、B，实......
题目：在火车货场车皮编解场，2条轨道连接到2条侧轨道，形成2个铁路转轨栈，其中左边轨道为车皮入口，编号为A；右边轨道为出口，编号为D；2个铁路转轨栈分别编号为C和D如下图所示。编号为a,......
（ 数据结构实训报告 ）目录一、实训目的 ...........................................................1二、实训题目 ..........................................................
这次课程设计的心得体会通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独......
注意：第5题和第7题有改动，第6题加了一句提示一、停车场管理仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问......
