数据结构栈实验
数据结构实验报告
1． 实验题目
利用链栈解决迷宫最小路径问题 2．需求分析
本程序用vs2008编写，利用入栈、出栈求出从迷宫（随机生成）起点到达迷宫终点的最小路径，并显示。
(1) 输入的形式和输入值的范围；
输入一个整数，表示迷宫的长宽，输入值应大于等于8。
(2) 输出的形式；输入的形式和输入值的范围；
输出迷宫地图及最短路径；若终点不可达，则输出无法找到出口。
(3) 程序所能达到的功能；
求出从迷宫（随机生成）起点到达迷宫终点的最小路径，若终点不可达，则输出无法找到出口。
(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 A ．输入5 B ．输入10 C ．输入30
D ．输入50
E ．输入 ’e’，结束
3．概要设计
(1) 栈的抽象数据类型
ADT Stack{
数据对象：,0,1{|},2,,,0i i D a a ElemSet i n n =∈=???≥ 数据关系：11,,,2,},{,2|i i i i R a a a a D i n n --=<>∈=???≥ 基本操作： InitStack(&S) 操作结果：构造一个空栈。 DestroyStack(&S) 初始条件：栈S 已存在。
操作结果：栈S 被销毁。
ClearStack(&S) 初始条件：栈S 已存在。
操作结果：将栈S 清为空栈。
StackEmpty(S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。
GetTop(S,&e)
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push(&S,e)
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&S,&e)
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
StackTraverse(S,visit())
初始条件：栈S已存在且非空。
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
(2) 所涉及函数
①主函数main()
②栈构造函数Stack()
③栈析构函数~Stack()
④获取栈长度函数Getlength()
⑤入栈函数Push()
⑥出栈函数Pop()
⑦获取栈顶元素函数GetTop()
⑧判断栈是否为空函数StackEmpty()
⑨清空栈函数Clear()
⑩拷贝栈函数CopyStack()
?初始化迷宫函数Initial()
?显示迷宫函数ShowMap()
?寻找迷宫出口函数Found()
?判断下一地点是否通行函数JudgePass()
?移动到下一地点函数Remove()
?回到上一地点函数Back()
?显示路径函数ShowRoad()
?移动Dos窗口光标函数Goxy()
?设置Dos窗口大小函数SetDosSize()
?删除迷宫函数DeleteMap()
(3) 函数关系
4．详细设计
(1) 栈的基本操作
详见附录（1）（2）
(2) 迷宫相关操作
详见附录（3）（4）
(3) 主函数
详见附录（5）
5．用户使用说明
界面友好，只需了解迷宫大小应不小于8*8格，算法执行时间依赖于迷宫大小和计算机处理能力。每个迷宫运算完毕后回车继续新的迷宫，输入字符e退出程序。
6．测试结果
(1) 输入5
(2) 输入10
(5) 输入字符e结束程序7．附录
(1) Stack.h
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;
//栈类
template
class Stack{
//结点
typedef struct SNode{
ElemType data;
struct SNode * next;
}SNode,*PSNode;
PSNode head;
int length;
public:
//构造
Stack();
//析构
~Stack();
//获取栈长
int Getlength();
//在栈顶插入元素data
Status Push(ElemType data);
//获取栈顶元素，赋给data
Status GetTop(ElemType & data);
//删除栈顶数据，赋给data
Status Pop(ElemType & data);
//判断栈是否为空
bool StackEmpty();
//清空栈
Status Clear();
//拷贝栈，为了本题而增设
Status CopyStack(Stack
};
(2) Stack.cpp
#include "Stack.h"
#include
//构造
template
Stack
head = new SNode;
head->next = NULL;
length = 0;
}
//析构
template
Stack
Clear();
delete head;
}
//获取栈长
template
int Stack
return length;
}
//在栈顶插入元素data
template
Status Stack
if(!p) return ERROR;
p->data=data;
p->next=head->next;
head->next=p;
length++;
return OK;
}
//获取栈顶元素，赋给data
template
Status Stack
data = head->next->data;
return OK;
}
//删除栈顶数据，赋给data
template
Status Stack
PSNode p = head->next;
data = p->data;
head->next = p->next;
delete p;
length--;
return OK;
}
//判断栈是否为空
template
bool Stack
if(head->next) return false;
return true;
}
//清空栈
template
Status Stack
PSNode p;
while(head->next){
p = head->next;
head->next = p->next;
delete p;
}
length = 0;
return OK;
}
//拷贝栈，为了本题而增设
template
Status Stack
while(p){
s.Push(p->data);
p = p->next;
}
return OK;
}
(3) Map.h
extern int N;
typedef int** Map;
//初始化地图
void Initial(Map&);
//显示地图
void ShowMap(Map&);
//寻找出口
bool Found(Stack
//判断下一方向是否可通行
bool JudgePass(Map&,int,int,int);
//移动到下一坐标
void Remove(int,int&,int&);
//回到上一个坐标
void Back(int,int&,int&);
//显示路径
void ShowRoad(Stack
//移动光标
void Goxy(int,int);
//设置dos大小
void SetDosSize();
//删除地图
void DeleteMap(Map&);
(4) Map.cpp
#include
#include
#include
#include
#include "Stack.cpp"
#include "Map.h"
//初始化地图
int N;
void Initial(Map& map){
map = (Map)malloc(sizeof(int*)*N);
for(int i=0;i map[i] = (int*)malloc(sizeof(int)*N); srand((unsigned int) time(0)); for(int i=0;i for(int j=0;j if(i==0 || i==N-1 || j==0 || j==N-1) map[i][j]=1; else if(rand()%2 && rand()%2 && rand()%3) map[i][j]=1; else map[i][j]=0; } for(int i=0;i map[i][N/3] = 1; for(int i=N-1;i>N/5;i--) map[i][N/3*2] = 1; map[N-2][N-2] = 0; } //显示地图 void ShowMap(Map& map){ for(int i=0;i for(int j=0;j if(map[i][j]==0) printf(" "); else if(map[i][j]==1) printf("■"); } printf("\n"); Sleep(30); } Goxy(1,1);printf("⊙"); Goxy(N-2,N-2);printf("⊙"); } //寻找出口 bool Found(Stack int total = N*N; Stack int innt = 0;//方向 int x = 1;//横坐标 int y = 1;//纵坐标 Map min = (Map)malloc(sizeof(int*)*N); for(int i=0;i min[i] = (int*)malloc(sizeof(int)*N); for(int i=0;i for(int j=0;j min[i][j]=N*N; do{ while(innt<4){ if(JudgePass(map,innt,x,y)){ Remove(innt,x,y); if(S.Getlength() min[y][x]=S.Getlength(); S.Push(innt); Back(innt,x,y); map[y][x] = 1; Remove(innt,x,y); innt=0; break; }else{ Back(innt,x,y); innt++; } }else{ innt++; }//ifJ }//while if(innt==4){ S.Pop(innt); Back(innt,x,y); map[y][x] = 0; innt++; }else if(x==N-2 && y==N-2){ if(S.Getlength() < total){ result.Clear(); total = S.Getlength(); S.CopyStack(result); } S.Pop(innt); Back(innt,x,y); map[y][x] = 0; innt++; }//ifi }while(!S.StackEmpty() || innt<4); if(total != N*N) return true; else return false; } //判断下一方向是否可通行 bool JudgePass(Map& map,int innt,int x,int y){ if(innt == 0 && map[y-1][x] ==0) return true; else if(innt == 1 && map[y][x+1] ==0) return true; else if(innt == 2 && map[y+1][x] ==0) return true; else if(innt == 3 && map[y][x-1] ==0) return true; else return false; } //移动到下一坐标 void Remove(int innt,int& x,int& y){ if(innt == 0) y--; else if(innt == 1) x++; else if(innt == 2) y++; else if(innt == 3) x--; } //回到上一个坐标 void Back(int innt,int& x,int& y){ if(innt == 0) y++; else if(innt == 1) x--; else if(innt == 2) y--; else if(innt == 3) x++; } //显示路径 void ShowRoad(Stack if(s.StackEmpty()) return; int innt; int last; int x = 1; int y = 1; int dion; s.Pop(innt); while(!s.StackEmpty()){ last = innt; Remove(innt,x,y); s.Pop(innt); Goxy(x,y); dion = (last+1)*10+innt+1; // printf("\n%d,%d",point.x,point.y); if(dion==11||dion==33) printf("┃"); else if(dion==22||dion==44) printf("━"); else if(dion==21||dion==34) printf("┛"); else if(dion==41||dion==32) printf("┗"); else if(dion==43||dion==12) printf("┏"); else if(dion==23||dion==14) printf("┓"); Sleep(30); } } //移动光标 void Goxy(int x,int y){ //每个字符占两个x坐标 x*=2; //以第三行起始为坐标原点 y+=2; HANDLE hCon; hCon = GetStdHandle(STD_OUTPUT_HANDLE); COORD setps; setps.X = x; setps.Y = y; SetConsoleCursorPosition(hCon,setps); } //设置dos大小 void SetDosSize(){ char s[50]; sprintf(s,"mode con cols=%d lines=%d",N*2+1,N+4); system(s); } //删除地图 void DeleteMap(Map& map){ for(int i=0;i free(map[i]); free(map); } (5) main.cpp #include #include #include "Stack.cpp" #include "Map.h" int main(){ char ch=' '; N=40; while(ch!='e'){ Stack Map map; SetDosSize(); Goxy((N-sizeof("迷宫最短路径求解（栈应用）")/2)/2,-2); printf("迷宫最短路径求解（栈应用）\n"); Goxy((N-sizeof("请输入地图大小: (^2格) ")/2)/2,-1); printf("请输入地图大小: (^2格)\b\b\b\b\b\b\b\b\b"); scanf("%d",&N); if(N<8){ printf("输入错误,回车重新输入"); getchar(); getchar(); N=40; continue; } SetDosSize(); Goxy((N-sizeof("迷宫最短路径求解（栈应用）")/2)/2,-2); printf("迷宫最短路径求解（栈应用）\n"); Goxy((N-sizeof("正在生成地图...")/2)/2,-1); printf("正在生成地图...\n"); Initial(map); ShowMap(map); Goxy((N-sizeof("正在寻找出口...")/2)/2,-1); printf("正在寻找出口...\n"); if(Found(result,map)){ Goxy((N-sizeof("正在绘制最短路径...")/2)/2,-1); printf("正在绘制最短路径...\n"); ShowRoad(result); Goxy((N-sizeof(" 绘制完毕")/2)/2,-1); printf(" 绘制完毕\n"); }else{ Goxy((N-sizeof(" 无法达到出口")/2)/2,-1); printf(" 无法达到出口\n"); } Goxy(0,N+1); DeleteMap(map); printf("回车继续，输入e结束程序："); getchar(); ch=getchar(); } return 0; } #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; } 宁波工程学院电信学院计算机教研室 实验报告 课程名称：___ 数据结构 ___ __ 实验项目：链串的基本算法 指导教师： 实验位置：电子楼二楼机房姓名： 学号： 班级：计科102 日期： 2011/10/13 一、实验目的 1）熟悉串的定义和串的基本操作。 2）掌握链串的基本运算。 3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋6.0的计算机。 三、实验内容 编写一个程序，实现链串的各种基本运算，并在此基础上设计一个主程序。具体如下： 编写栈的基本操作函数 链串类型定义如下所示： typedef struct snode{ char data; struct snode *next; }listring; （1）串赋值Assign(s,t) 将一个字符串常量赋给串s,即生成一个其值等于t的串s （2）串复制StrCopy(s,t) ?将串t赋给串s （3）计算串长度StrLength(s) ?返回串s中字符个数 （4）判断串相等StrEqual(s,t) ?若两个串s与t相等则返回1；否则返回0。 （5）串连接Concat(s,t) ?返回由两个串s和t连接在一起形成的新串。 （6）求子串SubStr(s,i,j) ?返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j 个字符组成的子串。 （7）插入InsStr (s,i,t) ?将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t 的第一个字符作为s的第i个字符,并返回产生的新串（8）串删除DelStr (s,i,j) ?从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j 的子串,并返回产生的新串。 （9）串替换RepStr (s,s1,s2) ?在串s中,将所有出现的子串s1均替换成s2。 （10）输出串DispStr(s) ?输出串s的所有元素值 （11）判断串是否为空IsEmpty(s) 编写主函数 调用上述函数实现下列操作： （1）建立串s=“abcdefghijklmn”，串s1=“xyz”，串t＝“hijk” （2）复制串t到t1，并输出t1的长度 （3）在串s的第9个字符位置插入串s1而产生串s2，并输出s2 （4）删除s第2个字符开始的5个字符而产生串s3，并输出s3 （5）将串s第2个字符开始的3个字符替换成串s1而产生串s4，并输出s4 （6）提取串s的第8个字符开始的4个字符而产生串s5，并输出s5 （7）将串s1和串t连接起来而产生串s6，并输出s6 （8）比较串s1和s5是否相等，输出结果 程序清单： #include 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 实验二堆栈和队列 实验目的： 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) /*初始化带头结点链式堆栈*/ 实验三的实验报告 学期： 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．实验目的 （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<<"建立一个单链表"< 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 实验报告 学院（系）名称：计算机科学与工程学院 姓名赵振宇学号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．进一步掌握指针变量的含义。 2．掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3．掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1．认真阅读和掌握本实验的参考程序。 2．按照对二叉树的操作需要，在创建好二叉树后再通过遍历算法验证创建结果。3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 以下参考程序是按完全二叉树思想将输入的字符串生成二叉树，并通过遍历来验证二叉树创建正确与否，但不能创建非完全二叉树，请认真研究该程序，然后模仿教材例6.4初始化方式创建二叉树:所有的空指针均用#表示，如教材图 6-13对应的二叉树，建立时的初始序列为：AB#D##CE##F##。然后通过遍历算法验证二叉树是否正确（先递归验证后非递归验证）。 参考程序略 程序代码如下： #include "stdio.h" #include "stdlib.h" typedef char Datatype; #define MAXSIZE 100 typedef struct bnode { Datatype data; struct bnode *lchild,*rchild; }BNode,*BTree; typedef struct{ BTree data[MAXSIZE]; int front,rear; }seqqueue,*Pseqqueue; typedef struct{ BNode *node; int flag; }Data; typedef struct node { Data Data[MAXSIZE]; int top; }SeqStack,*PSeqStack; PSeqStack Init(void) 数据结构实验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):"); //输入 实验难度： A □ B □ C □序号学号姓名成绩 指导教师（签名） 学期：2017秋季学期 任课教师: 实验题目: 组员及组长: 承担工作： 联系电话: 电子邮件: 完成提交时间：年月日 一、【实验构思（Conceive）】(10%) （本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析） 魔王语言的解释规则： 大写字母表示魔王语言的词汇，小写字母表示人的词汇语言,魔王语言中可以包含括号，魔王语言的产生式规则在程序中给定，当接收用户输入的合法的魔王语言时，通过调用魔王语言翻译函数来实现翻译。 在 A 的基础上，（根据产生式）自定义规则，将一段魔王的话翻译为有意义的人类语言（中文）：输入wasjg,则魔王语言解释为“我爱数据结构”。 运用了离散数学的一些基本知识及程序设计知识。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等） //---------------抽象数据类型的定义------------------// #define STACK_INIT_SIZE 50 #define STACKINCREMENT 10 #define OVERLOW -2 #define ERROR -1 typedef struct { char *base; //顺序栈的栈底指针 int top; //顺序栈的栈顶 int size; //栈元素空间的大小 }SqStack; //结构体类型顺序栈 typedef struct { char *base; int front; int rear; }SqQueue; //结构体类型队列 //---------------各个模块功能的描述------------------// void Init_SqStack(SqStack &s) //初始化顺序桟 void Push_SqStack(SqStack &s, char c) //压入数据 int Pop_SqStack(SqStack &s, char &e) //出桟 char GetTop_SqStack(SqStack s)//或得栈顶 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #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 三题目：哈夫曼编/译码器 班级：姓名：学号：完成日期：15.11.14 一、题目要求 描述：写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0. 输入：输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）； 输入串长小于或等于100的目标报文。 输出：经过编码后的二进制码，占一行； 以及对应解码后的报文，占一行； 最后输出一个回车符。 输入样例： 5 a b c d e 12 40 15 8 25 bbbaddeccbbb 输出样例： 00011111110111010110110000 bbbaddeccbbb 提示：利用编码前缀性质。 二、概要设计 1.设计需要的数据结构：树型结构 2.需要的抽象数据类型： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0)，对于任意j≠k(≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi?Di有数据结构实验三(顺序栈的基本操作)
数据结构实验报告3--链串
数据结构实验报告格式
数据结构_实验三_栈和队列及其应用
数据结构实验报告
数据结构堆栈与队列实验报告
数据结构 实验报告三
数据结构实验报告全集
数据结构实验报告模板
数据结构栈和队列实验报告.doc
数据结构实验三
数据结构实验3二叉树
数据结构实验3
(精选)云南大学软件学院数据结构实验3
数据结构实验报告及心得体会
数据结构栈和队列实验报告
《数据结构》实验3实验报告
数据结构实验三实验报告
- 栈和队列实验报告
- 数据结构栈和队列实验报告
- 数据结构(栈及队列)实验报告 C语言版
- 数据结构_实验三_栈和队列及其应用
- 栈和队列的基本操作及其应用数据结构实验报告书
- 数据结构课程设计实验报告-栈和队列的用
- 数据结构栈和队列C语言实现
- 数据结构栈与队列的实验报告
- 数据结构试验栈和队列
- 数据结构栈和队列实验报告.doc
- 数据结构栈和队列实验报告
- 数据结构实验二题目一栈和队列实验报告
- 简易计算器栈与队列实验报告
- 数据结构--栈和队列的应用实验报告
- 数据结构实验-栈和队列基本操作
- 数据结构实验三栈和队列的应用
- 数据结构栈和队列实验报告
- 东软数据结构实验报告——通过栈和队列来实现进制转换
- 数据结构栈和队列实验报告
- 数据结构实验二题目一栈和队列实验报告