云南大学数据结构实验

第一篇：云南大学数据结构实验

数据结构实验报告

注意：实验结束后提交一份实验报告电子文档

电子文档命名为“学号+姓名”，如：E01214058宋思怡

《数据结构》实验报告

(一)

学号：姓名：专业年级：

实验名称：线性表

实验日期：2014年4月14日

实验目的：

1、熟悉线性表的定义及其顺序和链式存储结构;

2、熟练掌握线性表在顺序存储结构上实现基本操作的方法;

3、熟练掌握在各种链表结构中实现线性表基本操作的方法;

4、掌握用 C/C++语言调试程序的基本方法。

实验内容：

一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能：

(1)初始化顺序表L;

(2)依次在L尾部插入元素-1,21,13,24,8;

(3)输出顺序表L;

(4)输出顺序表L长度;

(5)判断顺序表L是否为空;

(6)输出顺序表L的第3个元素;

(7)输出元素24的位置;

(8)在L的第4个元素前插入元素0;

(9)输出顺序表L;

(10)删除L的第5个元素;

(11)输出顺序表L。

源代码

调试分析(给出运行结果界面)

二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：

„„„„

„„„„

小结或讨论:

(1)实验中遇到的问题和解决方法

(2)实验中没有解决的问题

(3)体会和提高

第二篇：数据结构实验报告

第一次实验

学号：20141060106

姓名：叶佳伟

一、实验目的

1、复习变量、数据类型、语句、函数;

2、掌握函数的参数和值;

3、了解递归。

二、实验内容

1、(必做题)采用函数统计学生成绩：输入学生的成绩，计算并输出这些学生的最低分、最高分、平均分。

2、(必做题)采用递归和非递归方法计算k阶裴波那契序列的第n项的值，序列定义如下： f0=0, f1=0, …, fk-2=0, fk-1=1, fn= fn-1+fn-2+…+fn-k(n>=k) 要求：输入k(1<=k<=5)和n(0<=n<=30)，输出fn。

3、(选做题)采用递归和非递归方法求解汉诺塔问题，问题描述如下：

有三根柱子A、B、C，在柱子A上从下向上有n个从大到小的圆盘，在柱子B和C上没有圆盘，现需将柱子A上的所有圆盘移到柱子C上，可以借助柱子B，要求每次只能移动一个圆盘，每根柱子上的圆盘只能大的在下，小的在上。 要求：输入n，输出移动步骤。

三、算法描述

(采用自然语言描述)

1.先输入各个成绩，然后再逐一比较，筛选出最低分和最高分。在筛选的过程中使用累加把各个人的总成绩算出来，最后再除以总人数。 2.

四、详细设计

(画出程序流程图) 1.

五、程序代码

(给出必要注释) 1.#include float ave(int score[],int k) {int i;float s=0.0,ave; for(i=0;i

1 } int max(int score[],int k) {int i,max; max=score[0]; for(i=0;imax) max=score[i]; return max; } int min(int score[],int k) {int i,min; min=score[0]; for(i=0;i

2.#include int f(int n) {int k; if(n

2 else return (2*f(n-1)-f(n-k-1)); } void main() {int k,n,fn=0; printf("请输入k和n的值:[k(1<=k<=5)n(0<=n<=30)] "); scanf("%d",&k); scanf("%d",&n); while(k==1) {printf("f%d=1 ",n); break;} while(k>1) {fn=(n); printf("f%d=%d ",n,fn); break;} } 2.2 #include

六、测试和结果

(给出测试用例以及测试结果)

1.

2.

七、用户手册

(告诉用户如何使用程序) 1.使用Micrcosoft Visual C++。 2.使用Micrcosoft Visual C++。

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

}

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、折半插入排序程序结果截图：

程序重要模块修改截图：

修改程序后运行截图：

(一个程序，调试运行一次，可多次进行不同序列的不同排序)

第四篇：数据结构实验教案

第一次实验 线性表

(一)实验目的和要求：

1. 熟悉VC集成环境

2. 会定义线性表的顺序结构和链式结构

3. 熟悉对线性表的基本操作，如插入、删除等

(二)实验内容和原理或涉及的知识点(综合性实验)：

自己编写程序实现线性表的建立、插入、删除等功能。

写出线性表、顺序表、链表的定义，简单写出主要算法的思路。

(三)实验条件：安装有VC的计算机

(四)实验设计方案

设计的顺序表算法有： 1. 初始化顺序表 2. 顺序表的插入操作 3. 顺序表的删除操作 设计的链表算法有： 1. 建立链表

2. 链表的插入操作 3. 链表的删除操作 4. 链表数据元素的访问

(五)实验过程、数据和实验结果记录

程序代码(略)

实验过程中输入/输出数据、程序运行结果的记录。(一定要有!)

第二次实验 栈和队列

(一)实验目的和要求：

1. 熟练掌握栈和队列的结构，以及这种数据结构的特点 2. 会定义顺序栈、循环队列，能实现栈、队列的基本操作 3. 会利用栈解决典型问题，如数制转换等

(二)实验内容和原理或涉及的知识点(综合性实验)：

自己编写程序实现栈(或者队列)的各种基本操作，如初始化、入栈、出栈、判断栈是否为空等

写出栈的定义，简单写出主要算法的思路。

(三)实验条件：安装有VC的计算机

(四)实验设计方案

设计的算法有： 1. 初始化栈 2. 入栈 3. 出栈

4. 判断栈是否为空 5. 十进制转换为八进制

(五)实验过程、数据和实验结果记录

程序代码(略)

实验过程中输入/输出数据、程序运行结果的记录。(一定要有!)

第三次实验 二叉树

(一)实验目的和要求：

1. 熟练掌握二叉树的结构，以及这种数据结构的特点 2. 会定义二叉树的链式存储结构

3. 能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法

(二)实验内容和原理或涉及的知识点(综合性实验)：

自己编写程序实现二叉树的各种基本操作，如二叉树的建立(头插法或者尾插法)，遍历等 写出二叉树的定义，简单写出主要算法的思路。

(三)实验条件：安装有VC的计算机

(四)实验设计方案

设计的算法有： 1. 递归建立二叉树 2. 先序遍历二叉树 3. 中序遍历二叉树 4. 后序遍历二叉树

(五)实验过程、数据和实验结果记录

程序代码(略)

实验过程中输入/输出数据、程序运行结果的记录。(一定要有!)

第四次实验

查找

(一)实验目的和要求：

1. 熟练掌握查找算法的基本思想，以及算法的适用条件

2. 会定义静态查找表的顺序结构，能实现顺序查找、二分查找

(二)实验内容和原理或涉及的知识点(综合性实验)：

自己编写程序实现顺序查找、二分查找。

写出静态查找表的定义，简单写出主要算法的思路。

(三)实验条件：安装有VC的计算机

(四)实验设计方案

设计的算法有： 1. 建立静态查找表 2. 顺序查找

3. 建立有序的静态查找表 4. 二分查找

(五)实验过程、数据和实验结果记录

程序代码(略)

实验过程中输入/输出数据、程序运行结果的记录。(一定要有!)

第五篇：数据结构实验报告

课程 数据结构 _ 院 系

专业班级 实验地点

姓 名 学 号

实验时间 指导老师

数据结构上机实验报告1

一﹑实验名称：

实验一——链表

二﹑实验目的：

1. 了解线性表的逻辑结构特性;

2. 熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存储结构的描述方法;

3. 掌握链表的基本操作(建表、插入、删除等) 4. 掌握循环链表的概念，加深对链表的本质的理解。 5. 掌握运用上机调试链表的基本方法

三﹑实验内容：

(1) (2) (3) (4) 创建一个链表 在链表中插入元素 在链表中删除一个元素 销毁链表 四﹑实验步骤与程序

#include #include typedef struct LNode {int data; struct LNode *next; }Lnode, *LinkList; //假设下面的链表均为带头结点。 void CreatLinkList(LinkList &L,int j) {//建立一个链表L,数据为整数，数据由键盘随机输入。

LinkList p,q; L=(LinkList )malloc(sizeof(Lnode)); L->next=NULL; q=L;

cout<<"请输入一个链表："<

for(int i=0;i

{

p=(LinkList)malloc(sizeof(Lnode));

cin>>p->data;

p->next=q->next;

q->next=p;

q=p;

} } int PrintLinkList(LinkList &L) {//输出链表L的数据元素

LinkList p;

} void LinkListLengh(LinkList &L) {//计算链表L的数据元素个数。 int i=0; p=L->next; if(L->next==NULL) {

} cout<<"链表的数据元素为:"; while(p)

{

cout

p=p->next; } cout<<"链表没有元素!"<

} LinkList p; p=L->next; while(p) {

i++;

p=p->next;

} cout<<"链表的数据元素个数为:"<

LinkList p,s; int j=0; p=L;

while(p&&j

} if(!p||j>i-1) { p=p->next; ++j;

}

} cout<<"插入元素的位置不合理!"; return 0; s=(LinkList)malloc(sizeof(LNode)); s->data=x; s->next=p->next; p->next=s; return 1; int DeleteLinkList(LinkList &L,int i) {//删除链表L的第I个数据元素。

LinkList p,q; int j=0; p=L; while(p->next&&j

} if(!(p->next)||j>i-1) { p=p->next; ++j;

}

} cout<<"删除元素的位置不合理!"; return 0; q=p->next; p->next=q->next; i=q->data; free(q); return 1; void DestroyLinkList(LinkList &L) {//销毁链表L。

LinkList p,q; p=L->next; while(L->next!=NULL) { q=p->next; L->next=q;

free(p); } p=q;

free(L);

cout<<"链表已经被销毁!"<

LinkList L;

int i,j,x; cout<<"第一次数据结构上机实验—链表"<>j;

CreatLinkList(L,j);

LinkListLengh(L);

PrintLinkList(L);

cout<<"在第几个元素前插入:"; cin>>i; cout<<"输入插入的元素:"; cin>>x;

InsertLinkList(L,i,x);

LinkListLengh(L);

PrintLinkList(L);

cout<<"输入删除元素的位置:"; cin>>i;

DeleteLinkList(L,i);

LinkListLengh(L);

PrintLinkList(L);

cout<<"销毁程序后为:"<

DestroyLinkList(L); } 五﹑实验结果

六﹑实验心得体会：

链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。

实验的程序设计规划(实现的功能、分几个模块、子函数) (1) 编写链表创建子函数void CreatLinkList(L,j) (2) 编写链表插入子函数 int InsertLinkList(LinkList &L, int i, int x) (3)链表的打印int PrintLinkList(LinkList &L) (4)编写链表删除子函数 int DeleteLinkList(LinkList &L,int i) (5)编写链表销毁子函数void DestroyLinkList(LinkList &L) (6)编写主函数Main()，通过功能菜单调用子函数 (7)编译调试程序

经过多次的调试，修改，实验结果终于正确了，在这个过程中，经历了不知道怎么进行声明区的编写如包含文件，宏定义，函数声明，全局变量声明，结构体等的定义等的结合，到学会了使用先把程序主要规划为四个部分来写就简单多了，第一，定义;第二，写所要调用的子函数;第三，写主函数，调用子函数;第四就是程序的编译与调试，修改。数据结构实验需要我们对每个程序的算法有深刻的理解，才能应用到实际中去，因此我们需要在做实验之前要熟悉实验的内容，且先把所要实验的程序写出来，在实验中就可以查找错误并加以改正，这是一个成长的过程。

数据结构上机实验报告

2 一﹑实验名称：

实验二—队列

二﹑实验目的： 1. 掌握队列这种抽象数据类型的特点, 掌握栈与队列在实际问题中的应用和基本编程技巧,并能在相应的问题中选用它; 2. 熟练掌握循环队列和链队列的基本操作实现算法，特别是队满和队空的描述方法;

3.掌握栈与队列的数据类型描述及特点;

4.掌握栈的顺序和链式存储存表示与基本算法的实现; 5.掌握队列的链式存储表示与基本操作算法实现; 6.按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性; 7.认真书写实验报告，并按时提交。

三﹑实验内容：

对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求：

(1)掌握栈和队列的特点，即后进先出和先进先出的原则。 (2)设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空;

(3)编写主函数进行测试。

四﹑实验步骤与程序

#include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; int InitQueue(LinkQueue &Q) {

} Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode)); if(!Q.rear) exit(OVERFLOW); Q.front->next=NULL; return OK; void QueueEmpty(LinkQueue Q) {

} void EnQueue(LinkQueue &Q,int e) {

} int EnnQueue(LinkQueue &Q,int e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) printf("error"); if(Q.front==Q.rear) printf("该链队为空:"); else printf("该链队不为空:"); p->data=e; Q.rear->next=p; Q.rear=p; printf("元素%d入队成功",e);

} if(!p) return ERROR; p->data=e; Q.rear->next=p; Q.rear=p;

return OK; void DeQueue(LinkQueue &Q) {

} void GetHead(LinkQueue &Q) { QueuePtr p; QueuePtr p; if(Q.front==Q.rear) printf("该链队为空"); p=Q.front->next; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); printf("队首元素删除成功");

} if(Q.front==Q.rear) printf("该链队为空"); p=Q.front->next; printf("队首元素为:%d",p->data); void OutQueue(LinkQueue &Q) {

} void LengthQueue(LinkQueue &Q) {

int f=0; QueuePtr p; if(Q.front==Q.rear) QueuePtr p; if(Q.front==Q.rear) printf("该链队为空"); p=Q.front->next; while(p!=Q.rear->next) {

} printf("%d%,",p->data); p=p->next;

} printf("该队列的长度为:%d",f); else {

} p=Q.front->next; while(p!=Q.rear->next) {

} printf("该队列的长度为:%d",f); p=p->next; f++; void main() {

system("cls"); int flag=1,i; LinkQueue Q; InitQueue(Q); printf("************************链队列功能菜单*********************** "); printf("1:初始化链队列,

2:判断链队列是否为空, 3:进入队列,

4:取出队首元素 "); printf("5:输出该队列的所有元素,6:输出该队列的长度,

7:结束程序,

8:清屏 ");

while(flag) {

printf(" 请输入操作符:"); scanf("%d",&i); switch(i) { case 1:

int e,n,k; printf("请输入队列的长度:"); scanf("%d",&n); printf("请输入队列的元素:"); for(e=1;e<=n;e++) {

} printf("初始化链队成功"); break; scanf("%d",&k); EnnQueue(Q,k); case 2: QueueEmpty(Q);

break; case 3:

int j; printf("请输入要进入队列的元素"); scanf("%d",&j); EnQueue(Q,j); break; case 4: GetHead(Q); break; case 5:

printf("该队列的元素为:"); OutQueue(Q); break;

case 6: LengthQueue(Q); break; case 7: flag=0; break; case 8: system("cls"); } break;

} } 五﹑实验结果

六﹑实验心得体会：

程序主要构造了主函数main()和 InitQueue()，QueueEmpty ()EnQueue()，OutQueue()等调用函数，实现了队列的创立，队列是否为空的判断，入队和出队等功能。

通过此次实验，加深了对队列的存储结构的了解，同时也对程序设计能力有了提高，加深了对队列先进先出性质的理解，它允许在表的一端进行插入，在另一端删除元素，这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。 我们往往写不出程序，这其中的原因我觉得是对程序的结构不是很了解，对实验的内容也不熟练的结果，数据结构给我们许多程序的算法和模型，对我们写程序的思维有很大的锻炼，我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题，从而达到提升写程序的能力。

数据结构上机实验报告

3 一﹑实验名称：

实验三—二叉树的遍历

二﹑实验目的：

1、熟悉二叉树的结构特性，了解相应的证明方法;

2、掌握二叉树的生成，掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法;

3、理解二叉树的三种遍历方法：先序遍历、中序遍历和后序遍历;

4、 学会编写实现树的各种操作的算法。

二、实验内容：

1、使用类定义实现二叉树，补充完整所缺的函数，并实现创建和遍历二叉树的基本操作;

2、编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法为在先序、中序和后序遍历算法。

三、实验步骤与程序：

#include #include #include typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;//定义结点类型 BiTree CreateBiTree()//创建树 { char p;BiTree T; scanf("%c",&p); if(p==) T=NULL; else { T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间 T->data=p; T->lchild=CreateBiTree(); T->rchild=CreateBiTree(); } return (T); }

void PreOrder(BiTree T)//先序 { if(T!=NULL) { printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T)//中序 { if(T!=NULL) { InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); } } void PostOrder(BiTree T)//后序 { if(T!=NULL) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); } } void main()//主函数 {

printf("------------二叉树的遍历------------- "); printf("请输入要遍历的数："); BiTree Ta; Ta=CreateBiTree(); printf("先序遍历:"); printf(" "); PreOrder(Ta); printf(" "); printf("中序遍历:"); printf(" "); InOrder(Ta); printf(" "); printf("后序遍历:"); printf(" "); PostOrder(Ta); } 五﹑实验结果

六﹑实验心得体会：

实验的程序设计规划(实现的功能、分几个模块、子函数) (1) 先序遍历递归算法函数：void PreOrder(BiTree T) (2) 中序遍历递归算法函数：void InOrder(BiTree T) (3) 后续遍历递归算法函数：void PostOrder(BiTree T) (4) 主函数的实现：void main()

在实验前我认真阅读关于二叉树的实现的内容，为编程实现第一步，本次实验通过按上述的实验步骤一步步实现的，实验过程中出现了一些错误，经过一步步的调试，修改错误，得到了二叉树的遍历用递归运算的方法的程序。通过这个实验，我体会到了理解数据结构的重要性，这有真正理解了定义数据类型的好处，才能用好这样一种数据结构。二叉树的先序，中序与后序的输出都用了递归的算法，而且用起来不是很复杂，这使我更进一步理解了函数递归调用并得到灵活运用;在实现算法上，从算法的效率看，递归方法书写形式较为简洁，更为直观，一般具有较好的空间效率。

总之，不管做什么实验，我们在做实验前都要先预习，对所做的实验有较深的理解，在做实验的时候需要很严谨，仔细的查找错误，从而能在实验中收获知识，提升自己。

数据结构上机实验报告4 一﹑实验名称：

实验四—查找

二﹑实验目的：

1、熟悉掌握顺序表的查找方法;

2、熟练掌握二叉排序树的构造方法和查找算法

3、掌握描述查找过程的判定树的构造方法，以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度;

4、 学会定义线性表的储存类型，实现C++程序的基本结构对线性表的一些基本操作和具体的函数定义;

5、掌握顺序表的基本操作，实现顺序表的查找的等基本运算;

6、掌握对于多函数程序的输入，编辑，调试和运算过程。

二、实验内容：

1、实现顺序表的查找算法

2、 关于衡量查找的主要操作—查找的查找平均效率的平均长度的讨论。

三、实验步骤与程序：

#include #define MAX_SIZE 100 typedef struct{ int key; }element;

element list[MAX_SIZE];

int seqsearch(element list[],int searchnum,int num); int main() {

int i,num,searchnum,k;

printf("---------------数据结构查找实验------------- "); printf("请输入数据元素的个数："); scanf("%d",&num); printf("请输入数据的元素： "); for(i=0;i

printf("请输入要查询的数据元素:"); scanf("%d",&searchnum); k=seqsearch(list,searchnum,num); if(k!=-1) { printf("所查询元素的下标为："); printf("%d ",k); } else printf("查询元素不存在。 "); } return 0; }

int seqsearch(element list[],int searchnum,int num) { int j;

list[num].key=searchnum;

for(j=0;list[j].key!=searchnum;j++) ; return j

六﹑实验心得体会：

实验的程序设计规划为先写一个主函数int main() ，再写一个查找的子函数int seqsearch(element list[],int searchnum,int num) ，主函数通过调用子函数的方法实现程序的设计。

所谓“查找”即为在一个众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)，通过本次实验，我更进一步的了解数据结构程序实验设计实现算法的基本模型，和算法实现等基本内容，学会了顺序表的查找方法。

数据结构上机实验报告5 一﹑实验名称：

实验五—内部排序

二﹑实验目的：

1、通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况，并加以灵活应用。

2、掌握各种排序时间复杂度的分析方法。

二、实验内容：

1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

2、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。

3、讨论各种内部排序方法的基本思路，算法特点，排序过程及它们的时间复杂度的分析。

三、实验步骤与程序：

#include void main() {

} int x; void charu(); void kuaisu(); printf("----------内部排序--------- "); printf("

1、插入排序： "); printf("

2、选择排序： "); printf("请根据序号选择："); scanf("%d",&x); if(x==1) charu(); else kuaisu(); void charu() { int a[7],j,i,m;

printf("插入排序 ");

printf("请输入个您想排序的数据: ");

for(i=0;i<7;i++)scanf("%d",&a[i]);

for(j=1;j<7;j++)

{ m=a[j];

for(i=j-1;i>=0;i--)

{

if(a[i]

break;

else a[i+1]=a[i];

}

a[i+1]=m;

}

printf("排序成功:");

for(i=0;i<7;i++)

printf(" %d",a[i]);

printf(" "); } quick(int first,int end,int L[]) { int left=first,right=end,key;

key=L[first];

while(left

{ while((left=key))

right--;

if(left

L[left++]=L[right];

while((left

left++;

if(left

L[left]=key;

return left;

}

quick_sort(int L[],int first,int end)

{ int split;

if(end>first)

{ split=quick(first,end,L);

quick_sort(L,first,split-1);

quick_sort(L,split+1,end);

}

} void kuaisu() {

int a[7],i;

printf("快速排序 ");

printf("请输入个您想排序的数据: ");

for(i=0;i<7;i++)

scanf("%d",&a[i]);

quick_sort(a,0,9);

printf("排序成功:");

for(i=0;i<7;i++)

printf(" %d",a[i]);

printf(" "); } 五﹑实验结果：

六﹑实验心得体会：

排序的功能是将一个数据元素(或记录)的任意序列，从新排成按关键字有序的序列;直接插入排序的稳定性比快速排序高，且算法较简单。本次实验运用到的是插入排序和快速排序。