数据结构实验指导书-2014

更新时间:2023-11-04 17:39:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

《数据结构》

实验指导书

计算机专业实验中心

2014年9月

目 录

实验一、线性表的实现及操作(一) .............................................................................................. 5 实验二、线性表的实现及操作(二) .............................................................................................. 8 实验三、线性表的应用 .................................................................................................................... 13 实验四、二叉树的实现及操作 ........................................................................................................ 14 实验五、二叉树的应用 .................................................................................................................... 19 实验六、图的遍历操作 .................................................................................................................... 20 实验七、图的应用 ............................................................................................................................ 33

2

《数据结构》上机实验的内容和要求

通过上机实验加深对课程内容的理解,增加感性认识,提高程序设计、开发及调试能力。 本实验指导书适用于16学时《数据结构》实验课,实验项目具体内容如下:

序号 实 验 名 称 线性表的实现及操作1 (一) 线性表的实现及操作2 (二) 3 4 5 6 7 8 内 容 每组 实验 提 要 人数 时数 顺序表建立、插入、删除1 2 等基本操作 单链表的建立、插入、删1 2 除等基本操作 约瑟夫环问题或者长整数线性表的应用 1 2 相加的设计与实现 二叉树的基本操作:树的二叉树的实现及操作 建立、前序、中序、后序1 2 遍历 二叉树的应用 赫夫曼树 1 2 图的遍历:深度优先和广图的遍历 1 2 度优先 最短路径算法:Dijkstra图的应用 1 2 算法和Floyd算法 对实验课涉及到的算法进算法性能测试、总结行性能测试、对实验所遇1 2 和答疑 到的问题进行总结和答疑 实验 实验 分值(总要求 类别 100分) 必做 设计 15分 必做 设计 15分 选作 综合 10分 必做 设计 20分 选作 综合 10分 必做 设计 20分 选作 综合 10分 其中,第1、2、4、6实验项目为设计性实验,的其内容为程序代码分析与调试,要求每位同学在每次实验课结束前通过检查。这部分实验应撰写1份实验报告,总分70分。

第3、5、7实验项目为综合应用性实验,学生根据自己的兴趣和基础选作。这三个实验要求学生利用所学的理论知识解决实际问题,每一个实验应撰写一份实验报告,每个实验10分。

此实验指导书也适用于8学时《数据结构》实验课,要求完成第1、2、4、6实验项目。

实验报告要求

请按照实验教师要求,按时提交实验报告电子版文件。 实验报告格式可个性化定义,内容包括但不限于以下内容:

1、题目、姓名、学号、班级(首页)

2、需求分析:陈述程序设计的任务,强调程序要做什么,明确规定: (1)输入的形式和输出值的范围; (2)输出的形式; (3)程序所能达到的功能;

3

(4)测试数据:包括正确的输入输出结果和错误的输入及输出结果。

3、概要设计:说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。 4、详细设计:提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。 5、调试分析:

(1)调试过程中所遇到的问题及解决方法; (2)算法的时空分析; (3)经验与体会。

6、用户使用说明:说明如何使用你设计的程序,详细列出每一步操作步骤。(如果程序操作简单,可略去)

7、测试结果:列出对于给定的输入所产生的输出结果。(若有可能,测试随输入规模的增长所用算法的实际运行时间的变化) 8、总结

4

实验一、线性表的实现及操作(一)

一、实验目的

了解和掌握线性表的顺序存储结构;掌握用C语言上机调试线性表的基本方法;掌握线性表的基本操作:插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算,以及对相应算法的性能分析。

二、实验要求

给定一段程序代码,程序代码所完成的功能为:(1)建立一个线性表;(2)依次输入数据元素1,2,3,4,5,6,7,8,9,10;(3)删除数据元素5;(4)依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个,要求使用顺序表。

程序中有3处错误的地方,有标识,属于逻辑错误,对照书中的代码仔细分析后,要求同学们修改错误的代码,修改后上机调试得到正确的运行结果。

三、程序代码 #include #define MaxSize 100 typedef int DataType;

typedef struct {

DataType list[MaxSize]; int size; } SeqList;

void ListInitiate(SeqList *L) { }

int ListLength(SeqList L) { }

int ListInsert(SeqList *L, int i, DataType x)

/*在顺序表L的位置i(0 ≤ i ≤ size)前插入数据元素值x*/ /*插入成功返回1,插入失败返回0*/

5

/*初始化顺序表L*/ /*定义初始数据元素个数*/

L->size = 0;

/*返回顺序表L的当前数据元素个数*/

return L.size;

/*若当前结点curr非空,在curr的右子树插入元素值为x的新结点*/ /*原curr所指结点的右子树成为新插入结点的右子树*/ /*若插入成功返回新插入结点的指针,否则返回空指针*/ BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) {

BiTreeNode *s, *t;

if(curr == NULL) return NULL;

t = curr->rightChild; /*保存原curr所指结点的右子树指针*/

s = (BiTreeNode *)malloc(sizeof(BiTreeNode));

s->data = x; s->rightChild = t;

/*新插入结点的右子树为原curr的右子树*/

s->leftChild = NULL;

curr->rightChild = s; /*新结点成为curr的右子树*/

return curr->rightChild;

/*返回新插入结点的指针*/

}

void PreOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数前序遍历二叉树t {

if(t != NULL) {//此小段有一处错误 visit(t->data);

PreOrder(t-> rightChild, visit); PreOrder(t-> leftChild, visit);

} }

void InOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数中序遍历二叉树t {

if(t != NULL) {//此小段有一处错误 InOrder(t->leftChild, visit);

InOrder(t->rightChild, visit);

16

} }

visit(t->data);

void PostOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数后序遍历二叉树t {

if(t != NULL) {//此小段有一处错误 } }

void Visit(DataType item) {

printf(\}

BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中 {

BiTreeNode *find=NULL; if(root!=NULL) { }

return find; }

void main(void) {

17

visit(t->data);

PostOrder(t->leftChild, visit); PostOrder(t->rightChild, visit);

if(root->data==x) else { }

find=Search(root->leftChild,x); if(find==NULL)

find=Search(root->rightChild,x); find=root;

BiTreeNode *root, *p, *pp,*find; char x='E';

Initiate(&root);

p = InsertLeftNode(root, 'A'); p = InsertLeftNode(p, 'B'); p = InsertLeftNode(p, 'D'); p = InsertRightNode(p, 'G');

p = InsertRightNode(root->leftChild, 'C'); pp = p;

InsertLeftNode(p, 'E'); InsertRightNode(pp, 'F');

printf(\前序遍历:\

PreOrder(root->leftChild, Visit); printf(\中序遍历:\ InOrder(root->leftChild, Visit); printf(\后序遍历:\ PostOrder(root->leftChild, Visit);

find=Search(root,x); if(find!=NULL) printf(\数据元素%c在二叉树中 \\n\

else printf(\数据元素%c不在二叉树中 \\n\

Destroy(&root); }

18

实验五、二叉树的应用

一、实验目的

加深对二叉树的各项操作实现的理解,增强学生利用二叉树知识解决实际问题的能力。 二、实验要求

本实验为选作题目。需编程实现,撰写实验报告,并在实验报告中给出测试结果。 三、实验内容

假设有一串字符串“DBDBDABDCDADBDADBDADACDBDBD”或者你自己给定一串任意的字符串,利用赫夫曼树编程给出这串字符串的赫夫曼编码。

以下是上面字符串编码后程序运行结果示例(自己所编程序的输入输出形式可自由发挥):

四、 实验报告要求 1、 基本要求见第3页。 2、 给出实验结果。

3、 对算法的性能进行测试,要求分析算法的复杂度,测试程序在不同长度的字符串下运

行情况。

19

实验六、图的遍历操作

一、实验目的

掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。

二、 实验要求

采用邻接矩阵和邻接链表作为图的存储结构,完成有向图和无向图的DFS和BFS操作。本实验给出了示例程序,其中共有4处错误,错误段均有标识,属于逻辑错误。请认真理解程序,修改程序代码,并在电脑上调试运行。

三、 DFS和BFS 的基本思想

深度优先搜索法DFS的基本思想:从图G中某个顶点Vo出发,首先访问Vo,然后选择一个与Vo相邻且没被访问过的顶点Vi访问,再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问,……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W,从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。

广度优先算法BFS的基本思想:从图G中某个顶点Vo出发,首先访问Vo,然后访问与Vo相邻的所有未被访问过的顶点V1,V2,……,Vt;再依次访问与V1,V2,……,Vt相邻的起且未被访问过的的所有顶点。如此继续,直到访问完图中的所有顶点。

四、 示例程序

1. 邻接矩阵作为存储结构的程序示例 #include\#include\

#define MaxVertexNum 100 //定义最大顶点数 typedef struct{

char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum];

//邻接矩阵,可看作边表

int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) {

int i,j,k; char a;

printf(\

20

V7 V3 V4 V5 V6 V1 V0 V2 图G的示例

scanf(\输入顶点数和边数 scanf(\ printf(\ for(i=0;in;i++) {

scanf(\

G->vexs[i]=a; //读入顶点信息,建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

G->edges[i][j]=0; //初始化邻接矩阵

printf(\

for(k=0;ke;k++) { //读入e条边,建立邻接矩阵 }

//=========定义标志向量,为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum];

//========DFS:深度优先遍历的递归算法====== void DFSM(MGraph *G,int i)

{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索,邻接矩阵是0,1矩阵 int j;

printf(\访问顶点Vi visited[i]=TRUE; //置已访问标志 for(j=0;jn;j++) //依次搜索Vi的邻接点 }

void DFS(MGraph *G) { \\\\此段代码有一处错误 int i;

for(i=0;in;i++) }

21

scanf(\输入边(Vi,Vj)的顶点序号 G->edges[i][j]=1;

G->edges[j][i]=1; //若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句

}

if(G->edges[i][j]==1 && ! visited[j])

DFSM(G,j); //(Vi,Vj)∈E,且Vj未访问过,故Vj为新出发点

visited[i]=FALSE; //标志向量初始化 if(!visited[i]) //Vi未访问过

DFS (G,i); //以Vi为源点开始DFS搜索

for(i=0;in;i++)

//===========BFS:广度优先遍历======= void BFS(MGraph *G,int k)

{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0;

int cq[MaxVertexNum]; //定义队列 for(i=0;in;i++)

visited[i]=FALSE;

//标志向量初始化

for(i=0;in;i++)

cq[i]=-1; //队列初始化 printf(\访问源点Vk visited[k]=TRUE;

cq[r]=k; //Vk已访问,将其入队。注意,实际上是将其序号入队 while(cq[f]!=-1) { //队非空则执行 }

//==========main===== void main() {

int i; MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间 CreatMGraph(G); //建立邻接矩阵 printf(\

DFS(G); //深度优先遍历 printf(\

printf(\

BFS(G,3); //以序号为3的顶点开始广度优先遍历 printf(\}

执行顺序:

Input VertexNum(n) and EdgesNum(e): 8,9 Input Vertex string: 01234567

22

i=cq[f]; f=f+1; //Vf出队

for(j=0;jn;j++) //依次Vi的邻接点Vj

if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问 \\\\以下三行代码

printf(\访问Vj visited[j]=FALSE;

r=r+1; cq[r]=j; //访问过Vj入队

有一处错误

}

}

Input edges,Creat Adjacency Matrix 0 1 0 2 1 3 1 4 2 5 2 6 3 7 4 7 5 6

Print Graph DFS: 01374256 Print Graph BFS: 31704256

2. 邻接链表作为存储结构程序示例 #include\#include\

#define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex; //邻接点域 struct node *next; //链域 }EdgeNode;

typedef struct vnode{ //顶点表结点 char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 }VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型typedef struct {

AdjList adjlist; //邻接表

int n,e; //图中当前顶点数和边数 } ALGraph; //图类型 //=========建立图的邻接表======= void CreatALGraph(ALGraph *G) {

int i,j,k; char a;

EdgeNode *s; //定义边表结点

printf(\ scanf(\读入顶点数和边数 scanf(\

printf(\

23

for(i=0;in;i++) //建立边表 { scanf(\

G->adjlist[i].vertex=a; //读入顶点信息

G->adjlist[i].firstedge=NULL; //边表置为空表

}

printf(\ for(k=0;ke;k++) { //建立边表 scanf(\读入边(Vi,Vj)的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点 s->adjvex=j; //邻接点序号为j s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; //邻接点序号为i s->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部

}

}

//=========定义标志向量,为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum];

//========DFS:深度优先遍历的递归算法====== void DFSM(ALGraph *G,int i)

{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索 EdgeNode *p;

printf(\访问顶点Vi visited[i]=TRUE; //标记Vi已访问 p=G->adjlist[i].firstedge; //取Vi边表的头指针

while(p) { //依次搜索Vi的邻接点Vj,这里j=p->adjvex \\\\以下3行代码有一处错误 if(! visited[p->adjvex]) //若Vj尚未被访问

DFS (G,p->adjvex); //则以Vj为出发点向纵深搜索 p=p->next; //找Vi的下一个邻接点

} }

void DFS(ALGraph *G) {

int i;

for(i=0;in;i++)

24

}

visited[i]=FALSE; //标志向量初始化 if(!visited[i]) //Vi未访问过

DFSM(G,i); //以Vi为源点开始DFS搜索

for(i=0;in;i++)

//==========BFS:广度优先遍历========= void BFS(ALGraph *G,int k)

{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索 int i,f=0,r=0; EdgeNode *p;

int cq[MaxVertexNum]; //定义FIFO队列 for(i=0;in;i++) visited[i]=FALSE;

//标志向量初始化

for(i=0;i<=G->n;i++)

cq[i]=-1; //初始化标志向量 printf(\访问源点Vk visited[k]=TRUE;

cq[r]=k; //Vk已访问,将其入队。注意,实际上是将其序号入队 while(cq[f]!=-1) { 队列非空则执行 i=cq[f]; f=f+1; //Vi出队

p=G->adjlist[i].firstedge; //取Vi的边表头指针

while(p) { //依次搜索Vi的邻接点Vj(令p->adjvex=j) if(!visited[p->adjvex]) { //若Vj未访问过 printf(\访问Vj visited[p->adjvex]=TRUE;

\\\\以下3行代码有一处错误

r=r+1; cq[r]=p->adjvex; //访问过的Vj入队

}

p=p->next->next; //找Vi的下一个邻接点 }

}//endwhile

}

//==========主函数=========== void main() {

int i; ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G);

printf(\

25

DFS(G); printf(\

printf(\ BFS(G,3); printf(\}

执行顺序:

Input VertexNum(n) and EdgesNum(e): 8,9 Input Vertex string: 01234567 Input edges,Creat Adjacency List 0 1 0 2 1 3 1 4 2 5 2 6 3 7 4 7 5 6

Print Graph DFS: 02651473 Print Graph BFS: 37140265

1

、求出各个叶子节点的权重值

26

输入一个字符串,统计其中各个字母的个数和总的字母个数。

27

2

、构造哈夫曼树

统计出的字母种类为叶子结点个数,每个字母个数为相应的权值,建立哈

28

夫曼树。

29

3

、打印哈弗曼树的功能模块

30

本文来源:https://www.bwwdw.com/article/0bb2.html

微信扫码分享

《数据结构实验指导书-2014.doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档
下载全文
范文搜索
下载文档
Top