数据结构图的遍历实验

数据结构图的遍历实验（通用8篇）

数据结构图的遍历实验 篇1

课程名：数据结构（实验名：图的遍历姓

名：班

级：学

号：时

间：

C语言版）

2014.11.15

一 实验目的与要求

1.掌握图的遍历的方法

2.利用 C 语言实现图的遍历

二 实验内容

• 将一个图存储起来

• 对该图分别进行先深和先广遍历

三 实验结果与分析

程序：

#include #include #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数

#define QUEUE_SIZE(MAX_VEX+1)//队列长度 //using namespace std;bool *visited;//访问标志数组,避免同一顶点多次访问 /****图的邻接矩阵存储结构******/ typedef struct{ char *vexs;//顶点向量

int arcs[MAX_VEX][MAX_VEX];//邻接矩阵

int vexnum,arcnum;//图的当前顶点数和弧数 }Graph;/*********队列类************/ class Queue{ public: void InitQueue(){ base=(int *)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;} void EnQueue(int e){ base[rear]=e;rear=(rear+1)%QUEUE_SIZE;} void DeQueue(int &e){ e=base[front];front=(front+1)%QUEUE_SIZE;} public: int *base;int front;int rear;};/*图G中查找元素c的位置*/ int Locate(Graph G,char c){ for(int i=0;i

G.vexs=(char *)malloc(G.vexnum*sizeof(char));//分配顶点数目

printf(“输入%d个顶点.n”,G.vexnum);for(i=0;i

printf(“输入顶点%d:”,i);scanf(“%c”,&G.vexs[i]);temp=getchar();//接收回车

} for(i=0;i

for(j=0;j

printf(“输入弧%d:”,i);scanf(“%c %c %d”,&a,&b,&w);//输入一条边依附的顶点和权值

temp=getchar();//接收回车

s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;} } /*****图G中顶点k的第一个邻接顶点***********/ int FirstVex(Graph G,int k){ if(k>=0 && k

for(int i=0;i=0 && i=0 && j

for(int k=j+1;k

visited[k]=true;printf(“%c ”,G.vexs[k]);//访问第k个顶点

for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//对k的尚未访问的邻接顶点i递归调用DFS } } /****************广度优先遍历***************/ void BFS(Graph G){ int k;Queue Q;//辅助队列Q Q.InitQueue();for(int i=0;i

visited[i]=true;printf(“%c ”,G.vexs[i]);Q.EnQueue(i);//i入列

while(Q.front!=Q.rear){ Q.DeQueue(k);//队头元素出列并置为k for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))if(!visited[w]){ //w为k的尚未访问的邻接顶点

visited[w]=true;printf(“%c ”,G.vexs[w]);Q.EnQueue(w);} } } }

/***********主函数***************/ void main(){ int i;Graph G;CreateUDN(G);visited=(bool *)malloc(G.vexnum*sizeof(bool));

printf(“n广度优先遍历: ”);for(i=0;i

数据结构图的遍历实验 篇2

二叉树是一种重要的树形结构,其结构规整。许多实际问题抽象出来的数据结构往往是二叉树的形式,而且其存储结构及运算都较为简练,因此,二叉树在数据结构课程中显得特别重要,这里我们先了解一下二叉树。

二叉树是由结点的有限集合构成,这个有限集合或者为空集,或者是由一个根节点及两棵互不相交的分别称之为这个根的左子树和右子树的二叉树组成。从定义来看,二叉树定义是一个递归定义,但由于学生对递归算法的理解存在一些误区,同时递归算法效率较低,并且在实际应用中有些问题也不允许调用递归算法,故有关二叉树的试题通常要求采用非递归算法,这就使得掌握二叉树的生成及遍历的非递归算法成为必要。

二、二叉树的生成

建立一个二叉树是指在内存中建立二叉树的存储结构,这里讨论建立一个二叉链表的方式生成一个二叉树。要建立一个二叉链表,需按照完全二叉树的层次顺序,依次输入结点信息建立二叉链表。对于一般的二叉树,必须添加一些虚结点,使其成为完全二叉树。我用@表示虚结点,#表示输入结束标志。同时设置一个队列,队列是一个指针类型的数组,保存已输入的结点的地址。根据对为指针奇偶数的判断,来决定把字符放到左孩子结点中还是右孩子结点中,这样就能生成想要的二叉树。

三、二叉树的先序、中序、后序遍历

上面虽然已经生成二叉树,但实际上用户生成的二叉树是抽象,用户并不太确信已经生成的二叉树是否是自己想要的,于是,可以编制输出程序进一步验证这个已经存在的二叉树的正确性。

二叉树的遍历就是对二叉树的每一个结点访问一次且仅访问一次。我们通过二叉树的序遍历的非递归算法来验证其正确性。二叉树非递归遍历是用显示栈来存储二叉树的结点指针。

1、先序遍历

使用一个栈,首先将根结点入栈,开始循环;从战中退出当前结点,先访问它,然后将其右结点入栈,再将其左结点入栈,如此直到栈空为止。

2、后序遍历

先将根结点的所有左结点并入栈,出栈一个结点,将该结点的右结点入栈,再将该结点的左结点入栈,当一个结点的左右子树均访问后再访问该结点,如此,直到栈空为止。

3、中序遍历

先将根结点的所有左结点并入栈,出栈一个结点,访问该结点,将该结点的右结点入栈,再将该结点的左结点入栈,当一个结点的左子树均访问后再访问该结点,最后访问右结点。如此,直到栈空为止。

四、总结

二叉树在计算机科学中有着重要的作用,现实世界中有好多问题都是用树这种数据结构描述的,而二叉树在计算机中操作和实现都非常方便,因此在二叉树的建立及其遍历是非常重要的。同时二叉树的三种遍历算法是二叉树运算的基础,大多数二叉树上的复杂运算都是建立在这三种遍历之上的。因此,要深刻理解这三种遍历算法是十分必要的。

参考文献

[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京.清华大学出版社,2007.

[2]王昆仑,李红.数据结构与算法[M].北京.中国铁道出版社,2007.

[3]李春葆.数据结构习题与解析(第2版)[M].北京.清华大学出版社,2004TP311.

《数据结构实验》教学探析 篇3

关键词：数据结构；实验；编程；教学

中图分类号：TP3-4 文献标识码：A文章编号：1007-9599 (2011) 06-0000-01

Teaching Research on Data Structure Experiment

Zhang Xiujian

(Guangzhou University Sontan Collehe,Guangzhou 511370,China)

Abstract:Data structure is a course that emphasizes that exercise of logical thinking and programming ideas.In this paper,we argue that the appropriate experimental program and integration of software engineering can improve student’s innovative ability.

Keyword:Data Structure;Experiment;Programming;Teaching

《数据结构》，是一门重要的理论学科。通过调研看出，该科目在各个院校的实验教学情况存在较大差异。学生学习理解过程缓慢，教师教学也不能得心应手，尤其是实验课，由于部分学生对编程语言掌握不熟练，实验内容抽象，而有较大畏难情绪，甚至不参加实验课。虽然曾经有些教师参考了任务驱动、实例教学等方法，但过于强调某种教法，也会影响教学效果。所以，该课程宜结合课程特点设计教学，切实通过贴近于实际的方法传道授业，结合实验落实教学效果是非常重要的。

一、数据结构课程实验教学中问题所在

（一）实验课时欠缺。有的学校压缩实验时间，让位于理论教学，这对学习效果的落实来说是本末倒置。没有足够的实验课时，学生就无法把理论知识加以系统地整理，进而在实验中消化吸收。

（二）综合性、创新性实验科目欠缺，系统性不强。开设的数据结构的实验课程中，虽然安排了相关知识点的实例，但是对设计的创新性和综合性上有待提高，要加强知识点的综合运作。

（三）没有很好地结合课堂教学和实验教学。作为一门比较抽象的理论教学课，尤其要重视课堂和实验教学相结合。实验中要突出该课程的实践性，教学中要注重理论和实践的结合。现在，不少教师只重视知识的灌输，在实验中任务不明确，要求不明晰，让学生在实验中迷失了对理论的进一步实践的方向。

二、实验教学的改革探索

（一）教学模式的改变。基于数据结构课程理论难于理解的特点，要突出实验课的效果，要注重“课堂.一章的基础性实验.综合实验”相结合的框架。注意从逻辑机构到存储结构，再到实现基本算法，继而具体应用的方法，一以贯之地落实到数据结构教学中去。算法的讲授要先分析算法，再运用编程语言演练算法，最后进一步分析算法。如能采用多媒体演示算法的步骤，会使学生更加清晰地理解。课堂教学始终要把应用的要求作为做种目标，辅以实验训练，加强学生动手编程和自我创新的能力。

（二）基础实验环节要重视。实验环节要让学生进一步理解数据结构的特点，明确相关概念，熟练各种基本算法的实现。枯燥的理论讲述的再多，也不如配合实验让学生一练，所以教学要重视基础实验环节。要想获得扎实的教学效果，教师要提供实验编程语言，Turbo C、Visual C++、Delphi等都可以。根据教材确定实验方案，明确实验目的、内容、要点和必备注意事项，最后安排几个演练题目，比如矩阵的遍历、数据的折半查找等。实验课程要贴近学生的编程水平，不可偏离太过。实验中，学生有章可循，对要点有较强的针对性，实验效率就会大大提高，使学生真正能举一反三。

（三）课程实验要理论应用相结合。实验要注意结合原理和应用，让学生在解决实际问题时学会调用学过的知识点，养成动手练习语言编程的习惯，所以，这个层面的综合实验要求要高于普通的课下练习和基础实验，更贴近于应用。平时虽然侧重练习简单的算法程序，但综合实验课是软件设计的高级训练阶段，融合了问题的分析，系统结构设计、操作界面设计、编程技能技巧，是软件设计的系统工程。教师分阶段拟定数据机构在实践中的各种应用，比如：汉诺塔问题、约涩夫环问题、Huffman Coding方式、班级信息管理系统等，把任务分配给学生，让学生组织课题公关。课题的结题要提供课题表述、基本要求、实验数据、实现结果和关键实现步骤等内容，这能协助学生破题解题，以免形成错误的认识，同时也讲解了程序设计的基本路线，确保实验目标的实现。最后每个课题组都集中展示实验过程接结果。试试证明，这样的实验环节，综合了数据结构知识、编程语言技能和软件工程思想，让学生系统地理解各门课程的联系，融合相关专业课的精髓，锻炼了学生的团队合作互助精神，提高了组织能力和管理水平

三、重点组织好教学实验的各个环节

（一）实验题目的设计。鉴于实验环节教学时间的限制，学生的编程基础和技能较为薄弱，所以，设计和拟定合适的实验题目尤为重要。实践题目应该由易到难循序渐进：

1.常用算法练习。主要讲解各章节知识点，深入贯彻算法理论的理解；2.基础性应用练习。主要让学生针对单一的数据结构解决应用难题，其难度中等；3.综合应用题目练习。要涵盖多个章节的内容，系统性强，难度较高，可以组织学生成立课题组，在课外实验环节共同研讨解决，再集中展示。课题的设计要注意：（1）常用算法的练习要有一定代表性，重点练习各个章节的知识点，难度较小，目的在于理论知识的掌握。课堂教学要和实验环节对应，学生在试验中重点演练课上讲授的内容。（2）基础性应用练习难度要适中，既要带动基础薄弱的学生，又要注意发挥基础好的学生的能动性，可以加以延伸，或是鼓励提供多种解决方法，进行不同思路的性能的比较，让各个层面的学生都能参与实验。（3）综合应用练习题不宜太难，但要引起学生的兴趣，宜于结合实际中的事物或应用系统，让学生宜于接受和理解，这样才能促进学生的积极性。

（二）实验环境的搭建。现在很多学校选取谭浩强教授出版的《数据结构（c语言版）》作为教材，应用C语言进行数据结构的设计语言，用TC搭建实验环境。而在实际教学中，应用C语言讲解数据结构常常对算法设计和实现上较为突出，对数据结构的系统性容易忽视。如果用C++进行数据结构的实验练习，可以注重其整体性和系统性，先定义数据结构的类，再分析其逻辑特性，然后把存储结构延伸到算法的实现中去，能帮助学生构建数据机构的概念。

（三）实验过程的组织与实施。实验中可以采取学生分组、一人负责的机制进行实验。提倡互动探讨和交流，既能让学生接触更多的实验题目，也能提高学生的团队合作精神。

（四）实验结果的检验和考核。对实验结果，教师要辅以必备的检查来进行督导。对于实验报告的书面汇报，要设计题目、要求、步骤、结构、程序代码和改进方法，以及最后的体会等。教师通过实验报告书可以详细了解学生的实验情况，进而发现共性的问题集中解决。

（五）实验问题的总结与弥补。通过实验，教师对于学生学习中存在的问题要进行系统总结和分析加以更正，有些不良的编程习惯，教师要着重强调。

四、结束语

《数据结构》的实验课注重学生动手能力的培养，强调创新思维的养成，通过实验，结合应用案例，能够进一步提高该课程的教学质量，加深学生对知识点的理解，具有积极的现实意义。

参考文献：

[1]程满玲.数据结构课程教学模式改革的探索与研究[J].武汉商业服务学院学报,2007,3

数据结构实验报告 篇4

一、实验目的

1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。

2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。

3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实验要求及内容

要求编写的程序所能实现的功能包括：

1、从键盘输入要排序的一组元素的总个数

2、从键盘依次输入要排序的元素值

3、对输入的元素进行快速排序

4、对输入的元素进行折半插入排序

三、实验代码及相关注释

#include using namespace std;#include “malloc.h”

typedef struct { int key;}RedType;

typedef struct { RedType r[100];int length;}SqList;

//1 快速排序的结构体

typedef struct {

int data[100];

int last;}Sequenlist;//2 折半插入排序的结构体

int Partition(SqList &L, int low, int high)

//1 寻找基准

{

L.r[0]=L.r[low];//子表的第一个记录作基准对象

int pivotkey = L.r[low].key;//基准对象关键字 while(low

while(low= pivotkey)--high;

L.r[low] = L.r[high];//小于基准对象的移到区间的左侧

while(low

L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 }

L.r[low] = L.r[0];return low;}

void QuickSort(SqList &L, int low, int high)

//1 快速排序 { //在序列low-high中递归地进行快速排序

if(low < high)

{

int pivotloc= Partition(L, low, high);

//寻找基准

QuickSort(L, low, pivotloc-1);//对左序列同样递归处理

QuickSort(L, pivotloc+1, high);//对右序列同样递归处理

} }

Sequenlist *Sqlset()

//2 输入要折半插入排序的一组元素

{

Sequenlist *L;

int i;

L=(Sequenlist *)malloc(sizeof(Sequenlist));

L->last=0;

cout<<“请输入要排序的所有元素的总个数：”;

cin>>i;

cout<

cout<<“请依次输入所有元素的值：”;

if(i>0)

{

for(L->last=1;L->last<=i;L->last++)

cin>>L->data[L->last];

L->last--;

}

return(L);}

middlesort(Sequenlist *L)

//2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){

L->data[0]=L->data[i];

low=1;

high=i-1;

while(low<=high)

{

mid=(low+high)/2;

if(L->data[0]data[mid])

high=mid-1;//插入点在前半区

else

low=mid+1;//插入点在后半区

}

for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移

L->data[high+1]=L->data[0];//插入 } return 0;}

int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout<

if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout<

cin>>L.r[i].key;

} cout<

QuickSort(L,1,L.length);

for(int j=1;j<=L.length;j++)

{

cout<

}

cout<

cout<

}

if(m==2){

Sequenlist *L;

int i;

L=Sqlset();

cout<

middlesort(L);

cout<<“折半插入排序后为：”;

for(i=1;i<=L->last;i++)

{

cout<data[i]<<“ ”;

}

cout<

cout<

goto gg;}

if(m==3){

exit(0);

cout<

四、重要函数功能说明

1、Sequenlist *Sqlset()

输入要折半插入排序的一组元素

2、int Partition(SqList &L, int low, int high)

寻找快速排序的基准

3、void QuickSort(SqList &L, int low, int high)

快速排序

4、middlesort(Sequenlist *L)

折半插入排序

五、程序运行结果

下图仅为分别排序一次，可多次排序，后面有相关截图：

六、实验中遇到的问题、解决及体会

1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。

运行程序错误截图：

2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。

修改程序前两个运行结果截图

（两个程序，调试运行两次，每次只能进行一次排序）

1、快速排序程序运行结果截图：

2、折半插入排序程序结果截图：

程序重要模块修改截图：

修改程序后运行截图：

数据结构查找实验报告 篇5

//文件名:exp9-1.cpp #include #define MAXL 100 typedef int KeyType;typedef char InfoType[10];typedef struct {

KeyType key;

//KeyType为关键字的数据类型 //其他数据

//定义表中最多记录个数

InfoType data;

} NodeType;typedef NodeType SeqList[MAXL];

//顺序表类型

int SeqSearch(SeqList R,int n,KeyType k)//顺序查找算法

{

int i=0;

while(i

{

} printf(“%d ”,R[i].key);i++;

//从表头往后找

if(i>=n)return-1;

else

} void main(){ SeqList R;{

} printf(“%d”,R[i].key);return i;

} int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i

//建立顺序表

printf(“关键字序列:”);for(i=0;i

截图如下：

实验题9.2 设计一个程序exp9-2.cpp，输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找关键字9的过程。

程序如下：

//文件名:exp9-2.cpp #include #define MAXL 100 typedef int KeyType;typedef char InfoType[10];typedef struct {

//定义表中最多记录个数 KeyType key;

//KeyType为关键字的数据类型

InfoType data;

//其他数据 } NodeType;typedef NodeType SeqList[MAXL];

//顺序表类型

int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high)

{

mid=(low+high)/2;printf(“ 第%d

次

比

较

:在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key);

if(R[mid].key==k)

//查找成功返回

return mid;

if(R[mid].key>k)

//继续在R[low..mid-1]中查找

high=mid-1;

else

low=mid+1;

//继续在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i

//建立顺序表

R[i].key=a[i];printf(“关键字序列:”);for(i=0;i

比

较

元

素

中

} else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k);

截图如下：

实验题9.3 设计一个程序exp9-3.cpp，输出在顺序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找（每块的块长为5，共5块）关键字46的过程。

程序如下：

//文件名:exp9-3.cpp #include #define MAXL 100 #define MAXI 20 typedef int KeyType;typedef char InfoType[10];typedef struct {

KeyType key;

//KeyType为关键字的数据类型

//定义表中最多记录个数

//定义索引表的最大长度

InfoType data;

//其他数据 } NodeType;typedef NodeType SeqList[MAXL];typedef struct {

KeyType key;int link;

//KeyType为关键字的类型 //指向分块的起始下标

//顺序表类型

} IdxType;typedef IdxType IDX[MAXI];

//索引表类型

int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分块查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m;

//b为每块的记录个数

printf(“二分查找n”);while(low<=high)

//在索引表中进行二分查找,找到的位置存放在low中

{

mid=(low+high)/2;printf(“ 第%d

次

比

较

:在[%d,%d]

中

比

较

元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key);

if(I[mid].key>=k)

high=mid-1;

else

low=mid+1;

count1++;

//累计在索引表中的比较次数

} if(low

//在索引表中查找成功后,再在线性表中进行顺序查找

{

printf(“比较%d次,在第%d块中查找元素%dn”,count1,low,k);

i=I[low].link;

printf(“顺序查找:n

”);

while(i<=I[low].link+b-1 && R[i].key!=k)

{

i++;count2++;

printf(“%d ”,R[i].key);} //count2累计在顺序表对应块中的比较次数

printf(“n”);

printf(“比较%d次,在顺序表中查找元素%dn”,count2,k);

if(i<=I[low].link+b-1)

return i;

else

return-1;}

素 } return-1;void main(){

} SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i];

//建立顺序表

I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”);

数据结构图的遍历实验 篇6

关键词：数据结构与算法,实验教学,改革

数据结构与算法是计算机专业的核心基础课程之一, 通过本门课程的学习, 可以使学生透彻地理解各种数据对象的特点, 学会数据的组织方法和实现方法, 并进一步培养良好的程序设计能力, 而该课程的实验课是学生验证、掌握和应用数据结构理论的重要途径。

一、数据结构与算法上机实验课程的现状

数据结构与算法课程涉及大量数据类型及算法, 理论性很强, 抽象难懂, 对学生的学习造成了一定的难度。受传统的教学模式的影响, 课程的实验教学一直处于从属地位, 同时因学生基本程序设计能力有待提高等因素影响, 实验效果不甚理想。如何使学生理论学习和实践学习相结合, 提高学生的实践能力, 已成为高等院校培养应用型本科人才的一项重要课题。

目前在数据结构与算法实验教学过程中发现的问题主要有以下几点:

1.学生对于上机实验的重要性认识不够。对于学生来说, 由于部分院校的教学资源所限, 数据结构与算法课程长期以来都是课堂和实验分开进行, 授课教师对于上机实验过程几乎不参与, 这就导致了学生重视课堂理论的讲授, 而忽视上机实验课程的重要性。

2.课程实验缺乏层次性。上机实验教学内容大多为简单的验证性实验, 缺乏综合性、应用型、设计性实验项目。增加论述。

3.课程理论性强、难度大。数据结构与算法课程理论性极强, 抽象难懂, 很多学生在课堂听课过程中不能够完全理解, 无法建立起数据结构和相应算法的概念, 长此以往导致学生对于这门课程的畏惧和抵触情绪, 同时也严重打击了学生上机实验的积极性。

4.学生对掌握程序语言的程度不够。学生对程序设计语言掌握得不理想, 也是导致学生上机实验缺乏积极性的一个重要原因。数据结构与算法是学生在学过一门或几门语言课程之后开设的, 其算法大都由C或C++语言描述, 要求学生能够使用某种程序设计语言对算法进行程序设计, 并且上机调试通过。以我学院为例, 学生在学习数据结构时, 虽然已经学过C语言, 但仅是初学, 并不精通。因此对于抽象的数据类型、动态分配存储空间等概念, 在理解上还是有一定困难的。由于对程序设计语言掌握得不好, 大部分学生在编程的过程中陷入迷茫的状态, 阻碍了他们对各类数据结构和算法等知识点的理解和应用, 使教学目标难以实现。

二、实验教学的改革和探索

(一) 实验教学内容的改革

数据结构与算法课程主要使学生掌握程序数据的结构、组织和管理技术以及在此基础上的算法设计与分析技术, 不仅为后续课程操作系统、编译原理、数据库原理、软件工程、人工智能等课程提供必要的知识准备, 更重要的是可以提高学生软件分析、设计、编程和数据组织的能力。根据数据结构与算法整个课程体系的划分, 本课程的上机实验主要分为以下几种类型:

1. 验证性实验。

这一类型的实验主要在上机实验课中完成。以西安交通大学城市学院为例, 本门课程有8个学时的上机实验, 主要任务是将课堂上讲过的内容以实验的形式贯穿起来, 所涉及的实验以教材中提及到的基本算法和例题为主, 基本都是验证性的实验。以单链表为例, 要求学生通过定义线性表的抽象数据类型, 在链式存储结构下完成单链表的建立、插入、删除、查找、求前驱节点和求后继节点等操作, 通过实验教学, 在加深学生对数据结构课程内容理解的同时, 达到理论联系实际的目的。

学生通过完成此类实验, 一方面可以强化基础知识, 另一方面也可以通过编写算法掌握高级语言程序, 同时还可以训练学生良好的编程风格、基本实验技能和科学严谨的实验作风。

2. 综合性实验。

综合性实验部分实在课程设计阶段来完成。主要任务是考查学生运用所学基本数据结构解决实际问题的能力。所设计的实验项目可以是课程设计指导书中提供的参考题目, 也可以是工程中的实际课题, 选题要与所学阶段性知识紧密联系, 任务有一定的难度和综合性, 对学生的编程思路和方法有启发作用的项目。例如:学习了栈和队列知识后可以要求学生设计一个停车场管理系统, 以栈模拟停车场, 以队列模拟车场外的便道, 按照从终端读入的输入数据序列进行模拟管理。又如:学习了图的路径的相关算法后, 可利用学生熟悉的当地交通情况、旅游景点等设计问路系统。这些问题与课本理论知识联系密切, 而且具有一定的实用价值。

3. 研究性实验。

此类实验是针对于学有余力的学生, 可安排一些研究性实验, 针对计算机专业学生的特点, 可以以软件开发的形式进行, 让学生以创新者的角色去做实验。所设计的实验项目都是实际工程中的课题, 题目的解法要求符合工程实际情况, 具有可行性。学生可以自己提出实验题目和开发工具, 自己设计实验过程等, 有条件者还可以进入工程实践中进一步提升实践能力。

(二) 实验教学方法的改革

根据我院学生的特点和学院培养应用性本科人才教育宗旨, 我们在实验教学的方法上进行了改革。

1. 先简后难, 循序渐进。

在上机实验课中, 主要以验证性试验为主, 针对堂课讲授的知识安排配套的练习。练习的内容以编写的数据结构与算法实验指导书的形式发给学生, 每节课明确实验任务、实验方法和结果要求, 使学生在有限的课堂时间中完成相应训练目标, 掌握基础知识, 夯实基础;在课程完成之后的课程设计阶段, 加大难度, 主要以综合性的题目为主, 对于程度特别好的学生也可以完成研究性的项目。针对这一阶段的训练, 我们也编写了相应的课程设计指导书, 提供给学生适合的参考题目和编程提示。有助于学生更好的完成项目要求。通过一系列的训练, 培养学生算法设计能力以及创造性思维, 以达到提高学生应用知识解决复杂问题能力的目标。

2. 启发式教学和分组实验。

在教学方法上, 把传统教法中老师讲, 学生听的“灌输法”转化为“启发式”的教学方法, 引导学生自主思考, 常常提问“WWW”, 即“What, Hao, Why”:这个问题做什么的?需要用的哪方面的知识?怎么去解决问题?如何解决?教师教给学生提出问题、分析问题和解决问题的方法, 学生自行探究问题和解决问题, 激发学生探求知识的欲望和积极的学习兴趣。

在训练的形式上, 改变传统的“集体化”路线, 根据程度的不同将2~4名学生分成多个小组, 任命一名学习能力强、组织能力好的学生担任项目组长, 以软件开发小组的形式协同工作, 合理分工, 共同学习, 通过团队讨论解决问题。各小组成员不仅要完成自己的工作, 还要与其他成员合作, 共同完成整个项目。教师应多给予学生鼓励, 激发学生的思维, 促进他们合作的欲望和热情, 使课堂活泼积极, 并且适时的提供必要的启发式帮助, 只提供意见, 不具体替学生完成。让学生从解决问题和团队合作中获得成就感和自我认同感, 在轻松的氛围中达到激发学生兴趣, 提高学生综合实践能力的目标。

(三) 项目答辩和实验报告结合的考核方法。

1. 项目答辩。

在课程设计实验结束时, 专门抽出时间对个小组成员的工作进行考核, 要求每个小组选派2名学生进行答辩, 在规定时间内陈述小组工作情况, 遇到的问题及解决的办法, 最终达到的效果及心得体会等。根据答辩情况, 给予优、良、中、差和不及格五档评分。通过这种团队合作和答辩的方式大大提升了学生的实践能力、组织和口头表达能力及合作精神。

2. 实验报告的规范。

课程设计实验结束后要求学生写出实验报告, 以作为实验环节评分的书面依据之一和存档材料。实验报告以规定格式的电子文档书写、打印并装订, 排版及图、表要清楚、工整。每个小组每个题目提交一份实验报告, 实验报告除介绍本小组成员所做工作外还应包括以下内容:

(1) 需求分析。以规范的技术文档语言陈述说明项目设计的任务并明确规定: (1) 输入的形式和输入值的范围; (2) 输出的形式; (3) 程序所能达到的功能; (4) 测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。

(2) 概要设计。说明本程序中用到的所有抽象数据类型的定义、主控程序的流程以及各程序模块之间的层次关系。

(3) 详细设计。本阶段的主要任务是实现概要设计中定义的所有数据类型, 对各操作、主程序和其他模块均要求写出伪码算法, 同时可以使用流程图或者N———S图进行描述, 画出函数和过程的调用关系图。

(4) 调试分析。在程序的调试过程中出现的问题以及解决办法, 回顾和讨论设计与实现过程中的相关问题。

(5) 测试结果。列出完整和严格的测试数据, 包括输入和输出。

(6) 用户使用说明。说明程序的使用方法, 并列出每一步的具体操作步骤。

(7) 代码注释。算法必须给出完整、正确的文字注释。

三、改革的效果

通过数据结构与算法实验教学的改革, 学生的学习热情和积极性得到了明显的提高, 学生的主动思考和积极实践的热情得以激发。学生能够在实验期间主动积极的参与并解决问题, 提高了学生的实践能力和编程能力。通过分组合作的方式进行项目训练, 培养了学生的团队合作意识和严谨的工作作风。通过小组答辩, 教师了解了每组学生的学习情况, 把握学生的学习状态和程度, 有助于在日后的教学中给予适当的指导。教师在此过程中不断总结问题, 积累经验, 使教学质量得到显著提高。

四、结束语

数据结构与算法在计算机课程体系中占据重要地位, 其实验环节的教学质量直接关系到本门课程的学习效果。在实验教学过程中必须以培养学生的综合实践能力为宗旨, 不断改进教学方法, 加大实验教学力度, 做到夯实基础, 提高能力, 为学生后续专业课程的学习打下良好的基础。

参考文献

[1]耿国华.数据结构——C语言描述[M].北京:高等教育出版社, 2006.

[2]赵玉霞.《数据结构》课程上机实验改革初探[J].福建电脑, 2007, (4) :213-214.

[3]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1997.

[4]宁正元, 王秀丽, 林大辉.与数据结构[M].北京:清华大学出版社, 2006.

二叉树的遍历研究及还原研究 篇7

关键词：二叉树;二叉树的遍历;二叉排序树;还原

中图分类号：G42文献标识码：A文章编号：16723198（2007）11022101

二叉树是最为常用的数据结构，它的实际应用非常广泛。二叉树的遍历方式有三种，前序遍历、中序遍历、后序遍历。先序遍历的顺序为：NLR，即先根结点，然后左子树、右子树；中序遍历顺序为：LNR先左子树，然后根结点、右子树；后序遍历顺序为：LRN先左子树、然后右子树、根结点。由前序和中序遍历、由中序和后序遍历序列可以唯一确定一棵二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树。

二叉排序树对二叉树作了进一步的限定：根结点的权值大于（或小于）左子树中所有结点的权值；根结点的权值小于（或大于）其右子树中所有结点的权值。

那么如何根据三种遍历序列之间的关系及二叉排序树来快速还原一棵二叉树？下面以二叉树的前序和中序遍历序列为基础，利用二叉排序树的性质，给出快速还原二叉树的方法。

1由给定前序和中序序列或中序和后序序列还原二叉树的方法

例：前序序列：ABDECFGH中序序列：DEBACGFH（后序序列：EDBGHFCA）

（1）给中序序列中的每个结点从小到大、从左到右赋以权值，如下：

D（1）E（2）B（3）A（4）C（5）G（6）F（7）H（8）

（2）还原时读入的序列为前序序列，从左到右依次读入序列中的各个结点值和相应的权值； 

（3）由读入的序列，根据第1）步中给定的权值按照二叉排序树的构造规则构造二叉排序树。第一个读入的结点为根结点，其他结点分别为左右子树中的结点。设根结点为TT，权值为NN，当前读入结点为SS，权值为MM，若MM

（4）将SS插入到TT的左子树或右子树的过程中，仍然遵循3）中的规则，直至左子树或右子树为空时止。

（5）读入序列结束时，二叉树还原成功。还原后的二叉树如下图。

（6）对于由中序序列和后序序列还原二叉树是，读入的序列为后序序列，从右向左读入，构造规则同上。还原结果与上述结果完全一致。

2还原方法的确定依据

二叉树遍历过程中，在中序序列中，根结点的左子树中的所有结点都在根结点的左侧，根结点的右子树中的所有结点都在根结点的右侧，这个特点恰好与二叉排序树具有相同的性质；在读入序列时，前序序列则从左向右读，这恰好与遍历二叉树的顺序相同；后序序列从右向左读，则按照根结点、右子树、左子树的顺序还原。

（1）设二叉树共有N个结点（N为大于1的正整数），我们按照还原方法给中序序列中的这N个结点分别赋予权值1,2…N，设根结点的权值为M（1

（2）由二叉树的遍历规则可知，权值为1,2…M-1的结点为根结点的左子树中的结点，而权值为M+1,…N的结点为根结点的右子树中的结点。

（3）将这N个结点划分成3个子集AA＝（1,2…M-1）BB＝（M）CC＝（M+1,…N），由于前序序列第一个读入的结点必定为二叉根的根结点，所以BB为根结点，AA集为左子树，CC集为右子树。

（4）同理不断读入前序序列中的结点，依次递归还原BB对应的左子树和CC对应的右子树，最后将三棵子树合并成以BB为根结点、AA的根结点为BB的左子树、CC的根结点为BB的右子树的一棵二叉排序树。

（5）同理可以得出，由中序序列和后序序还原二叉树的规则也成立。

（6）在还原过程中，读入序列的顺序也遵循也先根结点，后子树的规律。

3总结

在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。

参考文献

数据结构实验指导书 篇8

实验规则················································2 实验环境················································2 实验报告要求············································3 实验一 单链表

（一）······································4 实验二 单链表

（二）······································5 实验三 栈···············································6 实验四 二叉树···········································7 实验五 最短路径·········································8 实验六 内部排序·········································9

实 验 规 则

为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则：

1、实验前必须充分预习，完成指定的预习任务。预习要求如下：

（1）认真阅读指导书，进行必要的设计与计算。（2）熟悉实验内容。

（3）预先复习，并按要求编写程序。（4）未完成预习任务者不得进入实验室。

2、遵守以下纪律：

（1）在实验室不得做和实验无关的事情。

（2）进行任课老师指定内容以外的实验，必须经指导教师同意。（3）遵守纪律，不迟到。

（4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。

实 验 环 境

本实验在386以上的微机上进行，运行环境为VC6.0。

实验报告要求

1、实验题目 2．实验目的 3．实验环境

4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案 6．实验思考：（学生对本次实验的收获的总结）

实验一 单链表

（一）一、实验目的

掌握线性表的链式存储结构及其基本操作。

二、预习要求

1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。

2、根据要求，编写程序准备上机调试。

三、实验内容

实现一个简单的学生信息管理系统，该系统的功能有：

1、利用单链表建立学生基本信息表

2、浏览每个学生的信息

3、根据学号查询某个学生的基本信息

4、添加学生信息到单链表中

5、删除一个学生的信息

四、实现提示

设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。

实验二 单链表

（二）一、实验目的

掌握线性表的链式存储结构及其基本操作。

二、预习要求

1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。

2、根据要求，编写程序准备上机调试。

三、实验内容

1、实现单链表的就地逆置。

2、建立两个非递减有序单链表，然后合并成一个非递减链表。

3、建立两个非递减有序单链表，然后合并成一个非递增链表。

4、编写一个主函数,调试上述算法。

四、选做题、思考题

1、如何用带表头结点的单链表作为多项式的存储表示，实现两个多项式的相加。

2、约毖夫环的实现。

3、如何利用文件实现学生信息的存取。

实验三 栈

一、实验目的

深入了解并掌握栈的特性及其在实际中的应用；熟练掌握栈的算法实现；运用栈操作求解实际问题。

二、预习要求

1、看懂书上的算法，深入理解栈的特性和存储结构，以便在实际问题背景下灵活运用。

2、根据要求，编写程序准备上机调试。

三、实验内容

利用栈实现数据的分类，要求当输入为偶数时进栈1，当输入为奇数时进栈2，最后分别从栈1和栈2输出偶数和奇数序列。

四、实现提示

1、开辟一个连续的存储空间，实现两个栈顺序存储空间的共享；分别在两端设置栈顶指针，并按要求实现栈操作。

2、采用顺序存储实现栈的初始化、入栈、出栈操作。

五、选做题、思考题

1、两栈空间共享时，栈满的条件是什么？

2、为停车场编制进行管理的模拟程序（习题集P96，2.1）。

3、编写程序，利用栈实现表达式求值。

实验四 二叉树

一、实验目的

通过实践掌握二叉树的存储结构和遍历思想；掌握二叉树的常见算法的程序实现。

二、预习要求

二叉树的三种遍历方法。

三、实验内容

1、输入字符序列，建立二叉链表。

2、利用栈，编写非递归算法，编程实现二叉树的中序遍历。

3、求二叉树的叶子结点个数。

4、在主函数中设计一个简单的菜单，分别调试上述算法。

四、选做题、思考题

1、如何实现二叉树的后序遍历（非递归）。

2、如何求二叉树的高度。

实验五 最短路径（旅游景点导游咨询模拟）

一、实验目的

利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。

二、预习要求

学习了解图的存储结构，掌握求最短路径的两种算法。

三、实验内容

设计一个旅游景点导游模拟程序，为来访的客人提供景点最短路径的信息查询服务，任意选取n城市，构成一个有向带权图，图中顶点表示城市，边上的权值表示两点间的距离，根据用户指定的始点和终点输出相应的最短路径。

四、实现提示

咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的城市。存储结构可选用邻接矩阵。

五、选做题、思考题

1．如何实现对城市信息进行编辑（如：添加或删除）的功能。

2．用邻接表作存储结构，求一指定景点出发，到其余各景点的最短路径。

实验六 内部排序

一、实验目的

直观感受算法的关键字比较次数和关键字移动次数。

二、预习要求

1、常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。

2、根据要求，编写程序准备上机调试。

三、实验内容

1、对直接插入排序和简单选择排序算法进行关键字比较次数和关键字移动次数的比较。

2、利用链式存储结构，编写程序，实现直接插入排序和冒泡排序。

四、实现提示

测试数据可以为几组典型的数据：正序、逆序、乱序。

五、选做题、思考题

1、快速排序算法的非递归实现。

2、结合实验，理解针对不同待排元素的特点而选择不同排序方法的重要性。