数据结构实验报告




实验报告


课程：数结构
班级：网络工程
学号：
姓名：


















实验1 链表插入删
实验目
1 解单链表循环链表双链表基知识
2 掌握算法思想数结构描述
3 掌握链表插入删相关语句基方法
二 实验步骤求
1实验前准备
a) 解C语言基概念
b) 解C语言基段落
2 机操作
a) 解链表基知识
b) 掌握算法思想数结构描述
c) 掌握链表插入删相关语句基方法
三 实验容
设两头结点单链表头指针分hahb链中数域data链域next两链表数递增序存放现求hb表ha表中ha递增序中ha表中已数hb中hb中数ha中hb链表算法中允许破坏
四 实验结果
1 源代码：
#include
#include

typedef struct LNode{
int data
struct LNode *next
}LNode *LinkList

LinkList CreatList (LinkList &L int n){
int i
LinkList p R
L(LinkList) malloc (sizeof(LNode))
L>nextNULL
RL
printf(请输入d整数(递增序)：＼nn)
for(ini>0i){
p(LinkList) malloc (sizeof(LNode))
scanf(d&p>data)
R>nextp
Rp
}
p>nextNULL
return L
}

LinkList ConnectList(LinkList & La LinkList & Lb){
LinkList pa pb pc q Lc
LcpcLa
paLa>next
pbLb>next
while(pa&&pb){
if(pa>datadata){
pc>nextpa
pcpa
papa>next
}
else if(pa>data>pb>data){
pc>nextpb
pcpb
pbpb>next
}
else{
pc>nextpa
pcpa
papa>next
qpb>next
free(pb)
pb q
}

}
pc>nextpapapb
free(Lb)
return Lc
}

void print (LinkList & L){
LinkList p
pL>next
printf(链表：＼n)
while(p){
printf(d p>data)
pp>next
}
printf(＼n)
}

void main (){

int n1 n2
LinkList La Lb Lc

printf(输入创建链表La长度(n1)：)
scanf(d&n1)
LaCreatList(Lan1)
printf(La)
print(La)

printf(输入创建链表Lb长度(n2)：)
scanf(d&n2)
LbCreatList(Lbn2)
printf(Lb)
print(Lb)

LcConnectList(La Lb)
printf(合Lc)
print(Lc)

}

2 运行界面截图：


五 总结（出现问题解决方案知识点总结）（少100字）
1 链表结尾处处处理（p>nextNULL）需注意链表尾指针空否会指意区域系统会报错
2 链表合程中注意相数域取中外需释放
3 链表操作程中注意指针位置变化




















实验3 二叉树遍历
实验目
1 解二叉树前序中序序列排列
2 C语言二叉树数结构联系起
3 掌握生成二叉树链表结构
4 掌握层次输出二叉树结点
5 掌握动态二叉树转换静态二叉链表
二实验步骤求
1实验前准备
（1）解二叉树基概念
（2）解二叉树基结构
2机操作
（3）解二叉树前序中序序列排列
（4）C语言二叉树数结构联系起
（1） 掌握生成二叉树链表结构
（2） 掌握层次输出二叉树结点
（3） 掌握动态二叉树转换静态二叉链表
三实验容
创建二叉树棵动态二叉树进行分析静态二叉链表表示二叉树动态二叉链表结构中结点三字段：datalchildrchild静态二叉链表数组作存储空间数组元素存储二叉树结点三字段：datalchildrchildlchildrdhild分存储左右孩子标
四实验结果
1 源代码：
#include
#include
typedef struct BiTNode{
char data
struct BiTNode *lchild*rchild
}BiTNode*BiTree

typedef struct ATNode{
char data
int lchild
int rchild
}ATNode

BiTree create (BiTree &T){ 构建二叉树
char ch
scanf(c&ch)
if(ch＇#＇)
TNULL
else{
T(BiTree)malloc(sizeof(BiTNode))
T>datach
create(T>lchild)
create(T>rchild)
}
return T
}

static int length0 初始化二叉树结点数

static char *nodeNULL 定义数组存储节点信息

void preorder(BiTree T){
if(T)
{
printf(c>T>data)
length++
node[length]T>data
preorder(T>lchild)
preorder(T>rchild)
}
}

static ATNode *TarrayNULL 定义结构数组存储二叉树结点信息
static int num11 num21 定义静态变量

void initTarray(BiTree T)
{
if(TNULL)
{
Tarray[num1++]dataT>data
initTarray(T>lchild)
initTarray(T>rchild)
}
}

void transform(BiTree T){
int i
if(T){
if(T>lchildNULL){
i0
while(T>lchild>datanode[i])
i++
Tarray[num2]lchildi
}
if(T>rchildNULL){
i0
while(T>rchild>datanode[i])
i++
Tarray[num2]rchildi
}
num2++
transform(T>lchild)
transform(T>rchild)
}

}


void main (){
BiTree TNULL
printf(输入二叉树节点中值：＼n)
create(T)
node(char *)malloc(sizeof(char)*length)
printf(先序次序输出二叉树节点中值：＼n)
preorder(T)
printf(＼n)
printf(二叉树静态二叉链表：＼n)

Tarray(ATNode*)malloc(sizeof(ATNode)*length)
if (TarrayNULL)
{
printf(out of memorypress any key to quit＼n)
exit(0)
}

0初始化数组
for(int i1i Tarray[i]dataTarray[i]lchildTarray[i]rchild0

动态二叉树链表转化静态数组
initTarray(T)
transform(T)
printf(标 data lchild rchild＼n)
for(int j1j {
printf(2d8c8d8d＼n j Tarray[j]data Tarray[j]lchild Tarray[j]rchild)
}
printf(长度：d＼nlength)
}

2 运行界面截图：

五 总结（出现问题解决方案知识点总结）（少100字）
1 二叉树创建程中递方法需搞清楚样递生成二叉树
2 二叉树链表转化成静态时需知道双亲结点左右孩子位置应需先节点编序号静态数组存储然先序遍历找结点应左右孩子lchildrchild记住编号空时置0遍历完成静态数组存储
3 关键需弄清楚先序遍历程找应结点左右孩子
实验4 图深度优先搜索
实验目
1 解图定义特点区分图图概念
2 解图数结构搜索方法
3 掌握图邻接矩阵邻接表表示方法
4 写出图深度优先搜索程序
二实验求
1 解图定义特点区分图图概念
2 解图数结构搜索方法
3 掌握图邻接矩阵邻接表表示方法
4 写出图深度优先搜索程序
三实验容
设图Gn点e条边写算法建立G邻接表深度优先搜索输出顶点求该算法时间复杂性O（n+e）邻接表身占空间外O（1）辅助空间

四实验结果
1 源代码：
#include
#include
#include
#include

定义Status值
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 2
#define NULL 0
#define MAX 20

typedef int Status

typedef struct Node
{
int elem
struct Node *next
}Node*QNode

typedef struct
{
QNode front
QNode rear
}Queue

typedef struct ArcNode 头节点
{
int adjvex 该边指顶点位置
struct ArcNode *nextarc 指条边
}ArcNode

typedef struct VNode 表节点
{
int data 顶点信息
ArcNode *firstarc 指第条附该节点边指针
}VNodeAdjList[MAX]

typedef struct
{
AdjList vertices 表节点
int vexnum 节点数
int arcnum 边条数
}Graph

Status InitQueue(Queue *Q) 初始化队列
{
Q>frontQ>rear(QNode)malloc(sizeof(Node))
if(Q>front)
exit(OVERFLOW)
Q>front>nextNULL
return OK
}

Status EnQueue(Queue *Qint e) 入队
{
QNode p(QNode)malloc(sizeof(Node))
if(p)
exit(OVERFLOW)
p>eleme
p>nextNULL
Q>rear>nextp
Q>rearp
return OK
}

Status DeQueue(Queue *Qint *e) 出队
{
QNode p
pQ>front>next
Q>front>nextp>next
if(Q>rearp)
Q>rearQ>front
*ep>elem
free(p)
return OK
}

Status QueueEmpty(Queue Q) 判断队否空
{
if(QrearQfront)
return TRUE
else
return FALSE
}

int LocateVex(Graph *G int v) 返回节点v图中位置
{
int i
for(i0ivexnum++i)
if(G>vertices[i]datav)
break
else
continue
if(ivexnum)
return i
else
return 1
}

Status CreateGraph(Graph *G)
{
邻接表形式创建连通图G
int m n i j k v1 v2 flag0
ArcNode *p1 *q1 *p *q
printf(Please input the number of VNode)
scanf(d&m)
printf(Please input the number of ArcNode)
scanf(d&n)
G>vexnumm 顶点数目
G>arcnumn 边数目
for(i0ivexnum++i)
{
G>vertices[i]datai+1 顶点信息
G>vertices[i]firstarcNULL
}
输出顶点信息
printf(Output the message of VNode＼n)
for(i0ivexnum++i)
printf(vd＼nG>vertices[i]data)

for(k0karcnum++k) 输入边两结点值
{
printf(Please input the d edge beginpoint and endpoint k+1)
scanf(dd&v1&v2)
iLocateVex(Gv1)
jLocateVex(Gv2)

if(i>0&&j>0)
{
++flag

p(ArcNode *)malloc(sizeof(ArcNode))
p>adjvexj
p>nextarcNULL
if(G>vertices[i]firstarc)
G>vertices[i]firstarcp
else
{
for(p1G>vertices[i]firstarcp1>nextarcp1p1>nextarc)
p1>nextarcp
}

q(ArcNode *)malloc(sizeof(ArcNode))
q>adjvexi
q>nextarcNULL
if(G>vertices[j]firstarc)
G>vertices[j]firstarcq
else
{
for(q1G>vertices[j]firstarcq1>nextarcq1q1>nextarc)
q1>nextarcq
}
}
else
{
printf(Nothava this edge＼n)
kflag
}
}

printf(The Adjacency List is＼n) 输出邻接表
for(i0ivexnum++i)
{
printf(＼td vd>iG>vertices[i]data)
pG>vertices[i]firstarc
while(p>nextarc)
{
printf(d>p>adjvex)
pp>nextarc
}
printf(d＼np>adjvex)
}
return OK
}

int FirstAdjVex(Graph Gint v)
{
返回v第邻接顶点
if(Gvertices[v]firstarc)
return Gvertices[v]firstarc>adjvex
else
return 1
}

int NextAdjVex(Graph Gint vint w)
{
返回v中相w邻接顶点
int flag0
ArcNode *p
pGvertices[v]firstarc
while(p)
{
if(p>adjvexw)
{
flag1
break
}
pp>nextarc
}
if(flag &&p>nextarc)
return p>nextarc>adjvex
else
return 1
}

int Visited[MAX]

void DFS(Graph Gint v)
{
深度优先遍历
int w
Visited[v]TRUE
printf(vd Gvertices[v]data)
for(wFirstAdjVex(Gv)w>0wNextAdjVex(Gvw))
if(Visited[w])
DFS(Gw)
}

void DFSTraverse(Graph G)
{
int v
for(v0v Visited[v]FALSE
for(v0v if(Visited[v])
DFS(Gv) 递
}


void BFSTraverse(Graph G)
{
广度优先遍历
int vv1w
Queue q 定义队列
for(v0v Visited[v]FALSE
InitQueue(&q) 初始化队列
for(v0v if(Visited[v])
{
Visited[v]TRUE
printf(vd Gvertices[v]data)
EnQueue(&qv) 第顶点入队
while(QueueEmpty(q))
{
DeQueue(&q&v1) 第顶点出
for(wFirstAdjVex(Gv1)w>0wNextAdjVex(Gv1w))
if(Visited[w])
{
Visited[w]TRUE
printf(vd Gvertices[w]data)
EnQueue(&qw)
}
}
}
}

void main()
{
Graph G
CreateGraph(&G)
printf(Depth First Search＼n)
DFSTraverse(G)
printf(＼nBreadth First Search＼n)
BFSTraverse(G)
printf(＼n)
}

2 运行界面截图：


五 总结（出现问题解决方案知识点总结）（少100字）
1 弄明白邻接链表结构邻接链表存储图原理
2 创建邻接链表程中边创建需两次
3 深度遍历时需静态数组存储节点访问状态访问置1否置0
4 深度遍历时学会递方法
5 文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档