《数据结构》实验指导书
贵州大学
电子信息学院
通信工程
目录
实验一顺序表的操作 (3)
实验二链表操作 (8)
实验三集合、稀疏矩阵和广义表 (19)
实验四栈和队列 (42)
实验五二叉树操作、图形或网状结构 (55)
实验六查找、排序 (88)
贵州大学实验报告 (109)
实验一顺序表的操作
实验学时：2学时
实验类型：验证
实验要求：必修
一、实验目的和要求
1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。
2、以线性表的各种操作（建立、插入、删除等）的实现为重点。
3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。
二、实验内容及步骤要求
1、定义顺序表类型，输入一组整型数据，建立顺序表。
typedef int ElemType; //定义顺序表
struct List{
ElemType *list;
int Size;
int MaxSize;
};
2、实现该线性表的删除。
3、实现该线性表的插入。
4、实现线性表中数据的显示。
5、实现线性表数据的定位和查找。
6、编写一个主函数，调试上述算法。
7、完成实验报告。
三、实验原理、方法和手段
1、根据实验内容编程，上机调试、得出正确的运行程序。
2、编译运行程序，观察运行情况和输出结果。
四、实验条件
运行Visual c++的微机一台
五、实验结果与分析
对程序进行调试，并将运行结果进行截图、对所得到的的结果分析。
六、实验总结
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等，并将其写入实验报告中。
【附录----源程序】
#include
#include
using namespace std;
typedef int ElemType;
struct List
{
ElemType *list;
int Size;
int MaxSize;
};
//初始化线性表
bool InitList(List &L)
{
L.MaxSize=20;
L.list=new ElemType[L.MaxSize];
for(int i=0;i<20&&L.list==NULL;i++)
{
L.list=new ElemType[L.MaxSize];
}
if(L.list==NULL)
{
cout<<"无法分配内存空间，退出程序"<return false;
}
L.Size=0;
return true;
}
//向线性表中插入元素
bool InsertList(List &L,int pos,ElemType item)
{
if(pos>L.Size+1||pos<1)
{
cout<<"位置无效"<return false;
}
else if(L.Size==L.MaxSize)
{
int k=sizeof(ElemType);
L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);
if(L.list==NULL)
{
cout<<"动态分配内存失败，退出运行"<return false;
}
L.MaxSize=2*L.MaxSize;
}
for(int i=L.Size-1;i>=pos-1;i--)
{
L.list[i+1]=L.list[i];
}
L.list[pos-1]=item;
L.Size++;
return true;
}
//删除线性表中的元素
bool DeleteList(List &L,ElemType &item,int pos)
{
if(L.Size==0)
{
cout<<"线性表中没有元素，无法删除"<return false;
}
if(pos<1||pos>L.Size)
{
cout<<"位置无效"<return false;
}
item=L.list[pos-1];
for(int i=pos;iL.list[i-1]=L.list[i];
L.Size--;
if(float(L.Size)/L.MaxSize<0.4&&L.Size>10)
{
int k=sizeof(ElemType);
L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2);
L.MaxSize=L.MaxSize/2;
}
return true;
}
