数据结构实验报告

2022-08-25

国民经济的快速发展下，越来越多的行业，开始通过报告的方式，用于记录工作内容。怎么样才能写出优质的报告呢？以下是小编收集整理的《数据结构实验报告一》，仅供参考，希望能够帮助到大家。

第一篇：数据结构实验报告一

数据结构实验一图[推荐]

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称：实验二——图学生姓名：佘晨阳班

级： 2014211117 班内序号： 20 学

号： 2014210491 日

期： 2015年12月05日

1．实验要求

根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：

1、图的建立

2、图的销毁

3、深度优先遍历图

4、广度优先遍历图

5、使用普里姆算法生成最小生成树

6、使用克鲁斯卡尔算法生成最小生成树

7、求指定顶点到其他各顶点的最短路径

8、其他：比如连通性判断等自定义操作

编写测试main()函数测试图的正确性

2. 程序分析

本实验要求掌握图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。

2.1 存储结构

存储结构：1.不带权值的无向图邻接矩阵

2.带权值的无向图邻接矩阵

3.带权值的有向图邻接矩阵

1．不带权值的无向图邻接矩阵

第1页北京邮电大学信息与通信工程学院

2带权值的无向图邻接矩阵.

3.带权值的有向图邻接矩阵

[备注]：

1. 在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式 2. 在使用PRIM、KRUSKAL、

3. 在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式

2.2 关键算法分析

第2页北京邮电大学信息与通信工程学院

一．图的邻接矩阵构造函数：

1.关键算法： template Graph::Graph(f a[], int n, int e)

//带权值的图的构造函数 { int i, j, k, height; f s1, s2; vnum = n; arcnum = e; for (k = 0; k < n; k++) { vertex[k] = a[k]; }

//初始化顶点

for (k = 0; k

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

{

arc[k][i] = -1;

if (i == k) arc[k][i] = 0;

//初始化权值的大小

}

visited[k] = 0; } cout << endl; for (k = 0; k

//初始化边

{

cout << "请输入线性链接节点:";

cin >> s1 >> s2 >> height;

arc[convert(s1)][convert(s2)] = height;

arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)]; //采用无向图带权值的邻接矩阵

} cout << endl; cout << "所得邻接矩阵为：" << endl;

for (k = 0; k

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

{

if (arc[k][i] == -1)

cout << "∞" << " ";

else cout << arc[k][i] << " ";

//打印邻接矩阵的格式

}

cout << endl;

} cout << endl 2.算法的时间复杂度

第3页北京邮电大学信息与通信工程学院

有构造可知，初始化时其时间复杂度：O(n2)

二．深度优先便利DFS:

1.关键算法

①从某顶点v出发并访问

②访问v的第一个未访问的邻接点w，

访问w的第一个未访问的邻接点u，

……

③若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历

④直到所有和v路径相通的顶点都被访问到； 2.代码图解：

深度优先遍历示意图 3.代码详解：

template void Graph::DFS(int v) { cout << vertex[v]; visited[v] = 1;

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

//连通图

if ((visited[j] == 0) && (arc[v][j] >= 1)) DFS(j); //当存在回路时，则连通深一层遍历

} 4.时间复杂度

时间复杂度：O(n2)

空间复杂度：栈的深度O(n)

辅助空间O(n)

第4页北京邮电大学信息与通信工程学院

三．广度遍历BFS 1.关键算法 ①访问顶点v ②依次访问v的所有未被访问的邻接点v1,v2,v3…

③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点 ④反复①②③ ，直到所有和v路径相通的顶点都被访问到；

2.代码图解

3.代码详解

1.初始化队列Q

2.访问顶点v， visited[v]=1

3. while(队列非空)

3.1 v=队头元素出队

3.2 访问队头元素的所有未访问的邻接点 4.时间复杂度

时间复杂度：O(n2)

空间复杂度：辅助空间O(n)

四.最小生成树——普里姆算法

1,关键思路

一般情况下，假设n个顶点分成两个集合：U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点)，则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构：

邻接矩阵辅助数据结构：

int

adjvex[MAXSIZE]; // U集中的顶点序号

第5页北京邮电大学信息与通信工程学院

int

lowcost[MAXSIZE];

// U(V-U)的最小权值边

2.代码图解

第6页北京邮电大学信息与通信工程学院

第7页北京邮电大学信息与通信工程学院

3;代码详解

template void Graph::Prim() { for (int i = 0; i < vnum; i++)

//辅助数组存储所有到的V0边

{

adjvex[i] = 0; lowcost[i] = arc[0][i];

} lowcost[0] = 0; for (int j = 1; j < vnum; j++)

//循环n-1次

{

int k = Mininum(lowcost);

//求下一个顶点

cout << vertex[adjvex[k]] << "->" << vertex[k] << endl;

lowcost[k] = 0;

//U=U+{Vk}

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

//设置辅助数组

{

if ((lowcost[j] != 0 && arc[k][j] < lowcost[j]))

{

lowcost[j] = arc[k][j];

adjvex[j] = k;

}

第8页北京邮电大学信息与通信工程学院

} } 4,时间复杂度：

时间复杂度O(n2)，适合稠密图

五.最小生成树----克鲁斯卡尔算法

1,关键思路

先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。 2.代码图解：

3.代码详解

template void Graph::Kruskal()

//最小生成树—kruskal算法

{ cout<<"Krusal算法结果为："<

int k = 0, j = 0;

while (k < vnum - 1) {

int m = vedgelist[j].fromv, n = vedgelist[j].endv;

int sn1 = vset[m];

int sn2 = vset[n];

//两个顶点分属

第9页北京邮电大学信息与通信工程学院

不同的集合

if (sn1 != sn2)

{

cout << vertex[m] << "->" << vertex[n] << endl;

k++;

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

{

if (vset[i] == sn2)

vset[i] = sn1;

//集合sn2全部改成sn1

}

j++; } } 4.时间复杂度

时间复杂度O(nlogn)，适合稀疏图

六．最短路径——Dijkstra算法 1.关键代码

• 按路径长度递增的次序产生源点到其余各顶点的最短路径。 • 1)设置集合s存储已求得的最短路径的顶点， • 2)初始状态：s=源点v • 3)叠代算法：

• 直接与v相连的最近顶点vi,加入s • 从v经过vi可以到达的顶点中最短的，加入s

……

2.代码图解

第10页北京邮电大学信息与通信工程学院

3.代码详解

emplate void Graph::ShotPath(f x)

//关于最短路径的初始化 { int v=convert(x);

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

//初始化路径和点

{

s[i]=0;

disk[i] = arc[v][i];

if (disk[i] != maxs) path[i] = v;

else path[i] = -1; } s[v] = 1; disk[v] = 0; path[v]=-1; for (int i = 0; i < vnum; i++)

//反复经过从该点到其他点的路径

{

if ((v = FindMin()) == -1) continue;

s[v] = 1;

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

if (!s[j] && (disk[j]>arc[v][j] + disk[v]))

{

第11页北京邮电大学信息与通信工程学院

disk[j] = arc[v][j] + disk[v];

path[j] = v;

} } Print();

//打印路径长度和遍历

} 4.时间复杂度

时间复杂度为：n^2

七．判断连通图算法

template bool Graph::judgegraph() { DFS(convert(vertex[0])); if(count==vnum)

{

cout<<"该图为连通图！*******输入成功！"<

return false;

} else {

cout<<"该图不为连通图！*******请重新输入"<

return true;

} }

时间复杂度：n^2

3. 程序运行结果

1. 测试主函数流程：

第12页北京邮电大学信息与通信工程学院

函数流程图：

1. 输入图的连接边并打印

构造下面所示图的邻接矩阵：

第13页北京邮电大学信息与通信工程学院

2.判断图连通是否成功

3.BFS DFS PRIM算法的实现

第14页北京邮电大学信息与通信工程学院

4.克鲁斯卡尔算法实现过程

4. 有向图邻接矩阵的构建

第15页北京邮电大学信息与通信工程学院

插入V0位置后打印距离并开始回溯

总结

1.调试时出现的问题及解决的方法

问题一：prim算法中

解决方法：调整循环条件，修正函数体注意有无Next的区别

第16页北京邮电大学信息与通信工程学院

问题二：BFS和DFS同时在一个类里作用时会输出错误

解决方案：每次BFS/DFS使用时都把visited数组初始化一遍

问题三：在最短路径，经常出现了停止输入的情况

解决方法：改return为continue，并修改打印算法 2.心得体会

通过本次实验，基本熟练掌握了c++基本语句，尤其对图的结构及应用有了较深了解；调试代码时尽量做到完成一个代码段调试一次，可以最快检测出错误所在；类的封装和调用，类的共有成员和私有成员的设置。

3.下一步的改进

第一，设置增加图节点和边的函数

第二，实现图形化输出图的路径的功能

第三，主函数设计简单，不要过于累赘

4.程序中出现的亮点

1) 利用dfs算法衍生生成判断是否为连通图的连通算法

2) 采用graph类实现所有图的所有算法，所需的数据类型均在私有成员内，封装 3) 利用convert函数采取象意输入，采用ABCD的节点输入方式而并非转化成01234再输入。

4) BFS中采用c++标准库的。

5) 打印邻接矩阵时，打印出非链接的∞符号和与自身路径的0距离 6) 判断图为非连通图后，提示输入错误，重新输入图元素

第17页

第二篇：实验一微型计算机结构认识

一、实验目的

1.了解计算机组成原理。

2.认识微型计算机的主要组成部件。

二、实验环境

ATX主板，机箱，软驱，硬盘，光驱，CPU，内存条，电源，显卡，声卡，网卡，键盘，鼠标，显示器等。

三、实验内容、步骤及要求

1. 识别微型计算机的主要组成部件。

主板、CPU、软驱、硬盘、光驱、内存、电源、显卡、显示器等。

2. 了解微型计算机各个部件的功能。

主板：又叫Mother Board(母板)。可以说是PC机的神经系统，属于多层印刷电路板，通过板上的各种数据与控制总线同各个部件联系。

CPU：英文全称是"Central Processor Unit"，翻译成中文就是"中央处理器单元"。微机系统核心部件，对程序指令进行解释和处理。

软驱：软盘读写驱动器，驱动可携带软盘的读写。

硬盘：硬盘驱动器与金属盘体的封装，是可高速读写数据的外存储器。

光驱：光盘读写驱动器，驱动可携带光盘的读取。

内存：是指CPU可以直接读取的内部存储器，主要是以芯片的形式出现。电源：通过将220v交流电转换为低压直流电，为计算机系统提供运行动力。显卡：驱动显示缓冲区中的数据转换为RGB显示信号。

显示器：是电脑的输出设备之一，外形与电视机相似，将显示信号在屏幕上进行显示。

3. 登记组成计算机的各种部件的名称和数量。

要求对计算机的组成从一般了解到非常熟悉，要能很快的指出计算机各部件的名称和摆放位置以及连接情况。

4. 抄录型号、编号和主要参数。

电脑型号Acer E1-471G--32352G50Mnks

操作系统Windows 7 家庭普通版 64位 SP1

处理器Intel(R) Core(TM) i3-2350M @2.3GHz双核

主板Acer JE41_CP

内存2 GB DDR3

主硬盘500GB SATA

显卡NVIDIA GeForce GT 620M

显示器高清LED宽屏14英寸

光驱DVD SuperMulti双层刻录

网卡Acer Nplify(TM) 802.11b/g/N

四、实验心得与体会

通过本次实验，我对计算机的主要组件及性能参数有了一定程度的了解，为以后选购电脑以及电脑维护打下了一定的基础。

第三篇：实验一：数据的预处理及探索

实验一：数据的预处理及探索实验目的：

1、数据的基本描述统计

2、找出变量中的离群值及极端值并修正(参考

5.1.2)

3、找出对输出变量影响最重要的一些输入变

量。(参考5.6.2)

第四篇：数据结构实验报告

南京信息工程大学实验(实习)报告

实验(实习)名称数据结构实验(实习)日期 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)

{

1 //在非递减的顺序表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->datadata){} 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所对应的实际参数集合中得到并集。

第五篇：数据结构实验报告

一. 题目要求

1)编程实现二叉排序树，包括生成、插入，删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历;

3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二. 解决方案

对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上

typedefintElemType;

//数据类型 typedefint Status;

//返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType

data;

structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数

if(T==NULL) {

T = (BiTree)malloc(sizeof(BiTNode));

T->data=key;

T->lChild=T->rChild=NULL;

return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){

InsertBST(T->rChild,key); } else

return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

//数据域

InsertBST(bst,a[i]);

i++; } returnbst; } int Delete(BiTree&T)

{

BiTreeq,s;

} if(!(T)->rChild){ //右子树为空重接它的左子树

q=T; T=(T)->lChild; free(q); }else{

if(!(T)->lChild){ //若左子树空则重新接它的右子树

q=T; T=(T)->rChild; }else{ q=T; s=(T)->lChild; while(s->rChild){

q=s; s=s->rChild; }

(T)->data=s->data; //s指向被删除结点的前驱

if(q!=T)

q->rChild=s->lChild;

else

q->lChild=s->lChild;

free(s); } } return 1;

//删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T) return 0; else{

if(key==(T)->data) return Delete(T);

else{

if(key<(T)->data)

returnDeleteBST(T->lChild,key);

else

returnDeleteBST(T->rChild,key);

} } } intPosttreeDepth(BiTree T){//求深度

inthr,hl,max; if(!T==NULL){ hl=PosttreeDepth(T->lChild); hr=PosttreeDepth(T->rChild); max=hl>hr?hl:hr; return max+1; } else

return 0;

} void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL) return ; printtree(T->rChild,nlayer+1); for(inti=0;i

"); } printf("%d ",T->data); printtree(T->lChild,nlayer+1); } void PreOrderNoRec(BiTree root)//先序非递归遍历 { BiTree p=root; BiTreestack[50]; intnum=0; while(NULL!=p||num>0) {

while(NULL!=p)

{

printf("%d ",p->data);

stack[num++]=p;

p=p->lChild;

}

num--;

p=stack[num];

p=p->rChild; } printf(" "); } void InOrderNoRec(BiTree root)//中序非递归遍历 { BiTree p=root;

} intnum=0; BiTreestack[50]; while(NULL!=p||num>0) { while(NULL!=p) {

stack[num++]=p;

p=p->lChild; } num--; p=stack[num]; printf("%d ",p->data); p=p->rChild; } printf(" "); void PostOrderNoRec(BiTree root)//后序非递归遍历 { BiTree p=root; BiTreestack[50]; intnum=0; BiTreehave_visited=NULL;

while(NULL!=p||num>0) {

while(NULL!=p)

{

stack[num++]=p;

p=p->lChild;

}

p=stack[num-1];

if(NULL==p->rChild||have_visited==p->rChild)

{

printf("%d ",p->data);

num--;

have_visited=p;

p=NULL;

}

else

{

p=p->rChild;

} } printf(" "); }

int main(){//主函数

printf("

---------------------二叉排序树的实现-------------------"); printf(" "); int layer; inti; intnum; printf("输入节点个数:"); scanf("%d",&num); printf("依次输入这些整数(要不相等)"); int *arr=(int*)malloc(num*sizeof(int)); for(i=0;i

scanf("%d",arr+i); } BiTreebst=CreateBST(arr,num); printf(" "); printf("二叉树创建成功!"); printf(" "); layer=PosttreeDepth(bst); printf("树状图为: "); printtree(bst,layer); int j; int T; int K; for(;;){ loop: printf(" "); printf("

***********************按提示输入操作符************************:"); printf(" "); printf("

1:插入节点

2:删除节点

3:打印二叉树

4:非递归遍历二叉树

5:退出"); scanf("%d",&j);

switch(j){

case 1:

printf("输入要插入的节点:");

scanf("%d",&T);

InsertBST(bst,T);

printf("插入成功!"); printf("树状图为: ");

printtree(bst,layer);

break;

case 2:

}

printf("输入要删除的节点"); scanf("%d",&K); DeleteBST(bst,K); printf("删除成功!"); printf("树状图为: "); printtree(bst,layer); break; case 3: layer=PosttreeDepth(bst); printtree(bst,layer); break; case 4:

printf("非递归遍历二叉树"); printf("先序遍历: "); PreOrderNoRec(bst); printf("中序遍历: "); InOrderNoRec(bst);

printf("后序遍历: ");

PostOrderNoRec(bst);

printf("树状图为: ");

printtree(bst,layer);

break; case 5:

printf("程序执行完毕!");

return 0; } goto loop; } return 0; 对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为 typedefintElemType;

//数据类型 typedefstring SlemType;

typedefint Status;

//返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name; ElemType score; ElemType no;

//数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; 参数不是key,而是另外三个

intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数

if(T==NULL) {

T = (BiTree)malloc(sizeof(BiTNode));

T->no=no;T->name=name;T->score=score;

T->lChild=T->rChild=NULL;

return 1; } else if(nono){ InsertBST(T->lChild,no,score,name); } else if(key>T->data){

InsertBST(T->rChild,no,score,name); } else

return 0; } 其他含参函数也类似即可完成50个信息存储

用数组存储50个信息，查看以往代码

#include #include using namespace std; class student{ private: intnum; string name; int ob1; int ob2; intara; public: void set(inta,stringb,intc,int d); void show(); int average(); }; void student ::set(inta,stringb,intc,int d){ num=a; name=b; ob1=c; ob2=d; ara=(c+d)/2; } void student::show(){ cout<<"学号："numlock; switch(numlock){ case 0: cout<<"输入想查询的学号"<>i; if(i==j){ cout<<"该学号信息已被删除"<>j; delete[j]ptr; cout<<"删除成功"<>k; if(k!=j){

cout<<"该学号信息已经存在，添加失败"<

break; } cout<<"重新输入添加的学号"<>q; cout<<"输入姓名"<>w; cout<<"输入科目一的成绩"<>e; cout<<"输入科目二的成绩"<>r; ptr[k].set(q,w,e,r); break; case 3: for( m=1;m<20;m++){

for(int n=m+1;n<20;n++){

if(ptr[m].average()

student a;

a=ptr[m];

ptr[m]=ptr[n];

ptr[n]=a;

}}

ptr[m].show(); } break; case 4: cout<<"谢谢使用"<

二叉排序树储存数据界面(储存学生信息略)

创建二叉树：