数据结构实验报告Word文档下载推荐.docx

数据结构实验报告Word文档下载推荐.docx

《数据结构实验报告Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告Word文档下载推荐.docx（45页珍藏版）》请在冰点文库上搜索。

#include<

stdio.h>

malloc.h>

#defineLIST_INIT_SIZE100

#defineLISTINCREMENT10

#defineTURE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintElemType;

typedefintStatus;

typedefstruct

{

ElemType*elem;

intlength;

intlistsize;

}SqList;

StatusInitList_Sq（SqList*L）

L->

elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;

if（!

L->

elem）returnOVERFLOW;

length=0;

listsize=LIST_INIT_SIZE;

returnOK;

}

StatusCreatList_Sq（SqList*L,intn）

inti;

length=n;

for（i=0;

i<

n;

i++）

{

printf（"

请输入第%d个整数:

"

i+1）;

scanf（"

%d"

&

elem[i]）;

}

voidTraverList_Sq（SqList*L）

printf（"

顺序表的长度为：

%d\n"

L->

length）;

顺序表中的元素依次为：

"

）;

length;

%5d"

\n"

intListInsert_Sq（SqList*L,inti,inte）

int*newbase,*q,*p;

if（i<

1||i>

length+1）

由于插入位置不合法导致插入操作失败\n"

returnERROR;

else

if（L->

length>

=L->

listsize）

{

newbase=（int*）realloc（L->

elem,（L->

listsize+LISTINCREMENT）*sizeof（int））;

if（!

newbase）returnOVERFLOW;

L->

elem=newbase;

length=+LISTINCREMENT;

}

q=&

（L->

elem[i-1]）;

for（p=&

elem[L->

length];

p>

=q;

p--）

*（p+1）=*p;

*q=e;

++L->

returnOK;

intDeleteList_Sq（SqList*L,inti,inte）

intx,*q,*p;

length）

由于删除位置不合法无法进行删除\n"

elseif（L->

length==0）

由于是空表无法删除\n"

returnOVERFLOW;

else

e=L->

elem[i-1];

第%d个元素%d已删除\n"

i,e）;

length-1]）;

q<

p;

++q）*q=*（q+1）;

--L->

intmain（）

SqLista,*l=&

a;

intselect,n,i,x,m,b;

do{

\n第一次使用初始化\n"

1初始化\n"

2顺序表的创建\n"

3顺序表的插入\n"

4顺序表的删除\n"

5顺序表的遍历\n"

0退出\n\n"

请选择操作1-5:

select）;

switch（select）{

case1:

{

if（!

InitList_Sq（l））printf（"

顺序表初始化失败\n"

InitList_Sq（l）;

printf（"

顺序表已经初始化\n"

break;

}

case2:

请输入要创建的顺序表的长度：

scanf（"

n）;

CreatList_Sq（l,n）;

TraverList_Sq（l）;

case3:

请输入要插入的位置：

i）;

请输入要插入的元素：

x）;

ListInsert_Sq（l,i,x）;

case4:

请输入要删除的位置：

m）;

DeleteList_Sq（l,m,b）;

case5:

}while（select<

=5&

&

select>

=1）;

return0;

stdlib.h>

typedefstructnode{

intdata;

structnode*next;

}node,*list;

voidinit（list&

head）

head=（list）malloc（sizeof（node））;

head->

next=NULL;

voidinput（list&

h）

listp,q;

q=h;

输入数据的个数：

intn;

scanf（"

请输入%d个有序递增的数据"

n）;

for（inti=0;

i<

i++）

p=（list）malloc（sizeof（node））;

p->

data）;

p->

next=q->

next;

q->

next=p;

q=p;

voidoutput（listh）

listp;

p=h->

输出数据\n"

while（p!

=NULL）

%d"

p->

p=p->

voidcombine（list&

a,list&

b,list&

c）

listp,q,t;

p=a->

q=b->

free（b）;

b=q;

c=a;

a=p;

c->

while（p&

q）

if（p->

data<

=q->

data）

a=a->

p->

next=c->

c->

p=a;

else

b=q->

q->

next=q;

q=b;

if（p!

while（p）

if（q!

while（q）

lista,b,c;

init（a）;

init（b）;

输入链表A:

input（a）;

输入链表B:

\b"

input（b）;

combine（a,b,c）;

output（c）;

#include<

voidfun（intx,intk）;

你要测试几组数据?

&

请输入%d组数据（输入格式:

ab）:

inti,k,x;

for（i=0;

i<

n;

++i）

%d%d"

x,&

k）;

十进制数%d的%d进制表示是:

x,k）;

fun（x,k）;

printf（"

voidfun（intx,intk）

inta,b,c=0,zu[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

b=x;

a=b%k;

zu[c]=a;

c++;

b=b/k;

}while（b>

0）;

for（--c;

c>

=0;

--c）

if（zu[c]!

=-1&

zu[c]>

9）

printf（"

%c"

zu[c]+（'

A'

-10））;

zu[c]）;

4.程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。

或对其他程序环境的使用情况的记录。

注：

必须认真书写）

5.讨论（通过实验的一些体会、学会的知识和技能等）

1、线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素

2、线性链表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素

信息学院班级：

二叉树的基本应用实验日期

实验指导教师刘勇实验机房D410

2.实验目的：

（1）理解树这种数据结构。

（2）掌握二叉树二叉链表这种存储结构。

（3）完成二叉树各种基本运算的算法。

（1）实现二叉树创建的算法。

（2）实现二叉树各种遍历算法。

（3）实现二叉树其他操作的算法，包括：

统计叶子结点的个数、求二叉树的深度、线索二叉树等。

3．算法设计（编程思路或流程图）

1、二叉树创建的算法

2、叶子结点统计的算法

3、二叉树深度统计算法

1#include<

#defineMAX20

#defineOVERFLOW0

typedefcharTElemType;

typedefstructBiTNode

TElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

BiTreeCreateBiTree（BiTreeT）

charch;

ch）;

if（ch=='

#'

）T=NULL;

else{

T=（BiTNode*）malloc（sizeof（BiTNode））;

if（!

T）exit（OVERFLOW）;

T->

data=ch;

lchild=CreateBiTree（T->

lchild）;

rchild=CreateBiTree（T->

rchild）;

returnT;

voidLevelOrder（BiTreeT）

BiTreeQueue[MAX],b;

intfront,rear;

front=rear=0;

if（T）{

Queue[rear++]=T;

while（front!

=rear）{

b=Queue[front++];

%2c"

b->

if（b->

lchild!

=NULL）Queue[rear++]=b->

lchild;

rchild!

rchild;

主函数

#include"

BiTNode.h"

BiTreeT=NULL;

*******采用递归函数构造一棵二叉树*******\n"

请读入构造二叉树的字符序列:

if（T=CreateBiTree（T））{

二叉树建立成功!

并以层序遍历输出构造的二叉树\n"

LevelOrder（T）;

elseprintf（"

很遗憾，不能成功建立二叉树！

！

intleafcount（BiTreebt）

if（bt==NULL）return0;

elseif（（bt->

lchild==NULL）&

（bt->

rchild==NULL））n=1;

elsen=leafcount（bt->

lchild）+leafcount（bt->

returnn;

intm;

*******构造一颗二叉树并统计叶子结点的数*******\n"

请输入二叉树的序列:

T=CreateBiTree（T）;

if（T）

二叉树建立成功！

以层序遍历输出构造的二叉树\n"

m=leafcount（T）;

\n该二叉树的叶子结点数目是:

%d\n"

m）;

二叉树建立不成功！

3#include<

intdepth（BiTreebt）;

*******构造一颗二叉树并统计深度*******\n"

intm=depth（T）;

\n该二叉树的深度是:

}

intdepth（BiTreebt）

{intdm=depth（bt->

intdn=depth（bt->

returndm>

dn?

dm+1:

dn+1;

4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。

5．讨论（通过实验的一些体会、学会的知识和技能等）

1、树形结构是一类重要的非线性数据结构。

二叉树的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分次序不能任意颠倒

2、二叉树的性质：

（1）在二叉树的第i层上至多有2^i-1个结点（i>

=1）

（2）深度为K的二叉树至多有2^k-1个结点（k>

（3）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2则n0=n2+1

（4）具有n个结点的完全二叉树的深度为log2n+1

图的基本实现与应用实验日期

3.实验目的：

（1）理解图这种数据结构。

（2）掌握邻接矩阵、邻接表这种存储结构的实现方法。

（3）完成图的遍历的算法。

（1）实现图的邻接矩阵与邻接表结构的转换。

（必做）

（2）实现图遍历的算法。

（3）实现图的拓扑排序的算法。

（4）实现图的最短路径的算法

3．算法设计（编程思路或流程图）

1、图的邻接矩阵和邻接表创建的算法

2、图的两种遍历算法

#defineVERTEXTYPEint

#defineADJTYPEint

#defineMAXLEN40

typedefstruct{

VERTEXTYPEvexs[MAXLEN];

ADJTYPEarcs[MAXLEN][MAXLEN];

intvexnum,arcnum;

intkind;

}MGRAGH;

typedefstructnode3{

intadjvex;

structnode3*next;

}EDGENODE;

VERTEXTYPEvertex;

EDGENODE*link;

intid;

}VERTEXNODE;

VERTEXNODEadjlist[MAXLEN];

}ADJGRAGH;

MGRAGHcreate_MGRAGH（）

inti,j,k;

MGRAGHmg;

mg.kind=2;

\n\ninputvertexnumandarcnum（,）:

%d,%d"

i,&

j）;

fflush（stdin）;

mg.vexnum=i;

mg.arcnum=j;

\n\n"

for（i=0;

mg.vexnum;

inputthevalueofvertex%d:

mg.vexs[i]）;

fflush（stdin）;