实验报告
（2015 / 2016学年第二学期）
课程名称数据结构A
实验名称图的基本运算及飞机换乘次数最少问题
实验时间2016 年 5 月19 日
指导单位计算机科学与技术系
指导教师骆健
学生姓名班级学号
学院(系) 管理学院专业信息管理与信息系统
实习题名:图的基本运算
班级姓名学号日期2016.05.19
一、问题描述
验证教材中关于在邻接矩阵和邻接表两种不同的储存结构上实现图的基本运算的算法(见程序9.1~程序9.8)，在邻接矩阵存储结构上实现图的深度和广度优先遍历算法，设计主函数，测试上述运算。
二、概要设计
文件graph.cpp中在该文件中定义图数据结构的抽象模板类Graph。邻接矩阵类MGraph是从抽象类Graph派生得来，邻接表类LGraph也是从抽象类Graph派生得来。
主函数的代码如图所示。
三、详细设计
1.类和类的层次设计
程序定义了Graph类，以及邻接矩阵类MGraph和邻接表类LGraph以及循环列表类SeqQueue。邻接矩阵类MGraph继承了Graph的数据成员n和e，重载了Graph的纯虚函数。保护数据成员T** a指向动态生成的二维数组，用以存储邻接矩阵。邻接表类LGraph也继承了Graph的数据成员n和e及重载了Graph的纯虚函数，边结点由类ENode定义，每个结点有三个域adjVex、w和nextArc。邻接表的表头组成为一维数组，a是指向该数组的指针。
（a ）循环队列类
（b ）模版类Graph ， MGraph 和LGraph
SeqQueue -int front, rear; -int maxSize; -BTNode
+SeqQueue(int mSize); +~SeqQueue(){delete []q;}
+bool IsEmpty() const{return front == rear;}
+bool IsFull() const{return (rear + 1) % maxSize == front;}
+bool Front(BTNode
+void Clear(){front = rear = 0;}
MGraph
#T **a; #T noEdge;
#void DFS(int v,bool *visited); #void BFS(int v,bool *visited); +MGraph(int mSize,const T& noedg); +~MGraph();
+ResultCode Insert(int u,int v,T&w); +ResultCode Remove(int u,int v); +bool Exist(int u,int v)const; +void DFS(); +void BFS();
T
LGraph #ENode
+LGraph(int mSize); +~LGraph();
+ResultCode Insert(int u,int v,T&w); +ResultCode Remove(int u,int v); +bool Exist(int u,int v)const;
T
Graph #int n,e;
+virtual ResultCode Insert(int u,int v,T&w)=0; +virtual ResultCode Remove(int u,int v)=0; +virtual bool Exist(int u,int v)const=0;
T
T
2.核心算法
深度优先搜索用栈来实现：
1)把根节点压入栈中
2)每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并
把这个元素记为它下一级元素的前驱
3)找到所要找的元素时结束程序
4)如果遍历整个树还没有找到，结束程序
广度优先搜索使用队列来实现：
1)把根节点放到队列的末尾
2)每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队
列的末尾。并把这个元素记为它下一级元素的前驱
3)找到所要找的元素时结束程序
4)如果遍历整个树还没有找到，结束程序
DFS()
BFS()
四、程序代码
template
void MGraph
{
bool *visited=new bool[n];
for (int i=0;i visited[i]=false; for(i=0;i if(!visited[i]) DFS(i,visited); delete[]visited; } template void MGraph { visited[v]=true; cout<<" "< for(int i=0;i if(a[v][i]!=noEdge&&a[v][i]!=0&&!visited[i]) DFS(i,visited); } template void MGraph { bool *visited=new bool[n]; for (int i=0;i visited[i]=false; for(i=0;i if(!visited[i]) BFS(i,visited); delete[]visited; } template void MGraph { SeqQueue visited[v]=true; cout<<" "< q.EnQueue(v); while(!q.IsEmpty()) { q.Front(v); q.DeQueue(); for(int i=0;i if(a[v][i]!=noEdge&&a[v][i]!=0&&!visited[i]) { visited[i]=true; cout<<" "< q.EnQueue(i); } } } 五、测试和调试 1.测试用例和结果 测试结果如下图 1)输入元素的个数以及权值 2)输入边以及权值 3)得到图的深度遍历以及广度遍历 4)输入要搜索的边，得到搜索结果 5)输入要删除的边，得到新的遍历 2.结果分析 1)程序能够正确的实现关于在邻接矩阵和邻接表两种不同的储存结构上实现图 的基本运算的算法，在邻接矩阵存储结构上实现图的深度和广度优先遍历算法 2)由测试结果来看，若在输出数据时以图的形式输出，更简单直观，程序还有待 改进。 实习题名:飞机最少换乘问题 班级姓名学号日期2016.05.19 一、问题描述 设有n个城市，编号为0～n?1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。（提示：可以使用有向图表示城市间的航线。只要两城市间有航班，则图中这两点间存在一条权为1的边。可以使用Dijkstra算法实现） 二、概要设计 文件min.cpp中定义了两个类,分别是图数据结构的抽象模板类Graph以及从抽象类Graph派生得来邻接矩阵类MGraph。主函数mian的代码如图所示： 三、详细设计 1.类和类的层次结构 程序定义了Graph类，以及邻接矩阵类MGraph。同上邻接矩阵类MGraph也继承了Graph的数据成员n和e，重载了Graph的纯虚函数。保护数据成员T** a指 向动态生成的二维数组，用以存储邻接矩阵。 T Graph #int n,e; +virtual ResultCode Insert(int u,int v,T&w)=0; +virtual ResultCode Remove(int u,int v)=0; +virtual bool Exist(int u,int v)const=0; T MGraph #T **a; #T noEdge; #void DFS(int v,bool *visited); #void BFS(int v,bool *visited); +MGraph(int mSize,const T& noedg); +~MGraph(); +ResultCode Insert(int u,int v,T&w); +ResultCode Remove(int u,int v); +bool Exist(int u,int v)const; +void DFS(); +void BFS(); 模版类Graph和 MGraph 2.核心算法 定义了类之后，求换乘次数最少主要是通过迪杰斯特拉算法实现。迪杰斯特拉算法主要通过动态创建数据结构，初始化操作，将源点v加入集合S，使用for 循环，按照长度的非递减次序，依次产生n-1条最短路径等步骤实现。核心算法程图如下： Dijkstra () 四、程序代码 template void MGraph { int i,k,w; if(v<0||v>n-1) throw OutOfBounds; bool *s=new bool[n]; for(i=0;i { s[i]=false; d[i]=a[v][i]; if(i!=v&&d[i] path[i]=v; else path[i]=-1; } s[v]=true; d[v]=0; for(i=1;i { k=Choose(d,s); s[k]=true; for(w=0;w if(!s[w]&&(d[k]+a[k][w]) { d[w]=d[k]+a[k][w]; path[w]=k; } } } 五、测试和调试 1.测试用例和结果 1)输入城市个数以及航线条数 2)分别输入每条航线的起点和终点 3)得到换乘次数最小的路线 4)最后输入N退出 2.结果分析 1)程序能够完全实现题目的要求，通过迪杰斯特拉算法实现了飞机换乘次数最小 的路线 2)下一步的目标是使用类似的算法对城市公交车的最少换乘问题进行解决 实习小结 在本次实验中出现了一些问题在用邻接矩阵存储结构实现图的广度优先遍历时，出现了输出结果为有序排列，改变图的顶点之间的关系后结果仍然不变，修改约束条件后，问题得以解决。在用邻接表存储结构实现Djikstra算法时，出现了指针访问冲突的问题，经调试检查发现是由访问数组越界导致，修改了约束条件后问题得以解决。 本次实验主要是要求在邻接表存储结构上实现图的深度优先遍历以及广度优先遍历和使用Djikstra算法求单源最短路径的问题。经过本次实验对图的不同存储结构适用情况有了更进一步认识，通过修改Djikstra算法使其实现在图的邻接表存储结构上求最短路径，进一步加深对该算法的理解。 通过这次实验我对图这种应用广泛的数据结构更加熟悉，结合课堂知识，以及老师的帮助，让我学到了更多。 附录： 1.图的基本运算 #include const int INFTY=2147483640; enum ResultCode{Underflow,Duplicate,Failure,Success,NotPresent}; template class Graph //抽象类 { public: virtual ResultCode Insert(int u,int v,T&w)=0; virtual ResultCode Remove(int u,int v)=0; virtual bool Exist(int u,int v)const=0; protected: int n,e; }; template class SeqQueue { public: SeqQueue(int mSize); ~SeqQueue(){delete []q;} bool IsEmpty() const{return front==rear;} bool IsFull() const{return (rear+1)%maxSize==front;} bool Front(T &x)const; bool EnQueue(T x); bool DeQueue(); void Clear(){front=rear=0;} private: int front,rear; int maxSize; T *q; }; template SeqQueue { maxSize=mSize; q=new T[maxSize]; front=rear=0; } template bool SeqQueue { if(IsEmpty()) { return false; } x=q[(front+1)%maxSize]; return true; } template bool SeqQueue if(IsFull()) { cout<<"Full"< return false; } q[rear=(rear+1)%maxSize]=x; return true; } template bool SeqQueue if(IsEmpty()) { cout<<"Underflow"< return false; } front=(front+1)%maxSize; return true; } template class MGraph:public Graph { public: MGraph(int mSize,const T& noedg); ~MGraph(); ResultCode Insert(int u,int v,T&w); ResultCode Remove(int u,int v); bool Exist(int u,int v)const; void DFS(); void BFS(); protected: T **a; T noEdge; void DFS(int v,bool *visited); void BFS(int v,bool *visited); template MGraph n=mSize; e=0; noEdge=noedg; a=new T*[n]; for(int i=0;i { a[i]=new T[n]; for(int j=0;j a[i][j]=noEdge; a[i][i]=0; } } template MGraph { for(int i=0;i delete []a[i]; delete []a; } template ResultCode MGraph if(u<0||v<0||u>n-1||v>n-1||u==v) return Failure; if(a[u][v]!=noEdge) return Duplicate; a[u][v]=w; e++; return Success; } template ResultCode MGraph if(u<0||v<0||u>n-1||v>n-1||u==v) return Failure; if(a[u][v]==noEdge) return NotPresent; a[u][v]=noEdge; e--; return Success; template bool MGraph if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge) return false; return true; } template void MGraph { bool *visited=new bool[n]; for (int i=0;i visited[i]=false; for(i=0;i if(!visited[i]) DFS(i,visited); delete[]visited; } template void MGraph { visited[v]=true; cout<<" "< for(int i=0;i if(a[v][i]!=noEdge&&a[v][i]!=0&&!visited[i]) DFS(i,visited); } template void MGraph { bool *visited=new bool[n]; for (int i=0;i visited[i]=false; for(i=0;i if(!visited[i]) BFS(i,visited); delete[]visited; } template void MGraph { SeqQueue visited[v]=true; cout<<" "< q.EnQueue(v); while(!q.IsEmpty()) { q.Front(v); q.DeQueue(); for(int i=0;i if(a[v][i]!=noEdge&&a[v][i]!=0&&!visited[i]) { visited[i]=true; cout<<" "< q.EnQueue(i); } } } template class ENode { public: ENode() {nextArc=NULL;} ENode(int vertex,T weight,ENode *next) { adjVex=vertex; w=weight; nextArc=next; } int adjVex; T w; ENode * nextArc; }; template class LGraph:public Graph { public: LGraph(int mSize); ~LGraph(); ResultCode Insert(int u,int v,T&w); ResultCode Remove(int u,int v); bool Exist(int u,int v)const; protected: ENode }; template LGraph #include<> #include<> #include<> #define MAXSIZE 100 typedef int DataType; typedef struct stack { DataType data[MAXSIZE]; int top; }sqstack; sqstack *InitStack(sqstack *S)出* 1.顺序栈的初始化*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 2.元素的入栈* 3.元素的出栈*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 4.取栈顶元素* 5.判空*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* *┃\n"); printf("\t┃* 6.将十进制数转换为其他进制数*┃\n"); printf("\t┃* *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); while ((m='0')&&(m='1')&&(m='2')&&(m='3')&&(m='4')&&(m='5')&&(m='6')&&(m='7')) { printf("\n请选择你需要操作的步骤(0至7):"); fflush(stdin); scanf("%c",&m); switch(m) { case '0': { exit(0); break; } 实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称二叉树的基本操作及哈夫曼编码译码系统的实现 实验时间2016 年 4 月14 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名班级学号 学院(系) 管理学院专业信息管理与信息系统 实习题名:二叉树的基本操作 班级姓名学号日期2016.04.14 一、问题描述 设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。设计main函数，测试上述每个运算。 二、概要设计 文件tree.cpp中在该文件中定义二叉树的链式存储结构，用队列实现二叉树的层次遍历，并且编写实现二叉树的各种基本操作函数。其中包括结点类BTNode，循环队列类SeqQueue，二叉树类BinaryTree。主函数main的代码如图所示。 三、详细设计 1.类和类的层次设计 程序定义了循环队列SeqQueue类和二叉树BinaryTree类。SeqQueue类主要是用队列实现，层次遍历。运用后序遍历思想，把树分解为左右子树和跟结点再进行左右交换并计算树的高度，最后删除二叉树。 （a ）循环队列类 （b ）二叉树类 2. 核心算法 程序利用循环队列SeqQueue 类通过不断出队并输出节点的值，将左右孩子入队直到队列为空实现二叉树的层次遍历。并运用后序遍历思想，将二叉树树分解为左右子树和根结点，利用(p -> lChild)和(p -> rChild)计算结点数目，并通过交换结点的左右子树实现左右交换，计算树的高度，最后删除二叉树。核心算法主要是二叉树BinaryTree 类中的High ，Node_num ，Exchange ，Level_traversal 四个函数，其设计流程图如下： SeqQueue -int front, rear; -int maxSize; -BTNode 第二章基本数据结构及其运算 一、单项选择题 1．数据的基本单位是( B ) A．数据B．数据元素C．数据项D．数据结构 2．在数据结构中，构成数据元素的最小单位称为（D）A．字符B．关键字C．数据元素 D．数据项 3．数据在计算机内的存储形式称为数据的（ D ）A．算法描述B．数据类型 C．逻辑结构D．物理结构 4．数据的逻辑结构可分为（C） A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构5．顺序表中的每个元素占m个字节，第一个元素的存储地址为LOC(1)，则任意1个元素i的地址为( B ) A．LOC(1)+i*m B．LOC(1)+(i-1)*m C．LCO(1)+(i+1)*m D．(i-1)*m 6．线性表若采用链表存储，其（D） A．所有结点的地址必须是连续的 B．部分结点的地址必须是连续的 C．所有结点的地址一定不连续 D．所有结点的地址连续、不连续都可以 7．线性表在采用链式存储时，其地址（ C ）A．必须是连续的B．一定是不连续的 C．连续不连续都可以D．部分是连续的 8．下列不属于线性结构的是( C )。 A．单链表B．队列 C．二叉树D．数组 9．链表不具有的特点是( A) A．可随机访问任一元素B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与线性表的长度成正比 10．数据结构反映了数据元素之间的结构关系，链表是一种( D)。 A．顺序存储线性表B．非顺序存储非线性表 C．顺序存储非线性表D．非顺序存储线性表 11．在单链表表示的线性表中，可以从( A )。 A．第一个结点访问到所有结点 B．某个结点访问到所有结点 C．某个结点访问到该结点的所有前趋结点 D．最后一个结点访问到所有结点 12．在一个单链表中，已知指针q所指向的结点是指针p所指向的结点的前驱结点，若在指针q和p所指向的两个结点之间插入指针s指向的结点，则执行( C )。 A．s->link=p->link; p->link=s; B．p->link=s->link; s->link=p; C．q->link=s; s->link=p; D．p->link=s; s->link=q; 13．长度为n的顺序存储的线性表，设在任何位置上删除一个元素的概率相等，则删除一个元素时平均要移动的元素 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 实验三的实验报告 学期： 2010 至_2011 第 2 学期 2011年 3月 27日课程名称: 数据结构专业:信息与计算科学 09 级5班实验编号： 03 实验项目：栈和队列实验指导教师 _冯山_姓名：朱群学号： 2009060548 实验成绩： 一实验目的： (1)熟练掌握栈和队列的抽象数据类型及其结构特点； (2)实现基本的栈和队列的基本操作算法程序。 二实验内容：(类C算法的程序实现，任选其一) (1) 设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP 等操作）(必做)； (2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计 与实现（选做）； (3)以迷宫问题为例，以堆栈结构完成迷宫问题的求解算法和程序（选做）。三实验准备： 1) 计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分 析与代码设计与分析准备。 四实验步骤： 1.录入程序代码并进行调试和算法分析； 2.编写实验报告。 五实验过程 一设计与实现基本的堆栈结构下的各种操作（如堆栈的PUSH、POP等操作）（1）问题描述 实现堆栈各种基本操作，如Pop,Push,GetTop等操作，即输入数据，通过Push入栈，再通过Pop操作输出出栈的元素,即入栈a,b,c,d,出栈d,c,b,a （2）算法实现及基本思想 堆栈是后进先出的线性表，由Push输入元素，Pop输出元素，堆栈的Push 操作思想,即插入元素e为新的的栈顶元素，先判断栈满与否，追加存储空间，然后将e值赋给栈顶指针Top。输入数据时用for循环 堆栈的Pop操作思想，先判断栈是否为空，若栈不空，则删除栈的栈顶元素，用e返回其值， （3）数据结构 栈的顺序存储结构 Typedef struct { 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图： head head head 心得体会： 本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。 实验2 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.doczj.com/doc/bd15363263.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数 实验报告 学院（系）名称：计算机科学与工程学院 姓名赵振宇学号20175302 专业 计算机科学与技术 班级 2017级4班实验项目 实验三：图的遍历与应用 课程名称 数据结构与算法 课程代码 0661913 实验时间 2019年5月27日 第3、4节 实验地点 7-219 考核标准实验过程25分 程序运行20分 回答问题15分 实验报告30分 特色功能5分 考勤违纪情况5分 成绩 成绩栏 其它批改意见: 教师签字： 考核内容 评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。 □功能完善,□功能不全□有小错□无法运行 ○正确○基本正确○有提示○无法回答 ○完整○较完整 ○一般 ○内容极少○无报告 ○有 ○无 ○有 ○无一、实验目的 1、实验目的：通过实验使学生理解图的主要存储结构，掌握图的构造算法、图的深度优先和广度优先遍历算法，能运用图解决具体应用问题。 二、实验题目与要求 要求：第1题为必做题，2，3，4至少选一 1.输入指定的边数和顶点数建立图，并输出深度优先遍历和广度优先遍历的结果。 1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束 2）实验要求：在程序中定义下述函数，并实现要求的函数功能：CreateGraph():按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图 3）实验提示: 图的存储可采用邻接表或邻接矩阵； 图存储数据类型定义（邻接表存储） #define MAX_VERTEX_NUM8//顶点最大个数 typedef struct ArcNode {int adjvex; struct ArcNode*nextarc; int weight;//边的权 }ArcNode;//表结点 #define VertexType int//顶点元素类型 typedef struct VNode {int degree,indegree;//顶点的度，入度 VertexType data; ArcNode*firstarc; }Vnode/*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum;//顶点的实际数，边的实际数}ALGraph; 4）注意问题: 注意理解各算法实现时所采用的存储结构。 注意区别正、逆邻接。 2.教学计划编制问题 1.1实验步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如实际中真正的软件系统，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实验的5个步骤： 1、问题分析和任务定义 通常，实验题目的陈述比较简洁，或者说有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么，解决问题的关键是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。 2．数据类型和算法设计 在设计这一步骤中需分概要设计和详细设计两步实现。概要设计指的是，对问题分析中提出的解决问题的关键点进行进一步阐述，提出问题的解决方案（算法思想）；详细设计中首先对概要设计中涉及的操作对象定义相应的数据类型，并在具体的存储结构下描述关键问题解决过程；同时要综合考虑程序功能，按照以数据结构为中心的原则划分模块，说明各模块的功能，画出模块之间的调用关系图，模块的划分和调用应使得程序结构清晰、合理、简单和易于调试。详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，定义相应的存储结构并写出各过程和函数的伪码算法。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。 3．编码实现和静态检查 编码是把详细设计的结果进一步求精为程序设计语言程序。如何编写程序才能较快地完成调试是特别要注意的问题。程序的每行不要超过60个字符。每个过程（函数）体一般不要超过40行，最长不得超过60行，否则应该分割成较小的过程（函数）。要控制if语句连续嵌套的深度，分支过多时应考虑使用switch语句。对函数功能和重要变量进行注释。一定要按格式书写程序，分清每条语句的层次，对齐括号，这样便于发现语法错误。 在上机之前，应该用笔在纸上写出详细的程序编码，并做认真地静态检查。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是极为有害的。对一般的程序设计者而言，当编写的程序长度超过50行时，通常会含有语法错误或逻辑错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先检查单个模块）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解。 4．上机准备和上机调试 上机准备包括以下几个方面： （1）熟悉C语言用户手册或程序设计指导书。 （2）注意Turbo C、VC与标准C语言之间的细微差别。 （3）熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。 （4）掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍柴工”。学生应该熟练运用高级语言的单步调试和程序调试器DEBUG调试程序。 《数据结构》实验报告 实验序号：1 实验项目名称：概论 附源程序清单： 1. #include 2. #include 实验1: 顺序表的操作实验 一、实验名称和性质 二、实验目的 1．掌握线性表的顺序存储结构的表示和实现方法。 2．掌握顺序表基本操作的算法实现。 3．了解顺序表的应用。 三、实验内容 1．建立顺序表。 2．在顺序表上实现插入、删除和查找操作（验证性内容）。 3．删除有序顺序表中的重复元素（设计性内容）。 4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。 四、实验的软硬件环境要求 硬件环境要求： PC机（单机） 使用的软件名称、版本号以及模块： Windows环境下的VC++6.0 五、知识准备 前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。 六、验证性实验 1．实验要求 编程实现如下功能： （1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。 （2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。 （3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。 （4）在顺序表中查找值为e的数据元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。 2. 实验相关原理： 线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为： #define MAXLEN 30 /*线性表的最大长度*/ typedefstruct { Elemtypeelem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序 具体实现时可以用任意类型代替*/ int length; /*顺序表的长度，即元素个数*/ }Sqlist; /*顺序表的类型*/ 【核心算法提示】 1．顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。 2．顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i 的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。 3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值为e的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值e进行比较，若相等则查找成功，函数返回该数据元素在顺序表中的位置，若顺序表中所有元素都与给定值e不相片，则查找失败，函数返回0值。 【核心算法描述】 status Sqlist_insert(Sqlist&L,inti,Elemtypex) /*在顺序表L中第i个元素前插入新元素x*/ {if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/ if (L.length>=MAXLEN) return OVERFLOW; /*顺序表L中已放满元素，再做插入操作则溢出*/ for(j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/ L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/ L.length++; /*顺序表L的长度加1*/ return OK; } status Sqlist_delete(Sqlist&L,inti,Elemtype&e) /*在顺序表L中删除第i个元素*/ {if (i<1||i>L.length)return ERROR; /*删除位置不正确则出错*/ for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/ L.length--; /*顺序表L的长度减1*/ return OK； } int Sqlist_search(SqlistL,Elemtype x) /* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/ 数据结构实验3 《数据结构与算法》实验报告 实验序号：3 实验项目名称：链式表的操作学号1507112104 姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09 一、实验目的及要求 1. 通过实验理解单链表的逻辑结构； 2. 通过实验掌握单链表的基本操作和具体的函数实现。 二、实验设备（环境）及要求 微型计算机； windows 操作系统； Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 链式表表示和实现线性表的如下： #include"stdio.h" #include"stdlib.h" typedef struct node //定义结点 { int data; //结点的数据域为整型 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自 定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 ListNode *LocateNode(LinkList head, int key); //函数，按值查找结点 void DeleteList(LinkList head,int key); //函数，删除指定值的结点 void printlist(LinkList head); //函数，打印链表中的所有值 void DeleteAll(LinkList head); //函数，删除所有结点，释放内存 //==========主函数============== void main() { int num; char ch; LinkList head; head=CreatListR1(); //用尾插入 法建立单链表，返回头指针 printlist(head); //遍历链表 输出其值 printf(" Delete node (y/n):"); //输入 实验报告 （2015 / 2016 学年第一学期） 课程名称数据结构 实验名称图的基本运算及飞机换乘次数最少问题 实验时间2015 年12 月 4 日 指导单位计算机科学与技术系 指导教师黄海平 学生姓名陈明阳班级学号Q14010119 学院(系) 贝尔英才专业信息科技强化班 实验报告 实验名称图的基本运算及飞机换乘次数最少问题指导教师黄海平 实验类型验证实验学时 4 实验时间12.4 一、实验目的和要求 飞机最少换乘次数问题。 （1）设有n个城市，编号为0~n-1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。 （2）参考：可以使用有向图表示城市间的航线；只要两城市间有航班，则图中这两点间存在一条权值为1的边；可以使用Dijkstra算法实现。 二、实验环境(实验设备) VSUAL STUDIO2015 三、实验原理及内容 对象视图： 源代码： Graph.h #include 南京工程学院实验报告 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素（学号）。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 程序1的主要代码(附简要注释) #include p->rchild=NULL; p->data=n; } else if(n>p->data) p->rchild=initBST(n,p->rchild); else p->lchild=initBST(n,p->lchild); return p; } void inorder(BSTNODE *BT){ if(BT!=NULL){ inorder(BT->lchild); printf("%d",BT->data); inorder(BT->rchild); } } BSTNODE *search_btree(BSTNODE *root,int key) { if(!root) {printf("Emptu btree\n"); return root;} while(root->data!=key) { if(key数据结构实验三(顺序栈的基本操作)
数据结构实验
南邮数据结构上机实验二二叉树的基本操作及哈夫曼编码译码系统的实现
基本数据结构及其运算习题
数据结构实验报告
数据结构实验报告全集
数据结构 实验报告三
数据结构实验一 实验报告
数据结构实验报告-答案
数据结构实验
数据结构实验三
数据结构实验1
数据结构实验1
《数据结构》实验1
数据结构实验3
南邮数据结构实验三
《数据结构》实验3实验报告
相关主题
文本预览