数据结构实验报告目的要求１．掌握图的存储思想及其存储实现..２．掌握图的深度、广度优先遍历算法思想及其程序实现..３．掌握图的常见应用算法的思想及其程序实现..实验内容１．键盘输入数据;建立一个有向图的邻接表..２．输出该邻接表..3．在有向图的邻接表的基础上计算各顶点的度;并输出..4．以有向图的邻接表为基础实现输出它的拓扑排序序列..5．采用邻接表存储实现无向图的深度优先递归遍历..6．采用邻接表存储实现无向图的广度优先遍历..7．在主函数中设计一个简单的菜单;分别调试上述算法..源程序：主程序的头文件：队列#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef struct QNode{ //队的操作QElemType data;struct QNode *next;}QNode;*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;void InitQueueLinkQueue &Q{ //初始化队列Q.front =Q.rear =QueuePtrmallocsizeofQNode;ifQ.front exitOVERFLOW; //存储分配失败Q.front ->next =NULL;}int EnQueueLinkQueue &Q;QElemType e //插入元素e为Q的新的队尾元素{QueuePtr p;p=QueuePtrmallocsizeofQNode;ifp exitOVERFLOW;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear =p;return OK;}int DeQueueLinkQueue &Q;QElemType &e //删除Q的队头元素;用e返回其值{ ifQ.front ==Q.rear return ERROR;QueuePtr p;p=Q.front ->next;e=p->data;Q.front->next=p->next ;ifQ.rear==p Q.rear =Q.front ;freep;return OK;}主程序：#include <stdio.h>#include<stdlib.h>#include"duilie.h"#define TRUE 1#define FALSE 0#define Status int#define MAX_VERTEX_NUM 8 /*顶点最大个数*/#define VertexType char /*顶点元素类型*/enum BOOlean {False;True};BOOlean visitedMAX_VERTEX_NUM; //全局变量——访问标志数组typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;int weight; /*边的权*/}ArcNode; /*表结点*/typedef struct VNode{ int degree;indegree;/*顶点的度;入度*/V ertexType data;ArcNode *firstarc;}VNode/*头结点*/;AdjListMAX_VERTEX_NUM;typedef struct{ AdjList vertices;int vexnum;arcnum;/*顶点的实际数;边的实际数*/}ALGraph;//建立图的邻接表void creat_linkALGraph *G{ int i;j;ArcNode *s;printf"请依次输入顶点数、边数：";scanf"%d%d";&G->vexnum;&G->arcnum;for i=0;i<G->vexnum;i++{ G->verticesi.data='A'+i;G->verticesi.firstarc=NULL;}for i=0;i<G->vexnum;{ printf"请输入顶点的数组坐标若退出;请输入-1：";scanf"%d";&i;ifi==-1 break;printf"请输入顶点所指向下一个顶点的数组坐标：";scanf"%d";&j;s=ArcNode *mallocsizeofArcNode;s->adjvex=j;s->nextarc=G->verticesi.firstarc;G->verticesi.firstarc=s;}}// 输出邻接表void visitALGraph G{ int i;ArcNode *p;printf"%4s%6s%18s\n";"NO";"data";"adjvexs of arcs";for i=0;i<G.vexnum;i++{printf"%4d%5c ";i;G.verticesi.data;forp=G.verticesi.firstarc;p;p=p->nextarcprintf"%3d";p->adjvex;printf"\n";}}// 计算各顶点的度及入度void cacuALGraph *G{ArcNode *p;int i;for i=0;i<G->vexnum;i++{G->verticesi.degree=0;G->verticesi.indegree=0;}//度与初度初始化为零for i=0;i<G->vexnum;i++forp=G->verticesi.firstarc;p;p=p->nextarc{G->verticesi.degree++;G->verticesp->adjvex.degree++;G->verticesp->adjvex.indegree++;}}void print_degreeALGraph G{int i;printf"\n Nom data degree indegree\n";for i=0;i<G.vexnum;i++printf"\n%4d%5c%7d%8d";i;G.verticesi.data;G.verticesi.degree;G.verticesi.indegree;printf"\n";}// 拓扑排序Status TopologiSortALGraph G{int i;count;top=0;stack50;ArcNode *p;cacu&G;print_degreeG;printf"\nTopologiSort is \n";fori=0;i<G.vexnum;i++ifG.verticesi.indegree stacktop++=i;count=0;whiletop=0{i=stack--top;if count==0 printf"%c";G.verticesi.data;else printf"-->%c";G.verticesi.data;count++;forp=G.verticesi.firstarc;p;p=p->nextarcif --G.verticesp->adjvex.indegreestacktop++=p->adjvex;}if count<G.vexnumreturnFALSE; else returnTRUE;}//在图G中寻找第v个顶点的第一个邻接顶点int FirstAdjVexALGraph G;int v{ifG.verticesv.firstarc return 0;else returnG.verticesv.firstarc->adjvex;}//在图G中寻找第v个顶点的相对于u的下一个邻接顶点int NextAdjVexALGraph G;int v;int u{ArcNode *p;p=G.verticesv.firstarc;whilep->adjvex=u p=p->nextarc; //在顶点v的弧链中找到顶点u ifp->nextarc==NULL return 0; //若已是最后一个顶点;返回0else returnp->nextarc->adjvex; //返回下一个邻接顶点的序号}//采用邻接表存储实现无向图的深度优先递归遍历void DFSALGraph G;int i{ int w;visitedi=True; //访问第i个顶点printf"%d->";i;forw=FirstAdjVexG;i;w;w=NextAdjVexG;i;wifvisitedw DFSG;w; //对尚未访问的邻接顶点w调用DFS}void DFSTraverseALGraph G{ int i;printf"DFSTraverse:";fori=0;i<G.vexnum;i++ visitedi=False; //访问标志数组初始化fori=0;i<G.vexnum;i++ifvisitedi DFSG;i; //对尚未访问的顶点调用DFS}//按广度优先非递归的遍历图G;使用辅助队列Q和访问标志数组visited void BFSTraverseALGraph G{int i;u;w;LinkQueue Q;printf"BFSTreverse:";fori=0;i<G.vexnum;i++ visitedi=False; //访问标志数组初始化InitQueueQ; //初始化队列fori=0;i<G.vexnum;i++ifvisitedi{visitedi=True; //访问顶点iprintf"%d->";i;EnQueueQ;i; //将序号i入队列whileQ.front ==Q.rear //若队列不空;继续{DeQueueQ;u; //将队头元素出队列并置为uforw=FirstAdjVexG;u;w;w=NextAdjV exG;u;wifvisitedw //对u的尚未访问的邻接顶点w进行访问并入队列{ visitedw=True;printf"%d->";w;EnQueueQ;w;}}}}void main{ALGraph G;int select;printf" 图的有关操作实验\n ";do{printf"\n1 创建一个有向图的邻接表 2 输出该邻接表\n";printf"3.输出该有向图的度和入度 4.输出该有向图拓扑排序序列\n";printf"5.创建一个无向图的邻接表 6.深度优先递归遍历该无向图\n";printf"7.广度优先遍历该无向图0.退出\n";printf"请输入选择：";scanf"%d";&select;switchselect{case 1:printf"\n创建一个有向图的邻接表：\n";creat_link&G;break;case 2:printf"\n输出该邻接表：\n";visitG;break;case 3:printf"\n输出该有向图的度和入度：\n";cacu&G;print_degreeG;break;case 4:printf"\n输出该有向图拓扑排序序列：\n";ifTopologiSortGprintf"Toposort is not success";break;case 5:printf"\n创建一个无向图的邻接表: \n";creat_link&G;break;case 6:printf"\n深度优先递归遍历该无向图: \n";DFSTraverseG;break;case 7:printf"\n广度优先遍历该无向图：\n";BFSTraverseG;break;case 0:break;default:printf"输入选项错误重新输入\n";}}whileselect;}运行结果截图：1.主菜单界面：2.创建一个有向图的领接表3.输出该邻接表4. 在有向图的邻接表的基础上计算各顶点的度;并输出..5. 输出它的拓扑排序序列6. 输出所建无向图的邻接表7. 深度优先递归遍历该无向图8. 广度优先遍历该无向图说明：本实验用的有向图是课本182页图7.28;无向图为课本168页图a实验总结这次的图的操作实验;与树的操作类似;但又比树复杂;包含更多的存储结构和遍历方法的操作;而且图的遍历需要沿着弧进行;以便输出弧上的信息..本实验中图的遍历采用邻接表的存储结构;在输入图的信息时;首先要画出图的邻接表信息..图有两种遍历的形式;一种为深度优先搜索;另一种为广度优先搜索..由于能力有限;没能实现图的深度非递归优先搜索;而是实现了图的深度递归优先搜索..本实验基本完成了图的操作;也学到了很多关于图的知识和算法..。
实验一顺序表的基本操作一、实验目的掌握线性表的顺序表基本操作：建立、插入、删除、查找、合并、打印等运算。
二、实验要求包含有头文件和main函数；1.格式正确，语句采用缩进格式；2.设计子函数实现题目要求的功能；3.编译、连接通过，熟练使用命令键；4.运行结果正确，输入输出有提示，格式美观。
三、实验设备、材料和工具1.奔腾2计算机或以上机型2.turboc2,win-tc四、实验内容和步骤1. 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。
2. 往该顺序表中第i位置插入一个值为x的数据元素。
3. 从该顺序表中第j位置删除一个数据元素，由y返回。
4. 从该顺序表中查找一个值为e的数据元素，若找到则返回该数据元素的位置，否则返回“没有找到”。
五、程序#include<stdio.h>#include<stdlib.h>#define list_init_size 10#define increment 2typedef struct {int *elem;int length,listsize;}sqlist; //类型定义void initlist_sq(sqlist &L) //初始化顺序表{ }void output(sqlist L) //输出顺序表{ }void insertlist(sqlist &L,int i, int x) //顺序表中插入x{ }void deletelist(sqlist &L,int j, int y) //顺序表中删除y{ }int locateelem(sqlist &L,int e) //顺序表中查找e{ }void main(){ }【运行结果】void initlist_sq(sqlist &L) //初始化顺序表{L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem) exit (OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;}void output(sqlist L) //输出顺序表{for(int i=0;i<=L.length-1;i++)printf("%d,",L.elem[i]);return OK;}void insertlist(sqlist &L,int i, int x) //顺序表中插入x{int p,q;if(i<1||i>L.length+1)return ERROR;if(L.length>=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbasde)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1];for(p=&(L.elem[L.length-1]);p>=q;--p*(p+1)=*p;*p=x;++L.length;return ok;}void deletelist(sqlist &L,int j, int y) //顺序表中删除y{int p,q;if(i<1||I>L.length+1) return ERROR;p=&(L.elem[i-1]);y=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;return ok;}int locateelem(sqlist &L,int e) //顺序表中查找e { int p;i=1;p=L.elem;while(i<=L.length&&!(*p++,e))++i;if(i<=L.length) return i;else return 0;}void main(){int d,p,a,b;int c;initlist_sq(&L);output( L);insertlist( &L, d, a);deletelist( &L, p, b);locateelem( &L, c);}。
《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。
2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。
二、实验内容√ 1、单链表的表示与操作实现 ( * )2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。
2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。
3、严格按照数据结构实验报告模板和规范，及时完成实验报告。
四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode{ DataType data;struct LNode *next;}LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit( ){ // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }3、清空单链表void LinkedListClear(LinkedList L){// 每个模块或函数应加注释，说明函数功能、入口及出口参数}4、检查单链表是否为空int LinkedListEmpty(LinkedList L){ …. }5、遍历单链表void LinkedListTraverse(LinkedList L){….}6、求单链表的长度int LinkedListLength(LinkedList L){ …. }7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i){ //L是带头结点的链表的头指针，返回第 i 个元素 }8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedList LinkedListLocate(LinkedList L, DataType x){ …… }9、向单链表中插入元素void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法// 在链表中第i 个结点之前插入新的元素 x}10、从单链表中删除元素void LinkedListDel(LinkedList L,DataType x){ // 删除以 L 为头指针的单链表中第 i 个结点 }11、用尾插法建立单链表LinkedList LinkedListCreat( ){ …… }㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结五、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。
中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科112姓名：康岩岩学号：201100814220 指导老师：高艳霞2012-11-22实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。
[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
【测试数据】由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、实验报告要求1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
【设计思路】【代码整理】#include "stdafx.h"#include <iostream>#include <malloc.h>using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX_SIZE 20typedef enum{DG,DN,UDG,UDN}Kind;typedef struct ArcNode{int adjvex; //顶点位置struct ArcNode *nextarc; //下一条弧int *info; //弧信息};typedef struct{char info[10]; //顶点信息ArcNode *fistarc; //指向第一条弧}VNode,AdjList[MAX_SIZE];typedef struct{AdjList vertices;int vexnum,arcnum; //顶点数，弧数int kind; //图的种类，此为无向图}ALGraph;//这是队列的节点，仅用于广度优先搜索typedef struct Node{int num;struct Node* next;};//队列的头和尾typedef struct{Node * front;Node *rear;}PreBit;int LocateV ex(ALGraph G,char info[]);//定位顶点的位置Status addArcNode(ALGraph &G,int adjvex); //图中加入弧Status CreatGraph(ALGraph&G);//创建图的邻接表Status DFSTraverse(ALGraph G);//深度优先搜索Status BFSTraverse(ALGraph G);//广度优先搜索Status DFS(ALGraph G,int v);//深度优先搜索中的数据读取函数，用于递归bool visited[MAX_SIZE]; // 访问标志数组//初始化队列Status init_q(PreBit&P_B){P_B.front=P_B.rear=(Node*)malloc(sizeof(Node));if(!P_B.front){exit(OVERFLOW);}P_B.front->next=NULL;}//将数据入队Status en_q(PreBit & P_B,int num){Node *p=(Node*)malloc(sizeof(Node));if(!p){exit(OVERFLOW);}p->num=num;p->next=NULL;P_B.rear->next=p;P_B.rear=p;return OK;}//出队Status de_q(PreBit & P_B){if(P_B.front==P_B.rear){return ERROR;}Node* p=P_B.front->next;P_B.front->next=p->next;if(P_B.rear==p){P_B.rear=P_B.front;}free(p);return OK;}Status CreatGraph(ALGraph&G){cout<<"请输入顶点数目和弧数目"<<endl;cin>>G.vexnum>>G.arcnum;//依次输入顶点信息for(int i=0;i<G.vexnum;i++){cout<<"请输入顶点名称"<<endl;cin>>G.vertices[i].info;G.vertices[i].fistarc=NULL;}//依次输入弧信息for(int k=1;k<=G.arcnum;k++){char v1[10],v2[10]; //用于表示顶点名称的字符数组int i,j; //表示两个顶点的位置BACK: //返回点cout<<"请输入第"<<k<<"条弧的两个顶点"<<endl;cin>>v1>>v2;i=LocateV ex(G,v1); //得到顶点v1的位置j=LocateV ex(G,v2); //得到顶点v2的位置if(i==-1||j==-1){ //头信息不存在则返回重输cout<<"不存在该节点!"<<endl;goto BACK; //跳到BACK 返回点}addArcNode(G,i); //将弧的顶点信息插入表中addArcNode(G,j);}return OK;}//倒序插入弧的顶点信息Status addArcNode(ALGraph &G,int adjvex){ArcNode *p; //弧节点指针p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=adjvex;p->nextarc=G.vertices[adjvex].fistarc;//指向头结点的第一条弧G.vertices[adjvex].fistarc=p; //头结点的第一条弧指向p，即将p作为头结点的第一条弧return OK;}//定位顶点的位置int LocateV ex(ALGraph G,char info[]){for(int i=0;i<G.vexnum;i++){if(strcmp(G.vertices[i].info,info)==0){ //头结点名称与传入的信息相等，证明该头节点存在return i; //此时返回位置}}return -1;}//深度优先搜索Status DFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int i;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;i=LocateV ex(G,v1);if(i==-1){cout<<"不存在该节点!"<<endl;goto BACK;}DFS(G,i);return OK;}//深度优先搜索递归访问图Status DFS(ALGraph G,int v){visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息ArcNode *p;p=G.vertices[v].fistarc; //向头节点第一条while(p) //当弧存在{if(!visited[p->adjvex]){DFS(G,p->adjvex); //递归读取}p=p->nextarc;}return OK;}//广度优先搜索Status BFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int v;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;v=LocateV ex(G,v1);if(v==-1){cout<<"不存在该节点!"<<endl;goto BACK;}PreBit P_B;init_q(P_B);ArcNode *p;visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息en_q(P_B,v); //将头位置v入队while(P_B.front!=P_B.rear){//当队列不为空时，对其进行访问int w=P_B.front->next->num;//读出顶点位置de_q(P_B);//顶点已经访问过，将其出队列p=G.vertices[w].fistarc;//得到与顶点相关的第一条弧while(p){if(!visited[p->adjvex]){en_q(P_B,p->adjvex);//将弧入队，但不读取，只是将其放在队尾}p=p->nextarc;}}return OK;}int _tmain(int argc, _TCHAR* argv[]){ALGraph G;CreatGraph(G);cout<<"深度优先搜索图:"<<endl;DFSTraverse(G);cout<<endl;cout<<"广度优先搜索图:"<<endl;BFSTraverse(G);cout<<endl;system("pause");return 0;}。
