《数据结构试验》讲义

本文格式为Word版，下载可任意编辑——《数据结构试验》讲义试验1线性表的基本操作

试验编号JX020231-01

所属院系计算机科学与技术所属年级2023-03

所属课程数据结构试验

试验目的

1．把握线性表的特点及其存储结构2．把握线性表的基本操作

试验要求

1．线性表可以用顺序表也可以用单链表实现，勉励大家用两种方式实现；2．创立线性表时，数据从键盘输入整形数据；

3．线性表类型定义和或各种操作的实现，可以用教材给出的方法，也可以自己设计。

试验环境

硬件平台：计算机CPU主频2.0G以上；内存128兆以上；软件平台：Windows2023或以上版本，VisualC++6.0。

试验内容

1．用结构体描述一个线性表；

2．创立线性表，在线性表中实现插入、删除、按位置查找、按元素值查找和求表长等操作；3．设计选择式菜单，以选择菜单方式进行操作。

试验步骤

试验指导定义顺序表

#defineLIST_INIT_SIZE100/*线性表存储空间的初始分派量*/#defineLISTINCREMENT2/*线性表存储空间的分派增量*/structSqList{

ElemType*elem;/*存储空间基址*/intlength;/*当前长度*/

intlistsize;/*当前分派的存储容量(以sizeof(ElemType)为单位)*/};

定义算法函数

StatusInitList(SqListif(!L.elem)

exit(OVERFLOW);/*存储分派失败*/

L.length=0;/*空表长度为0*/

L.listsize=LIST_INIT_SIZE;/*初始存储容量*/returnOK;}

StatusListInsert(SqList

if(iL.length+1)/*i值不合法*/returnERROR;

if(L.length>=L.listsize){/*当前存储空间已满,增加分派*/if(!(newbase=(ElemType*)realloc(

L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))))

exit(OVERFLOW);/*存储分派失败*/L.elem=newbase;/*新基址*/

L.listsize+=LISTINCREMENT;//增加存储容量}

q=L.elem+i-1;/*q为插入位置*/

for(p=L.elem+L.length-1;p>=q;--p)/*插入位置及之后的元素右移*/*(p+1)=*p;*q=e;//插入e

++L.length;/*表长增1*/returnOK;}

主函数样例

voidmain(){

SqListL;Statusi;intj;i=InitList(

printf(\初始化L后：L.elem=%uL.length=%dL.listsize=%d\\n\for(j=1;j3．从森林中删除选取的两棵树，并将新树参与森林；4．重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。由已形成的哈夫曼树求哈夫曼编码：对每个叶结点都进行如下的处理：

扫描由叶结点到根结点的各条分支，若分支中的当前结点与双亲结点是左支关系，则生成编码0，若分支中的当前结点与双亲结点是右支关系，则生成编码1，由此生成的二进制码的序列即为该结点的哈夫曼编码。

思考题

1．用非递归算法实现二叉树的前序、中序和后序遍历；2．设计一个哈夫曼编码器的译码系统。

试验4图的遍历的实现

试验编号JX020231-04所属院系计算机科学与技术所属年级2023-03所属课程数据结构试验

试验目的

1．把握图的邻接矩阵、邻接表的表示方法。2．把握建立图的邻接矩阵的算法。3．把握建立图的邻接表的算法。

4．加深对图的理解，逐步培养解决实际问题的编程能力。

试验要求

试验环境

硬件平台：计算机CPU主频2.0G以上；内存128兆以上；软件平台：Windows2023或以上版本，VisualC++6.0

试验内容

1．建立图的邻接矩阵、邻接表。

2．对建立好的邻接矩阵表示的图进行深度优先探寻遍历。

试验步骤

试验指导

1．图的结构定义

#defineVMAX30/*图中最多顶点数*/

typedefstructnode/*邻接表中链表的结点类型*/{

intvno;/*邻接顶点的顶点序号*/structnode*next;/*后继邻接顶点*/}EdgeNode;

typedefEdgeNode*lgraph[VMAX];/*邻接表类型*/

typedefintmgraph[VMAX][VMAX];/*邻接矩阵类型*/

intvisited[VMAX];/*访问标志*/

intqueue[VMAX];/*广度优先探寻遍历存储队列*/

2．函数定义

intcreate_graph(lgraphlg,mgraphmg)

/*输入无向图的边，建立图的邻接表，邻接矩阵*/

voidldfs(lgraphg,inti)/*邻接表表示的图的深度优先探寻遍历*/voidlbfs(lgraphg,ints,intn)/*广度优先探寻遍历*/

3