数据结构实验报告格式

实验1线性表的基本操作

一、实验目的

1.掌握使用VC++上机调试线性表的基本方法；

2.掌握线性表的基本操作：插入、删除、查找等运算在顺序和链式存储结构上的实现。

二、实验内容

线性表的基本操作的实现

三、实验要求

1.认真阅读和理解本实验的程序。

2.上机运行调试本程序。

四、写出该程序的功能和运行结果。

五、实验总结

（在实验中遇到了哪些问题，如何解决的）

六、实验评价（教师）

实验2 栈和队列的基本操作

一、实验目的

1深入了解栈的特性，掌握栈和队列的各种基本操作。

二、实验内容

栈和队列在顺序存储结构下的各种基本操作

三、实验要求

1.认真阅读和掌握本实验的算法。

2.上机将本算法实现

2.上机运行写出的程序，并且独立调试通过。

四、写出该程序的功能和运行结果。

五、实验总结

（在实验中遇到了哪些问题，如何解决的）

六、实验评价（教师）

实验3 串及其应用

一、实验目的:

本次实验的目的是熟悉串类型的实现方法和文本模式匹配方法。

二、实验内容

实现串的模式匹配算法

三、实验要求

1.认真阅读和掌握本实验的算法。

2.写出程序并上机运行本程序。

（源程序）

四、写出该程序的输入和运行结果

五、实验总结

（在实验中遇到了哪些问题，如何解决的）

六、实验评价（教师）

实验4 二叉树

一、实验目的

本次实验的目的是熟悉树的各种物理表示方法及各种遍历方式 (其中以二叉树为侧重点)，了解树在计算机科学及其他工程中的应用。

二、实验内容

1.二叉树的建立

2.遍历二叉树 (递归和非递归形式)

三、实验要求

1.认真阅读和掌握本实验的算法。

2.写出程序并上机运行程序。

四、写出程序的输入和运行结果

五、实验总结

（在实验中遇到了哪些问题，如何解决的）

六、实验评价（教师）

实验5 图

一、实验目的

本次实验的目的是熟悉图的各种物理表示方法及各种遍历方式，了解图在计算机科学

及其他工程中的应用。

二、实验内容

1.图的两种存储结构

2.图的遍历

3.最小生成树

4.拓扑排序和关键路径

5.最短路径

三、实验要求

1.认真阅读和掌握本实验的算法。

2.写出程序并上机运行本程序。

四、写出程序的输入和运行结果

五、实验总结

（在实验中遇到了哪些问题，如何解决的）

六、实验评价（教师）

实验6 查找和排序

一、实验目的

本次实验的目的是掌握各种查找和排序算法及其实现技术，了解它们在时间和空间复杂性方面的性能，熟悉各种查找和排序方法的适用性，

二、实验内容

1.顺序查找和二分查找

2.二叉排序树和平衡二叉树

3.哈希表

4.各种简单排序 (插人排序、选择排序、冒泡排序等)

5.快速排序、堆排序、归并排序和基数排序

三、实验要求

1.认真阅读和掌握本实验的算法。

2.上机将算法实现并独立调试通过。

四、写出程序的输入和运行结果

五、实验总结

六、实验评价（教师）

设计性实验一：一元多项式计算

一、课程设计目的

本次实验的主要目的是设计一个一元多项式简单计算器，熟悉掌握一元多项式在链式存储结构上的实现，能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入并体会两种存储结构各自的优缺点和适用性。

二、实验内容

（1）输入并建立多项式

（2）输出多项式，输出形式为整数序列：n，a，e1，c2，e2…,cn,en,其中n是多项式的项数,ci，ei分别是第i项的系数和指数,序列按指数降序排列。

（3）多项式a和b相加，建立多项式a+b

（4）求多项式a的导数，建立多项式a=a’

三、实验环境

硬件环境：IBM—PC机及其兼容机。

软件环境：（1）操作系统Windows98或Windows2000。

（2）Microsoft Visual C++ 6.0或TurboC2〃0系统。

四、实验要求

1.认真阅读和掌握本实验的算法。

2.上机将算法实现并独立调试通过。

给出存储结构、多项式相加的源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

五、实验总结

六、实验评价（教师）

设计性实验二：约瑟夫环

一、问题描述：

约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1顺序报数，如此下去，直到所有人全部出列为止。

二、课程设计目的：

本次课程设计的主要目的是利用单向循环链表存储结构模拟约瑟夫环过程，按照出列的顺序输出各个人的编号。

三、实验内容：

1.输入数据：输入m的初值，n ，输入每个人的密码，建立单循环链表

2.写出算法，输出正确的序列

四、实验要求

1.认真阅读和掌握本实验的算法。

2.上机将算法实现并独立调试通过。

3.测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

给出存储结构、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

五、实验总结

六、实验评价（教师）

设计性实验三：订票系统

一、问题描述

航空客运订票的业务活动包括：查询航线、客票预定和办理退票等。

二、课程设计目的：

本次实验的主要目的是设计航班信息，订票信息的存储结构，设计程序完成功能。

三、实验内容：

(1)录入：

可以录入航班情况。每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日（星期几飞行）、乘员定额、余票量、已订票的客户名单以及等候替补的客户名单。

(2)查询：

可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；

可以输入起飞抵达城市，查询飞机航班情况；

(3)订票：

可以订票，如果该航班已经无票，可以提供相关可选择航班；

(4)退票： 可退票，退票后修改相关数据；

客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

(5)修改航班信息：

当航班信息改变可以修改航班数据文件实验环境：

四、实验要求

1. 上机将算法实现并独立调试通过。

给出存储结构、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

五、实验总结

六、实验评价（教师）

课程设计四：迷宫求解

一、课程设计目的：

本次实验的主要目的是实现一个以链表作存储结构的栈，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一座标的方向。

二、实验内容及要求：

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。可以输入一个任意大小的迷宫数据，用递归非递归的方法求出一条走出迷宫的路径，并将路径输出，或得出没有路径的结论。

三、实验手段和方法:

(1)计算机解迷宫通常用“穷举求解”法。即从入口出发，顺某一个方向进行探索，若能走通，则继续往前进；否则沿原路退回，换一个方向继续探索，直至出口位置，求一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。

(2)可以二维数组存储迷宫数据，通常设定入口点的下标为 （1，1），出口点的下标为（n，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

四、实验要求

1. 上机将算法实现并独立调试通过。

给出存储结构、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

五、实验总结

六、实验评价（教师）

课程设计五：判断回文

一、课程设计目的：

本次实验的主要目的是掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用他们。要求熟练掌握栈和队列两种抽象数据类型的各种基本操作的实现算法。

二、实验内容及要求：

假设正读和反读都相同的字符序列为“回文”，例如，’abba’和’abcba’是回文，’abcde’和’ababab’则不是回文。请写出程序，判断读入的一个以’@’为结束符的字符序列是否是“回文”。要求用栈和队列

三、实验手段和方法:

(1)要求用两种方法实现本程序，第一种方法要求使用栈和队列来实现。

(2)第2种方法要求使用栈和队列以外的其他方法。

四、实验要求

1. 上机将算法实现并独立调试通过。

给出存储结构、源程序、测试数据和结果

五、实验总结

六、实验评价（教师）

 

第二篇：数据结构实验报告参考格式

数据结构实验设计报告

题目名称：

设计环境：

指导教师：

专业班级：

姓    名：

学    号：

联系电话：

电子邮件：

设计日期：

设计报告日期：

工程训练实习总结报告

    每次上课，我都会提前几分到训练基地，但我发现，老师总在我之前，并且已经画好图、检验好机床设施等待同学们的到

               

算术表达式求值演示

1.题目简介

2.需求分析

2.1输入形式和输入值的范围

2.2输出的形式

2.3程序所能达到的功能

2.4测试数据

3.设计思路及具体实现 

4.调试分析

5.测试结果和分析

  5.1输入中缀表达式信息

  5.2中缀变为后缀表达式

  5.3后缀表达式计算过程

6.实验总结

1．题目

算术表达式求值演示

表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子，设计一个程序，实现利用算符优先算法计算算术表达式求值。

2．需求分析

本演示程序用 C++ 编写，实现利用算符优先算法计算算术表达式求值：

（1）通过键盘输入表达式字符序列，并转换为整数表达式。

（2）进行输入合法性验证

（3）对算术运算表达式求值

（4）运算符包括乘方，开方，单目减等运算符

2.1 输入的形式和输入值的范围：

    将需要计算的中缀表达式通过键盘输入，输入形式是字符型；

2.2输出的形式

输入操作结束后，如同输入的表达式非法，则会显示“您输入的表达式错误！”字样，如果输入是正确的，则直接进入计算过程，首先是把中缀表达式变换为后缀表达式输出，然后再显示每一步后缀表达式运算过程，最终输出表达式计算过程。

                        

                                     4

2.3程序所能达到的功能：

将中缀表达式转换为后缀表达式，后缀表达式计算出最终结果，自动退出系统服务。

2.4测试数据：

A．测试输入中缀表达式。在主函数中输入提示输入语句结束后，开始输入表达式，系统自动检验输入是否正确。

B.测试中缀变后缀表达式函数Infix(Middle,Middle.length (),Behind)，在函数中添加语句，显示“转换的后缀表达式如下：”字样，然后循环输出数组array[]保存后缀表达式的字符。

C.测试后缀表达式计算函数Suffixal(Behind,length)，添加语句实现循环输出后缀表达式计算的每一步，直到计算出最终结果。

D．测试退出系统功能。输入任意键退出系统。

3. 设计思路及具体实现

实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块写出伪码算法。

3.1数据类型

//用类SeqStack来存储中缀表达式字符

class SeqStack

{

private:

    char data[MaxStackSize];//存放数据元素的数组

                      5

    int top;//栈顶位置指示器

public:

    SeqStack(void)//构造函数

    {top=0;}

    ~SeqStack(void){}//析构函数

    void Push(const char& item);//入栈

    char Pop(void);//出栈

    char Peek(void)const;//读栈顶元素

    bool StackEmpty(void)const//判断堆栈是否为空

    {return (top==0);}

    int GetSize(void)const//读栈顶元素个数

    {return top;}

    void ClearStack(void)//清空栈

    {top=0;}

};

3.2基本操作

//运算符优先级比较

char Proceed(char a,char b)             //运算符优先级比较

{

    char Result;

    char MidString[2];

                   

                                6

    Result='<';

    MidString[0]=b;

    MidString[1]=0;

    if(((a=='+'||a=='-')&&strstr("+-)#",MidString)!=NULL)||((a=='*'||a=='/')&&strstr("+-*/)#",MidString)!=NULL)||(a=='^')&&strstr("+-*/^)#",MidString)!=NULL)                //k表开方

          Result='>';

    else if((a=='('&&b==')')||(a=='#'&&b=='#'))

          Result='=';

    else if((a=='('&&b=='#')||(a==')'&&b=='(')||

          (a=='#'&&b==')'))

          Result=' ';

    return Result;

}

//中缀变后缀表达式函数：

int Infix(string& middle,int n,int array[])       //中缀变后缀      

{

      SeqStack s;

      char x1,x2;

      int j=0,z,count=0;

      s.Push('#');

                

                                       7

      x1=s.Peek();

      while(j<n)

      {

            x2=middle[j];

            if(x2>='0'&&x2<='9')

            {

                  z=x2-'0';

                  j++;

                  while (j<n&&middle[j]>=48&&middle[j]<=57)

                  {

                        z=z*10+middle[j++]-'0';                          

                  }

                  array[count++]=z;

            }

            else if (x2=='$')                            //$表示开方符

            {

                  if (j==(n-1)||middle[j+1]>57&&middle[j+1]<48)

                  {

                      cout<<"您输入的表达式错误！"<<endl;

                      exit(0);

                  }

8

                  j++;

                  z=middle[j++]-'0';

                  while (j<n&&middle[j]>=48&&middle[j]<=57)

                  {

                        z=z*10+middle[j++]-'0';                          

                  }

                  array[count++]=sqrt(z);

            }

            else if (x2!='+'&&x2!='-'&&x2!='*'&&x2!='/'&&x2!='^'&&x2!='('&&x2!=')')

            {

                    cout<<"您输入的表达式错误！"<<endl;

                    exit(0);

            }

            else

            {               

                  if(Proceed(x1,x2)=='<')

                  {

                        s.Push(x2);

                        x1=x2;

      

                 9          

}

                  }

                  else if(Proceed(x1,x2)=='>')

                  {

                  if (x1!='+'&&x1!='-'&&x1!='*'&&x1!='/'&&x1!='^')

                  {

                      cout<<"您输入的表达式错误！"<<endl;

                      exit(0);

                  }

                        array[count]=int(x1);

                        flag[count++]=true;

                        s.Pop();

                        x1=s.Peek();

                        while(Proceed(x1,x2)=='>')

                        {

                              if (x2!='+'&&x2!='-'&&x2!='*'&&x2!='/'&&x2!='^')

                              {

                             cout<<"您输入的表达式错误！"<<endl;

                             exit(0);

                              }

                              array[count]=int(x1);                                                                         

                                                                           

10

    flag[count++]=true;

                              s.Pop();

                              x1=s.Peek();

                        }

                        if (Proceed(x1,x2)==' ')

                        {

                  {

                      cout<<"您输入的表达式错误！"<<endl;

                      exit(0);

                  }

                        }

                        else if (Proceed(x1,x2)=='=')

                        {

                              s.Pop();

                              x1=s.Peek();

                        }

                        else

                        {

                              s.Push(x2);

                              x1=x2;

                        }

               

                                    11

                  }

                  else if(Proceed(x1,x2)=='=')

                  {

                        s.Pop();

                        x1=s.Peek();

                  }

                  else

                  {

                      cout<<"您输入的表达式错误！"<<endl;

                      exit(0);

                  }                j++;

            }

      }

      x2='#';

      while (1)                              //清空栈

      {

            if (Proceed(x1,x2)=='=')

            {

                  break;

            }

            if (Proceed(x1,x2)=='>')

                         

                          12

            {

                  if ((x1!='+')&&(x1!='-')&&(x1!='*')&&(x1!='/')&&(x1!='^'))

                  {

                      cout<<"您输入的表达式错误！"<<endl;

                      exit(0);

                  }

                  array[count]=int(x1);

                  flag[count++]=true;

                  s.Pop();

                  if (s.StackEmpty())

                  {

                      cout<<"您输入的表达式错误！"<<endl;

                      exit(0);

                  }

                  x1=s.Peek();

            }

            else

            {

                  cout<<"您输入的表达式错误！"<<endl;

                  exit(0);

            }

                   

                            13

      }

      int i,k=0;                    //k表示操作符的个数

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

      {

            if (flag[i])

            {

                  k++;

            }

      }

      if((k*2+1)!=count)                   //运算符不比运算数少1，则非法

            {

                  cout<<"您输入的表达式错误！"<<endl;

                  exit(0);

            }

      if (count>=0)

      {

            cout<<"转换的后缀表达式如下："<<endl;

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

            {

                  if (flag[i])

                                                                 

                            14 

{

                        cout<<char(array[i])<<" ";

                  }

                  else

                        cout<<array[i]<<" ";

            }

            cout<<endl;

      }

      return count;

}

//后缀表达式的运算

void Suffixal(int s[],int t)                        //后缀表达式的运算

{

      while (t>1)

            {

                int     j=0;

                  while (j+2<t&&!flag[j+2])

                        j++;

                  if (j+2>=t)

                        break;

             

                           15

                  switch (char(s[j+2]))

                  {

                  case '+':s[j]=s[j]+s[j+1];break;

                  case '-':s[j]=s[j]-s[j+1];break;

                  case '*':s[j]=s[j]*s[j+1];break;

                  case '/':s[j]=s[j]/s[j+1];break;

                  case '^':s[j]=pow(s[j],s[j+1]);break;

                  }

                  for (int i=j+1;i<t-2;i++)

                  {

                        s[i]=s[i+2];

                        flag[i]=flag[i+2];

                  }

                  t=t-2;

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

                  {

                        if (flag[i])

                        {

                              cout<<char(s[i])<<" ";

                        }

                        else

                                        16

                              cout<<s[i]<<" ";

                  }

                  cout<<endl;

            }

}

3.3主函数功能伪代码：

int main()

{

      string Middle;         //接收中缀表达试

      int Behind[1000];  //此数组用来接收中缀所变得整形后缀表达式

      cout<<"请输入需要计算的中缀表达式（加、减、乘、除、乘方、开方 分别用 +、-、*、/、^、$ 表示 ）"<<endl;

      cin>>Middle;

      int length=Infix(Middle,Middle.length (),Behind);

            if(length>1)

            Suffixal(Behind,length);        //后缀运算

      return 0;  

}

4.调试分析

开始设计时，使用数组存储中缀表达式，其中有一些麻烦，后

        

                                      17

来发现用顺序堆栈存储会更显得方便，所以改用顺序堆栈。在存储中缀表达式过程中，需要先把字符数字改为数学数字。其中，还有要把运算符号改为数字形式，最终有其还原。

5.测试结果和分析

5.1输入中缀表达式信息

直接输入需要转换和计算的中缀表达式，接着系统自动对算术表达式进行合法性验证。如果错误，就显示出错语句提示，并退出程序。

5.2中缀变为后缀表达式

如果上一步验证算术表达式合法，就进入中缀转换为后缀函数，并输出转换后的后缀表达式。

5.3后缀表达式计算过程

输出玩后缀表达式后，紧接着进入下一步操作，由后缀表达式计算出最终结果，并显示中间的每一步计算过程，然后按任意键退出程序。

6.案例总结

     表达式计算是编译系统中的基本问题，利用堆栈来实现表达式的转换和计算，编译系统对中缀形式的算术表达式处理的方法是，先把它转换为后缀形式的算术表达式，然后再计算后缀表达式，计算后缀表达式值的过程仍然是一个堆栈应用过程。

    此算术表达式演示功能比较齐全，能够实现算术表达式的转换和计算，其中的运算除了基本的加、减、乘、除以外，还添加了乘方和开方运算符。但是还可以进一步改进，增加更多的功能。若考虑到界面友好问题，再增加一些改变界面的功能，使界面变得较友好，效果会更好。