数据结构实验报告栈和队列迷宫图最短路径

数据结构

实

验

报

告

书

广东机电职业技术学院

2011年5月

目录

一、实验要求（需求分析） (3)

a. 实验目的 (3)

b. 实验内容 (3)

c．程序功能 (3)

二、程序分析 (4)

2.1 存储结构 (4)

2.2 关键算法分析 (4)

三、程序运行分析 (8)

1.程序运行流程图： (8)

2.程序运行结果截图： (9)

四．总结 (11)

五、附录 (12)

2010级数据结构实验报告

实验名称：迷宫求解问题

学生姓名：黄若海

班级：软件1004班

学号：

日期：2011年6月2日

一、实验要求（需求分析）

a. 实验目的

通过实验，掌握如下内容：

?进一步掌握指针、模板类、异常处理的使用

?掌握队列的操作的实现方法

?学习使用队列解决实际问题的能力

?学习使用图的广度优先搜索解决实际问题的能力

b. 实验内容

利用队的结构实现迷宫求解问题。迷宫求解问题如下：

心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。

c．程序功能

输入起始点的坐标，输出走出迷宫最短路径的长度。

二、程序分析

2.1 存储结构

存储结构: 队列顺序存储结构

示意图如下:

2.2 关键算法分析

核心算法思想：

1.如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路

径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。

2.为查找最短路径，使用了“图”中的算法：广度优先搜索。

关键算法思想描述和实现：

关键算法1：

为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。

C++实现：

struct Node

{

int parent_id; //保存父节点的位置

int node_id; //当前节点的序号，以便传递给孩子节点

int x,y; //当前结点对应的坐标

}Q[10*10]; //每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列

关键算法2：

遍历每个位置四周的位置，将没有走过的位置入队，形成树形的队列，通过出队操作就能找到最短路径。

C++实现：

bool GetNextPos(int *i ,int *j,int count)

{

switch(count)

{

case 1:(*j)++; return 1; //右

case 2:(*i)++; return 1; //下

case 3:(*j)--; return 1; //左

case 4:(*i)--; return 1; //上

default: return 0;

}

}

void EnQueue(int i,int j,int k)

{

Q[rear].x = i;

Q[rear].y = j; //保存当前节点对应的坐标位置

Q[rear].parent_id = k; //保存父节点的序号

Q[rear].node_id = rear; //保存当前节点序号

rear++;

}

关键算法3：

广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层序遍历，如下图：

在迷宫地图中，关键算法三通过不断调用关键算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到最浅深度即为最短路径。例如H节点的坐标就是出口坐标，当层序搜索到H时就终止了，入队工作结束，不再将I和J入队。通过关键算法四逆序就能找到最短路径A->B->C。其实最短路径不一定只有一条，例如J点也可能是出口坐标，但是当搜索到H时就停止了，故此算法只是输出了所有最短路径中可能的一条。

C++实现：

void ShortestPath_BFS(int i ,int j)

{

int count,m,n,k;

EnQueue(i,j,-1); Map[1][1] = 1; //起点入队,标记起点已走过

while(true)

{

count = 1;

DeQueue(&i,&j,&k);

n = i,m = j; //保存当前位置

while(GetNextPos(&i,&j,count))

{

count++;

if(!Map[i][j])

{

EnQueue(i,j,k); Map[i][j] = 1;

if(i == 8 && j == 9) return; //到达终点,(8,9)是默认终点，可以任意修改}

i = n; j = m; //保证遍历当前坐标的所有相邻位置

}

}

}

关键算法4：

使用队列指针查找父节点的方式，从队尾回溯到队首，标记出最短路径。

队列的元素示意图如下：

入队之后的队列如下图：

…………

5 6 3 7 7 4 7 13

例如从13号节点可以读出它在迷宫地图中的坐标（7，4），通过第三个元素7就能找到第七号节点，也即其父节点（5，6），从父节点又可以同理找到它的父节点第三号节点。这样就能实现逆序找到路径。

C++实现：

k = rear-1;

while(k != -1)

{

i = Q[k].x; j = Q[k].y;

Map[i][j] = 2;

k = Q[k].parent_id;

}

时间复杂度与空间复杂度：

算法一和二时间复杂度与空间复杂度均为O(1)。

算法三占用空间为迷宫边长n的平方，故空间复杂度为O(n*n)。最多走n*n步,最少走1步，故时间复杂度为O(n*n/2)。

三、程序运行分析

1.程序运行流程图：

开始

输出迷宫图

输入x,y

否

(x,y)是否合法

是

广度优先搜索

标记最短路径

输出最短路径

结束

2.程序运行结果截图：

测试条件：

以实验题目中给出的迷宫图进行测试。

测试时固定终点位置，选择不同的起点位置进行测试，测试各个位置下的输出是否正常。测试结论：

本程序对于测试地图在不同起始和终止位置输出都完全正确。

四．总结

1、在最初尝试编写代码时，采用的是递归算法。虽然用栈实现代码很简单，只需要向四个方向不断递归即可，但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后，我开始思索如何能输出最短路径。查找大量资料，结论是用栈很难实现，即使要实现也需要不断比较各种路径的长短，然后不断更新最短路径。偶然发现迪杰斯特拉算法，后又学习广度优先搜索算法，才用队列才最终使得问题得以解决。

2、在将新算法应用到迷宫问题过程中，遇到不少困难，反复琢磨和看书才将其解决。由于顺序队列的出队入队操作加上了赋值和标记位置、建立链表关系，实际将一个顺序队列以指针的作用，变成了一棵树的结构，而树的深度恰好能反映最短路径。

3、从一个小小的迷宫问题，引出了许多知识，这种探索式的学习是很有意义的。从迷宫基本的递归和回溯到栈的运用和理解，再到队列的运用，后又到树与图以及队列的综合运用，将很多知识点串联起来了，加深了理解。同时探索式地学习迪杰斯特拉算法也收获颇多。

4、改进：本题为了实现代码的简便，没有采用链队结构，因而浪费了一定的空间，特别是当迷宫的边长很长的时候，空间复杂度以O（n*n）增长，程序效率将大大降低，因而如果是计算复杂的迷宫，可以考虑将本程序的顺序队列稍加修改变为链队，实现动态分配内存，以节省空间消耗。

5、进一步的思考：此方法只能输出一条最短路径，如何能输出所有最短路径？初步算法是将同一深度的节点全部遍历，如果后续还有同样长度的路径则输出该路径，如果没有则只有一条最短路径。

五、附录

源代码:

//本程序在windows7 、visual studio2008 环境下调试运行成功

#include

using namespace std;

void EnQueue(int i,int j,int k); //入队一个节点

void DeQueue(int *i,int *j,int *k); //获取当前节点的序号和对应的迷宫坐标，然后出列

bool GetNextPos(int *i ,int *j,int count); //得到下一个邻接点的位置

void ShortestPath_BFS(int i,int j); //广度优先遍历寻找最短路径

void ShortestPath(); //输出最短路径

void Print(); //输出迷宫形状

int Map[10][10] = {{1,1,1,1,1,1,1,1,1,1},

{1,0,0,1,0,0,0,1,0,1},

{1,0,0,1,0,0,0,1,0,1},

{1,0,0,0,0,1,1,0,0,1},

{1,0,1,1,1,0,0,0,0,1},

{1,0,0,0,1,0,0,0,0,1},

{1,0,1,0,0,0,1,0,0,1},

{1,0,1,1,1,0,1,1,0,1},

{1,1,0,0,0,0,0,0,0,0},

{1,1,1,1,1,1,1,1,1,1}};

struct Node

{

int parent_id; //保存父节点的位置

int node_id; //当前节点的序号，以便传递给孩子节点

int x,y; //当前结点对应的坐标

}Q[10*10]; //每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列

int front = 0,rear = 0; //队列头指针和尾指针

void main()

{

cout<<"程序说明："<<'\n'<<"1.输出路径为最短路径；"<<'\n'<<"2.默认的出口在最右下角，如有需要可以调整。"<<'\n'<<'\n';

cout<<"初始地图如下："<

Print();

int i,j;

reinput:

cout<<"请输入起点坐标（x,y）："<

cin>>i>>j;

if(Map[i][j]) {cout<<"不能从该处出发，请重新输入！"<

ShortestPath_BFS(i,j);

cout<<"最短路径之一如下："<

ShortestPath();

}

void EnQueue(int i,int j,int k)

{

Q[rear].x = i;

Q[rear].y = j; //保存当前节点对应的坐标位置

Q[rear].parent_id = k; //保存父节点的序号

Q[rear].node_id = rear; //保存当前节点序号

rear++;

}

void DeQueue(int *i,int *j,int *k)

{

*i = Q[front].x;

*j = Q[front].y;

*k = Q[front].node_id;

front++; //出列一个节点

}

bool GetNextPos(int *i ,int *j,int count)

{

switch(count)

{

case 1:(*j)++; return 1; //右

case 2:(*i)++; return 1; //下

case 3:(*j)--; return 1; //左

case 4:(*i)--; return 1; //上

default: return 0;

}

}

void ShortestPath_BFS(int i ,int j)

{

int count,m,n,k;

EnQueue(i,j,-1); Map[1][1] = 1; //起点入队,标记起点已走过while(true)

{

count = 1;

DeQueue(&i,&j,&k);

n = i,m = j; //保存当前位置

while(GetNextPos(&i,&j,count))

{

count++;

if(!Map[i][j])

{

EnQueue(i,j,k); Map[i][j] = 1;

if(i == 8 && j == 9) return; //到达终点,(8,9)是默认终点，可以任意修改

}

i = n; j = m; //保证遍历当前坐标的所有相邻位置

}

}

}

void ShortestPath()

{

int i,j,k,sum(0) ;

k = rear-1;

while(k != -1)

{

i = Q[k].x; j = Q[k].y;

Map[i][j] = 2;

k = Q[k].parent_id;

}

cout<<" 0 1 2 3 4 5 6 7 8 9"<

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

{

cout<

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

if(Map[i][j]==2)

{sum++; cout<<"□";}

else

cout<<"■";

cout<

}

cout<<"最短路径长度："<

void Print()

{

cout<<" 0 1 2 3 4 5 6 7 8 9"<

for(int i = 0;i < 10;i++)

{

cout<

for(int j = 0;j < 10;j++)

if(Map[i][j]) cout<<"■";

else cout<<"□";

cout<

}

}

栈和队列习题答案

第三章栈和队列习题答案 一、基础知识题 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈) (2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。 (3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 链栈中为何不设置头结点 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } .. // 设Q1已有内容，Q2已初始化过 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的

数据结构-实验报告顺序栈

（封面） 学生实验报告 学院：国际经贸学院 课程名称：数据结构 专业班级： 09电子商务 姓名： 学号： 学生实验报告

（经管类专业用） 一、实验目的及要求： 1、目的 通过实验，实现顺序栈的各种基本运算。 2、内容及要求 编写一个程序，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成下列功能： （1）初始化栈S。 （2）判断栈S是否非空。 （3）依次进栈元素a，b，c，d，e。 （4）判断栈S是否非空。 （5）输出栈的长度。 （6）输出从栈顶到栈底的元素。 （7）输出出栈序列； （8）判断链栈S是否为空； （9）释放链栈 二、仪器用具： 三、实验方法与步骤:

一、查阅顺序栈等相关资料，熟悉顺序栈基本概念和流程 二、“开展”顺序栈实验流程 三、整理实验数据和文档，总结实验的过程，编写实验报告 四、实验结果与数据处理： 1、顺序栈的代码： #include #include #define MaxSize 100 typedef char ElemT ype; typedef struct { ElemT ype data[MaxSize]; int top; //栈顶指针 } SqStack; void InitStack(SqStack *&s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } void ClearStack(SqStack *&s) { free(s); } int StackLength(SqStack *s) { return(s->top+1);

数据结构堆栈与队列实验报告

实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

顺序栈的基本操作讲解

遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 ： 计算机科学与技术（师 范） 课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范1班 学号:201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1 ?熟悉掌握栈的定义、结构及性质； 2. 能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3?了解和掌握栈的应用。 二、实验环境： Microsoft Visual C++ 6.0

三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作

五、代码： #include #include #define maxsize 64 typedef int datatype; //定义结构体typedef struct { datatype data[maxsize]; int top; }seqstack; //建立顺序栈seqstack *SET(seqstack *s) { int i; s=(seqstack*)malloc(sizeof(seqstack)); s->top=-1; printf(" 请输入顺序栈元素(整型，以scanf("%d",&i); do{ s->top++; s->data[s->top]=i; scanf("%d",&i); 0 结束)："); }while(i!=0); printf(" 顺序栈建立成功\n"); return s; } //清空栈void SETNULL(seqstack *s) { s->top=-1;} //判断栈空 int EMPTY(seqstack *s) { if(s->top>=0) return 0; else return 1;} //进栈 seqstack *PUSH(seqstack *s) { int x; printf(" 你想要插入的数字："); scanf("%d",&x); if(s->top==maxsize-1) { printf("overflow"); return NULL; } else {

栈的操作(实验报告)

实验三栈和队列 3.1实验目的： （1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现； （2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。 3.2实验要求： （1）复习课本中有关栈和队列的知识； （2）用C语言完成算法和程序设计并上机调试通过； （3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。 3.3基础实验 [实验1] 栈的顺序表示和实现 实验内容与要求: 编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 分析: 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。 注意： （1）顺序栈中元素用向量存放 （2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 参考程序: #include #include #define MAXNUM 20

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

数据结构图的遍历实验报告

实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;} MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{ int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);

第3章 栈和队列

《数据结构》 第3章栈和队列 共85题 一、单选 1. (1)分题目ID号：10705 题目难度：容易 设对一组数据的处理具有“后进先出”的特点，则应采用的数据结构是【1】 A. 队列 B. 栈 C. 顺序表 D. 二叉树题目答案：B 2. (1)分题目ID号：10706 题目难度：容易 若进栈序列为3、5、7、9，进栈和出栈可穿插进行，则不可能的出栈序列是【1】 A. 7，5，3，9 B. 9，5，7，3 C. 9，7，5，3 D. 7，5，9，3 题目答案：B 3. (1)分题目ID号：10707 题目难度：较难 设用一维数组A[m]存储栈，令A[m-1]为栈底，t指示当前栈顶的位置。如果栈不空，则出栈时应使【1】 A. t=t+l B. t=t-1 C. t=m-1 D. 不改变t 题目答案：A 4. (1)分题目ID号：10708 题目难度：容易 设用一维数组A[m]存储栈，令A[0]为栈底，top指示当前钱顶的位置，当把栈清空时所要执行的操作是【1】 A. top-- B. top=0 C. top=-1 D. top=m-1 题目答案：C 5. (1)分题目ID号：10709 题目难度：容易 设栈s的初始状态为空，如果进栈序列为1、2、3、4、5、6，出栈序列为3、2、5、6、4、1，则s的容量至少是【1】 A. 6 B. 4 C. 2 D. 3 题目答案：D 6. (1)分题目ID号：10710 题目难度：容易 设栈s最多能容纳4个元素，现有A、B、C、D、E、F六个元素按顺序进栈，以下可能的出栈序列是【1】 A. E、D、C、B、A、F B. B、C、E、F、A、D C. C、B、E、D、A、F D. A、D、F、E、B、C 题目答案：C

数据结构栈的基本操作,进栈,出栈

第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 1、在演示程序中，出现的元素以数字出现定义为int型， 2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上 3、顺序栈的程序执行的命令包括如下： （1）定义结构体 （2）顺序栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）顺序栈的打印结果 3、链栈的程序执行的命令包括如下： （1）定义结构体 （2）链栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）链栈的打印结果 二概要设计 1、顺序栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作： InitStack(SqStack &S) 操作结果：构造一个空栈 Push(L,e) 操作结果：插入元素e为新的栈顶元素

Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作： LinkStack(SqStack &S) 操作结果：构造一个空栈 Status Push(L,e) 操作结果：插入元素e为新的栈顶元素 Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 3、顺序栈程序包含的主要模块： (1) 已给定的函数库： （2）顺序栈结构体： （3）顺序栈初始化及创建: (4)元素插入 (5)元素删除

栈和队列综合实验报告

栈和队列综合实验报告 一、实验目的 （1）能够利用栈和队列的基本运算进行相关操作。 （2）进一步熟悉文件的应用 （3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、迷宫求解 设计一个迷宫求解程序，要求如下： 以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 能任意设定的迷宫 （选作）如果有通路，列出所有通路 提示： 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：11

01 01 01 01 01 01 01 11 入口位置：1 1 出口位置：8 8 四、重要数据结构 typedef struct{ int j[100]; int top;栈顶指针，一直指向栈顶 }stack;//存放路径的栈 int s[4][2]={{0,0},{0,0},{0,0},{0,0}}; //用于存放最近的四步路径坐标的数组，是即使改变的，即走一步，便将之前的坐标向前移一步，将最早的一步坐标覆盖掉，新的一步放入数组末尾其实功能和队列一样。 其作用是用来判断是否产生了由于本程序算法产生的“田”字方格内的死循环而准备的，用于帮助跳出循环。 五、实现思路分析 if(a[m][n+1]==0&&k!=3){ n++; k=1; o=0; }else if(a[m+1][n]==0&&k!=4){ m++;

k=2; o=0; }else if(a[m][n-1]==0&&k!=1){ n--; k=3; o=0; }else if(a[m-1][n]==0&&k!=2){ m--; k=4; o=0; }else{ o++;} if(o>=2){ k=0; }//向所在方格的四个方向探路，探路顺序为→↓←↑（顺时针），其中if判断条件内的&&k!=n和每个语句块中的对k赋值是为防止其走回头路进入死循环，而最后一个else{}内语句是为了防止进入死路时，不能走回头路而造成的死循环。 push(q,m,n);//没进行一次循环都会讲前进的路径入栈。 if (pushf(&s[0][0],m,n)==0){ k=3;}//用来判断是否产生了由于本程序探路算法产生的“田”字方格内的死循环而准备的，用于帮助跳出田字循环。同时会将路径存入用于下次判断 六、程序调试问题分析 最开始写完时是没有死路回头机制的，然后添加了两步内寻路不回头机制。 第二个是“田”字循环问题，解决方法是加入了一个记录最近四步用的数组和一个判断田字循环的函数pushf。

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

数据结构第三章栈和队列3习题

第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType;

数据结构实验报告 顺序栈

《数据结构与算法》实验报告

一、实验内容 1．栈的实现 2．顺序栈的基本操作 二、实验目的及要求 熟悉栈的基本操作在顺序栈的实现。通过具体应用实例在复习高级编程语言使用方法的基础上初步了解数据结构的应用。 三、设计分析与算法描述 顺序栈的存储结构： typedef struct { int elem[Stack_Size]; int top; }SeqStack; void InitStack(SeqStack *S)//构造一个空栈(初始化) int Push(SeqStack *S,int x)//进栈 int Pop(SeqStack *S,int *x)//出栈 int IsEmpty(SeqStack *S)//判栈是否空 int IsFull(SeqStack *S)//判栈是否满 int GetTop(SeqStack *S,int *x)//读栈顶 四、附件：带注释的源程序 #include"iostream.h" #define Stack_Size 50 #define false 0 #define true 1

typedef struct { int elem[Stack_Size]; int top; }SeqStack; void InitStack(SeqStack *S)//构造一个空栈(初始化) { S->top=-1; } int Push(SeqStack *S,int x)//进栈 { if(S->top==Stack_Size-1)//栈已满 return (false); S->top++; S->elem[S->top]=x; return (true); } int Pop(SeqStack *S,int *x)//出栈 { if(S->top==-1)//栈已空 return (false); else { *x=S->elem[S->top];

栈溢出实验报告

华中科技大学计算机学院《信息系统应用安全》实验报告 实验名称团队成员： 注：团队成员贡献百分比之和为1 教师评语： 一.实验环境 ? 操作系统：windows xp sp3 ? 编译平台：visual c++ 6.0 ? 调试环境：ollydbg 二.实验目的 1. 掌握缓冲区溢出的原理； 2. 掌握缓冲区溢出漏洞的利用技巧； 3. 理解缓冲区溢出漏洞的防范措施。 三.实验内容及步骤 1. 缓冲区溢出漏洞产生的的基本原理和攻击方法 ? 缓冲区溢出模拟程序 由于拷贝字符串时产生缓冲区溢出，用“abcd”字符串的值覆盖了原来eip的值，所以 main函数返回时eip指向44434241，引发访问异常。 ? 运行命令窗口的shellcode 由于把main函数的返回eip地址替换成了jmp esp的地址，main函数 返回的时候就会执行我们的shellcode代码。该shellcode，运行命令窗口。 2. ms06-040 缓冲区溢出漏洞分析和利用 ? 溢出点定位 篇二：缓冲区溢出实验报告 缓 冲 区 溢 出 报 告 院系：计算机与通信工程学院 班级：信息安全10-02班 1. 实验目的 掌握缓冲区溢出的原理 掌握常用的缓冲区溢出方法 理解缓冲区溢出的危害性 掌握防范和避免缓冲区溢出攻击的方法 2. 实验工具 溢出对象：ccproxy 7.2 (1) (2)调试工具： 使用vmware虚拟机，安装ccproxy7.2进行实验调试。 3. 实验步骤 了解ccproxy 7.2 代理服务器为大家解决了很多问题，比如阻挡黑客攻击和局域网共享上网等。 ? 国内非 常受欢迎的一款代理服务器软件 ? 设置简单，使用方便 关于ccproxy6.2缓冲区溢出漏洞说明

栈和队列及其应用实验报告

数据结构实验报告 实验名称：栈和队列及其应用 班级：12级电气本2 学号：2012081227 姓名：赵雪磊 指导教师：梁海丽 日期：2013年9月23日 数学与信息技术学院 一、实验目的

1. 掌握栈和队列的概念。 2．掌握栈和队列的基本操作（插入、删除、取栈顶元素、出队、入队等）。 3．理解栈和队列的顺序、链式存储。 二、实验要求 利用顺序栈将任意一个给定的十进制数转换成二进制、八进制、十六进制数并输出。 三、算法描述 #include "stdafx.h" #include "iomanip.h" void D10to2_8_16(int i,char radix) { char m; if(i>=radix) D10to2_8_16(i/radix,radix); if((m=i%radix+'0')>0x39) m+=7; cout << m; } void main(void) { int nDec; cout << "请输入一个十进制正整数...\n" << "nDec="; cin >> nDec; cout << "转换为二进制是:"; D10to2_8_16(nDec,2); cout << endl; cout << "转换为八进制是:0"; D10to2_8_16(nDec,8); cout << endl; cout << "转换为十六进制是:0x"; D10to2_8_16(nDec,16); cout << endl; } 四、程序清单 #include #include #define N 2 //可以控制进制转换 using namespace std; typedef struct{ int *top; int *base; int stacksize; }stack;

数据结构实验报告无向图

《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v)

以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main()

数据结构栈和队列习题及答案

习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front

(完整word版)顺序栈基本操作实验报告

数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期：年月日评分 一、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈的应用。 二、实验要求 1．进行栈的基本操作时要注意栈"后进先出"的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。 主要功能描述如下： （1）从键盘上输入表达式。 （2）分析该表达式是否合法： ?a) 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 ?b) 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 ?c) 若是其它字符，则返回错误信息。 （3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 程序中应主要包含下面几个功能函数： ?l void initstack()：初始化堆栈 ?l int Make_str()：语法检查并计算

?l int push_operate(int operate)：将操作码压入堆栈 ?l int push_num(double num)：将操作数压入堆栈 ?l int procede(int operate)：处理操作码 ?l int change_opnd(int operate)：将字符型操作码转换成优先级 ?l int push_opnd(int operate)：将操作码压入堆栈 ?l int pop_opnd()：将操作码弹出堆栈 ?l int caculate(int cur_opnd)：简单计算+，-，*，/ ?l double pop_num()：弹出操作数 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果） 第一题： #include using namespace std; #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 #define OVERFLOW -1 #define OK 1 #define NO -1 #define NULL 0 typedef int Status; typedef char SElemType; typedef struct { SElemType *base; //在栈构造之前和销毁之后，base的值为NULL SElemType *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位 } SqStack; 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; }//InitStack Status StackEmpty(SqStack &S) { if(S.base==S.top)