《数据结构与算法》上机实验要求

时间:2024.7.17

《数据结构与算法》课程实验内容与要求

一、 课程简介

本课程着重讲述 ①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法 ③典型内部排序算法。

二、 实验的作用、地位和目的

数据结构是一门技术基础课,通过实验深刻理解各种逻辑结构、存储结构的特性,培养为实际问题分析其数据对象、基本操作,选择逻辑结构、存储结构灵活应用基本算法,设计出具有专业水准的应用程序的能力。

三、 实验方式与要求

①首先要求学生在课下完成问题分析、算法设计,基本完成程序设计。

②实验时,每位学生使用一台微机,独立调试,完成程序。

③程序调试好后,由指导教师检测运行结果,并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据,运行结果及源程序。

⑤在一周内完成实验报告。

四、 考核方式与实验报告要求

实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。

学生在实验后的一周内提交实验报告。实验报告首页按学校统一印刷的实验报告模版书写。实验报告中应包括如下内容:

?

? 实验内容按任课教师下达的实验任务填写(具体实验题目和要求); 实验过程与实验结果应包括如下主要内容:

? 算法设计思路简介

? 算法描述:可以用自然语言、伪代码或流程图等方式

? 算法的实现和测试结果:包括算法运行时的输入、输出,实验中出现的问题及解决办

法等

?

? 源程序清单与实验结果或其它说明可打印,并装订在实验报告首页之后。 实验报告雷同者,本次实验成绩为0分或雷同实验报告平分得分

五、 实验的软硬件环境

硬件环境:PⅡ以上微型计算机

软件环境:Windows98/2000, VC++6.0或turbo C

六、 实验内容安排

实验一 线性表应用

实验时间:20xx年3月26日1-2节,3月30日1-2节(地点:7-220)

实验目的: 理解线性表的逻辑特点;掌握顺序表、链表存储结构,以及线性表的基本操作,如插入、删除、查找,以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法,并能够在实际问题背景下的灵活运用线性表来解决问题,实现相应算法。

具体实验题目与要求:(任课教师根据实验大纲自己指定)

每位同学可从下面题目中选择1-2题实现:

1.一元稀疏多项式简单的计算器

1)问题描述:用线性表表示一元稀疏多项式,设计一个一元多项式运算器

2)要求: (1)采用单链表存储结构一元稀疏多项式

(2)输入并建立多项式

(3)输出多项式

(4)实现多项式加、减运算

2.单链表基本操作练习

1)问题描述:在主程序中提供下列菜单:

1…建立链表 2…连接链表 3…输出链表 0…结束

2)实验要求:算法中包含下列过程,分别完成相应的功能:

CreateLinklist(): 从键盘输入数据,创建单链表

ContLinklist():将前面建立的两个单链表首尾相连

OutputLinklist():输出显示单链表

3.约瑟夫环问题

1)问题描述:有编号为1, 2…n 的 n 个人按顺时针方向围坐一圈,每人持有一个正整数密码。开始给定一个正整数 m,从第一个人按顺时针方向自1开始报数,报到m者出列,不再参加报数,这时将出列者的密码作为m,从出列者顺时针方向的下一人开始重新自1开始报数。如此下去,直到所有人都出列。试设计算法,输出出列者的序列。

2)要求: 采用顺序和链式两种存储结构实现

实验报告格式及要求:按学校印刷的实验报告模版书写。(具体要求见四)

实验二 栈与队列应用

实验时间:20xx年4月16日10:00-13:00(地点:7-220)

实验目的:理解栈和队列的逻辑特点;掌握栈和队列基本操作的实现,并能达到在实际问题背景下的灵活运用栈或队列结构解决问题的程度。

具体实验题目:(任课教师根据实验大纲自己指定)

每位同学完成下面2个题目:

1.十进制数与N进制数据的转换

1)问题描述:将从键盘输入的十进制数转换为N(如二进制、八进制、十六进制)进制数据。

2)要求: 利用顺序栈实现数制转换问题

2.算术表达式求值算法

1)问题描述:从键盘输入一个算术表达式并输出它的结果

2)要求:算术表达式可包含加、减、乘、除、十进制整数和小括号,利用栈实现

实验报告格式及要求:按学校印刷的实验报告模版书写。(具体要求见四)

实验三 二叉树操作

实验时间:20xx年4月30日 10:00-13:00(地点:7-220)

实验目的:理解二叉树的逻辑特点和二叉树的性质;掌握二叉树的二叉链表存储结构,掌握二叉树的创建算法、遍历算法的递归与非递归实现。

具体实验题目:(任课教师根据实验大纲自己指定)

第1题为必做题,第2题为选做题目:

1.每位同学按下述要求实现相应算法:以二叉链表为存储结构,实现二叉树的创建、遍历算法

1)问题描述:在主程序中提供下列菜单:

1…建立树

2…前序遍历树 3…中序(非递归)遍历树 0…结束 4…后序遍历树

2)实验要求:

① 定义下列过程:

CreateTree(): 按从键盘输入的前序序列,创建树

PreOrderTree():前序遍历树(递归)

InOrderTree():中序(非递归)遍历树

LaOrderTree(): 后序遍历树(递归)

② 每位同学在实验过程中要单步运行程序,跟踪二叉树的创建过程与前序遍历的递归过程。

2. 树的转换:我们都知道用“孩子兄弟”表示法可以将一棵一般的树转换为二叉树。请设计算法将一棵树用这种方法转换为二叉树,并输出转换前和转换后树的前序遍历序列。

实验报告格式及要求:按学校印刷的实验报告模版书写。(具体要求见四)

实验四 图的深度优先与广度优先遍历

实验时间:20xx年5月28日,10:00-13:00(地点:7-220)

实验目的:理解图的逻辑特点;掌握理解图的两种主要存储结构(邻接矩阵和邻接表),掌握图的构造、深度优先遍历、广度优先遍历算法。

具体实验题目:(任课教师根据实验大纲自己指定)

第1题为必做题,第2题为选做题目:

1. 每位同学按下述要求实现相应算法: 根据从键盘输入的数据创建图(图的存储结构可采用邻接矩阵或邻接表),并对图进行深度优先搜索和广度优先搜索

1)问题描述:在主程序中提供下列菜单:

1…图的建立

2…深度优先遍历图 3…广度优先遍历图 0…结束

2)实验要求:图的存储可采用邻接表或邻接矩阵;定义下列过程:

CreateGraph(): 按从键盘的数据建立图

DFSGrahp():深度优先遍历图

BFSGrahp():广度优先遍历图

2. 拓扑排序:给出一个图的结构,输出其拓扑排序序列(顶点序列用空格隔开),要求在同等条件下,编号小的顶点在前。

实验报告格式及要求:按学校印刷的实验报告模版书写。(具体要求见四)

实验五 查找算法应用

实验时间:20xx年6月15日 1-2节(地点:7-220),6月16日 1-2节(地点:7-215)

实验目的:理解二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现;掌握散列存储结构的思想,能选择合适散列函数,实现不同冲突处理方法的散列表的查找、建立。散列表等查找算法解决实际问题。

具体实验题目:(任课教师根据实验大纲自己指定)

每位同学可从下面题目中选择1-2题实现:

1.哈希表查找

1)问题描述:针对某个集体的“人名”构造哈希表,解决按“人名”进行查找的索引结构。

2)实验要求:要求表的平均查找长度不超过R(R可以从键盘输入确定),完成相应的建表和查表程序。

2.构造二叉排序树,并进行中序遍历

1)问题描述:从键盘读入一串整数构造一棵二叉排序树,并对得到的二叉排序述进行中序遍历,得到有序序列。

2)实验要求:该二叉排序树以二叉链表存储

3. 拼写检查

1)问题描述:现在有一些英语单词需要做拼写检查,你的工具是一本词典。需要检查的单词,有的是词典中的单词,有的与词典中的单词相似,你的任务是发现这两种情况。单词A与单词B相似的情况有三种:

① 删除单词A的一个字母后得到单词B;

② 用任意一个字母替换单词A的一个字母后得到单词B;

③ 在单词A的任意位置增加一个字母后得到单词B。

2)实验要求:发现词典中与给定单词相同或相似的单词。

实验报告格式及要求:按学校印刷的实验报告模版书写。(具体要求见四)


第二篇:实验:数据结构与算法


《数据结构与算法》实验

提交实验结果的要求:

实验完成后,将文件夹中的Debug文件夹删除,然后将整个文件夹打包成压缩文件,并以“学号 姓名”的方式重命名,提交该压缩包。

实验1VC环境的面向对象程序设计

实验目的:掌握VC环境下面向对象编程的基本步骤

实验准备

1. 复习面向对象程序设计的有关概念

2. 阅读VC有关编程操作的说明

实验步骤及要求

按照实验指导教师的指导,逐条完成以下要求:

1. 启动VC,新建空的控制台工程myproj,新建C++源程序文件main,查看目前文件夹中有哪些文件

2. 新建一个名为CA的类,查看文件夹中新添了哪些文件

3. 为CA类添加1个int型私有数据成员x和1个char*型私有数据成员y

4. 在CA类的构造函数中添加代码,令x赋值为0,y赋值为空指针

5. 在CA类的析构函数中添加代码:如果y不是空指针,则释放y所指向的内存区域

6. 为CA增加带int型和char*型双参数的构造函数,在代码部分令x赋值为int型参数,令y指向动态申请的内存空间(字节数为char*型参数所指字符串的串长加1),并将char*型参数所指字符串复制到新申请的空间中

7. 为CA类增加函数成员Display,用于显示x的值和y所向的指字符串

8. 编写下面的主函数,添加相应的#include预处理命令,并编译、运行程序:

void main( )

{

      CA a,b(12,"abcdefg");

      a.Display( );

      b.Display( );

}

9. 在主函数main中添加以下三行:

      a=b;

      a.Display( );

      b.Display( );

       再运行可发现正确显示了信息后程序运行出错,请说明原因。

10. 为CA类重载赋值运算符“=”,在其中对指针型数据成员y重新申请空间并做字符串复制。再次编译、运行程序,观察是否出错。

11. 为CA类建立拷贝构造函数,实现深拷贝,代码与重载赋值运算符“=”基本相同(不需要return语句)。再次编译、运行程序,观察是否出错。

12. 为CA类重载“+”运算符,做两个对象的加法运算:整数部分相加,字符串部分拼接。在主函数中增加一个CA类的对象c,并在主函数中的“a=b;”语句后面增加一行:

      c=a+b;

在程序的最后增加一行:

      c.Display( );

再次编译、运行程序,观察结果。

实验2:顺序表

实验目的:掌握顺序表的基本运算相关算法并编程实现

实验准备

1. 阅读以下“用顺序表存储多项式”的方法:

一元多项式表现为:

       

用顺序表存储多项式时,一个数据元素由一个用于存储系数的实型分量coe(coefficient)和一个用于存储指数的整型分量exp(exponent)构成,在顺序表中只存储coe和exp即可表示多项式的一项。例如,多项式

              

在顺序表中依次存放(2,5)、(3,2)、(-1,1)、(-4,0)共4个元素即可。注意,系数为0的项不存储,各个数据元素必须按指数降序排列。

2. 阅读、理解以下算法:顺序表的遍历、两个多项式相加

3. 将压缩包ex02.rar中的内容解压,双击文件夹中的dsw工程文件。当前工程中包含三个文件:关于类与类型定义的SeqList.h、类的函数成员SeqList.cpp、主函数文件main.cpp。查看各个文件中的内容。

实验步骤及要求

1. 针对存储多项式的顺序表,修改SeqList.h中的类型定义SeqNode,使其符合多项式的存储要求。

2. 为CSeqList类增加Display方法,用于显示一个多项式。

3. 为CSeqList类重载“+”,实现多项式加法。

4. 去掉主函数main中各语句的注释符号,使得各条语句可以正确执行。

//以下是关于数据元素的类型定义,请根据实际情况修改

typedef struct datatype

{

      double coe;                    //存放系数

      int exp;                  //存放指数

} DataType;

typedef DataType SeqNode;

//以下是关于SeqList类型的声明

class CSeqList 

{

public:

      friend CSeqList operator+(const CSeqList &x , const CSeqList &y);

      void Display();

      virtual bool DeleteData(int i);                      //删除顺序表的第i号元素

      virtual bool GetData(int i,SeqNode *q);        //取顺序表的第i号元素,存放到q所指向的位置

      virtual void Empty();                                         //将当前顺序表置为空表

      virtual bool InsertData(SeqNode x,int i);      //将新元素x插入到顺序表的第i号位置

      virtual void InputData();

      CSeqList& operator=(const CSeqList &x);           //重载赋值运算符

      virtual int GetLength();   //取表长

      virtual bool IsFull();              //判断表是否已满

      virtual bool IsEmpty();          //判断表是否为空

      CSeqList(int maxlen);

      CSeqList(CSeqList &x);         //拷贝构造函数

      virtual ~CSeqList();

private:

      int m_MaxLength;                 //最大表长

      int m_CurLength;                  //当前表长

      SeqNode *m_List;                 //初始化时指向申请的空间,存放表的各个元素

};

#include "SeqList.h"

#include "iostream.h"

#include "windows.h"

#include "math.h"

//构造函数

CSeqList::CSeqList(int maxlen)

{

       if(maxlen<=0)

       {

              cout<<"构造函数创建顺序表失败:表中最多存储元素数量必须是正数\n";

              exit(1);

       }

       m_List=new SeqNode[maxlen];

       if(m_List==NULL)

       {

              cout<<"构造函数创建顺序表失败:内存空间不够\n";

              exit(1);

       }

       m_CurLength=0;

       m_MaxLength=maxlen;

}

//拷贝构造函数

CSeqList::CSeqList(CSeqList &x)

{

       int i;

       m_MaxLength=x.m_MaxLength;

       m_List=new SeqNode[m_MaxLength];

       if(m_List==NULL)

       {

              cout<<"拷贝构造函数创建顺序表失败:内存空间不够\n";

              exit(1);

       }

       m_CurLength=x.m_CurLength;

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

              m_List[i]=x.m_List[i];

}

//析构函数,清理内存

CSeqList::~CSeqList()

{

       delete m_List;

}

//判空

bool CSeqList::IsEmpty()

{

       return m_CurLength==0;

}

//判满

bool CSeqList::IsFull()

{

       return m_CurLength==m_MaxLength;

}

//取表长

int CSeqList::GetLength()

{

       return m_CurLength;

}

//从键盘输入数据存入顺序表中

void CSeqList::InputData()

{

       int x1,x2;

       cout<<"请每次输入系数和指数,用空格分隔,输入两个值均<0表示输入结束\n";

       while(m_CurLength<m_MaxLength)

       {

              cout<<"List["<<m_CurLength<<"] : ";

              x1=x2=-1;

              cin>>x1;

              cin>>x2;                             //输入两个数值

              if(x1<0 && x2<0)

                     break;                                 //如果两个值都<0则表示输入完毕

              m_List[m_CurLength].coe=x1;

              m_List[m_CurLength].exp=x2;     //否则将这两个值存入顺序表

              m_CurLength++;

       }

}

//重载赋值运算符

CSeqList& CSeqList::operator =(const CSeqList& x)

{

       int i;

       m_MaxLength=x.m_MaxLength;

       m_List=new SeqNode[m_MaxLength];

       if(m_List==NULL)

       {

              cout<<"=重载时创建顺序表失败:内存空间不够\n";

              exit(1);

       }

       m_CurLength=x.m_CurLength;

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

              m_List[i]=x.m_List[i];

       return *this;

}

//将新元素x插入到顺序表的第i号位置

bool CSeqList::InsertData(SeqNode x, int i)

{

       int j,k=GetLength();

       if(IsFull() || i<0 || i>k+1)

              return false;

       for(j=k;j>i;j--)

              m_List[j]=m_List[j-1];

       m_List[i]=x;

       m_CurLength++;

       return true;

}

/将当前顺序表置为空表

void CSeqList::Empty()

{

       m_CurLength=0;

}

//取顺序表的第i号元素,存放到q所指向的位置

bool CSeqList::GetData(int i, SeqNode *q)

{

       int k=GetLength();

       if(i<0 || i>=k)

              return false;

       *q=m_List[i];

       return true;

}

//删除顺序表的第i号元素

bool CSeqList::DeleteData(int i)

{

       int j,k=GetLength();

       if(i<0 || i>=k)

              return false;

       for(j=i;j<k-1;j++)

              m_List[j]=m_List[j+1];

       m_CurLength--;

       return true;

}

//以下为新增函数

void CSeqList::Display()

{

       int i;

       if(m_CurLength==0)

              cout<<"该顺序表为空表";

       else

       {

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

              {

                     //显示系数

                     cout<<' ';                             //系数前面先显示一个空格

                     if(m_List[i].coe<0)               //系数为负数,直接显示

                     {

                            if(m_List[i].exp==1 && fabs(m_List[i].coe+1)<1e-10)      //-1X^1显示成-X

                                   cout<<"-";

                            else

                                   cout<<m_List[i].coe;

                     }

                     else

                     {

                            if(i>0)                                 //如果不是最前面一项,则显示'+'[

                                   cout<<'+';

                            if(m_List[i].exp!=1 || fabs(m_List[i].coe-1)>1e-10)    //系数和指数均为1,不显示系数

                                   cout<<m_List[i].coe;

                     }

                     //显示“X^指数”

                     if(m_List[i].exp>0)

                     {

                            if(m_List[i].exp==1)

                                   cout<<"X";

                            else

                                   cout<<"X^"<<m_List[i].exp;

                     }

              }

       }

       cout<<endl<<endl;

}

CSeqList operator +(const CSeqList &x , const CSeqList &y)

{

       int i,j,k,m;

       SeqNode p;

       k=y.m_MaxLength;

       if(k<x.m_MaxLength)

              k=x.m_MaxLength;                     //最大表长取两个表中较大的一个

       CSeqList z(k);

       i=j=m=0;

       while(i<x.m_CurLength && j<y.m_CurLength)  //两个表都未处理完时

       {

              if(m>k)                        //相加后的表长超过最大表长

              {

                     cout<<"重载+时两表相加超过最大表长限制\n";

                     exit(1);

              }

              if(x.m_List[i].exp>y.m_List[j].exp)

                     z.InsertData(x.m_List[i++],m++);               //将指数大的x表中第i项添加到z中

              else if(x.m_List[i].exp<y.m_List[j].exp)

                     z.InsertData(y.m_List[j++],m++);               //将指数大的y表中第j项添加到z中

              else

              {

                     p.coe=x.m_List[i].coe+y.m_List[j].coe;

                     p.exp=x.m_List[i].exp;

                     if(fabs(p.coe)>1e-10)

                            z.InsertData(p,m++);

                     i++;

                     j++;

              }

       }

       return z;

}

#include "iostream.h"

#include "seqlist.h"

void main()

{

       CSeqList list1(100),list2(100),list3(100);

       list1.InputData();

       list1.Display();

       list2.InputData();

       list2.Display();

       list3=list1+list2;

       list3.Display();

}

实验3 链表

实验目的:掌握单链表的基本运算相关算法并编程实现

实验准备

1. 阅读、理解以下算法:单链表的遍历、两个单链表的合并、在单链表中删除重复元素、单链表的排序(冒泡排序法)

2. 将压缩包ex03.rar中的内容解压,双击文件夹中的dsw工程文件。当前工程中包含三个文件:关于类与类型定义的LinkList.h、类的函数成员LinkList.cpp、主函数文件main.cpp。查看各个文件中的内容。

实验步骤及要求

1. 创建CLinkList类的派生类CMyLinkList。如果创建成功,在工程文件夹中将新增MyLinkList.h和MyLinkList.cpp两个文件。

2. 为CMyLinkList类添加用于输入的函数InputData,调用该函数可以从键盘上输入若干组数据存放到链表中。注意调用父类中的InsertData函数时,如果想在链表原来的表头结点(记为1号结点)前面添加新结点,则调用的第二参数应为0。

3. 为CMyLinkList类添加用于显示链表的函数Display,调用该函数可以显示链表中各结点的数据信息。

4. 为CMyLinkList类重载“+”,用于将两个链表合并

5. 为CMyLinkList类添加函数DelRepeat,调用该函数可以删除链表中整型数据项重复的元素,即:从前向后查看每一个结点,记当前查看的结点的整型数据域的值为K,则删除后续所有整型数据域的值为K的结点。

6. 编写主函数main,实现以下功能:

(1) 建立CMyLinkList类的三个对象,其中两个对象的数据值从键盘输入

(2) 利用重载的“+”运算符把上述两个对象合并,结果存放到第三个对象中

(3) 调用第5步建立的函数删除链表中的重复元素

(4) 对链表进行排序

这些功能的相应语句已经以注释的形式编写在主函数中,逐个地去掉注释符号,检查各语句是否能正确执行。

//此处定义数据元素的类型,请根据实际问题作相应的修改

typedef struct dataofnode

{

       double coe;

       int exp;

} DataType;

typedef struct linknode

{

       DataType data;

       struct linknode* next;

} LinkNode ;

class CLinkList 

{

public:

       CLinkList();                                                     //构造函数,生成带有头结点的空链表

       CLinkList(const CLinkList& x);                         //拷贝构造函数

       virtual ~CLinkList();                                        //析构函数,清理内存

public:

       LinkNode* GetLink();          //取指向1号结点的指针,如果是空链表则返回值为NULL

       CLinkList& operator =(const CLinkList &x);      //重载赋值运算符"="

       virtual bool DeleteData(int i);                     //删除链表的第i号结点,头结点为第0号结点

       virtual bool GetData(int i,DataType *q);      //取链表第i号结点,将其数据域复制到q所指向的位置

       virtual int GetLength();                              //取链表的表长

       virtual bool InsertData(DataType x,int i);     //在链表第i号结点的后面插入新结点

       virtual bool IsEmpty();                                     //判断链表是否为空

private:

       LinkNode* m_Head;

};

#include "LinkList.h"

#include "iostream.h"

#include "windows.h"

//构造函数,生成带有头结点的空链表

CLinkList::CLinkList()

{

       m_Head=new LinkNode;

       if(m_Head==NULL)

       {

              cout<<"构造函数创建链表失败:内存空间不够\n";

              exit(1);

       }

       m_Head->next=NULL;                //头结点的指针域置为空指针

       *((int*)&(m_Head->data))=0;      //用数据域存放表长

}

//拷贝构造函数

CLinkList::CLinkList(const CLinkList& x)

{

       LinkNode *q1,*q2;

       int n=0;

       m_Head=new LinkNode;

       if(m_Head==NULL)

       {

              cout<<"拷贝构造函数创建链表失败:内存空间不够\n";

              exit(1);

       }

       m_Head->next=NULL;         //头结点的指针域置为空指针

       q1=m_Head;

       q2=x.m_Head->next;

       while(q2!=NULL)

       {

              q1->next=new LinkNode;

              if(q1->next==NULL)

              {

                     cout<<"拷贝构造函数创建链表失败:内存空间不够\n";

                     exit(1);

              }

              *(q1->next)=*q2;

              q1=q1->next;

              q2=q2->next;

              n++;

       }

       q1->next=NULL;

       *((int*)&(m_Head->data))=n;             //用数据域存放表长

}

//析构函数,清理内存

CLinkList::~CLinkList()

{

       LinkNode *q;

       while(m_Head!=NULL)

       {

              q=m_Head;

              m_Head=m_Head->next;

              delete q;

       }

}

//判断链表是否为空

bool CLinkList::IsEmpty()

{

       return m_Head->next==NULL;

}

//在链表第i号结点的后面插入新结点

bool CLinkList::InsertData(DataType x, int i)

{

       LinkNode *q1,*q2;

       int k,len;

       len=*((int*)&(m_Head->data));    //取表长

       if(i<0 || i>len)

              return false;           //如果位置有错则返回false

       q1=new LinkNode;

       if(q1==NULL)

              exit(1);                  //如果申请空间失败则程序结束

       q1->data=x;                         //为新结点填充数据域

       q2=m_Head;

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

              q2=q2->next;         //令q2指向第i-1号结点,以头结点为第0号结点

       q1->next=q2->next;              //为新结点连接后继

       q2->next=q1;                //为新结点连接前趋

       (*((int*)&(m_Head->data)))++;   //表长加1

       return true;

}

//取链表的表长

int CLinkList::GetLength()

{

       return *((int*)&(m_Head->data));

}

//取链表第i号结点,将其数据域复制到q所指向的位置

bool CLinkList::GetData(int i,DataType *q)

{

       int len,k;

       LinkNode *q1;

       len=*((int*)&(m_Head->data));    //取表长

       if(i<=0 || i>len)

              return false;           //如果位置有错则返回false

       q1=m_Head->next;

       for(k=1;k<i;k++)

              q1=q1->next;         //令q1指向第i号结点,以头结点为第0号结点

       *q=q1->data;

       return true;

}

//删除链表的第i号结点,头结点为第0号结点

bool CLinkList::DeleteData(int i)

{

       int k,len;

       LinkNode *q1,*q2;

       len=*((int*)&(m_Head->data));    //取表长

       if(i<=0 || i>len)

              return false;           //如果位置有错则返回false

       q1=m_Head;

       for(k=1;k<i;k++)

              q1=q1->next;         //令q1指向第i-1号结点,以头结点为第0号结点

       q2=q1->next;                //令q2指向待删结点

       q1->next=q2->next;              //修改链接关系

       delete q2;                     //释放被删结点的空间

       (*((int*)&(m_Head->data)))--;     //表长减1

       return true;

}

//重载赋值运算符"="

CLinkList& CLinkList::operator =(const CLinkList &x)

{

       LinkNode *q1,*q2;

       while(m_Head!=NULL)

       {

              q1=m_Head;

              m_Head=m_Head->next;

              delete q1;

       }

       m_Head=new LinkNode;

       if(m_Head==NULL)

       {

              cout<<"重载赋值号创建链表失败:内存空间不够\n";

              exit(1);

       }

       m_Head->next=NULL;         //头结点的指针域置为空指针

       q1=m_Head;

       q2=x.m_Head->next;

       while(q2!=NULL)

       {

              q1->next=new LinkNode;

              if(q1->next==NULL)

              {

                     cout<<"重载赋值号创建链表失败:内存空间不够\n";

                     exit(1);

              }

              *(q1->next)=*q2;

              q1=q1->next;

              q2=q2->next;

       }

       q1->next=NULL;

       *((int*)&(m_Head->data))=*((int*)&(x.m_Head->data));         //用数据域存放表长

       return *this;

}

//取指向1号结点的指针,如果是空链表则返回值为NULL

LinkNode* CLinkList::GetLink()

{

       return m_Head->next;

}

#include "MyLinkList.h"

#include "iostream"

#include "math.h"

using namespace std;

CMyLinkList::CMyLinkList()

{

}

CMyLinkList::~CMyLinkList()

{

}

void CMyLinkList::InputData()

{

       DataType x;

       cout<<"请每次输入两个数据,用空格分隔,输入中有负数表示输入结束\n";

       while(1)

       {

              cin>>x.coe>>x.exp;                                   //输入两个数值

              if(x.coe<0 || x.exp<0)

                     break;                                 //如果有负数则表示输入完毕

              this->InsertData(x,0);

       }

}

void CMyLinkList::Display()

{

       int i,k;

       DataType x;

       k=this->GetLength();

       if(k==0)

              cout<<"数据表为空表\n";

       else

       {

              for(i=1;i<=k;i++)

              {

                     this->GetData(i,&x);

                     cout<<"( "<<x.coe<<" , "<<x.exp<<" )\n";

              }

              cout<<endl;

       }

}

CMyLinkList operator+(CMyLinkList x,CMyLinkList y)

{

       CMyLinkList z;

       int i,k,m;

       DataType w;

       m=0;

       k=x.GetLength();

       for(i=1;i<=k;i++)

       {

              x.GetData(i,&w);

              z.InsertData(w,m++);

       }

       k=y.GetLength();

       for(i=1;i<=k;i++)

       {

              y.GetData(i,&w);

              z.InsertData(w,m++);

       }

       return z;

}

void CMyLinkList::DelRepeat()

{

       int i,j,k;

       DataType a,b;

       k=GetLength();

       for(i=1;i<=k;i++)

       {

              this->GetData(i,&a);

              j=i+1;

              while(j<=k)

              {

                     GetData(j,&b);

                     if(fabs(a.coe-b.coe)<1e-10 && a.exp==b.exp)

                     {

                            DeleteData(j);

                            k--;

                     }

                     else

                            j++;

              }

       }

}

void CMyLinkList::Sort(bool m)

{

       int i,j,k;

       DataType a,b;

       k=GetLength();

       for(i=1;i<k;i++)            //冒泡排序

       {

              for(j=1;j<=k-i;j++)

              {

                     GetData(j,&a);

                     GetData(j+1,&b);

                     if(a.exp<b.exp)

                     {

                            DeleteData(j);

                            DeleteData(j);

                            InsertData(a,j-1);

                            InsertData(b,j-1);

                     }

              }

       }

}

#include "iostream"

#include "MyLinkList.h"

using namespace std;

void main()

{

       CMyLinkList list1,list2,list3;

       cout<<"\n请输入第1个链表的数据:\n";

       list1.InputData();

       cout<<"\n第1个链表的当前情况是:\n";

       list1.Display();

       cout<<"\n请输入第2个链表的数据:\n";

       list2.InputData();

       cout<<"\n第2个链表的当前情况是:\n";

       list2.Display();

       list3=list1+list2;

       cout<<"\n合并后的链表是:\n";

       list3.Display();

       list3.DelRepeat();

       cout<<"\n删除重复元素后的链表是:\n";

       list3.Display();

       list3.Sort(false);

       cout<<"\n按降序排列元素后的链表是:\n";

       list3.Display();

}

实验4

实验目的:运用栈解决实际问题

实验准备

1. 复习栈的基本运算及其实现

2. 提取实验2或者实验3的结果,找到其中的SeqList或者LinkList文件

3. 阅读、理解中缀表达式转换成后缀表示法的算法

4. 将压缩包ex04.rar中的内容解压,双击文件夹中的dsw工程文件。当前工程中只有一个主函数文件main.cpp。

实验步骤及要求

1. 选取顺序结构者链式结构(任选其一)作为本题栈的物理结构,将相应的.cpp和.h文件复制到本工程的文件夹中。并修改.h文件中关于数据元素类型的定义,使其符合本实验的要求

2. 以CSeqList或者CLinkList为基类创建CStack派生类,并实现栈的基本运算。要求各函数的名称如下:

       bool GetTop(DataType *q);   //取栈顶元素

       bool Pop(DataType *q);        //退栈

       bool Push(DataType x);         //进栈

       CStack();                             //构造函数,用于创建空栈

3. 将主程序文件expchg函数补充完整,使得程序可以正确运行。

//以下是关于数据元素的类型定义,请根据实际情况修改

typedef struct datatype

{

       char varible;

} DataType;

typedef DataType SeqNode;

//以下是关于SeqList类型的声明

class CSeqList 

{

public:

       virtual bool DeleteData(int i);                            //删除顺序表的第i号元素

       virtual bool GetData(int i,SeqNode *q);              //取顺序表的第i号元素,存放到q所指向的位置

       virtual void Empty();                                        //将当前顺序表置为空表

       virtual bool InsertData(SeqNode x,int i);     //将新元素x插入到顺序表的第i号位置

       CSeqList& operator=(const CSeqList &x);          //重载赋值运算符

       virtual int GetLength();  //取表长

       virtual bool IsFull();             //判断表是否已满

       virtual bool IsEmpty();         //判断表是否为空

       CSeqList(int maxlen);

       CSeqList(CSeqList &x);        //拷贝构造函数

       virtual ~CSeqList();

private:

       int m_MaxLength;                //最大表长

       int m_CurLength;                 //当前表长

       SeqNode *m_List;                //初始化时指向申请的空间,存放表的各个元素

};

#include "SeqList.h"

#include "iostream.h"

#include "windows.h"

#include "math.h"

//构造函数

CSeqList::CSeqList(int maxlen)

{

       if(maxlen<=0)

       {

              cout<<"构造函数创建顺序表失败:表中最多存储元素数量必须是正数\n";

              exit(1);

       }

       m_List=new SeqNode[maxlen];

       if(m_List==NULL)

       {

              cout<<"构造函数创建顺序表失败:内存空间不够\n";

              exit(1);

       }

       m_CurLength=0;

       m_MaxLength=maxlen;

}

//拷贝构造函数

CSeqList::CSeqList(CSeqList &x)

{

       int i;

       m_MaxLength=x.m_MaxLength;

       m_List=new SeqNode[m_MaxLength];

       if(m_List==NULL)

       {

              cout<<"拷贝构造函数创建顺序表失败:内存空间不够\n";

              exit(1);

       }

       m_CurLength=x.m_CurLength;

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

              m_List[i]=x.m_List[i];

}

//析构函数,清理内存

CSeqList::~CSeqList()

{

       delete m_List;

}

//判空

bool CSeqList::IsEmpty()

{

       return m_CurLength==0;

}

//判满

bool CSeqList::IsFull()

{

       return m_CurLength==m_MaxLength;

}

//取表长

int CSeqList::GetLength()

{

       return m_CurLength;

}

//从键盘输入数据存入顺序表中

//DEL void CSeqList::InputData()

//DEL {

//DEL     int x1,x2;

//DEL     cout<<"请每次输入系数和指数,用空格分隔,输入两个值均<0表示输入结束\n";

//DEL     while(m_CurLength<m_MaxLength)

//DEL     {

//DEL            cout<<"List["<<m_CurLength<<"] : ";

//DEL            x1=x2=-1;

//DEL            cin>>x1;

//DEL            cin>>x2;                             //输入两个数值

//DEL            if(x1<0 && x2<0)

//DEL                   break;                                 //如果两个值都<0则表示输入完毕

//DEL            m_List[m_CurLength].coe=x1;

//DEL            m_List[m_CurLength].exp=x2;     //否则将这两个值存入顺序表

//DEL            m_CurLength++;

//DEL     }

//DEL }

//重载赋值运算符

CSeqList& CSeqList::operator =(const CSeqList& x)

{

       int i;

       m_MaxLength=x.m_MaxLength;

       m_List=new SeqNode[m_MaxLength];

       if(m_List==NULL)

       {

              cout<<"=重载时创建顺序表失败:内存空间不够\n";

              exit(1);

       }

       m_CurLength=x.m_CurLength;

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

              m_List[i]=x.m_List[i];

       return *this;

}

//将新元素x插入到顺序表的第i号位置

bool CSeqList::InsertData(SeqNode x, int i)

{

       int j,k=GetLength();

       if(IsFull() || i<0 || i>k+1)

              return false;

       for(j=k;j>i;j--)

              m_List[j]=m_List[j-1];

       m_List[i]=x;

       m_CurLength++;

       return true;

}

//将当前顺序表置为空表

void CSeqList::Empty()

{

       m_CurLength=0;

}

//取顺序表的第i号元素,存放到q所指向的位置

bool CSeqList::GetData(int i, SeqNode *q)

{

       int k=GetLength();

       if(i<0 || i>=k)

              return false;

       *q=m_List[i];

       return true;

}

//删除顺序表的第i号元素

bool CSeqList::DeleteData(int i)

{

       int j,k=GetLength();

       if(i<0 || i>=k)

              return false;

       for(j=i;j<k-1;j++)

              m_List[j]=m_List[j+1];

       m_CurLength--;

       return true;

}

#include "Stack.h"

CStack::CStack(int n):CSeqList(n)

{

}

CStack::~CStack()

{

}

void CStack::Push(DataType x)

{

       int k;

       k=this->GetLength();

       this->InsertData(x,k);

}

bool CStack::GetTop(DataType *q)

{

       int k;

       if(IsEmpty())

              return false;

       else

       {

              k=GetLength();

              GetData(k-1,q);

              return true;

       }

}

bool CStack::Pop(DataType *q)

{

       int k;

       if(IsEmpty())

              return false;

       else

       {

              k=GetLength();

              GetData(k-1,q);

              DeleteData(k-1);

              return true;

       }

}

#include "Stack.h"

#include "stdio.h"

void expchg(char* s1, char *s2)

{

       CStack st;

       int i,j;

//此处添加临时使用的变量

       DataType x;

       for(i=j=0;s1[i]!='\0';i++)

       {

              if(s1[i]>='A' && s1[i]<='Z')         //如果当前字符s1[i]是变量,即s1[i]是大写字母

              {

                     s2[j++]=s1[i];                      //将大写字母直接存放到s2中

              }

              else if(s1[i]=='+' || s1[i]=='-' || s1[i]=='*' || s1[i]=='/')    //如果当前字符s1[i]是运算符

              {

//此处添加针对运算符的处理,由于优先级只有两级,只需要区分加减号和乘除号即可

                     if(s1[i]=='+' || s1[i]=='-')

                     {

                            while(!st.IsEmpty())             //退栈,直到栈空或者栈顶是'('

                            {

                                   st.GetTop(&x);

                                   if(x.varible=='(')

                                          break;

                                   s2[j++]=x.varible;

                                   st.Pop(&x);

                            }

                            x.varible=s1[i];

                            st.Push(x);

                     }

                     else

                     {

                            while(!st.IsEmpty())             //退栈,直到栈空或者栈顶是'('

                            {

                                   st.GetTop(&x);

                                   if(x.varible=='(' || x.varible=='+' || x.varible=='-')

                                          break;

                                   s2[j++]=x.varible;

                                   st.Pop(&x);

                            }

                            x.varible=s1[i];

                            st.Push(x);

                     }

              }

              else if(s1[i]=='(')                                //如果当前字符s1[i]是左括号'('

              {

                     x.varible=s1[i];                    //进栈

                     st.Push(x);

              }

              else if(s1[i]==')')                                //如果当前字符s1[i]是右括号')'

              {

//此处添加针对右括号')'的处理

                     while(!st.IsEmpty())             //退栈,直到栈空或者栈顶是'('

                     {

                            st.Pop(&x);

                            if(x.varible=='(')

                                   break;

                            s2[j++]=x.varible;

                     }

                     if(st.IsEmpty())

                     {

                            printf("该表达式有错!\n");

                            return;

                     }

              }

              else                                                   //当前字符是除了以上情况外的其它符号

              {

                     printf("该表达式有错!\n");

                     return;

              }

       }

       while(!st.IsEmpty())             //退栈,直到栈空或者栈顶是'('

       {

              st.Pop(&x);

              if(x.varible=='(')

              {

                     printf("该表达式有错!\n");

                     return;

              }

              s2[j++]=x.varible;

       }

       s2[j]=0;                                             //转换结束,为转换结果字符串添加结束符

}

void main()

{

       char buf1[]="A*(B+C-A/(B-C))",buf2[100]={0};

//     char buf1[]="A*B+(",buf2[100]={0};

       expchg(buf1,buf2);

       printf("转换结果 : %s\n",buf2);

}

实验5 二叉树

实验目的:掌握二叉树的存储方法及Huffman编码原理

实验准备

1. 复习二叉树存储方法,重点是存储Huffman树所使用的父、子指针存储法

2. 掌握Huffman编码原理

3. 掌握在已知Huffman树的情况下,原文与Huffman编码的转换规则

4. 将压缩包ex05.rar中的内容解压,双击文件夹中的dsw工程文件。当前工程中只有一个主函数文件main.cpp,查看该文件中的内容。

实验步骤及要求

1. 将选择最小值的函数SelectMin和生成哈夫曼编码的函数HuffCode补充完整,使得程序可以运行。注意程序中用于存放哈夫曼树的数组包含2n-1个结点,使用了0号结点,与教材上的算法稍有不同。

2. 在生成哈夫曼编码的函数HuffCode中添加代码,计算并显示平均编码长度。

3. 在解码函数Decode中添加代码,使得程序运行后能够显示出主函数main中的一个编码对应的原文是什么。注意:正确的原文是HGJAEIJBBADACBH。

#include "iostream.h"

#include "windows.h"

#include "string.h"

typedef struct datatype

{

       char name;                    //使用的字符

       int count;               //使用的次数或者频率

       char code[15];        //Huffman码

       int left,right,parent;       //左子、右子、父结点的下标

} HNode;

HNode *node;

int count;

//根据整型数组的值产生n个结点作为叶结点,以及n-1个结点作为中间结点

void GetData()

{

       int buf[]={23,126,322,45,18,25,187,21,216,17}; //前若干个字母分别使用了多少次

       int i,k;

       k=sizeof(buf)/sizeof(int);

       node=new HNode[k+k+1];           //申请2n+1个结点,前n个结点为外部结点/叶结点

       if(node==NULL)

       {

              cout<<"申请内存失败!\n";

              exit(1);

       }

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

       {

              node[i].name=65+i;

              node[i].count=buf[i];                          //使用次数

              node[i].left=node[i].right=node[i].parent=-1;             //先将左右子、父结点指针置空

       }

       count=k;

}

//在前k号下标中找父指针为空的元素的最小值,函数值为下标

int SelectMin(int k)

{

       int i,t;

       t=0;

       while(node[t].parent!=-1)      //找第一个父指针为空(-1)的元素

              t++;

       for(i=t+1;i<k;i++)

              if(node[i].parent==-1 && node[i].count<node[t].count)     //如果第i#“未处理”并且比t#的次数更小

                     t=i;

       return t;                 //返回找到的最小值下标

}

//生成Huffman树及Huffman编码

void HuffCode()

{

       int i,j,k,t1,t2;

       char buf[15];

       //生成Huffman树

       for(i=1;i<count;i++)      //第i次生成中间结点,产生的结点是第count+i-1#下标

       {

              t1=SelectMin(count+i-1);             //前n+i-1个元素中找最小值

              node[t1].parent=count+i-1;           //填该结点的父指针,这同时表示该结点“已处理”

              t2=SelectMin(count+i-1);             //再次在前n+i-1个元素中找最小值,由于有“已处理”标记,不会与t1相同,这实际上是次小值

              node[t2].parent=count+i-1;           //填该结点的父指针,这同时表示该结点“已处理”

              node[count+i-1].count=node[t1].count+node[t2].count;      //中间结点的“使用次数”域是左右子的“使用次数”之和

              node[count+i-1].left=t1;

              node[count+i-1].right=t2;

              node[count+i-1].name='*';

              node[count+i-1].parent=-1;          //新生成的结点,其父指针为-1

       }

       //生成Huffman编码

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

       {

              t1=i;

              k=0;

              while(node[t1].parent!=-1)    //如果t1#结点有父结点

              {

                     t2=t1;                           //以t2记住房当前结点的下标

                     t1=node[t1].parent;        //以t1记父结点的下标,则t1为父、t2为子

                     if(node[t1].left==t2)      //如果t2#结点是t1#结点的左子

                            buf[k++]='0';

                     else                       //否则t2#结点一定是t1#结点的右子

                            buf[k++]='1';

                     for(j=0;j<k;j++)            //将得到的编码逆转

                            node[i].code[j]=buf[k-j-1];

                     node[i].code[k]=0;        //结束符

              }

              cout<<node[i].name<<':'<<node[i].code<<'\n';     //显示编码

       }

       //此处添加代码计算并显示平均编码长度

       t1=k=0;

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

       {

              t1+=strlen(node[i].code)*node[i].count;

              k+=node[i].count;

       }

       cout<<"平均编码长度="<<(double)t1/k<<endl<<endl;

       return;

}

//将Huffman编码还原成原文

void Decode(char *buf)

{

       //此处添加代码

       int i,k;

       i=0;

       k=count*2-2;         //根结点下标

       while(buf[i])          //当密码串未看完时

       {

              if(buf[i]=='0')

                     k=node[k].left;

              else

                     k=node[k].right;

              if(k<count)            //已经到叶结点

              {

                     cout<<node[k].name;

                     k=count*2-2;

              }

              i++;

       }

       cout<<"\n\n";

}

void main()

{

       char s[]="10110000101010101101101011011010101001001011011011110110111100101100";

       GetData();             //产生符号与次数的基本数据

       HuffCode();           //生成Huffman树及Huffman编码

       Decode(s);

}

实验6

实验目的:掌握图的存储方法及判断有无回路及求关键路径的算法

实验准备

1. 复习图的存储方法,重点是用三元组存储边的存储法。

2. 掌握深度优先遍历判断回路的原理,或者宽度优先遍历判断回路的原理。

3. 掌握求关键路径的算法,以及显示关键路径的算法

4. 将压缩包ex06.rar中的内容解压,双击文件夹中的dsw工程文件。当前工程中有一个主函数文件main.cpp,以及关于CGraph类的两个文件Graph.h和Graph.cpp,查看这些文件中的内容。

5. 仔细阅读CGraph.cpp文件中函数上方的说明,打开graph1.txt或者graph2.txt进行对照。这两个文件中的图均视为有向图。

实验步骤及要求

1. 工程中已经创建了CGraph类的Circle函数框架,该函数用于判断当前的图中是否含有回路,编写该函数的函数体,使得程序运行时可以显示出由graph1.txt生成的图中一条回路。

2. 由graph2.txt生成的图是没有回路的,试找出以0号顶点为源点、7号顶点为汇点的关键路径。工程中已经创建了求关键路径的函数Keypath,编写该函数的函数体即可。

#include "Graph.h"

#include "stdio.h"

#include "iostream.h"

#include "string.h"

//构造函数,创建一个空的图

CGraph::CGraph()

{

       m_Ver=NULL;

       m_Edge=NULL;

       m_VerCount=m_EdgeCount=0;

}

CGraph::~CGraph()

{

       if(m_Ver!=NULL)

              delete m_Ver;

       if(m_Edge!=NULL)

              delete m_Edge;

}

//从文本文件中读取图的顶点和边的数据

/*文件中的数据格式:

第1行为两个整数,用逗号分隔,分别表示顶点数和边数

第2行开始是各个顶点名称,每行一个字符串,串长不超过19,中间不得空行

顶点名称之后是边的三元组,是由逗号分隔的三个整数,分别表示边的起点、终点、权

*/

bool CGraph::CreatFrom(char *fn)

{

       FILE *fp;

       int c1=0,c2=0,i;

       fp=fopen(fn,"r");

       if(fp==NULL)

       {

              cout<<"打开文件["<<fn<<"]失败,不能创建图!\n";

              return false;

       }

       fscanf(fp,"%d,%d",&c1,&c2);

       if(c1<=0 || c2<=0)  //顶点数<=0或者边数<=0

       {

              cout<<"图文件中数据有错,不能创建图!\n";

              return false;

       }

       m_VerCount=c1;

       m_EdgeCount=c2;

       m_Ver=new Vertex[c1]; //申请存放顶点的空间

       m_Edge=new Edge[c2]; //申请存放边的空间

       if(m_Ver==NULL)

       {

              cout<<"申请存放顶点的空间失败,不能创建图!\n";

              return false;

       }

       if(m_Edge==NULL)

       {

              delete m_Ver;

              cout<<"申请存放边的空间失败,不能创建图!\n";

              return false;

       }

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

       {

              fscanf(fp,"%s",m_Ver[i].name);

              if(feof(fp) || strlen(m_Ver[i].name)==0)

              {

                     cout<<"图文件中数据有错,不能创建图!\n";

                     delete m_Ver;

                     delete m_Edge;

                     return false;

              }

       }

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

       {

              fscanf(fp,"%d,%d,%d",&m_Edge[i].v1,&m_Edge[i].v2,&m_Edge[i].weight); //读取一条边的三元组

              if(feof(fp) || m_Edge[i].v1<0 ||  m_Edge[i].v1>=c1 ||  m_Edge[i].v2<0

                     ||  m_Edge[i].v2>=c2 || m_Edge[i].weight<=0)

              {

                     cout<<"图文件中数据有错,不能创建图!\n";

                     delete m_Ver;

                     delete m_Edge;

                     return false;

              }

       }

       fclose(fp);

       return true;

}

//判断图中有没有回路,如果有回路则显示出一条回路

bool CGraph::Circle()

{

       int *visit,i,j,k,m,n,t;

       int *stack,top;

       visit=new int[m_VerCount];

       stack=new int[m_VerCount];

       if(visit==NULL || stack==NULL)  //如果申请空间失败

       {

              cout<<"申请空间失败\n";

              return false;

       }

       top=-1;                                              //置空栈

       for(i=0;i<m_VerCount;i++)          //做"未访问"标记

              visit[i]=0;

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

              if(!visit[i])                           //找到一个未访问的顶点

              {

                     visit[i]=1;

                     stack[++top]=i;                    //进栈

                     while(top>=0)               //深度优先搜索

                     {

                            k=stack[top];         //取栈顶

                            for(j=0;j<m_EdgeCount;j++)

                                   if(m_Edge[j].v1==k && visit[m_Edge[j].v2]==0)     //找到一个与栈顶相邻的未访问的顶点

                                   {

                                          t=m_Edge[j].v2;

                                          visit[t]=1;                     //做访问标记

                                          stack[++top]=t;             //进栈

                                          for(n=0;n<m_EdgeCount;n++)            //找回路:如果存在从m_Edge[j].v2出发并且指向栈内元素的边,则有回路

                                          {

                                                 if(m_Edge[n].v1==t && visit[m_Edge[n].v2])   //如果从t出发的边所指向的顶点已访问,则检查它是否在栈内

                                                 {

                                                        for(m=0;m<top;m++)

                                                               if(stack[m]==m_Edge[n].v2)

                                                                      break;

                                                        if(m<top)              //如果在栈内,则有回路

                                                        {

                                                               for(;m<=top;m++)

                                                                      cout<<m_Ver[stack[m]].name<<' ';

//                                                                    cout<<stack[m]<<' ';

                                                               cout<<m_Ver[m_Edge[n].v2].name<<endl;

//                                                             n=j=m_EdgeCount;              //用于终止所有循环

//                                                             i=m_VerCount;

//                                                             top=-1;

                                                        }

                                                 }

                                          }

                                          break;

                                   }

                            if(j==m_EdgeCount)            //找不到与栈顶相邻且未访问的顶点

                                   top--;

                     }

              }

       delete visit;

       delete stack;

       if(i==m_VerCount)

              return false;

       else

              return true;

}

//释放图的存放空间,并置为空图

void CGraph::Empty()

{

       if(m_Ver!=NULL)

              delete m_Ver;

       if(m_Edge!=NULL)

              delete m_Edge;

       m_Ver=NULL;

       m_Edge=NULL;

       m_VerCount=m_EdgeCount=0;

}

//求以start为源点、以end为汇点的关键路径

void CGraph::KeyPath(int start, int end)

{

       int i,j,k;

       int *dist,*prec,*que,*degree,*visit,qf=0,qr=-1;

       visit=new int[m_VerCount];                //存放"已访问"

       dist=new int[m_VerCount];                 //存放"代价"

       prec=new int[m_VerCount];                //存放"前趋"

       degree=new int[m_VerCount];                    //存放当前的入度

       que=new int[m_VerCount];                 //队列

       if(dist==NULL || prec==NULL || degree==NULL || que==NULL)      //如果申请空间失败

       {

              cout<<"申请空间失败\n";

              return;

       }

       for(i=0;i<m_VerCount;i++)                 //初始化

       {

              visit[i]=dist[i]=0;                        //各顶点置"未访问",当前代价置0

              prec[i]=start;                               //所有顶点的前趋都置为起点

              degree[i]=0;

       }

       for(i=0;i<m_EdgeCount;i++)              //统计入度

              degree[m_Edge[i].v2]++;

       if(degree[start]>0)

       {

              cout<<"起点入度不为0!\n";

              return;

       }

       que[++qr]=start;                                 //起点进队列

       visit[start]=1;                                     //起点置"已访问"

/*    for(i=0;i<m_EdgeCount;i++)

              if(m_Edge[i].v1==start)

              {

                     degree[m_Edge[i].v2]--;              //起点的各个直接后继入度-1

                     dist[m_Edge[i].v2]=m_Edge[i].weight;       //代价置为相应边上的权值

              }

*/

       while(qf<=qr)                                    //当队列不空时

       {

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

                     if(m_Edge[i].v1==que[qf])

                     {

                            k=m_Edge[i].v2;

                            degree[k]--;                  //直接后继入度-1

                            if(degree[k]==0)

                            {

                                   que[++qr]=k;         //入度为0,进队列

                                   visit[k]=1;                    //已处理

                            }

                            if(dist[k]<dist[que[qf]]+m_Edge[i].weight) //如果找到一条更长的路径

                            {

                                   dist[k]=dist[que[qf]]+m_Edge[i].weight;     //更新代价

                                   prec[k]=que[qf];                                              //更新前趋

                            }

                     }

              qf++;                                                //队首元素已处理完,出队列

       }

       if(qf<m_VerCount) //如果还有未处理的顶点

              cout<<"图中存在环!\n";

       else                       //否则,显示关键路径

       {

              k=0;

              cout<<m_Ver[end].name;

              i=end;

              while(i!=start)

              {

                     for(j=0;j<m_EdgeCount;j++)

                            if(m_Edge[j].v1==prec[i] && m_Edge[j].v2==i)

                            {

                                   cout<<" <--("<<m_Edge[j].weight<<")-- ";

                                   k+=m_Edge[j].weight;

                                   break;

                            }

                     i=prec[i];

                     cout<<m_Ver[i].name;

              }

              cout<<"\nTotal : "<<k<<"\n\n";

       }

       delete visit;

       delete dist;

       delete prec;

       delete degree;

       delete que;

}

#include "iostream.h"

#include "graph.h"

typedef struct vertex

{

       char name[20];

} Vertex;        //顶点类型

typedef struct edge

{

       int v1,v2;

       int weight;

} Edge;                 //边的类型

class CGraph 

{

public:

       CGraph();

       virtual ~CGraph();

public:

       void KeyPath(int start,int end);     //求以start为源点、以end为汇点的关键路径

       void Empty();                      //释放图的存放空间,并置为空图

       bool Circle();                       //判断图中有没有回路

       bool CreatFrom(char *fn);    //从文件中读取数据创建图

private:

       Vertex *m_Ver;             //指向存放顶点的数组

       int m_VerCount;            //顶点数量

       Edge *m_Edge;            //指向存放边的三元组

       int m_EdgeCount;  //边的数量

};

void main()

{

       CGraph g;

       cout<<"判断g1是否有回路\n\n";

       g.CreatFrom("graph1.txt");

       g.Circle();

       g.Empty();

       cout<<"\n\n====================\n\n求g2的关键路径\n";

       g.CreatFrom("graph2.txt");

       if(g.Circle())

              cout<<"该图存在回路,无法寻找关键路径!\n";

       else

              g.KeyPath(0,7);     //求0#顶点到7#顶点的关键路径

}

实验7 查找

实验目的:掌握顺序查找、二分查找、线性插值查找算法并编程实现

实验准备

1. 阅读顺序查找、二分查找、线性插值查找算法,以及三种算法的时间复杂度

2. 将压缩包ex07.rar中的内容解压,双击文件夹中的dsw工程文件。当前工程中包含三个文件:关于线性表的SeqList.h和SeqList.cpp,以及主函数文件main.cpp。查看各个文件中的内容。

3. 仔细阅读SeqList类的RandomData函数,该函数能够按照顺序表的最大容量无重复地产生数据,并将数据从小到大排列,理解该函数产生数据的方法。

实验步骤及要求

CSeqList类中有三个成员函数框架Search1、Search2和Search3,在其中编写代码,分别实现对顺序表的顺序查找、二分查找、线性插值查找,针对二分查找和线性插值查找函数,还要显示出分别用查找目标与顺序表中的哪些下标的元素进行了比较。运行程序并查看结果。希望二分查找和线性插值查找的运行效果类似于下图:

#include "SeqList.h"

#include "iostream"

#include "windows.h"

#include "math.h"

using namespace std;

//构造函数

CSeqList::CSeqList(int maxlen)

{

       if(maxlen<=0)

       {

              cout<<"构造函数创建顺序表失败:表中最多存储元素数量必须是正数\n";

              exit(1);

       }

       m_List=new SeqNode[maxlen];

       if(m_List==NULL)

       {

              cout<<"构造函数创建顺序表失败:内存空间不够\n";

              exit(1);

       }

       m_CurLength=0;

       m_MaxLength=maxlen;

}

//析构函数,清理内存

CSeqList::~CSeqList()

{

       delete m_List;

}

//判空

bool CSeqList::IsEmpty()

{

       return m_CurLength==0;

}

//判满

bool CSeqList::IsFull()

{

       return m_CurLength==m_MaxLength;

}

//取表长

int CSeqList::GetLength()

{

       return m_CurLength;

}

int CSeqList::Search1(int k)

{

//此处编写代码,功能是用顺序检索法在当前顺序表中查找是否存在key域的值等于k的元素

       int i;

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

              if(m_List[i].key==k)

                     break;

       if(i<m_CurLength)

              return i;

       else

              return -1;

}

int CSeqList::Search2(int k)

{

//此处编写代码,功能是用二分法在当前顺序表中查找是否存在key域的值等于k的元素

//二分查找法还要显示分别与哪些元素进行了比较

       int a,b,d=-1,m;

       a=0;

       b=m_CurLength-1;

       while(a<=b)

       {

              m=(a+b)/2;

              cout<<"List["<<m<<"]="<<m_List[m].key<<endl;

              if(m_List[m].key==k)

              {

                     d=m;

                     break;

              }

              else if(m_List[m].key>k)             //往左继续查找

                     b=m-1;

              else

                     a=m+1;

       }

       return d;

}

int CSeqList::Search3(int k)

{

//此处编写代码,功能是用线性插值法在当前顺序表中查找是否存在key域的值等于k的元素

//线性插值法还要显示分别与哪些元素进行了比较

       int a,b,d=-1,m;

       a=0;

       b=m_CurLength-1;

       while(a<=b)

       {

              m=a+(b-a+1)*(k-m_List[a].key)/(m_List[b].key-m_List[a].key);

              if(m<a || m>b)

                     break;

              cout<<"List["<<m<<"]="<<m_List[m].key<<endl;

              if(m_List[m].key==k)

              {

                     d=m;

                     break;

              }

              else if(m_List[m].key>k)             //往左继续查找

                     b=m-1;

              else

                     a=m+1;

       }

       return d;

}

//按顺序表的最大容量无重复地产生数据,并将数据由小到大排列

void CSeqList::RandomData()

{

       int i=0,j,k,R=10000;

       while(i<m_MaxLength)               //产生的数据还不到最大容量时循环

       {

              k=rand()%R;                              //产生一个数

              for(j=0;j<i;j++)                    //查看新产生的数在不在顺序表中

                     if(k==m_List[j].key)

                            break;

              if(j<i)                                        //如果j<i说明新产生的数在顺序表中,不添加

                     continue;

              j=i;

              while(j>0 && k<m_List[j-1].key) //从后往前找新产生的数应该添加到几号下标

              {

                     m_List[j]=m_List[j-1];   //将比新产生的数更大的数后移

                     j--;

              }

              m_List[j].key=k;                  //存放新产生的数

              itoa(k,m_List[j].name,10);    //在该数据元素的name域填一个字符串

              i++;                                    //计数值加1

       }

       m_CurLength=i;

}

//以下是关于数据元素的类型定义,请根据实际情况修改

typedef struct datatype

{

       int key;

       char name[20];

} DataType;

typedef DataType SeqNode;

//以下是关于SeqList类型的声明

class CSeqList 

{

public:

       void RandomData();

       int Search1(int k);

       int Search2(int k);

       int Search3(int k);

       virtual int GetLength();  //取表长

       virtual bool IsFull();             //判断表是否已满

       virtual bool IsEmpty();         //判断表是否为空

       CSeqList(int maxlen);

       virtual ~CSeqList();

private:

       int m_MaxLength;                //最大表长

       int m_CurLength;                 //当前表长

       SeqNode *m_List;                //初始化时指向申请的空间,存放表的各个元素

};

#include "iostream"

#include "seqlist.h"

#include "windows.h"

using namespace std;

void main()

{

       CSeqList lst(5000);

       int m,x;

       srand(GetCurrentTime());

       lst.RandomData();

       while(1)

       {

              x=-1;

              cout<<"请输入要查找的整数(负数表示结束查找):";

              cin>>x;

              if(x<0)

                     break;

              cout<<"============= Search 1 =============\n";

              m=lst.Search1(x);

              if(m<0)

                     cout<<"表中不存在整数["<<x<<"]\n";

              else

                     cout<<"整数["<<x<<"]在表中的第"<<m<<"号下标\n";

              cout<<"+++++++++++++ Search 2 +++++++++++++\n";

              m=lst.Search2(x);

              if(m<0)

                     cout<<"表中不存在整数["<<x<<"]\n";

              else

                     cout<<"整数["<<x<<"]在表中的第"<<m<<"号下标\n";

              cout<<"************* Search 3 *************\n";

              m=lst.Search3(x);

              if(m<0)

                     cout<<"表中不存在整数["<<x<<"]\n";

              else

                     cout<<"整数["<<x<<"]在表中的第"<<m<<"号下标\n";

       }

}

实验8 排序

实验目的:掌握各种排序算法,并从时间复杂度和空间复杂度方面进行比较

实验准备

1. 掌握以下排序法:插入排序、选择排序、堆排序、冒泡排序、快速排序

2. 理解Shell排序和两路归并排序的原理。

3. 将压缩包ex08.rar中的内容解压,双击文件夹中的dsw工程文件。当前工程中有一个主函数文件main.cpp,以及关于顺序表类CSeqList的两个文件SeqList.h和SeqList.cpp,查看这些文件中的内容。

4. 运行程序,观察结果。

5. 仔细阅读SeqList.cpp文件中关于Shell排序的ShellSort函数和关于两路归并排序的CombineSort函数,与这两种排序法的原理进行对照。注意体会这两个函数中是如何对比较次数和数据移动次数进行统计的。

实验步骤及要求

1. 为CSeqList类添加关于插入排序的成员函数,函数名自定,函数中除了完成排序操作之外,还要对比较次数和数据移动次数进行统计。

2. 在CSeqList类Sort函数的相应switch分支中添加调用命令,调用插入排序函数。

3. 运行程序,观察结果。把主函数main中顺序表的元素数量分别改为10、100、1000,再运行程序观察结果。

4. 类似地,对选择排序、堆排序、冒泡排序、快速排序完成上述三项工作。

预期main中设定数据量为1000时,程序运行结果如下:

注意,由于数据是随机产生,每次运行的统计结果会不同,但可以多次运行并比较各算法的比较次数和数据移动次数。

#include "SeqList.h"

#include "iostream.h"

#include "windows.h"

#include "math.h"

//构造函数

CSeqList::CSeqList(int maxlen)

{

       if(maxlen<=0)

       {

              cout<<"构造函数创建顺序表失败:表中最多存储元素数量必须是正数\n";

              exit(1);

       }

       m_List=new SeqNode[maxlen];

       m_Backup=new SeqNode[maxlen];

       if(m_List==NULL || m_Backup==NULL)

       {

              cout<<"构造函数创建顺序表失败:内存空间不够\n";

              exit(1);

       }

       m_CurLength=0;

       m_MaxLength=maxlen;

}

//析构函数,清理内存

CSeqList::~CSeqList()

{

       delete m_List;

}

//判空

bool CSeqList::IsEmpty()

{

       return m_CurLength==0;

}

//判满

bool CSeqList::IsFull()

{

       return m_CurLength==m_MaxLength;

}

//取表长

int CSeqList::GetLength()

{

       return m_CurLength;

}

//在顺序表中用随机值填满数据

void CSeqList::CreateData()

{

       int i;

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

       {

              m_List[i].key=m_Backup[i].key=rand();

       }

       m_CurLength=m_MaxLength;

}

//将顺序表恢复原有的数据

void CSeqList::Restore()

{

       int i;

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

              m_List[i]=m_Backup[i];

       m_CountCmp=m_CountMov=0;   //两个统计次数用的变量清0

}

//显示顺序表中的元素

void CSeqList::Display()

{

       int i;

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

              cout<<m_List[i].key<<' ';

       cout<<"\n\n";

}

//对顺序表按第k种算法排序

void CSeqList::Sort(int k)

{

       switch(k)

       {

       case 0:

              cout<<"\n========插入排序========\n";

              //此处添加调用“插入排序”函数的代码

              InsertSort();

              break;

       case 1:

              cout<<"\n========选择排序========\n";

              //此处添加调用“选择排序”函数的代码

              SelectSort();

              break;

       case 2:

              cout<<"\n========堆排序========\n";

              //此处添加调用“堆排序”函数的代码

              HeapSort();

              break;

       case 3:

              cout<<"\n========冒泡排序(改进版)========\n";

              //此处添加调用“冒泡排序(改进版)”函数的代码

              BubbleSort();

              break;

       case 4:

              cout<<"\n========快速排序========\n";

              //此处添加调用“快速排序”函数的代码

              QuickSort(0,m_CurLength-1);

              break;

       case 5:            //Shell排序

              cout<<"\n========Shell排序========\n";

              ShellSort();

              break;

       case 6:            //两路归并排序

              cout<<"\n========两路归并排序========\n";

              CombineSort();

              break;

       }

       Display();

       if(m_CountCmp>0 || m_CountMov>0)

       {

              cout<<"本次排序共进行了"<<m_CountCmp<<"次比较,数据元素移动了"<<m_CountMov<<"次\n";

              cout<<"移动次数/比较次数 = "<<(double)m_CountMov/m_CountCmp<<"\n";

       }

}

//Shell排序

void CSeqList::ShellSort()

{

       int i,j,d,k,n;

       SeqNode tmp;

       n=GetLength();

       d=n/2;                   //取步长为n/2

       while(d>0)

       {

              for(i=0;i<d;i++)                                 //i为各组的开始下标,即i#,i+d#,i+2d#,...

                     for(j=i+d;j<n;j+=d)

                     {

                            tmp=m_List[j];                           //取出待插入的元素,这是一次数据移动

                            for(k=j;k>=d;k-=d)

                            {

                                   m_CountCmp++;   //每循环一次,比较次数+1

                                   if(m_List[k-d].key<=tmp.key)      //比较

                                          break;

                                   m_List[k]=m_List[k-d]; //移动数据

                                   m_CountMov++;    //每循环一次,移动次数+1

                            }

                            m_CountMov+=2;         //关于tmp的两次移动次数

                            m_List[k]=tmp;                           //数据填入本组中的正确位置,这是一次数据移动

                     }

                     d/=2;              //步长减半

       }

}

//两路归并排序

void CSeqList::CombineSort()

{

       int i,j,k1,k2,k3,n;

       SeqNode *tmp;

       n=GetLength();

       tmp=new SeqNode[n];

       if(tmp==NULL)

       {

              cout<<"归并排序申请内存失败!\n\n";

              return;

       }

       for(i=1;i<n;i*=2)                 //归并段的长度

       {

              for(j=0;j<n;j+=i*2)       //一轮归并时对组扫描,j为每一组两个归并段的起始下标

              {

                     k1=j;                            //第1归并段的起始下标

                     k2=j+i;                         //第2归并段的起始下标

                     k3=k1;                         //归并后存放的起始下标

                     while(k1<n && k2<n && k1<j+i && k2<j+i*2) //两个归并段都还有元素时

                     {

                            m_CountCmp++;          //比较次数+1

                            if(m_List[k1].key<m_List[k2].key)

                                   tmp[k3++]=m_List[k1++];           //取第1归并段的当前元素

                            else

                                   tmp[k3++]=m_List[k2++];           //取第2归并段的当前元素

                     }

                     if(k1<n && k1<j+i)      //如果第1归并段还有元素

                     {

                            while(k1<n && k1<j+i)        //将第1归并段的剩余元素复制到目标数组

                                   tmp[k3++]=m_List[k1++];

                     }

                     else

                     {

                            while(k2<n && k2<j+i*2)    //将第2归并段的剩余元素复制到目标数组

                                   tmp[k3++]=m_List[k2++];

                     }

              }

              for(j=0;j<n;j++)

                     m_List[j]=tmp[j];

              m_CountMov+=n*2;            //移动次数+2n:每个元素从m_List数组移动到tmp数组,再把tmp整体复制回m_List

       }

       delete tmp;

}

void CSeqList::InsertSort()

{

       int i,j;

       SeqNode tmp;

       for(i=1;i<m_CurLength;i++)

       {    

              tmp=m_List[i];

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

              {

                     m_CountCmp++;

                     if(m_List[j-1].key>tmp.key)

                     m_List[j]=m_List[j-1];

                     else

                            break;

                     m_CountMov++;

              }           

       m_List[j]=tmp;

       m_CountMov+=2;

       }                  

}

void CSeqList::SelectSort()

{

       int i,j,k;

       SeqNode tmp;

       for(i=1;i<m_CurLength;i++)

       {

              k=0;

              m_CountCmp++;

              for(j=1;j<=m_CurLength-i;j++)               

                     if(m_List[j].key>m_List[k].key)

                            k=j;

                     tmp=m_List[k];

                     m_List[k]=m_List[m_CurLength-i];

                     m_List[m_CurLength-i]=tmp;

                     m_CountMov+=3;

       }

}

void CSeqList::HeapSort()

{

    DataType temp;

       int i;

       int n=m_CurLength;

       for(i=(n-1)/2;i>=0;i--)

              MakeHeap(n,i);

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

       {

       temp=m_List[i];

       m_List[i]=m_List[0];

          m_List[0]=temp;

       MakeHeap(i,0);

       }

}

void CSeqList::BubbleSort()

{

       int i,j,m;

       SeqNode tmp;

       i=m_CurLength-1;

       while(i>0)

       { 

              m=-1;

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

                     if(m_List[j].key > m_List[j+1].key) 

                     {    

                      m_CountCmp++;

                         tmp=m_List[j];

                         m_List[j]=m_List[j+1];

                         m_List[j+1]=tmp;         

                         m=j;        

                         m_CountMov+=3;

                     }

              i=m;

       }

}

void CSeqList::QuickSort(int left, int right)

{

       int i,j,k;

       DataType tmp;

       if(right-left>0)

       {    

              i=left; j=right; k=1;

              tmp=m_List[i];

              while(i<j)                     

              {  

                     if(k==1) 

                     {

                            while(i<j &&m_List[j].key>=tmp.key)

                                   j--;

                            if(i<j)

                            {

                                   m_List[i]=m_List[j]; k=0;

                            }

                     }

                     else

                     {    

                            while(i<j &&m_List[i].key<=tmp.key)

                            i++;

                            if(i<j)

                            {

                                   m_List[j]=m_List[i]; k=1;

                            }

                     }

              }

              m_List[i]=tmp;     

     QuickSort(left,i-1);

        QuickSort(i+1,right);

       }

}

void CSeqList::MakeHeap(int n, int k)

{     DataType temp;

       int i;

       while( k*2+1<n&&m_List[k].key<m_List[2*k+1].key||m_List[k].key<m_List[2*k+2].key)

       {     i=k*2+1; //以i记左子下标,此时左子一定存在

              if(i+1<n&&m_List[i+1].key>m_List[i].key )//右子存在且右子>左子)

                     i++; //满足if的条件则以i记右子下标

              temp=m_List[i];

              m_List[i]=m_List[k];

       m_List[k]=temp;    //交换

              k=i;        //以交换到下层的结点为“本结点”

       }

}

//以下是关于数据元素的类型定义,请根据实际情况修改

typedef struct datatype

{

       int key;                        //排序码

       char name[20];

} DataType;

typedef DataType SeqNode;

//以下是关于SeqList类型的声明

class CSeqList 

{

public:

       void MakeHeap(int n,int k);

       void QuickSort(int left,int right);

       void BubbleSort();

       void HeapSort();

       void SelectSort();

       void InsertSort();

       void CombineSort();                    //两路归并排序

       void ShellSort();                  //Shell排序

       void Sort(int k);                   //对顺序表按第k种算法排序

       void Restore();                            //将顺序表恢复原有的数据

       void CreateData();                //在顺序表中用随机值填满数据

       virtual int GetLength();  //取表长

       virtual bool IsFull();             //判断表是否已满

       virtual bool IsEmpty();         //判断表是否为空

       void Display();                            //显示顺序表的各个元素

       CSeqList(int maxlen);

       virtual ~CSeqList();

private:

       int m_MaxLength;                //最大表长

       int m_CurLength;                 //当前表长

       SeqNode *m_List;                //初始化时指向申请的空间,存放表的各个元素

       SeqNode *m_Backup;                  //初始化时指向申请的空间,备份

       int m_CountCmp;                        //比较次数

       int m_CountMov;                        //元素移动的次数

};

#include "SeqList.h"

#include "iostream.h"

#include "windows.h"

void main()

{

       int i;

       CSeqList myList(10);

       srand(GetCurrentTime());

       myList.CreateData();            //用随机数填满顺序表

       for(i=0;i<=6;i++)                 //依次调用7种算法进行排序

       {

              myList.Restore();          //恢复最初产生的随机数

              myList.Sort(i);

                      //用第i种方法排序

       }

}

更多相关推荐:
数据结构上机实验报告

实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删除的基本操作算法实验内容1顺序表的实践1建立4个元素的顺序表ssqlist123...

数据结构上机实验答案

数据结构实验指导书答案实验一1请编写函数intfunintaintb函数的功能是判断两个指针a和b所指存储单元的值的符号是否相同若相同函数返回1否则返回0这两个存储单元中的值都不为0在主函数中输入2个整数调用函...

数据结构上机实验报告

空间数据结构基础上机实验报告20xx姓名班级地信121学号07122857环境与测绘学院级实验报告1C面向对象程序设计范例1二维坐标点point的C描述实验目的用面向对象的方法定义一个简单的抽象数据结构本例实验...

数据结构第一次上机实验报告

数据结构第一次上机实验报告线性表实验要求1实现顺序表结构的创建插入删除查找等操作2利用上述顺序表操作实现如下程序建立两个顺序表表示的集合集合中无重复的元素并求这样的两个集合的并交和源程序C实现visualstu...

数据结构上机实验报告

计算机科学与技术学院《数据结构教程》实验报告(20##/20##学年第2学期)学生姓名:学生专业:学生班级:学生学号:20##/6/5实验报告一.设计人员相关信息姓名:学号:班级:设计日期:20##年6月5日上…

数据结构上机报告实验一

《数据结构》上机报告_______年____月____日姓名__________学号___________同组成员___________1.实验题目及要求实验一、编写一个程序,实现顺序表的各种基本运算,并在此基…

数据结构实验报告格式1

数据结构实验报告格式实验1线性表的基本操作一实验目的1掌握使用VC上机调试线性表的基本方法2掌握线性表的基本操作插入删除查找等运算在顺序和链式存储结构上的实现二实验内容线性表的基本操作的实现三实验要求1认真阅读...

《数据结构》上机实验要求 (1)

数据结构与算法课程实验内容与要求一课程简介本课程着重讲述线性结构树型结构图等典型数据结构的逻辑特点存储结构及其相应的基本算法各种查找算法典型内部排序算法二实验的作用地位和目的数据结构是一门技术基础课通过实验深刻...

数据结构上机实验指导书

计算机系第一部分算法与数据结构课程实验概述一实验目的算法与数据结构是计算机专业的主干课程和必修课程之一其目的是让大家学习分析和研究数据对象特征掌握数据组织方法和计算机的表示方法以便选择合适的数据逻辑结构和存储结...

太原理工大学数据结构实验报告

数据结构实验报告课程名称数据结构实验项目线性表树图查找内排序实验地点专业班级物联网学号学生姓名指导教师周杰伦20xx年月日实验一线性表目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结...

数据结构实验报告

专业年级学号学生姓名指导老师华中师范大学信息管理系编数据结构实验报告I实验要求1每次实验中有若干习题每个学生至少应该完成其中的两道习题2上机之前应作好充分的准备工作预先编好程序经过人工检查无误后才能上机以提高上...

数据结构树的实验报告

数据结构实验报告目的要求1掌握二叉树的存储实现2掌握二叉树的遍历思想3掌握二叉树的常见算法的程序实现实验内容1输入字符序列建立二叉链表2中序遍历二叉树递归算法3中序遍历二叉树非递归算法最好也能实现先序后序非递归...

数据结构上机实验报告(39篇)