第一篇:数据结构实训报告
题目:在火车货场车皮编解场,2条轨道连接到2条侧轨道,形成2个铁路转轨栈,其中左边轨道为车皮入口,编号为A;右边轨道为出口,编号为D;2个铁路转轨栈分别编号为C和D如下图所示。编号为a, b, c, ┅, n的各车皮依序停放在车皮的入口处,调度室要安排个车皮进出栈次序,使得在出口处各车皮按照预先制定的顺序依次出站。车皮移动时只能按照从左到右的方向移动。组织与指导老师:
组长:*
成员:***
指导教师:*
完成时间、地点:
时间:第16周(6月6日~6月10日)
地点:南校区东教学楼2楼机房。
一、需求分析
1、问题描述
掌握队列、栈、树的结构以及基本操作,熟悉for循环语句,if条件语句的嵌套,结构体函数等,从而实现程序的功能。
例如:
typedef struct Stack
{
Data *data;
Data *end;
}Stack;
……
2、实现功能
(1)对于给定的车皮数n,以及各车皮的出站顺序,编程计算最优调度方案,使得移动车皮的次数最少。
(2)数据输入:由文件input.txt给出数据。第一行有1个正整数n,表示车皮数;接下来的1行是一个字符串,表示预先确定的车皮的出站顺序。
(3)数据输出:将计算得到的最优调度方案输出到文件output.txt,文件的第一行使最少移动次数m,接下来的m行使对于最优方案的m次移动。每次移动用“cXY”的3个字符表示,其中c表示车皮编号,X表示其时栈号,Y表示目标栈号。如果无法调度则输出“No Solution!”
二、概要设计
1、抽象数据类型
void ReadData(void)
{
int i;
FILE *fp;
fp = fopen(“input.txt”, “r”);
if(fp == NULL)
exit(__COUNTER__);
fscanf(fp, “%d”, &total);
if(total < 1)
{
fclose(fp);
exit(__COUNTER__);
}
……、void Show(Stack a, char *s)
{
char *tmp, *pc;
char *p =(char*)a.data;
pc = tmp =(char*)malloc(total + 1);
while(p <= a.end)
*pc++ = *p++;
*pc = 0;
printf(“%s%s”, tmp, s);
}
……
if(d == end)
{
if(min > count)
{
min = count;
strcpy(res, tmp);
return;
}
}
count++;
if(A.end >= A.data)
a = *A.end;
else
a = EOD;
……
2、程序中包含功能模块及模块间的调用关系
各个基本操作都通过公有成员函数实现,然后通过主程序调用来实现程序的功能。
例如:
void Init(Stack *a, int len)
{
a->data =(Data*)malloc(len * sizeof(Data));
memset(a->data, 0, len * sizeof(Data));
a->end = a->data-1;
}
……
void main(void)
{
ReadData();
Calc(head);
End();
}
三、调试分析
完成情况说明:
编译程序的过程中发现了许多漏洞,调试起来很不方便,经过我和同学的共同努力,终于有了突破性的进展,程序按照预定的时间调试出来了,虽然当中还存在不少的漏洞,但不会影响程序的正常运行。
程序的性能分析:各个操作都是通过公有函数的调用来实现的,其中用到结构体函数,for循环,If语句的嵌套等,通过测试可以实现其预定的功能。出现的问题及解决方案:
缺失头文件导致的定义无效错误,通过添加头文件即可解决问题;定义字符类型错误,使用正确的函数类型定义即可,for循环的循环语句语法使用不当,导致函数无法实现循环,if条件语句的应用还存在问题,以上所述的编译错误都通过我很同学的认真分析后纠正了。
四、用户使用说明
了解程序的执行过程,输入合法的数值是程序正常运行的关键,输入的数值和开始需要的字符的长度要符合五、心得体会:
通过多次编写程序,我总结出来一条心得,程序不能写完才调试,而是应该写一个函数调试一个函数,这样才能缩小调试的范围,提高编程的效率,程序编完后在进行一次综合调试,将不完善的函数和功能处理好,才能将程序做到最好!而且,很多时候,一个大的工程并不是一个人就能完成,这就要求我们有团队精神。让我感受最深的是在我调试程序的时候,一个很细微的错误就可能导致程序的出错,正所谓的“细节决定成败”,不管是在学习中,生活中,我们都要有一颗善于发现问题,解决问题的新,除此之外,还要有乐于助人的精神。
第二篇:《数据结构》实训报告
实验一
线性表
1.实验要求
1.1 掌握数据结构中线性表的基本概念。
1.2 熟练掌握线性表的基本操作:创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。1.3 熟练掌握链表的各种操作和应用。2.实验内容
2.1 编写一个函数,从一个给定的顺序表A中删除元素值在x到y之间的所有元素,要求以较高效率来实现。
2.2 试写一个算法,在无头结点的动态单链表上实现线性表插入操作 2.3 设计一个统计选票的算法,输出每个候选人的得票结果。
3.实验代码
2.1代码:
#include
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<=N;i++)printf(“%3d”,i);printf(“n得票数n”);for(i=1;i<=N;i++)printf(“%3d”,a[i]);printf(“n”);4.实验小结 线性表是最简单的、最常用的一种数据结构,是实现其他数据结构的基础。 实验二 栈与队列 1.实验要求 1.1 了解栈和队列的特性,以便灵活运用。1.2 熟练掌握栈和有关队列的各种操作和应用。 2.实验内容 2.1 设一个算术表达式包括圆括号,方括号和花括号三种括号,编写一个算法判断其中的括号是否匹配。 3.实验代码 2.1代码: #include 数据结构实验报告 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 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 数据结构实验报告 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(m 通过本章学习实验,对图有了具体的认识。图也是一种非线性的数据结构,这种结构有着广泛的应用,一切具有关系的问题都可以用图来表示。 数据结构实验报告 实验五 查找 1.实验要求 1.1 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。1.2 能运用线性表的查找方法解决实际问题。2.实验内容 2.1 编写一个算法,利用二分查找算法在一个有序表中插入一个元素X,并保持表的有序性。 2.2 根据给定的数据表,先建立索引表,然后进行分块查找。3.实验代码 2.1代码: #include 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<=m+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<=m;i++)scanf(“%d”,data+i);return m;} int search(int *data,int low,int high)/*递归查找插入位置*/ { int mid;if(low>high)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)else if(*()data+mid)>*data)*(data+insert)=*data 数据结构实验报告 } 2.2代码: #include /*元素个数*/ #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 数据结构实验报告 int b=n/m;/*每块有b个元素*/ while(low<=high){/*块间折半查找*/ } if(low } 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(i<=(list+low)->addr+b-1)return i;mid=(low+high)/2;if((list+mid)->key>=k)high=mid+1;else low=mid+1;else return-1;4.实验小结 通过本章的学习,对排序有较高层次的理解与认识,从平时的练习中可以看出排序是数据处理中经常用到的重要运算。有序的顺序表可以采用查找效率较高的折半查找法,而无序的顺序表只能用效率较低的顺序查找法。 (数据结构实训报告) 目录 一、实训目的...........................................................1 二、实训题目...........................................................1 三、实训步骤...........................................................2 四、实训内容...........................................................2 五、实训心得..........................................................19 六、参考文献..........................................................19 吉林工业职业技术学院 数据结构实训 一、实训目的 通过实训,对所学数据结构和程序设计的基本知识和基本理论有更进一步的了解和认识,将理论和实际相结合,能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来。主要是培养学生综合利用C语言进行程序设计的能力和创新能力以及综合解决问题的能力。运用算法分析与程序设计的一般方法进行实际项目的开发。本次实训尽量选取与实际结合紧密或学生比较感兴趣的项目,本次实训学生需要具备熟练的程序设计基础、数据结构和计算机应用基础知识,具备程序编写、调试的基本能力,具有一定的文字表达和报告撰写能力,具备办公软件使用能力。 通过实训,考查语言基本概述掌握是否牢固,并考查与后续课程较为密切的结构体,链表,文件的运用熟练程度,加强对基本概念的理解和复习,最重要的是了解基本软件的设计步骤,还有对软件调试的掌握。能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养基本的、良好的程序设计技能。 二、实训题目 (一)单项题目 1、二叉树遍历 【问题描述】建立二叉树,实现二叉树的先序遍历、中序、后序和层序遍历(用递归或非递归的方法都可以)。 【要 求】编写菜单程序。能够输入二叉树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立二叉树存储结构的输入函数、输出先序遍历序列的函数;输出中序遍历序列的函数;输出后序遍历序列的函数;输出层序遍历序列的函数。 (二)综合题目 1、图书管理系统 吉林工业职业技术学院 数据结构实训 【问题描述】建立一个图书信息文件,包括书号(num)、书名(bookname)、作者(name)、出版社(publish)、价格(price)等。 【要 求】建立一个图书信息文件,包括书号(num)、书名(bookname)、作者(name)、出版社(publish)、价格(price)等。 三、实训步骤 1、问题分析 正确理解问题,分析问题究竟“做什么”,分析问题已知的信息及其作用,分析在解决中对信息处理的规则、要求、限制条件,分析问题解决后应该输出什么样的结果(输出形式、格式、内容)。并分析得出判定结果是否正确的标准。 2、设计分析 得出解决问题的思路、主要流程、采用的数据结构类型的说明、主要算法的思想。 3、设计方案 采用的数据结构类型的定义、主要算法的描述及说明。 4、详细设计 根据问题要求和已得到的算法编写程序。 5、调试程序 发现程序中存在的语法错误和一些逻辑错误,并修改,使程序能够运行。 6、运行程序 选择若干具有代表性的输入数据(包括合理数据和不合理数据),进行测试,尽量使程序的各语句和分支都被检查到,以便发现程序中的错误和漏洞,以便改进算法和程序。 7、使用说明 包括程序源代码、算法(程序)流程图、开发过程中各阶段的有关记录、算法的正确性证明、程序的测试结果、对输入输出要求及格式的详细描述。 四、实训内容 (一)个人题目 1、二叉树遍历 【问题描述】建立二叉树,实现二叉树的先序遍历、中序、后序和层序遍历(用递归或非递归的方法都可以)。吉林工业职业技术学院 数据结构实训 【要 求】编写菜单程序。能够输入二叉树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立二叉树存储结构的输入函数、输出先序遍历序列的函数;输出中序遍历序列的函数;输出后序遍历序列的函数;输出层序遍历序列的函数。 【设计分析】 1、总体设计(基本概念)树的概念 树(Tree)是n(n>=0)个结点的有限集。在任意一棵非空树中: 1)有且仅有一个特定的称为根的结点; 2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2......Tm,其中每一个集合又是一棵树,并且称为根的子树(SubTree)。 【例】如图1所示: 图1 图1是有8个结点的树,其中A是根,其余结点分成2个互不相交的子集:T1={B,D},T2={C,E,F,G,H};T1和T2都是根A的子树,且本身也是一棵树。 【设计方案】1.创建二叉树(可从键盘输入各结点的值)2.按某种方式对二叉树进行遍历 3.树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的,在计算 机领域里也得到了广泛的应用。在编译程序里,也可用树来表示源程序的语法结构,在数据库系统中,数形结构也是信息的重要组织形式。 4.节点的有限集合(N大于等于0)。在一棵非空数里:(1)、有且仅有 吉林工业职业技术学院 数据结构实训 一个特定的根节点;(2)、当N大于1时,其余结点可分为M(M大于0)个互不相交的子集,其中每一个集合又是一棵树,并且称为根的子树。树的定义是以递归形式给出的。 5.二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树,并且,二叉 树的子树有左右之分,其次序不能颠倒。 从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:(1)访问结点本身(N),(2)遍历该结点的左子树(L),(3)遍历该结点的右子树(R)。以上三种操作有六种执行次序: NLR、LNR、LRN、NRL、RNL、RLN。【详细设计】本程序源代码如下: /*源程序*/ /* Note:Your choice is C IDE */ #include “stdio.h” #include typedef char DataType;#define MaxStackSize 50 using namespace std; typedef struct Node { DataType data; struct Node *leftChild; struct Node *rightChild; }BiTreeNode;typedef BiTreeNode* DataType2;typedef struct { DataType2 stack[MaxStackSize];吉林工业职业技术学院 数据结构实训 int top;} SeqStack;typedef struct { DataType2 quene[MaxStackSize]; int front; int rear;}Quene;void StackInitiate(SeqStack *S) { S->top = 0;} int StackNotEmpty(SeqStack S){ if(S.top <= 0)return 0; else return 1;} int StackPush(SeqStack *S, DataType2 x){ if(S->top >= MaxStackSize) { printf(“堆栈已满无法插入!n”); return 0; } else { S->stack[S->top] = x; S->top ++; return 1; } } int StackPop(SeqStack *S, DataType2 *d){ if(S->top <= 0) { printf(“堆栈已空无数据元素出栈!n”); return 0; } else { S->top--; *d = S->stack[S->top]; return 1;吉林工业职业技术学院 数据结构实训 } } int StackTop(SeqStack S, DataType2 *d){ if(S.top <= 0) { printf(“堆栈已空!n”); return 0; } else { *d = S.stack[S.top-1]; return 1; } } typedef struct node{ char data;struct node *lchild;struct node *rchild;}BTNode; typedef BTNode *BTree; int NodeNum,leaf; BTree CreatBTree(void){BTree T;char ch;if((ch=getchar())=='*')return(NULL); else{ T=(BTNode *)malloc(sizeof(BTNode));T->data=ch;T->lchild=CreatBTree();T->rchild=CreatBTree();return(T);} } void Preorder(BTree T)吉林工业职业技术学院 数据结构实训 { if(T){ printf(“%c”,T->data); Preorder(T->lchild); Preorder(T->rchild);} } void Inorder(BTree T){ if(T){ Inorder(T->lchild); printf(“%c”,T->data); Inorder(T->rchild);} } void Postorder(BTree T){ if(T){ Postorder(T->lchild); Postorder(T->rchild); printf(“%c”,T->data);} } int TreeDepth(BTree T){ int hl,hr,max;if(T){ hl=TreeDepth(T->lchild); hr=TreeDepth(T->rchild); max=hl>hr?hl:hr; NodeNum=NodeNum+1; if(hl==0&&hr==0) leaf=leaf+1; return(max+1);} 吉林工业职业技术学院 数据结构实训 else return(0);} void Levelorder(BTree T){ int front=0,rear=1;BTNode *cq[Max],*p;cq[1]=T;while(front!=rear){ front=(front+1)%NodeNum; p=cq[front]; printf(“%c”,p->data); if(p->lchild!=NULL) { rear=(rear+1)%NodeNum; cq[front]=p->lchild; cq[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%NodeNum; cq[front]=p->rchild; cq[rear]=p->rchild; } } } void main(){ BTree root;int i,depth;printf(“n”);printf(“创建二叉树,请输入完全二叉树的先序序列,用*代表虚结点:”);root=CreatBTree();//返回根结点 do{ 吉林工业职业技术学院 数据结构实训 printf(“t1:先序遍历n”);printf(“t2:中序遍历n”);printf(“t3:后序遍历n”);printf(“t4:深度、结点数、叶子数n”);printf(“t5:层次遍历n”);printf(“备注:选择层次遍历之前,需要先选择4,求出该树的结点数。”); printf(“t0:Exitn”); scanf(“%d”,&i);//输入菜单序号 switch(i) { case 1:printf(“先序遍历结果为:”); Preorder(root); break; case 2:printf(“中序遍历结果为:”); Inorder(root); break; case 3:printf(“后序遍历结果为:”); Postorder(root); break; case 4:depth=TreeDepth(root); printf(“深度=%d 结点数=%d”,depth,NodeNum); printf(“叶子数=%d”,leaf); break; case 5:printf(“层次遍历为:”); Levelorder(root); break; default:exit(1); } printf(“n”);} while(i!=0);} 吉林工业职业技术学院 数据结构实训 【使用说明】本程序在turboc 2.0环境下运行,迷宫大小为20×20,需要修改迷宫大小时,可以修改程序中N值的大小。迷宫图由系统自动随机生成,每次生成的迷宫图是不同的。按enter健显示最终搜索结果。按Q健退出程序。 【运行调试】 图(1)二叉树遍历主界面 图(2) (二)综合题目 1、图书管理系统 【问题描述】建立一个图书信息文件,包括书号(num)、书名(bookname)、作者(name)、出版社(publish)、价格(price)等。 【要 求】编写菜单程序,功能包括:建立图书信息、插入记录,删除记录、修改记录、按照书号或书名查询记录、显示记录、根据图书价格进行排序。定义图书信息结构体名称为book。书号(num)、书名(bookname)、作者(name)、出版社(publish)均为字符型数组。价格(price)为单精度型数据。 吉林工业职业技术学院 数据结构实训 【设计分析】系统目标分析 每个学校都有图书馆,最初由于图书数量和种类较少,人工手动管理比较方便和灵活。随着社会的发展,图书的数量和种类越来越多,人工手动管理会降低工作的效率,希望建立一个图书馆图书信息管理系统,是为了解决了人工手动管理图书信息在实践的问题,从而达到系统化、规范化、标准化的水平。该系统的建立不但给管理者带来了方便,也节省了工作时间从而提高了工作效率。 在构造系统时,首先从需求出发构造数据库表,然后再由数据库表结合需求划分系统功能模块。这样,就把一个大的系统分解成了几个小系统。这里把系统的层次划分为了三个部分:一个自由态:即面向任何用户的界面,提供登录功能,以便不同身份的用户登录子系统;一个是一般用户态:即图书有服务子系统;还有一个是管理员界面:提供图书的管理和维护功能。对于不同子系统之间的功换,采用了登录功能和用户注销功能。系统划分了子系统后,下一步的工作是继续划分子系统的小模块。先考虑在进入子系统时应该做什么,进入系统之后又应该做什么,提供那些服务等。例如,对于图书信息服务子系统,在用户进入时首先得调用相关数据库表,找出用户的图书借阅情况;进入系统后,子系统得提供图书查询、图书借阅和还书功能。另外,针对本系统的特殊情况,同时也考虑系统的可移植性,在系统中增加了数据库路径的维护部分。最后,考虑到系统的安全性,还在系统中特别增加了“加密界面”的功能。 【设计方案】本数据库管理系统主要由图书检索、图书管理、数据维护、图书统计、打印输出、系统维护六大模块组成, 如图1 所示。各模块功能如下: 1、主控模块主控模块的功能是控制各个分支模块,它是实现各模块功能的总控制台 2、图书检索模块是图书管理系统的重要模块之一,是读者快速查询图书的途径 本模块的功能是按书名、书号、作者、出版社、图书分类查询 数据维护模块是由图书管理员控制的模块,它由增加、修改和删除读者,增加、修改删除图书,浏览修改读者、浏览修改图书等程序组成。在软件设计时考虑到读者编号、书名、书号是唯一的,因此,在修改读者或图书中,读者记录或图书记录一经登记“读者编号”和“姓名”便不能修改,在删除读者或图书时只要读者有借出图书未还或库存图书原有数量与现有库存量不符便不能删除。 5、数据统计模块由读者统计、图书统计、借出图书分类统计、到期未归还图书读者统计几部分组成 吉林工业职业技术学院 数据结构实训 我们小组的信息系统开发课程设计题目是:图书管理系统开发。系统开发的总的设计目标是实现图书管理的系统化、规范化和自动化,实现对图书资料的集中统一的管理。 本系统主要实现对图书馆信息的管理,主要功能为管理有关读者,书籍,借阅和管理者的信息等。本系统结构分为读者信息管理模块,书籍信息管理模块,借阅信息管理模块,管理者信息管理模块。读者信息管理部分有两方面的功能,可以浏览读者的信息,可以对读者信息进行维护。书籍信息管理可以浏览书籍的信息,可以对书籍信息进行维护。借阅信息管理可以显示当前数据库中书籍借阅情况,可以对借阅信息进行维护。管理者信息管理可以显示数据库中管理者的情况,可以对管理者信息进行维护。可见,本系统并不复杂,主要解决的问题是利用关键字对数据库进行查询。 【详细设计】本程序源代码如下: /*源程序*/ /* Note:Your choice is C IDE */ /* Note:Your choice is C IDE */ #include struct books_list { char author[20]; /*作者名*/ char bookname[20]; /*书名*/ char publisher[20]; /*出版单位*/ char pbtime[15]; /*出版时间*/ char loginnum[10]; /*登陆号*/ float price; /*价格*/ char classfy[10]; /*分类号*/ struct books_list * next;/*链表的指针域*/ };吉林工业职业技术学院 数据结构实训 struct books_list * Create_Books_Doc(); /*新建链表*/ void InsertDoc(struct books_list * head);/*插入*/ void DeleteDoc(struct books_list * head , int num);/*删除*/ void Print_Book_Doc(struct books_list * head);/*浏览*/ void search_book(struct books_list * head);/*查询*/ void info_change(struct books_list * head);/*修改*/ void save(struct books_list * head);/*保存数据至文件*/ /*浏览操作*/ void Print_Book_Doc(struct books_list * head){ struct books_list * p;if(head==NULL || head->next==NULL)/*判断数据库是否为空*/ { printf(“n ━━━━ 没有图书记录!━━━━nn”); return;} p=head;printf(“┏━━━┳━━━┳━━━┳━━━┳━━━━┳━━━┳━━━┓n”);printf(“┃登录号┃书名 ┃ 作者 ┃出版单位┃出版时间┃分类号┃价格┃n”); printf(“┣━━━╋━━━╋━━━╋━━━╋━━━━╋━━━╋━━━┫n”);/*指针从头节点开始移动,遍历至尾结点,依次输出图书信息*/ while(p->next!= NULL){ p=p->next; printf(“┃%-6.6s┃%-10.10s┃%-10.10s┃%-10.10s┃%-12.12s┃%-6.6s┃%.2f ┃n”,p->loginnum,p->bookname,p->author,p->publisher,p->pbtime,p->classfy,p->price);/*循环输出表格*/ } printf(“┗━━━┻━━━┻━━━┻━━━┻━━━━┻━━━┻━━━┛n”);printf(“n”);吉林工业职业技术学院 数据结构实训 } /*删除操作*/ void DeleteDoc(struct books_list * head){ struct books_list *s,*p; /*s为中间变量,p为遍历时使用的指针*/ char temp[20];int panduan;/*此变量用于判断是否找到了书目*/ panduan=0;p=s=head;printf(“ [请输入您要删除的书名]:”);scanf(“%s”,temp);/*遍历到尾结点*/ while(p!= NULL) { if(strcmp(p->bookname,temp)==0) { panduan++; break; } p=p->next;} if(panduan==1){ for(;s->next!=p;) /*找到所需删除卡号结点的上一个结点*/ { s=s->next; } s->next=p->next;/*将后一节点地址赋值给前一节点的指针域*/ free(p); printf(“n ━━━━ 删除成功!━━━━n”);} else /*未找到相应书目*/ 吉林工业职业技术学院 数据结构实训 { printf(“ 您输入的书目不存在,请确认后输入!n”);} return;} int main(void){ struct books_list * head; char choice;head=NULL;for(;;)/*实现反复输入选择*/ { printf(“ ┏━━━━━━━━━━━━━━━━━━━┏━┓n”); printf(“ ┃ ┃ socat 图书管理系统 ┃ ┃n”); printf(“ ┃ ┗━━━━━━━━━━━━━━━━━━━┛ ┃n”); printf(“ ┃ ●[1]图书信息录入 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[2]图书信息浏览 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[3]图书信息查询 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[4]图书信息修改 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[5]图书信息删除 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[6]退出系统 ┃n”); printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━┛ 15 吉林工业职业技术学院 数据结构实训 n”); printf(“ 请选择:”); fflush(stdin); scanf(“%c”,&choice); if(choice=='1') { if(head==NULL) { head=Create_Books_Doc(); } InsertDoc(head); } else if(choice=='2') { Print_Book_Doc(head); } else if(choice=='3') { search_book(head); } else if(choice=='4') { info_change(head); } else if(choice=='5') { struct books_list *s,*p; /*s为中间变量,p为遍历时使用的指针*/ char temp[20];int panduan;/*此变量用于判断是否找到了书目*/ panduan=0;p=s=head;printf(“ [请输入您要删除的书名]:”);吉林工业职业技术学院 数据结构实训 scanf(“%s”,temp);/*遍历到尾结点*/ while(p!= NULL) { if(strcmp(p->bookname,temp)==0) { panduan++; break; } p=p->next;} if(panduan==1){ for(;s->next!=p;) /*找到所需删除卡号结点的上一个结点*/ { s=s->next; } s->next=p->next;/*将后一节点地址赋值给前一节点的指针域*/ free(p); printf(“n ━━━━ 删除成功!━━━━n”);} else /*未找到相应书目*/ { printf(“ 您输入的书目不存在,请确认后输入!n”);} return; } else if(choice=='6') { printf(“n”); printf(“ ━━━━━━━━ 感谢使用图书管理系统 ━━━━━━━━n”);吉林工业职业技术学院 数据结构实训 break; } else { printf(“ ━━━━ 输入错误,请重新输入!━━━━”); break; } } } 【使用说明】本程序在turboc 2.0环境下运行,迷宫大小为20×20,需要修改迷宫大小时,可以修改程序中N值的大小。迷宫图由系统自动随机生成,每次生成的迷宫图是不同的。按enter健显示最终搜索结果。按Q健退出程序。 【运行调试】 图(3)图书管理系统主界面 吉林工业职业技术学院 数据结构实训 图(4)图书信息浏览 五、实训心得 六、参考文献 北京联合大学 实训报告 课程(项目)名称: 数据结构 学 院: 专 业: 班 级: 学 号: 姓 名: 成 绩: 2012年 6 月 21 日 数据结构实训任务一 一、任务与目的: 1、用顺序表表示两个无序集合A、B,实现集合的如下操作,求两个集合的并集、交集、差集。 2、用顺序表表示两个集合A、B(集合A、B都是有序递增的情况)实现集合的如下操作,求两个集合的并集、交集、差集。 3、用带头单链表存储结构表示两个无序集合A、B,实现集合的如下操作,求两个集合的并集、交集、差集。 4、用带头单链表存储结构表示两个集合A、B(集合A、B都是有序递增的情况),实现集合的如下操作,求两个集合的并集、交集、差集。 5、杀人游戏 N个人坐成一圈玩杀人游戏,按顺时针编号 N。从1号开始顺时针开始数到第m号就杀掉第一个人,被杀掉的人要退出游戏。 如果数到了编号的末尾,接着数开头的编号。 重复,直至杀掉一半人时,游戏结束,聪明的你能告诉我活到最后的幸存者最初的编号是多少吗? 输入数据:N、M ;输出数据:幸存者的编号 分析该程序,如果N=20,M=2,……10。聪明的你应选择的编号是多少,(提示,计算出M分别等于1到10的情况下,那些编号生存概率较大)。给出实验结果 6、作业抽查问题:有35个学生的班级,由于某种原因不能够做到全部检查作业,现在希望每次抽查10名学生,希望能够随机抽查,并能够有记忆,即希望抽查过的学生,下次抽查的概率有所减小,但避免不被抽查。设计一个算法实现该功能,给出你的解释。1.void BingSet(SqList A, SqList B,SqList &C){//求并集 int i,j;int flag=0;C.length=0;for(i=0;i if(flag==0) {C.elem[i]=B.elem[j];i++;} } C.length=i;} void JiaoSet(SqList A, SqList B,SqList &C){//求交集 int i,j;int flag=0;C.length=0;i=0;for(j=0;j if(flag!=0) {C.elem[i]=B.elem[j];i++;} } C.length=i;} void ChaSet(SqList A, SqList B,SqList &C){//求差集 int i,j,k;int flag=0;C.length=0;k=0;for(i=0;i if(flag==0) {C.elem[k]=A.elem[i];k++;} } C.length=k;} 运行结果: 2.void BingSet(SqList A, SqList B,SqList &C){//求并集 int i,j,k;k=0;C.length=0;for(i=0,j=0;(i {C.elem[k]=A.elem[i];k++;i++; } else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {C.elem[k]=B.elem[j];k++;j++;} } } if(i {C.elem[k]=A.elem[i];k++;i++; } } if(j {C.elem[k]=B.elem[j];k++;j++;} } C.length=k;} void JiaoSet(SqList A, SqList B,SqList &C){//求交集 int i,j,k;k=0;C.length=0;for(i=0,j=0;(i {i++;} else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {j++;} } } C.length=k;} void ChaSet(SqList A, SqList B,SqList &C){//求差集 int i,j,k;int flag=0;k=0;C.length=0;for(i=0,j=0;(i {C.elem[k]=A.elem[i];i++;k++; } else {if(A.elem[i]==B.elem[j]) {i++;j++;} else {j++; } } } if(i {C.elem[k]=A.elem[i];k++;i++;} } C.length=k;} void InserOrder_Sq(SqList &L,ElemType e){int i,j;for(i=0;i L.elem[j+1]=L.elem[j];L.elem[i]=e;L.length++;} 运行结果: 3.void bing(link &p,link &h,link &q) {//求并集 link l,s,m;int j=0,i=0;q=new LNode;q->date=NULL;q->next=NULL;s=p->next;m=q;while(s){l=new LNode; l->date=s->date; l->next=NULL; s=s->next; m->next=l; m=l; s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==0){l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l; } s=s->next;} } void jiao(link &p,link &h,link &q) { //求交集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q; s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==1) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l; } s=s->next;} } void cha(link &p,link &h,link &q) {//求差集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=p->next;while(s){i=s->date; j=Locate(h,i); if(j==0){l=new LNode; l->date=s->date; l->next=NULL; m->next=l;m=l;} s=s->next;} } void shengcheng(link &p,link &h,link &q) { int i,j=0;Elem e;for(i=0;i<11;){if(i==0){p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=rand()%50+1; j=Locate(p,e); if(j==0) {LInsert(p,e);i++;}}}} 运行结果: 4.void bing(link &p,link &h,link &q) { //并集 link l,s,m;int j=0,i=0;q=new LNode;q->date=NULL;q->next=NULL;s=p->next;m=q;while(s){l=new LNode; l->date=s->date; l->next=NULL; s=s->next; m->next=l; m=l;} s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==0) {LInsert(q,i);} s=s->next;} } void jiao(link &p,link &h,link &q) {//交集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==1) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l;} s=s->next;} } void cha(link &p,link &h,link &q) {//差集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=p->next;while(s){i=s->date; j=Locate(h,i); if(j==0) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l;} s=s->next;} } void shengcheng(link &p,link &h,link &q) {int i,j=0;Elem e;for(i=0;i<11;){if(i==0) {p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=rand()%50+1; j=Locate(p,e); if(j==0) {LInsert(p,e);i++;}}}} 运行结果: 5.#include struct kill { int num; struct kill *next;}; struct kill *create(int m) {struct kill *head,*p1,*p2;int i;p1=p2=(struct kill*)malloc(LEN);head=p1; head->num=1; for(i=1,p1->num=1;i p2->next=p1;p2=p1;} p2->next=head;return head;} struct kill *findout(struct kill *start,int n){int i; struct kill *p;i=n;p=start; for(i=1;i struct kill *letout(struct kill *last){struct kill *out,*next;out=last->next; last->next=out->next;next=out->next;free(out);return next;} void main() { int m,n,i,servive;struct kill *p1,*p2; cout<<“请输入参加杀人游戏总人数m:”< cout<<“要杀掉的人的序号n:”< { p1=p2=create(m);for(i=1;i p2=letout(p1);p1=p2;} servive=p2->num;free(p2);} cout<<“幸存者是:”< 6.#include //学生id int times; //定义学生抽查数};Student stu[35];//35个学生 int cho[10]; //抽查的10个学生 int top; //已抽查学生数 int choose(){int n=rand()%35;//随机抽取 for(int i=0;i int n2=rand()%stu[n].times;//否则几率按抽取的次数减小,具体为(1/抽取次数)if(n2==0)return n;else return choose();} void main(){char a='Y';srand(time(0));//随机数初始化 int i;for(i=0;i<35;i++)//学生初始化 {stu[i].id=i+1;stu[i].times=0;} while(a=='Y'||a=='y'){int tmp;top=0;for(i=0;i<10;i++)//抽取10个学生 {tmp=choose();//抽取学生 cho[top++]=tmp;stu[tmp].times++;cout<<“第”<>a;}} 运行结果: 数据结构实训任务二 一、任务与目的:主要考察的是栈与队列的逻辑结构和存储结构。 1、用栈,判断一个算数表达式中的圆括弧、方括弧和花括弧是否匹配。 2、用栈,把十进制的整数转换为二至九之间的任一进制 3、设计一个算法,检测一个字符串数组是否是回文,回文是指这个字符串是否关于中心对称。int Check(char a[],int n) 4、采用SPT规则的单机生产计划问题。问题描述如下,存在一台机器,要加工n个工件,每个工件i都有一个确定的加工时间,采用按照 递增的顺序,进行加工,计算每个工件的完成时间(初始加工时间为0)。设计一个算法,输入工件数量n,随机在[1,30]的区间内产生每个工件的加工时间。按照SPT规则进行加工,输出每个工件的完成时间。 5、采用EDD规则的单机生产计划问题。问题描述如下,存在一台机器,要加工n个工件,每个工件i都有一个确定的加工时间,同时每个工件都有一个确定的交货期,采用按照 递增的顺序,进行加工,计算每个工件的完成时间(初始加工时间为0)。设计一个算法,输入工件数量n,随机在[1,30]的区间内产生每个工件的加工时间,在区间[2,20*n]内随机产生每个工件的交货期。按照EDD规则进行加工,输出每个工件的完成时间,计算每个工件i完成时间和 的差值。1.void Ininstack(stack &s) {//初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) {//扩容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) { //入栈 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} stype Pop(stack &s) {//出栈 stype e;e=s.elem[s.top];s.top--;return e;} stype GetTop(stack s) {//取栈顶 stype e;e=s.elem[s.top ];return e;} void main(){stype e,t,ch;stack s;char a[20];int i=0,n;Ininstack(s);cout<<“请输入算术表达式(以$结尾):”;while(ch!='$'){cin>>ch; a[i]=ch;i++;} n=i;for(i=0;i {e=a[i];Push(s,e);} if(a[i]=='}'||a[i]==']'||a[i==')']) {t=GetTop(s); if(a[i]=='}' && t=='{')Pop(s); else if(a[i]==']' && t=='[') Pop(s);else if(a[i]==')' && t=='(') Pop(s);}} if(s.top==-1) cout<<“括号匹配!”< cout<<“括号不匹配!”< 2.void Ininstack(stack &s) { //初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) { //扩容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) {//入栈 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} stype Pop(stack &s) { //出栈 stype e;e=s.elem[s.top];s.top--;return e;} void main(){stack s;int a,b;Ininstack(s);cout<<“请输入任意非负十进制数:”;cin>>a;cout<<“请输入需要转换的进制数(进制数为二至九):”;cin>>b;while(a){Push(s,a%b);a=a/b;} while(!(s.top==-1))cout< 运行结果: 3.void Ininstack(stack &s) { //初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) { //扩容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) {//入栈 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} void Error(char *a) { cout< stype Pop(stack &s) { stype e;e=s.elem[s.top];s.top--;return e;} int Check(char a[],int n,stack &s) {//判断 int i;char e;Pop(s);for(i=0;i urn 0;} void main(){stack s; r ch,a[50];t i=0,n,t;instack(s);cout<<“请输入字符串(以$结尾):”;while(ch!='$'){cin>>ch;[i]=ch;ush(s,ch);+;} n=i;Check(a,n,s);if(t==1)cout<<“是回文!”< 运行结果: 4.void chushihua(sqlist &a) //初始化 {a.elem=new elemtype[SIZE]; a.num=new elemtype[SIZE]; a.welem=new elemtype[SIZE]; a.length=0; a.listsize=SIZE; a.incrementsize=INCREMENT;} void paixu(sqlist a) //排序 { int i,j,t,m;for(i=0;i 5.typedef struct {elemtype *elem; //加工时间 elemtype *num; //序号 elemtype *welem; //完成时间 elemtype *jelem; //交货期 elemtype *celem; //差值 int length; //长度 int listsize; //分配量 int incrementsize;//增补量 }sqlist;void chushihua(sqlist &a) //初始化 {a.elem=new elemtype[SIZE]; a.num=new elemtype[SIZE]; a.welem=new elemtype[SIZE]; a.celem=new elemtype[SIZE]; a.jelem=new elemtype[SIZE]; a.length=0; a.listsize=SIZE; a.incrementsize=INCREMENT;} void paixu(sqlist a) //排序 {int i,j,t,m,p;for(i=0;i a.welem[i]=a.elem[i];else {a.welem[i]=a.elem[i]+a.welem[i-1];} a.celem[i]=a.jelem[i]-a.welem[i];cout< 数据结构实训任务书三:二叉树链式存储的基本操作 1、创建二叉树 a)熟悉使用教材的先序创建二叉树的方法 b)编写一个算法,实现在已知二叉树的先序序列和中序序列的情况下创建二叉树。 c)如果已知二叉树的顺序表示形式,将其转换为二叉树的链式存储方式。 2、二叉树的遍历 a)先序、中序和后序三种形式的链式存储递归式算法 b)先序、中序和后序三种形式的链式存储非递归式算法 c)层次遍历的算法。 3、二叉树一些基本操作 a)计算二叉树的深度; b)计算二叉树的叶子节点个数 c)计算二叉树的单支节点的个数 d)计算二叉树的双支节点的个数 4、编写一个主函数能够测试你所设计的算法。 主函数调用教材创建二叉树的创建教材图7-10的二叉树链式存储方式。 {p=st.a[st.top]; st.top--; cout< data; while(p->right!=NULL) {st.top++; st.a[st.top]=p->right; q=p->right; while(q->left!=NULL) {st.top++; st.a[st.top]=q->left; q=q->left; } 代码:#include //二叉树结点的结构体表示形式 {char data;struct node* left,*right;}BTree;typedef BTree *Tree;typedef struct stackelem //栈的结构体表示形式 {BTree* a[MAXSIZE];int top;}Stack;void CreateBiTree_Rec(Tree &T)//先序创建二叉树的方法 {char ch;cin>>ch;if(ch=='#') T=NULL;else {T= new BTree; T->data=ch; CreateBiTree_Rec(T->left); CreateBiTree_Rec(T->right);}} void Preorder(Tree t)//前序遍历,递归的方法 {if(NULL!=t){cout< Preorder(t->left); Preorder(t->right);}} void Preorder2(Tree t)//前序遍历的非递归实现 {Tree p;Stack st;st.top=-1;if(NULL==t){return;} else {st.top++; st.a[st.top]=t; while(st.top!=-1) {p=st.a[st.top]; st.top--; cout< data; if(p->right!=NULL) {st.top++; st.a[st.top]=p->right;} if(p->left!=NULL) {st.top++; st.a[st.top]=p->left;} void Inorder(Tree t)//中序遍历,递归实现 {if(NULL!=t){Inorder(t->left); cout< Inorder(t->right);}} void Inorder2(Tree t)//中序遍历,非递归实现 {Tree p,q;Stack st;st.top=-1;if(NULL==t){return;} else {while(t!=NULL) {st.top++; st.a[st.top]=t; t=t->left; }}} 20 } while(st.top!=-1)break; } }}} void Postorder(Tree t)//后序遍历,递归实现 {if(t!=NULL){Postorder(t->left); Postorder(t->right); cout< {st.top++; st.a[st.top]=t; t=t->left; } m=NULL; flag=1; while(st.top!=-1 && flag) {t=st.a[st.top]; if(t->right==m) {cout< st.top--; m=t;} else {t=t->right; flag=0; }}} while(st.top!=-1);} int Height(Tree t)//求二叉树的高度,递归实现{int depth1,depth2;if(!t){ return 0;} else {depth1=Height(t->left); depth2=Height(t->right); if(depth1>depth2) {return(depth1+1); } else {return(depth2+1); }}} int leafs_rec(Tree t) //叶子结点 {int l,r;if(t==NULL) return 0;else if((t->left==NULL)&&(t->right==NULL)) return 1;else {l=leafs_rec(t->left); r=leafs_rec(t->right); return(l+r);}} int danzhi(Tree t)//单只 {if(t==NULL) return 0;else if((t->left==NULL)&&(t->right!=NULL)) d++;else if((t->left!=NULL)&&(t->right==NULL)) d++;danzhi(t->left);danzhi(t->right);return(d);} int shuangzhi(Tree t) //双只 {if(t==NULL) return 0;else if((t->left!=NULL)&&(t->right!=NULL)) l++;shuangzhi(t->left);shuangzhi(t->right);return(l);} void TraversalOfLevel(Tree t)//层次遍历二叉树 { Tree p,q[100];int f=0,r=0;if(t!=NULL) {p=t; q[r]=t; r++;} while(f!=r){p=q[f];f++; cout< data; if(p->left!=NULL) {q[r]=p->left; r++; } if(p->right!=NULL) {q[r]=p->right; r++;} }} void CreateBiTree_XZ(Tree &T,char a[],int la,int ra,char b[],int lb,int rb)//知先序、中序求二叉树 {int i,lla,lra,llb,lrb,rla,rra,rlb,rrb;if(la>ra) T=NULL;else {T=new BTree; T->data=a[la]; for(i=lb;i<=rb;i++) {if(b[i]==a[la]) break;} lla=la+1; lra=lla+i-lb-1; rla=lra+1; rra=ra;llb=lb; lrb=i-1; rlb=i+1; rrb=rb; CreateBiTree_XZ(T->left,a,lla,lra,b,llb,lrb); CreateBiTree_XZ(T->right,a,rla,rra,b,rlb,rrb);}} void CreateBiTree_SX(Tree &T,char S[],int pos,int n)//二叉树的顺序表示形式,将其转换为二叉树的链式存储方式 {int i;if(S[pos]=='#') T=NULL;else {T=new BTree; T->data=S[pos]; if((i=2*pos+1)<=n) CreateBiTree_SX(T->left,S,i,n); else T->left=NULL; if((i=2*pos+2)<=n) CreateBiTree_SX(T->right,S,i,n); else T->right=NULL;}} void main(){int n,i;char a[30],b[30],c[30];Tree s;Tree m;cout<<“请输入先序:”;CreateBiTree_Rec(m);cout< 数据结构实训任务书四:图的操作 1、建立图的存储结构 a)创建图的邻接矩阵表示方式 b)创建图的邻接表表示方式 c)实现两种方式的互换 2、图的遍历 a)基于邻接矩阵的深度和广度遍历 b)基于邻接表的深度和广度遍历 3、最小生成树,使用Prim算法实现从某一节点出发的图的最小生成树25 4、单源最短路径,算法8-10 5、关键路径算法。 1.代码: typedef enum{DG,DN,UDG,UDN}GKind;typedef enum{FALSE,TRUE}Boolean;Boolean visited[max_v];typedef int VType;typedef int EType;typedef int qtype;typedef struct { qtype *elem;int front;int rear;int qsize;int insize;}squeue;typedef struct { VType vexs[max_v];EType edges[max_v][max_v];int vnum,ednum;GKind kind;}MGraph;typedef struct ENode { int advex;struct ENode *next;int weight;}ENode;typedef struct VNode { VType vex;ENode *first;}VNode,List[max_v];typedef struct { List ver;int vnum,ednum;int kind;}AGraph;int LocatV(MGraph g,VType x){ int k;k=-1;for(k=0;(k //邻接矩阵 { int i,j,k,v1,v2,w;cout<<“请输入顶点数:”;cin>>g.vnum;cout<<“请输入边数:”;cin>>g.ednum;cout<<“请输入构造顶点数组顶点值:”< g.edges[i][j]=infinity;cout<<“请输入构造邻接矩阵:”< cin>>v1; cout<<“请输入顶点V2:”; cin>>v2; cout<<“请输入权值:”; cin>>w; i=LocatV(g,v1); j=LocatV(g,v2); while((i<0)||(i>(g.vnum-1))||(j<0)||(j>(g.vnum-1))) { cout<<“编号超出范围,请重新输入顶点及权值:”< cin>>v1; cin>>v2; cin>>w; i=LocatV(g,v1); j=LocatV(g,v2); g.edges[i][j]=w; g.edges[j][i]=g.edges[i][j];}} int LocatVA(AGraph g,VType x){ int k;k=-1;for(k=0;(k cout<<“编号超出范围,请重新输入:”< cin>>v1; cin>>v2; i=LocatVA(g,v1); j=LocatVA(g,v2);} p=new ENode;p->advex=j;p->next=g.ver[i].first;g.ver[i].first=p;}} void DFS(AGraph g,VType i){ ENode *p;VType w;visited[i]=TRUE;cout< DFS(g,w);}} void Draverse(AGraph g) //邻接表深度遍历 { int i;for(i=0;i DFS(g,i);} void MDFS(MGraph g,VType i){ VType p;visited[i]=TRUE;cout< MDFS(g,p);}} void Mraverse(MGraph g) //邻接矩阵深度遍历 { int i;for(i=0;i MDFS(g,i);} void InQueue(squeue &q) { q.elem=new qtype[SIZE];q.front=q.rear=0;q.qsize=SIZE;q.insize=IN;} void INsize(squeue &q) { qtype *a;int i;a=new qtype[q.qsize+q.insize];for(i=0;i { if(((q.rear+1)%q.qsize)==q.front)INsize(q);q.elem[q.rear]=e;q.rear=(q.rear+1)%q.qsize;} void Error(char *a) //错 { cout< { qtype e;if(q.front==q.rear)Error(“循环队列空!”);e=q.elem[q.front];q.front=(q.front+1)%q.qsize;return e;} void BFS(MGraph g) { int i,w,u;squeue q; //初始化 //扩容 //入队 //出队 //邻接矩阵广度遍历29 for(i=0;i cout< EnQueue(q,i); while(q.front!=q.rear) { u=DeQueue(q); for(w=0;w if(g.edges[u][w]&&(!visited[w])) { visited[w]=TRUE; cout< EnQueue(q,w);}}}} void MBFS(AGraph g) //邻接表广度遍历 { int i,w,u;squeue q;ENode *p;for(i=0;i EnQueue(q,i); while(q.front!=q.rear) {u=DeQueue(q); cout< p=g.ver[u].first; while(p) {w=p->advex; if(visited[w]!=TRUE) { visited[w]=TRUE; EnQueue(q,w);} p=p->next;}}}}} void MatToList(MGraph l,AGraph &g)//此函数用于实现将邻接矩阵转换成邻接表{ int i,j;ENode *p;g.vnum = l.vnum;for(i = 0;i g.ver[i].first = NULL; g.ver[i].vex=l.vexs[i];} for(i=0;i for(j = l.vnum-1;j>=0;j--) { if((l.edges[i][j]!= 0)&&(l.edges[i][j]!=100)){ p =(ENode*)malloc(sizeof(ENode)); p->advex = j; p->next= g.ver[i].first; g.ver[i].first= p;}}} void ListToMat(MGraph &g, AGraph l)//表转矩阵 { int i,j;ENode *p;g.vnum=l.vnum;g.ednum=l.ednum;for(i = 0;i g.edges[i][j] = 0;for(i=0;i while(p){g.edges[i][p->advex] = 1; p=p->next;} }} void main(){ int j=0,i;MGraph g;AGraph h;ENode *p;CreatUDN_MG(g);cout<<“n此无向图共有”< for(j=0;j cout< ”; cout< { p=h.ver[i].first; while(p!=NULL) { cout<<“<”<advex].vex<<“>”< p=p->next; } } cout< Draverse(h);cout< MatToList(g,h);cout<<“n此无向图共有”< for(j=0;j cout< ”; cout< { p=h.ver[i].first; while(p!=NULL) {cout<<“<”<advex].vex<<“>”< p=p->next;} }} 2.代码:#include struct edgeNode *link;//与之相连的端点 }; //存储节点信息 vexNode adjlist[MAX];//访问标志 bool visited[MAX];//lowcost[j]存储从开始节点到节点j的最小花费 WeiType lowcost[MAX];//parent[j]表示节点j的前驱节点 int parent[MAX];//建立邻接表存储 void createGraph(vexNode *adjlist,const int n,const int e,const int v0){ edgeNode *p1,*p2;int i,v1,v2;WeiType weight;for(i=1;i<=n;i++){ cout<<“请输入节点”<>adjlist[i].info;adjlist[i].link = NULL;//初始化 visited[i] = false;lowcost[i] = Infinity;parent[i] = v0;} for(i=1;i<=e;i++){ cout<<“请输入边”<>v1>>v2;cout<<“此边的权值:”;cin>>weight;p1 =(edgeNode*)malloc(sizeof(edgeNode));p2 =(edgeNode*)malloc(sizeof(edgeNode));p1->no = v1; p1->weight = weight;p1->info = adjlist[v1].info;p1->next = adjlist[v2].link;adjlist[v2].link = p1;p2->no = v2;p2->weight = weight;p2->info = adjlist[v2].info;p2->next = adjlist[v1].link;adjlist[v1].link = p2;}} void f(int n,int e,int v){ int i,j,k;edgeNode *p,*q;WeiType sum = 0,minCost;createGraph(adjlist,n,e,v);p = adjlist[v].link; visited[v] = true;while(p!=NULL){ lowcost[p->no] = p->weight;p = p->next;} for(i=1;i minCost = Infinity; int k; for(j=1;j<=n;j++) { if(minCost>lowcost[j]&&!visited[j]) { minCost = lowcost[j]; k = j; } } sum += minCost; visited[k] = true; q = adjlist[k].link; while(q!= NULL) { if(!visited[q->no]&&q->weight { lowcost[q->no] = q->weight; parent[q->no] = k; } q = q->next;} } cout<<“最小生成树的边集为:”< cout<<“(”< } } 7、评语 工作态度(认真、一般、较差),工作量(饱满、一般、不够),每个任务能够独立(完成、基本完成、在辅导下完成),程序运行结果(正确、基本正确、部分正确),实训报告格式(标准、一般)。创新意识(较强、一般、没有),运行所学知识解决实际问题的能力(强、一般、较差)。 优(100~90):能够熟练运用开发工具,编程解决实际问题,创意新颖,功能实现完善。 良(89~80):能够熟练运用开发工具,编程解决实际问题,有一定创新,功能实现较好。 中(79~70):能够较熟练使用开发工具,编程解决实际问题,独立完成实训,功能实现一般。 及格(69~60):能够运用开发工具,在教师辅导下完成实训,实现部分功能。 不及格(59~0):编程解决实际问题的能力差,功能实现较差。 实训成绩为: 分 教师签字: 这次课程设计的心得体会通过实习我的收获如下 1、巩固和加深了对数据结构的理解,提高综合运用本课程所学知识的能力。 2、培养了我选用参考书,查阅手册及文献资料的能力。培养独立思考,深入研究,分析问题、解决问题的能力。 3、通过实际编译系统的分析设计、编程调试,掌握应用软件的分析方法和工程设计方法。 4、通过课程设计,培养了我严肃认真的工作作风,逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难,到最后把这个做出来,付出了很多,也得到了很多,以前总以为自己对编程的地方还不行,现在,才发现只要认真做,没有什么不可能。编程时要认真仔细,出现错误要及时找出并改正,(其中对英语的要求也体现出来了,因为它说明错误的时候都是英语)遇到问题要去查相关的资料。反复的调试程序,最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议,在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议,正所谓当局者迷旁观者清,把各个注意的问题要想到;同时要形成自己的编写程序与调试程序的风格,从每个细节出发,不放过每个知识点,注意与理论的联系和理论与实践的差别。另外,要注意符号的使用,注意对字符处理,特别是对指针的使用很容易出错且调试过程是不会报错的,那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。通过近两周的学习与实践,体验了一下离开课堂的学习,也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子,在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会,正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解,让我们的理解与记忆更深刻,对不懂的知识与不清楚的东西也做了一定的了解,也形成了一定的个人做事风格。 通过这次课程设计,让我对一个程序的数据结构有更全面更进一步的认识,根据不同的需求,采用不同的数据存储方式,不一定要用栈,二叉树等高级类型,有时用基本的一维数组,只要运用得当,也能达到相同的效果,甚至更佳,就如这次的课程设计,通过用for的多重循环,舍弃多余的循环,提高了程序的运行效率。在编写这个程序的过程中,我复习了之前学的基本语法,哈弗曼树最小路径的求取,哈弗曼编码及译码的应用范围,程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中,体现出自己单独设计模具的能力以及综合运用知识的能力,体会了学以致用、突出自己劳动成果的喜悦心情,也从中发现自己平时学习的不足和薄弱环节,从而加以弥补。篇二:数据结构试验心得 数据结构课程设计心得体会(专业:计算机科学与技术 姓名:朱文 学号:2011220137) 通讯录管理系统是基于双向循环链表设计而成的信息管理系统。该系统通过对程序进行模块化,建立添加、显示、查找和删除功能的函数,各函数中运用双向循环链表存储数据。为存储通讯录信息,需定义一个结构体类型,成员包括姓名、街道、城市、邮编、国家等,并建立双向循环链表,定义该结构体类型的指针,用于指向各结点。分别建立具有添加、删除、修改、查询等功能的子函数,完成相应功能,对程序实现模块化。这其中要用到对链表的删除、插入等知识。为实现存储功能,需用到文件的相关函数 开发一个通讯录管理系统,借助计算机可以方便、快捷、灵活的管理个人的朋友及相关人员的通讯信息,了解友人相关信息,帮助与友人保持联络。所以设计一个通讯录管理系统管理各人的通讯信息是非常必要的,同时,通过用循环双向链表设计通讯录管理系统可以让我们更好的去理解循环双向链表,更好的学好数据结构这门课程。本次实验中,我们使用分工合作的方式,首先定义了函数的结构体部分,剩下的根据函数所要实现的功能进行分工合作,我实现的是通讯录中删除功能的子函数,删除信息(void delete(dnode *head))的功能是按照用户输入的姓名首先进行按姓名查询功能,查找成功,则执行删除信息的功能,查询不成功,则提示错误信息。定义结点p,输入要删除的信息的姓名,按姓名查找结点,如果找到匹配的结点p,就进行相关的删除操作,否则就是没找到要删除的数据,最后返回到主函数。 这次实验中我深刻认识到合作的重要性。例如:我所编写的按名删除功能的实现中,应用了章林霞同学所编写写的按名搜索查询功能的那部分函数,在这次实验中,我学到很多东西,加强了我的动手能力,并且培养了我的独立思考能力。我们坚持理论联系实际的思想,以实践证实理论,从实践中加深对理论知识的理解和掌握。实验是我们快速认识和掌握理论知识的一条重要途径。通过这次课程设计,我们对c语言以及数据结构有了更深刻的了解,增强了程序的编写能力,巩固了专业知识,对程序的模块化观念也又模糊逐渐变的清晰了。在程序的运行与调试过程中出现了很多错误,通过反复地复习课本上的相关知识,不停地修改与调试,我们终于完成了这段程序。在调试过程中,我们认识到了数据结构的灵活性与严谨性,同一个功能可以由不同的语句来实现,但编写程序时要特别注意细节方面的问题,因为一个小小的疏忽就能导致整个程序不能运行。我们也认识到了自己的薄弱之处,如对链表相关知识的欠缺,文件运用的不熟练,在以后的学习中我们要集中精力、端正态度,争取把知识学得更扎实、更全面。 经过这次的实验,我们整体对各个方面都得到了不少的提高,希望以后学校和系里能够开设更多类似的实验,能够让我们得到更好的锻炼。也让我们深深感受到讨论交流很重要,遇到困难时,大家一起讨论,加强我们的团队合作精神,同时通过这次的课程设计,我们对 数据结构中双向链表结构有了更深刻的理解。篇三:数据结构综合实验心得体会 心得体会: 做了一个星期的程序设计终于做完了,在这次程序设计课中,真是让我获益匪浅。对大一学习的c语言和这学期开的数据结构,并没有掌握,很多知识都不太懂,突然让自己独立完成一个程序让我手忙脚乱,起码在我认为那真的特别难,看了老师给的题目以及上网查找了一些相关的知识,简单的编了几行就告一段落了,第一天等于只完成了老师要求写的需求分析和概要设计,后来查找了关于哈希表的相关知识,了解了如何创建哈希表,如何合适的构建哈希函数,(选取合适的表长,合适的余数,使得查找时间以及平均查找长度最短)以及什么是除留余数法,和怎样用除留余数法创建哈希表,看懂了之后,我又看了处理冲突的方法,有三种线性探测再散列法法,二次探测再散列法,伪随机数序列法三种,而我所要做的是第一种线性探测再散列的方法,相较后两种要简单很多,在遇到冲突的时候地址加一,知道冲突解决。 在了解这些概念以后,我就开始着手编程序了,在遇到问题的时候请教我们班擅长的同学,慢慢把不能不会不理解的地方给弄明白了,在经过很多次调试以后,一些基本功能已经可以实现了,为了使平均查找长度越小越好,我不断尝试新的表长以及除数,在没有出现错误的基础上,将功能实现,最后,终于在周四的时候将所有的程序调试完全。这次的综合性实验使我了解到,平时对知识的积累相当重要,同时也要注重课上老师的讲解,老师在课上的延伸是课本上所没有的,这些知识对于我们对程序的编写有很大的作用,同时,编程也要求我们有足够的耐心,细细推敲。越着急可能就越无法得到我们想要的结果,遇到不会的问题要多多请教,知识是在实践与向别人请教的过程中积累的,所以问是至关重要的,只要肯下功夫很多东西都是可以完成的。篇四:数据结构实验报告及心得体会 2011~2012第一学期数据结构实验报告 班级:信管一班 学号:201051018 姓名:史孟晨 实验报告题目及要求 一、实验题目 设某班级有m(6)名学生,本学期共开设n(3)门课程,要求实现并修改如下程 序(算法)。 1.输入学生的学号、姓名和 n 门课程的成绩(输入提示和输出显示使用汉字系统),输出实验结果。(15分) 2.计算每个学生本学期 n 门课程的总分,输出总分和n门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3.按学生总分和 n 门课程成绩关键字升序排列名次,总分相同者同名次。 二、实验要求 1.修改算法。将奇偶排序算法升序改为降序。(15分)2.用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为 降序算法。(45分))3.编译、链接以上算法,按要求写出实验报告(25)。4.修改后算法的所有语句必须加下划线,没做修改语句保持按原样不动。5.用a4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义,每种排序算法数据要求均不重复。(1)实验题目:《n门课程学生成绩名次排序算法实现》;(2)实验目的:掌握各种排序算法的基本思想、实验方法和验证算法的准确性;(3)实验要求:对算法进行上机编译、链接、运行;(4)实验环境(windows xp-sp3,visual c++);(5)实验算法(给出四种排序算法修改后的全部清单);(6)实验结果(四种排序算法模拟运行后的实验结果);(7)实验体会(文字说明本实验成功或不足之处)。 三、实验源程序(算法)score.c #include stdio.h #include string.h #define m 6 #define n 3 struct student { char name[10];int number;int score[n+1]; /*score[n]为总分,score[0]-score[2]为学科成绩*/ }stu[m];void changesort(struct student a[],int n,int j){int flag=1,i;struct student temp;while(flag){ flag=0;for(i=1;i /*对所有奇数项进行一遍比较*/ if(a[i].score[j]>a[i+1].score[j]) { temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;} for(i=0;i a[i]=a[i+1]; a[i+1]=temp;flag=1;} } } void print_score(struct student a[],int n,int j){ int i,k;printf(“ 奇偶交换 成绩 %d 排序表,j+1);printf(n);printf(名 次 学 号 姓 名 分 数n);k=1;for(i=0;k printf(%4d,a[i].number);printf(%s,a[i].name); printf(%6d,a[i].score[j]);printf(n);} } main(){ int i,j,k;for(i=0;i 名:);scanf(%s,stu[i].name);printf(编 号:);scanf(%4d,&stu[i].number);printf(数据结构:);scanf(%4d,&stu[i].score[0]);printf(离散数学:);scanf(%4d,&stu[i].score[1]);printf(大学英语:);scanf(%4d,&stu[i].score[2]);} for(i=0;i { stu[i].score[n]=0;for(j=0;j 山东科技大学泰山科技学院 课程实训说明书 课程: 数据结构项目实训 题目: 院 系: 信息工程系 2014年 5月 25日 专业班级: 学 号: 学生姓名: 指导教师: 目 录 一、设计题目..........................................................3 1.1 顺序表操作.........................................................3 1.2 链表操作..........................................................3 1.3 二叉树的基本操作..................................................3 二、运行环境(软、硬件环境).......................................3 2.1 软件环境..........................................................3 2.2 硬件环境..........................................................3 三、数据结构及算法设计的思想.......................................3 3.1 顺序表设计构思.....................................................3 3.2 链表设计构思......................................................4 3.3 二叉树设计构思....................................................4 四、源代码............................................................5 5.1 顺序表源代码......................................................5 5.2 链表源代码........................................................6 5.3 二叉树源代码......................................................8 五、运行结果分析.....................................................11 6.1 顺序表运行结果...................................................11 6.2 链表运行结果.....................................................13 6.3 二叉树运行结果...................................................15 七、实习总结........................................................18 一、设计题目 1.1链表操作 1.1.1 设计目的 ? 掌握线性表的在顺序结构和链式结构实现。? 掌握线性表在顺序结构和链式结构上的基本操作。1.1.2 设计内容和要求 利用顺序表链表的插入运算建立线性链表,然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数),并能在屏幕上输出操作前后的结果。1.2二叉树的基本操作 1.2.1 设计目的 ? 掌握二叉树的概念和性质 ? 掌握任意二叉树存储结构。? 掌握任意二叉树的基本操作。 1.2.2 设计内容和要求(1)对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历,输出三种遍历的结果。(2)求二叉树高度、结点数、度为1的结点数和叶子结点数。第三篇:数据结构实训报告样本
第四篇:数据结构实训报告
第五篇:数据结构实训心得体会范文