第一篇：数据结构：教学计划的编制问题(实验10实验报告)（范文模版）
数据结构实验报告
实验十:教学计划的编制问题
姓名：戴铁泉 学号：20101410305 班级：物联网1001班 完成日期：2012.05.21
一、问题描述：
若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。基本要求
（1）输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。
（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。
二．需求分析：
1、本程序需要基于图的基本操作来实现
三．概要设计
抽象数据类型：
为实现上述功能需建立一个结点类，线性表类，图类。算法的基本思想：
1、图的构建：
建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。
2、Topsort算法：
先计算每个点的入度，保存在数组中。找到第一个入度为0 的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。程序的流程：
（1）输入模块： 读入图的信息（顶点和边，用线性表进行存储）。（2）处理模块：topsort算法。（3）输出模块：将结果输出。
四．详细设计：
算法的具体步骤： class Node{//结点类 public:
string node;
int position;//位置
Node* next;
bool visit;//是否被访问
Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{
//线性表类 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();}
void insert(int v,string ch){
//插入元素
} Node* current=new Node();current->node=ch;current->position=v;fence->next=current;fence=current;num++;};class Graph{
//图类 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点
} void pushEdge(){ //读入边
string ch1,ch2;int pos1,pos2;for(int i=0;i } cout<<“请输入顶点”< } } cout<<“请输入边”< } line[pos1].insert(pos2,ch2);if(line[j].head->node==ch1)pos1=j; //找到该字母对应的位置 if(line[j].head->node==ch2){ } pos2=line[j].head->position;break; void topsort(){ //拓扑排序 int i;int *d=new int[numVertex]; for(i=0;i //数组初始化 for(i=0;i Node* p=line[i].head;while(p->next!=NULL){ d[p->next->position]++;//计算每个点的入度 } p=p->next;} int top=-1,m=0,j,k; for(i=0;i } while(top!=-1){ if(d[i]==0){ d[i]=top; //找到第一个入度为0的点 top=i; j=top; top=d[top]; cout< m++; Node* p=line[j].head; while(p->next!=NULL){ k=p->next->position; d[k]--; //当起点被删除，时后面的点的入度-1 if(d[k]==0){ d[k]=top; top=k; } p=p->next; } } } cout< if(m //输出点的个数小于输入点的个数，不能完全遍历 cout<<“网络存在回路”< delete []d;} };int main(){ int n,m;cout<<“请输入节点的个数和边的个数”< G.pushVertex();G.pushEdge();G.topsort();system(“pause”); return 0;} 五．调试分析： 将建立的线性表输出来检验图的信息是否完全被读入，构建是否正确。 六．测试结果： 七．实验心得： 1、本实验是在图的遍历问题的基础上做的，图的构建大部分是采用图 的遍历问题中的代码（不过要将结点类中的char改为string型），自己另外写了topsort函数，就完成了整个程序。 2、topsort函数中一开始采用的方法是找到一个入度为0的点，完成 相应的操作后，重新进行搜索，后来改进代码，先搜索入度为0的 点后面连接的点，这样减少了算法复杂度。 八、附件 教学计划的编制问题.cpp #include string node; int position;//位置 Node* next; bool visit;//是否被访问 Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{ //线性表类 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();} void insert(int v,string ch){ //插入元素 Node* current=new Node();current->node=ch;current->position=v; }; } fence->next=current;fence=current;num++;class Graph{ //图类 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点 } void pushEdge(){ //读入边 string ch;for(int i=0;i } cout<<“请输入顶点”< } string ch1,ch2;int pos1,pos2;for(int i=0;i } cout<<“请输入边”< } line[pos1].insert(pos2,ch2);if(line[j].head->node==ch1)pos1=j; //找到该字母对应的位置 if(line[j].head->node==ch2){ } pos2=line[j].head->position;break; void topsort(){ //拓扑排序 int i;int *d=new int[numVertex]; for(i=0;i //数组初始化 for(i=0;i } Node* p=line[i].head;while(p->next!=NULL){ d[p->next->position]++;//计算每个点的入度 p=p->next;} int top=-1,m=0,j,k; for(i=0;i } while(top!=-1){ if(d[i]==0){ d[i]=top; //找到第一个入度为0的点 top=i; j=top; top=d[top]; cout< m++; Node* p=line[j].head; while(p->next!=NULL){ k=p->next->position; d[k]--; //当起点被删除，时后面的点的入度-1 if(d[k]==0){ d[k]=top; top=k; } p=p->next; } } } cout< //输出点的个数小于输入点的个数，不能完全遍历 cout<<“网络存在回路”< delete []d;} };int main(){ int n,m;cout<<“请输入节点的个数和边的个数”< G.pushEdge();G.topsort();system(“pause”); return 0;} 问题描述： 若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。 基本要求： （1）输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。 （2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。 一、需求分析： 本程序需要基于图的基本操作来实现 二、概要设计 ： 抽象数据类型 ： 为实现上述功能需建立一个结点类，线性表类，图类。 算法的基本思想 ： 1、图的构建： 建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。 2、Topsort算法： 先计算每个点的入度，保存在数组中。找到第一个入度为0的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。程序的流程 程序由三个模块组成： 输入模块： 读入图的信息（顶点和边，用线性表进行存储）。处理模块：topsort算法。输出模块：将结果输出。 三、详细设计 算法的具体步骤： class Node{//结点类 public: string node;int position;//位置 Node* next;bool visit;//是否被访问 Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{ //线性表类 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();} void insert(int v,string ch){ //插入元素 Node* current=new Node(); current->node=ch; current->position=v; fence->next=current; fence=current; num++;} };class Graph{ //图类 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点 string ch; for(int i=0;i cout<<“请输入顶点”< cin>>ch; line[i].head->node=ch; line[i].head->position=i; } } void pushEdge(){ //读入边 string ch1,ch2; int pos1,pos2; for(int i=0;i { cout<<“请输入边”< cin>>ch1>>ch2; for(int j=0;j if(line[j].head->node==ch1) pos1=j;//找到该字母对应的位置 if(line[j].head->node==ch2){ pos2=line[j].head->position; break; } } line[pos1].insert(pos2,ch2); } } void topsort(){ //拓扑排序 int i; int *d=new int[numVertex]; for(i=0;i d[i]=0;//数组初始化 for(i=0;i Node* p=line[i].head; while(p->next!=NULL){ d[p->next->position]++;//计算每个点的入度 p=p->next; } } int top=-1,m=0,j,k; for(i=0;i if(d[i]==0){ d[i]=top;//找到第一个入度为0的点 top=i; } while(top!=-1){ j=top;top=d[top]; cout< Node* p=line[j].head; while(p->next!=NULL){ k=p->next->position; d[k]--;//当起点被删除，时后面的点的入度-1 if(d[k]==0){ d[k]=top; top=k; } p=p->next; } } } cout< cout<<“网络存在回路”< 四、调试分析 略。 五、测试结果 本实验的测试结果截图如下： 注：此处由于不会用文件流输入和输出，故在命令提示符上直接进行输入。 六、用户使用说明（可选） 1、本程序的运行环境为windows 操作系统，执行文件为Untitled1.exe 2、运行程序时 提示输入数据 并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。 七、实验心得（可选） 1、本实验是在图的遍历问题的基础上做的，图的构建大部分是采用图 的遍历问题中的代码（不过要将结点类中的char改为string型），自己另外写了topsort函数，就完成了整个程序。 2、topsort函数中一开始采用的方法是找到一个入度为0的点，完成 相应的操作后，重新进行搜索，后来改进代码，先搜索入度为0的 点后面连接的点，这样减少了算法复杂度。 附录（实验代码）： #include Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{ //线性表类 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();} void insert(int v,string ch){ //插入元素 Node* current=new Node(); current->node=ch; current->position=v; fence->next=current; fence=current; num++;} };class Graph{ //图类 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点 string ch; for(int i=0;i cout<<“请输入顶点”< cin>>ch; line[i].head->node=ch; line[i].head->position=i; } } void pushEdge(){ //读入边 string ch1,ch2; int pos1,pos2; for(int i=0;i { cout<<“请输入边”< cin>>ch1>>ch2; for(int j=0;j if(line[j].head->node==ch1) pos1=j;//找到该字母对应的位置 if(line[j].head->node==ch2){ pos2=line[j].head->position; break; } } line[pos1].insert(pos2,ch2); } } void topsort(){ //拓扑排序 int i; int *d=new int[numVertex]; for(i=0;i d[i]=0;//数组初始化 for(i=0;i Node* p=line[i].head; while(p->next!=NULL){ d[p->next->position]++;//计算每个点的入度 p=p->next; } } int top=-1,m=0,j,k; for(i=0;i if(d[i]==0){ d[i]=top;//找到第一个入度为0的点 top=i; } while(top!=-1){ j=top;top=d[top]; cout< Node* p=line[j].head; while(p->next!=NULL){ k=p->next->position; d[k]--;//当起点被删除，时后面的点的入度-1 if(d[k]==0){ d[k]=top; top=k; } p=p->next; } } } cout< cout<<“网络存在回路”< 《数据结构与算法设计》 迷宫问题实验报告 ——实验二 专业：物联网工程 班级：物联网1班 学号：15180118 姓名：刘沛航 一、实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1、概要设计 （1）设定栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={ 操作结果：构造一个空栈 Push（&S，e） 初始条件：栈已经存在 操作结果：将e所指向的数据加入到栈s中 Pop（&S,&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元 StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack （2）设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL} ROW={ InitMaze(MazeType &maze, int a[][COL], int row, int col){ 初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。 操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍 在迷宫四周加上一圈障碍 MazePath（&maze）{ 初始条件：迷宫maze已被赋值 操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变 } PrintMaze（M）{ 初始条件：迷宫M已存在 操作结果：以字符形式输出迷宫 } }ADTmaze （3）本程序包括三个模块 a、主程序模块 void main(){ 初始化； 构造迷宫； 迷宫求解； 迷宫输出； } b、栈模块——实现栈的抽象数据类型 c、迷宫模块——实现迷宫的抽象数据类型 2、详细设计 （1）坐标位置类型： typedef struct{ int row;//迷宫中的行 int col;//......的列 }PosType;//坐标 （2）迷宫类型： typedef struct{ int m,n;int arr[RANGE][RANGE];}MazeType;//迷宫类型 void InitMaze(MazeType &maze, int a[][COL], int row, int col)//设置迷宫的初值，包括边缘一圈的值 Bool MazePath(MazeType &maze,PosType start, PosType end)//求解迷宫maze中，从入口start到出口end的一条路径 //若存在，则返回true，否则返回false Void PrintMaze（MazeType maze）//将迷宫打印出来 （3）栈类型： typedef struct{ int step;//当前位置在路径上的“序号” PosType seat;//当前的坐标位置 DirectiveType di;//往下一个坐标位置的方向 }SElemType;//栈的元素类型 typedef struct{ SElemType *base;SElemType *top;int stacksize;}SqStack;栈的基本操作设置如下： Void InitStack（SqStack & S） //初始化，设S为空栈（S.top=NUL）Void DestroyStack(Stack &S)//销毁栈S，并释放空间 Void ClearStack（SqStack & S）//将栈S清空 Int StackLength（SqStack &S）//返回栈S的长度 Status StackEmpty（SqStack &S）？、若S为空栈（S.top==NULL），则返回TRUE，否则返回FALSE Statue GetTop（SqStack &S，SElemType e） //r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSE Statue Pop(SqStack&S，SElemType e)//若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE //否则栈不变，并返回FALSE Statue Push(SqStack&S，SElemType &e)//若分配空间程控，则删除栈顶并以e带回其值，则返回TRUE //否则返回FALSE Void StackTraverse（SqStack &S，Status）（*Visit）（SElemType e））//从栈顶依次对S中的每个节点调用函数Visit 4求迷宫路径的伪码算法： Status MazePath(MazeType &maze,PosType start, PosType end){ //求解迷宫maze中,从入口start到出口end的一条路径 InitStack(s);PosType curpos = start;int curstep = 1;//探索第一部 do{ if(Pass(maze,curpos)){ //如果当前位置可以通过,即是未曾走到的通道块 FootPrint(maze,curpos);//留下足迹 e = CreateSElem(curstep,curpos,1);//创建元素 Push(s,e);if(PosEquare(curpos,end))return TRUE;curpos =NextPos(curpos,1);//获得下一节点:当前位置的东邻 curstep++;//探索下一步 }else{ //当前位置不能通过 if(!StackEmpty(s)){ Pop(s,e);while(e.di==4 &&!StackEmpty(s)){ MarkPrint(maze,e.seat);Pop(s,e);//留下不能通过的标记,并退回步 } if(e.di<4){ e.di++;Push(s,e);//换一个方向探索 curpos = NextPos(e.seat,e.di);//设定当前位置是该方向上的相块 }//if }//if }//else }while(!StackEmpty(s));return FALSE;} //MazePath 四、程序调试分析 1.首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。 2.栈的元素类型 一开始有点迷惑，后来就解决了 3.本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n） 五、用户使用说明 1．本程序运行在windows系列的操作系统下，执行文件为：Maze_Test.exe。 六、程序运行结果 1.建立迷宫： 2．通过1功能建立8*8的迷宫后，通过2功能继续建立迷宫内部： 通过建立自己设定单元数目建立迷宫内墙。3．通过3功能观察已建立的迷宫结构： 4．通过4功能确立迷宫起点和终点： （此处像我们随机选择4,4和2,7分别为起点终点） 5．执行5功能，判断是否有路径走出迷宫： 这种情况无法走出迷宫。 我们再次观察图像设4,4和1,6分别为起点终点，再运行5功能。 观察到可以成功解开迷宫步数从1依次开始。 七、程序清单 #include // 列值 #define MAXLENGTH 25 // 设迷宫的最大行列为25 typedef int MazeType[MAXLENGTH][MAXLENGTH];// 迷宫数组[行][列] typedef struct // 栈的元素类型 { int ord;// 通道块在路径上的＂序号＂ PosType seat;// 通道块在迷宫中的＂坐标位置＂ int di;// 从此通道块走向下一通道块的＂方向＂(0～3表示东～北)}SElemType; // 全局变量 MazeType m;// 迷宫数组 int curstep=1;// 当前足迹,初值为1 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示 typedef struct SqStack { SElemType *base;// 在栈构造之前和销毁之后，base的值为NULL SElemType *top; int stacksize; // 构造一个空栈S int InitStack(SqStack *S){ // 为栈底分配一个指定大小的存储空间 (*S).base =(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base) (*S).top =(*S).base; return 1; // 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE;exit(0);}SqStack;// 顺序栈 // 栈顶指针 // 当前已分配的存储空间，以元素为单位 } // 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S){ if(S.top == S.base) else } // 插入元素e为新的栈顶元素。int Push(SqStack *S, SElemType e){ if((*S).top-(*S).base >=(*S).stacksize)// 栈满，追加存储空间 { } *((*S).top)++=e;return 1;} // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e){ if((*S).top ==(*S).base) 左 return 1;} // 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 // 当迷宫m的b点的序号为1(可通过路径)，return 1;否则，return 0。int Pass(PosType b){ if(m[b.x][b.y]==1) else return 0;return 1;return 0;*e = *--(*S).top; // 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向 (*S).base =(SElemType *)realloc((*S).base ，(*S).top =(*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;((*S).stacksize + STACKINCREMENT)* sizeof(SElemType));exit(0);if(!(*S).base)return 0;return 1;} void FootPrint(PosType a) // 使迷宫m的a点的序号变为足迹(curstep)，表示经过 { m[a.x][a.y]=curstep;} // 根据当前位置及移动方向，返回下一位置 PosType NextPos(PosType c,int di){ PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};// {行增量,列增量} // 移动方向,依次为东南西北 c.x+=direc[di].x;c.y+=direc[di].y;return c;} // 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b){ m[b.x][b.y]=-1;} // 若迷宫maze中存在从入口start到出口end的通道，则求得一条 // 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end){ SqStack S;PosType curpos;SElemType e; InitStack(&S);curpos=start;do { if(Pass(curpos)){// 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos);// 留下足迹 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e);// 入栈当前位置及状态 curstep++;// 足迹加1 if(curpos.x==end.x&&curpos.y==end.y)// 到达终点(出口) } else return 1;curpos=NextPos(curpos,e.di);{// 当前位置不能通过 } if(!StackEmpty(S)){ } Pop(&S,&e);// 退栈到前一位置 curstep--;while(e.di==3&&!StackEmpty(S))// 前一位置处于最后一个方向(北){ } if(e.di<3)// 没到最后一个方向(北){ } e.di++;// 换下一个方向探索 Push(&S,e);curstep++;// 设定当前位置是该新方向上的相邻块 curpos=NextPos(e.seat,e.di); MarkPrint(e.seat);// 留下不能通过的标记(-1)Pop(&S,&e);// 退回一步 curstep--;}while(!StackEmpty(S));return 0;} // 输出迷宫的结构 void Print(int x,int y){ int i,j; for(i=0;i } } void main(){ PosType begin,end;int i,j,x,y,x1,y1,n,k;for(j=0;j //清屏函数 printf(“***************************************************nnn”);printf(“ 1请输入迷宫的行数,列数n”);printf(“ 2请输入迷宫内墙单元数n”);printf(“ 3迷宫结构如下n”);printf(“ 4输入迷宫的起点和终点n”);printf(“ 5输出结果n”);printf(“ 0退出n”);printf(“nn请选择 ”);scanf(“%d”,&n);switch(n){ case 1:{ printf(“请输入迷宫的行数,列数(包括外墙)：(空格隔开)”); scanf(“%d%d”, &x, &y); for(j=1;j { for(i=1;i for(j=1;j // 迷宫左边列的周边即左边墙 m[j][y-1]=0;// 迷宫右边列的周边即右边墙 for(i=0;i // 迷宫上面行的周边即上边墙 m[x-1][i]=0;// 迷宫下面行的周边即下边墙 物 联 网 班 -15180118-刘沛 航 } }break; case 2: {printf(“请输入迷宫内墙单元数：”); scanf(“%d”,&j); printf(“请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n”); for(i=1;i<=j;i++) { scanf(“%d%d”,&x1,&y1); } m[x1][y1]=0; }break; case 3:{ Print(x,y);printf(“刘沛航建立的迷宫，定义墙元素值为0,可通过路径为1，输入0退出”);scanf(“%d”,&k);}break; case 4:{ printf(“请输入起点的行数,列数：（空格隔开）”); scanf(“%d%d”,&begin.x,&begin.y); printf(“请输入终点的行数,列数：（空格隔开）”); scanf(“%d%d”,&end.x,&end.y);}break; case 5:{ if(MazePath(begin,end))// 求得一条通路 { } else printf(“此迷宫没有从入口到出口的路径，谢谢使用刘沛航的程序n”);printf(“输入0退出”);scanf(“%d”,&k);}break;} }while(n!=0);} printf(“此迷宫从入口到出口的一条路径如下，谢谢使用刘沛航的程序:n”);Print(x,y);// 输出此通路 注意：实验结束后提交一份实验报告电子文档 电子文档命名为“学号+姓名”，如：E01214058宋思怡 《数据结构》实验报告 （一）学号：姓名：专业年级： 实验名称：线性表 实验日期：2014年4月14日 实验目的： 1、熟悉线性表的定义及其顺序和链式存储结构； 2、熟练掌握线性表在顺序存储结构上实现基本操作的方法； 3、熟练掌握在各种链表结构中实现线性表基本操作的方法； 4、掌握用 C/C++语言调试程序的基本方法。 实验内容： 一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）初始化顺序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）输出顺序表L； （4）输出顺序表L长度； （5）判断顺序表L是否为空； （6）输出顺序表L的第3个元素； （7）输出元素24的位置； （8）在L的第4个元素前插入元素0； （9）输出顺序表L； （10）删除L的第5个元素； （11）输出顺序表L。 源代码 调试分析（给出运行结果界面） 二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： „„„„ „„„„ 小结或讨论: （1）实验中遇到的问题和解决方法 （2）实验中没有解决的问题 （3）体会和提高 南京信息工程大学实验（实习）报告 实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍 系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700 3实验一顺序表的基本操作及C语言实现 【实验目的】 1、顺序表的基本操作及 C 语言实现 【实验要求】 1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。 2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。 【实验内容】 1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作； 2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重 复的元素），并求这样的两个集合的并。 【实验结果】 [实验数据、结果、遇到的问题及解决] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。 优点：简单，数据元素的提取速度快； 缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n） 求两个集合的并集 该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。第二篇：数据结构实验报告十—教学计划编制问题
第三篇：数据结构迷宫问题实验报告
第四篇：数据结构实验报告
第五篇：数据结构实验报告
点击咨询 