数据结构C语言版实验报告.docx

数据结构C语言版实验报告.docx

《数据结构C语言版实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版实验报告.docx（28页珍藏版）》请在冰点文库上搜索。

数据结构C语言版实验报告

（此文档为word格式，下载后您可任意编辑修改！

）

数据结构（C语言版）实验报告

学院计算机科学与技术

专业计算机大类强化

学号xxx

班级xxx

姓名xxx

指导教师xxx

实验1

实验题目：

单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。

实验主要步骤：

1、分析、理解给出的示例程序。

调试程序，并设计输入数据（如：

bat，cat，eat，fat，（）

{

charch[10],num[5];

LinkList）:

"）;输入"y"或"n"去选择是否删除结点

scanf（"%s",num）;

if（strcmp（num,"y"）==0||strcmp（num,"Y"）==0）{

printf（"PleaseinputDelete_data:

"）;

scanf（"%s",ch）;输入要删除的字符串

DeleteList（）:

"）;输入"y"或"n"去选择是否增加结点

scanf（"%s",num）;

if（strcmp（num,"y"）==0||strcmp（num,"Y"）==0）

{

p;若p=NULL则查找失败，否则p指向找到的值为key的结点

}

==========修改程序：

增加节点=======

ListNode*AddNode（LinkList"）;

if（pp==NULL）{没有重复的字符串，插入到链表中

s=（ListNode*）malloc（sizeof（ListNode））;

strcpy（s->data,ch）;

printf（"ok3\n"）;

s->next=error"）;

exit（0）;

}

while（q->next!

=p）p为要删除的结点，q为p的前结点

q=q->next;

r=q->next;

q->next=r->next;

free（r）;释放结点

}

===========打印链表=======

voidprintlist（LinkList"）;

}

==========删除所有结点，释放空间===========

voidDeleteAll（LinkList）:

y

PleaseinputDelete_data:

）:

y

PleaseinputInsert_data:

put

position:

5

mat,lat,jat,fat,eat,put,cat,bat,

请按任意键继续...

示意图：

心得体会：

本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。

另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。

实验2

实验题目：

二叉树操作设计和实现

实验目的：

掌握二叉树的定义、性质及存储方式，各种遍历算法。

实验要求：

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

实验主要步骤：

1、分析、理解程序。

2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

实验代码

#include"stdio.（NULL）;读入#，返回空指针

else{

T=（BinTNode*）malloc（sizeof（BinTNode））;生成结点

T->data=ch;

T->lchild=CreatBinTree（）;构造左子树

T->rchild=CreatBinTree（）;构造右子树

return（T）;

}

}

========NLR先序遍历=============

voidPreorder（BinTreeT）

{

if（T）{

printf（"%c",T->data）;访问结点

Preorder（T->lchild）;先序遍历左子树

Preorder（T->rchild）;先序遍历右子树

}

}

========LNR中序遍历===============

voidInorder（BinTreeT）

{

if（T）{

Inorder（T->lchild）;中序遍历左子树

printf（"%c",T->data）;访问结点

Inorder（T->rchild）;中序遍历右子树

}

}

==========LRN后序遍历============

voidPostorder（BinTreeT）

{

if（T）{

Postorder（T->lchild）;后序遍历左子树

Postorder（T->rchild）;后序遍历右子树

printf（"%c",T->data）;访问结点

}

}

=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========

intTreeDepth（BinTreeT）

{

int（max+1）;

}

elsereturn（0）;

}

====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========

voidLevelorder（BinTreeT）

{

intfront=0,rear=1;

BinTNode*cq[Max],*p;定义结点的指针数组cq

cq[1]=T;根入队

while（front!

=rear）

{

front=（front+1）%NodeNum;

p=cq[front];出队

printf（"%c",p->data）;出队，输出结点的值

if（p->lchild!

=NULL）{

rear=（rear+1）%NodeNum;

cq[rear]=p->lchild;左子树入队

}

if（p->rchild!

=NULL）{

rear=（rear+1）%NodeNum;

cq[rear]=p->rchild;右子树入队

}

}

}

====数叶子节点个数==========

intcountleaf（BinTreeT）

{

int

（1）;

elsereturn0;

}

==========主函数=================

voidmain（）

{

BinTreeroot;

chari;

intdepth;

printf（"\n"）;

printf（"CreatBin_Tree；Inputpreorder:

"）;输入完全二叉树的先序序列，

用#代表虚结点，如ABD###CE##F##

root=CreatBinTree（）;创建二叉树，返回根结点

do{从菜单中选择遍历方式，输入序号。

printf（"\t**********select************\n"）;

printf（"\t1:

PreorderTraversal\n"）;

printf（"\t2:

IorderTraversal\n"）;

printf（"\t3:

Postordertraversal\n"）;

printf（"\t4:

PostTreeDepth,Nodenumber,Leafnumber\n"）;

printf（"\t5:

LevelDepth\n"）;按层次遍历之前，先选择4，求出该树的结点数。

printf（"\t0:

Exit\n"）;

printf（"\t*******************************\n"）;

fflush（stdin）;

scanf（"%c",&i）;输入菜单序号（0-5）

switch（i-'0'）{

case1:

printf（"PrintBin_treePreorder:

"）;

Preorder（root）;先序遍历

break;

case2:

printf（"PrintBin_TreeInorder:

"）;

Inorder（root）;中序遍历

break;

case3:

printf（"PrintBin_TreePostorder:

"）;

Postorder（root）;后序遍历

break;

case4:

depth=TreeDepth（root）;求树的深度及叶子数

printf（"BinTreeDepth=%dBinTreeNodenumber=%d",depth,NodeNum）;

printf（"BinTreeLeafnumber=%d",countleaf（root））;

break;

case5:

printf（"LevePrintBin_Tree:

"）;

Levelorder（root）;按层次遍历

break;

default:

exit

（1）;

}

printf（"\n"）;

}while（i!

=0）;

}

实验结果：

CreatBin_Tree；Inputpreorder:

ABD###CE##F##

**********select************

1:

PreorderTraversal

2:

IorderTraversal

3:

Postordertraversal

4:

PostTreeDepth,Nodenumber,Leafnumber

5:

LevelDepth

0:

Exit

*******************************

1

PrintBin_treePreorder:

ABDCEF

2

PrintBin_TreeInorder:

DBAECF

3

PrintBin_TreePostorder:

DBEFCA

4

BinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnumber=3

5

LevePrintBin_Tree:

ABCDEF

0

Pressanykeytocontinue

二叉树示意图

心得体会：

这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解。

同时认识到，在设计程序时辅以图形化的描述是非常有用处的。

实验3

实验题目：

图的遍历操作

实验目的：

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

实验要求：

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。

实验主要步骤：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。

1．邻接矩阵作为存储结构

#include"stdio.,e;图中的顶点数n和边数e

}MGraph;用邻接矩阵表示的图的类型

=========建立邻接矩阵=======

voidCreatMGraph（MGraph*G）

{

inti,j,k;

chara;

printf（"InputVertexNum（n）andEdgesNum（e）:

"）;

scanf（"%d,%d",&G->n,&G->e）;输入顶点数和边数

scanf（"%c",&a）;

printf（"InputVertexstring:

"）;

for（i=0;in;i++）

{

scanf（"%c",&a）;

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

}

for（i=0;in;i++）

for（j=0;jn;j++）

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

printf（"Inputedges,CreatAdjacencyMatrix\n"）;

for（k=0;ke;k++）{读入e条边，建立邻接矩阵

scanf（"%d%d",&i,&j）;输入边（Vi，Vj）的顶点序号

G->edges[i][j]=1;

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

}

}

=========定义标志向量，为全局变量=======

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited[MaxVertexNum];

========DFS：

深度优先遍历的递归算法======

voidDFSM（MGraph*G,inti）

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

intj;

printf（"%c",G->vexs[i]）;访问顶点Vi

visited[i]=TRUE;置已访问标志

for（j=0;jn;j++）依次搜索Vi的邻接点

if（G->edges[i][j]==1&&!

visited[j]）

DFSM（G,j）;（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点

}

voidDFS（MGraph*G）

{

inti;

for（i=0;in;i++）

visited[i]=FALSE;标志向量初始化

for（i=0;in;i++）

if（!

visited[i]）Vi未访问过

DFSM（G,i）;以Vi为源点开始DFS搜索

}

===========BFS：

广度优先遍历=======

voidBFS（MGraph*G,intk）

{以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索

inti,j,f=0,r=0;

intcq[MaxVertexNum];定义队列

for（i=0;in;i++）

visited[i]=FALSE;标志向量初始化

for（i=0;in;i++）

cq[i]=-1;队列初始化

printf（"%c",G->vexs[k]）;访问源点Vk

visited[k]=TRUE;

cq[r]=k;Vk已访问，将其入队。

注意，实际上是将其序号入队

while（cq[f]!

=-1）{队非空则执行

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

for（j=0;jn;j++）依次Vi的邻接点Vj

if（G->edges[i][j]==1&&!

visited[j]）{Vj未访问

printf（"%c",G->vexs[j]）;访问Vj

visited[j]=TRUE;

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

}

}

}

==========main=====

voidmain（）

{

inti;

MGraph*G;

G=（MGraph*）malloc（sizeof（MGraph））;为图G申请内存空间

CreatMGraph（G）;建立邻接矩阵

printf（"PrintGraphDFS:

"）;

DFS（G）;深度优先遍历

printf（"\n"）;

printf（"PrintGraphBFS:

"）;

BFS（G,3）;以序号为3的顶点开始广度优先遍历

printf（"\n"）;

}

2．邻接链表作为存储结构

#include"stdio.,e;图中当前顶点数和边数

}ALGraph;图类型

=========建立图的邻接表=======

voidCreatALGraph（ALGraph*G）

{

inti,j,k;

chara;

EdgeNode*s;定义边表结点

printf（"InputVertexNum（n）andEdgesNum（e）:

"）;

scanf（"%d,%d",&G->n,&G->e）;读入顶点数和边数

scanf（"%c",&a）;

printf（"InputVertexstring:

"）;

for（i=0;in;i++）建立边表

{

scanf（"%c",&a）;

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

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

}

printf（"Inputedges,CreatAdjacencyList\n"）;

for（k=0;ke;k++）{建立边表

scanf（"%d%d",&i,&j）;读入边（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的边表头部

}

}

=========定义标志向量，为全局变量=======

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited[MaxVertexNum];

========DFS：

深度优先遍历的递归算法======

voidDFSM（ALGraph*G,inti）

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

EdgeNode*p;

printf（"%c",G->adjlist[i].vertex）;访问顶点Vi

visited[i]=TRUE;标记Vi已访问

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

while（p）{依次搜索Vi的邻接点Vj，这里j=p->adjvex

if（!

visited[p->adjvex]）若Vj尚未被访问

DFSM（G,p->adjvex）;则以Vj为出发点向纵深搜索

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

}

}

voidDFS（ALGraph*G）

{

inti;

for（i=0;in;i++）

visited[i]=FALSE;标志向量初始化

for（i=0;in;i++）

if（!

visited[i]）Vi未访问过

DFSM（G,i）;以Vi为源点开始DFS搜索

}

==========BFS：

广度优先遍历=========

voidBFS（ALGraph*G,intk）

{以Vk为源点对用邻接链表表示的图G进行广度优先搜索

inti,f=0,r=0;

EdgeNode*p;

intcq[MaxVertexNum];定义FIFO队列

for（i=0;in;i++）

visited[i]=FALSE;标志向量初始化

for（i=0;i<=G->n;i++）

cq[i]=-1;初始化标志向量

printf（"%c",G->adjlist[k].vertex）;访问源点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（"%c",G->adjlist[p->adjvex].vertex）;访问Vj

visited[p->adjvex]=TRUE;

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

}

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

}

}endwhile

}

==========主函数===========

voidmain（）

{

inti;

ALGraph*G;

G=（ALGraph*）malloc（sizeof（ALGraph））;

CreatALGraph（G）;

printf（"PrintGraphDFS:

"）;

DFS（G）;

printf（"\n"）;

printf（"PrintGraphBFS:

"）;

BFS（G,3）;

printf（"\n"）;

}

实验结果：

1.邻接矩阵作为存储结构

执行顺序：

InputVertexNum（n）andEdgesNum（e）:

8，9

InputVertexstring:

Inputedges,CreatAdjacencyMatrix

01

02

13

14

25

26

37

47

56

PrintGraphDFS:

PrintGraphBFS:

2.邻接链表作为存储结构

执行顺序：

InputVertexNum（n）andEdgesNum（e）:

8，9

InputVertexstring:

Inputedges,CreatAdjacencyList

01

02

13

14

25

26

37

47

56

PrintGraphDFS:

PrintGraphBFS:

心得体会：

这次实验较以前的实验难度加大，必须先理解深度优先和广度优先两种遍历思路，和数据结构中队列的基本操作，才能看懂理解代码。

同时图这种数据结构对抽象的能力要求非常高，代码不容易看懂，排错也比较麻烦，应该多加练习，才能掌握。

实验4

实验题目：

排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合