数据结构实验指导书.docx

《数据结构》

实验指导书

贵州大学电子信息学院

通信工程

目录

TOC\o1-1\h\z\u实验一 顺序表的操作 3

实验二 链表操作 8

实验三 集合、稀疏矩阵和广义表 19

实验四 栈和队列 42

实验五 二叉树操作、图形或网状结构 55

实验六 查找、排序 88

贵州大学实验报告 109

实验一 顺序表的操作

实验学时：2学时实验类型：验证实验要求：必修

一、实验目的和要求

1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。

2、以线性表的各种操作（建立、插入、删除等）的实现为重点。

3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。

二、实验内容及步骤要求

1、定义顺序表类型，输入一组整型数据，建立顺序表。typedefintElemType; //定义顺序表

structList{

ElemType*list;intSize;

intMaxSize;

};

2、实现该线性表的删除。

3、实现该线性表的插入。

4、实现线性表中数据的显示。

5、实现线性表数据的定位和查找。

6、编写一个主函数，调试上述算法。

7、完成实验报告。

三、实验原理、方法和手段

1、根据实验内容编程，上机调试、得出正确的运行程序。

2、编译运行程序，观察运行情况和输出结果。

四、实验条件

四、实验条件

运行Visualc++的微机一台

五、实验结果与分析

五、实验结果与分析

对程序进行调试，并将运行结果进行截图、对所得到的的结果分析。

六、实验总结

记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等，并将其写入实验报告中。

【附录 源程序】

【附录 源程序】

#includestdio.h#includeiostreamusingnamespacestd;

typedefintElemType;structList

{

ElemType*list;intSize;

intMaxSize;

};

//初始化线性表boolInitList(ListL)

{

L.MaxSize=20;

L.list=newElemType[L.MaxSize];for(inti=0;i20L.list==NULL;i++)

{

L.list=newElemType[L.MaxSize];

}

if(L.list==NULL)

{

cout无法分配内存空间，退出程序endl;returnfalse;

}

L.Size=0;returntrue;

}

//向线性表中插入元素

boolInsertList(ListL,intpos,ElemTypeitem)

{

if(posL.Size+1||pos1)

{

cout位置无效endl;returnfalse;

}

elseif(L.Size==L.MaxSize)

{

intk=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list==NULL)

{

cout动态分配内存失败，退出运行endl;returnfalse;

}

L.MaxSize=2*L.MaxSize;

}

for(inti=L.Size-1;i=pos-1;i--)

{

L.list[i+1]=L.list[i];

}

L.list[pos-1]=item;L.Size++;

returntrue;

}

//删除线性表中的元素

boolDeleteList(ListL,ElemTypeitem,intpos)

{

if(L.Size==0)

{

cout线性表中没有元素，无法删除endl;returnfalse;

}

if(pos1||posL.Size)

{

cout位置无效endl;returnfalse;

}

item=L.list[pos-1];

for(inti=pos;iL.Size;i++)L.list[i-1]=L.list[i];

L.Size--;if(float(L.Size)/L.MaxSize0.4L.Size10)

{

intk=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2);

L.MaxSize=L.MaxSize/2;

}

returntrue;

}

//输出线性表boolPrint(ListL)

{

if(L.Size==0)

{

cout线性表中无元素endl;returnfalse;

}

cout线性表为：endl;for(i