数据结构实验指导书样本[参照]

《数据结构实验指导书样本[参照]》由会员分享，可在线阅读，更多相关《数据结构实验指导书样本[参照]（178页珍藏版）》请在金锄头文库上搜索。

1、资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 数据结构 实验指导书 贵州大学 电子信息学院 通信工程 资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 目 录 实验一顺序表的操作 . 3 实验二链表操作 . 10 实验三集合、 稀疏矩阵和广义表. 28 实验四栈和队列 . 65 实验五二叉树操作、图形或网状结构. 87 实验六查找、 排序 . 140 贵州大学实验报告. 176 资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 实验一顺序表的操作 实验学时 : 2 学时 实验类型 : 验证 实验要求 : 必修 一、 实验目的和要求 1、 熟练掌握线

2、性表的基本操作在顺序存储和链式存储上的实现。 2、 以线性表的各种操作 ( 建立、 插入、 删除等 ) 的实现为重点。 3、 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。 二、 实验内容及步骤要求 1、 定义顺序表类型 , 输入一组整型数据 , 建立顺序表。 typedef int ElemType; /定义顺序表 struct List ElemType *list; int Size; int MaxSize; ; 2、 实现该线性表的删除。 3、 实现该线性表的插入。 4、 实现线性表中数据的显示。 5、 实现线性表数据的定位和查找。 6、 编写一个主函数 , 调试上述算法。

3、 7、 完成实验报告。 三、 实验原理、方法和手段 1、 根据实验内容编程 , 上机调试、得出正确的运行程序。 资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 2、 编译运行程序 , 观察运行情况和输出结果。 四、 实验条件 运行 Visual c+ 的微机一台 五、 实验结果与分析 对程序进行调试 , 并将运行结果进行截图、对所得到的的结果分析。 六、 实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见 和建议等 , 并将其写入实验报告中。 【附录 -源程序】 #include #include using namespace std; typedef

4、int ElemType; struct List ElemType *list; int Size; int MaxSize; ; / 初始化线性表 bool InitList(List L.list=new ElemTypeL.MaxSize; for(int i=0;i20i+) L.list=new ElemTypeL.MaxSize; if(L.list=NULL) cout 无法分配内存空间 , 退出程序 L.Size+1|pos1) cout 位置无效 endl; return false; else if(L.Size=L.MaxSize) int k=sizeof(ElemT

5、ype); 资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k); if(L.list=NULL) cout 动态分配内存失败 , 退出运行 =pos-1;i-) L.listi+1=L.listi; L.listpos-1=item; L.Size+; return true; / 删除线性表中的元素 bool DeleteList(List return false; if(posL.Size) 资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 cout 位置无效 end

6、l; return false; item=L.listpos-1; for(int i=pos;iL.Size;i+) L.listi-1=L.listi; L.Size-; if(float(L.Size)/L.MaxSize10) int k=sizeof(ElemType); L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2); L.MaxSize=L.MaxSize/2; return true; / 输出线性表 bool Print(List return false; cout 线性表为 : endl; 资料内容仅供您学习参考，如有不当

7、或者侵权，请联系改正或者删除。 for(int i=0;iL.Size;i+) coutL.listi ; cout 线性表长度为 L.Sizeendl; return true; / 查找数据 bool GetList(List L,ElemType item,int pos) if(posL.Size) cout 位置无效 endl; return false; int k; cout 按位置查找选择1, 按元素查找选择 0k; if(k=1) cout 第pos个元素为 L.listpos-1endl; return true; else if(k=0) for(int i=0;iL.S

8、ize;i+) 资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 if(L.listi=item) cout 你 要 找 的 元 素 为 :item在 第 i+1 个 endl; if(i=L.Size) cout 没有你要找的元素 endl; return false; else cout 查找无效 , 请选择 0 或 1endl; return false; void main() List m; InitList(m);/初始化线性表 Print(m); cout 请输入十个数据 endl; for(int i=0;im.listi; 资料内容仅供您学习参考，如有不当或者侵

9、权，请联系改正或者删除。 m.Size+; Print(m); cout 向线性表中第 r 个位置插入 sendl; cout 请输入 r, srs; cout(m,r,s)endl;/向线性表中插入元素 InsertList(m,r,s); Print(m); cout 查找数据 s 或者查找第 r 个数据 sr; GetList(m,s,r); Print(m); ElemType f=0; cout 删除第 r 个数据 r; DeleteList(m,f,r); Print(m); cout 删除的数据是 fendl; 实验二链表操作 实验学时 : 2 学时 实验类型 : 验证 资料内容

10、仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 实验要求 : 必修 一、 实验目的和要求 1、掌握链表的概念 , 了解线性表的链式存储结构, 学会定义线性表的链式 存储结构。 2、 加深对链式存储数据结构的理解, 逐步培养解决实际问题的编程能力。 二、实验内容及步骤要求 1、 简单链表的基本操作 (1) 编写链表基本操作函数。 初始化链表InitList(LIST *L,int ms) 向链表指定位置插入元素InsertList1(LIST *L,int item,int rc) 向有序链表指定位置插入元素InsertList2(LIST *L,int item,int rc) 删除指

11、定元素之的链表记录DeleteList(LIST *L,int item) 查找链表中的元素 FindList(LIST *L,int item) (2) 调用上述函数实现下列操作, 操作步骤如下 : 从键盘输入一个数据元素x, 插入到线性表中第i( 包含 1 号位置 ) 个位置 ; 从键盘输入一个数据元素关键字x 或位置 i( 包含 1 号位置 ) , 从 线性表中删除相应数据元素。 2 、 约瑟夫环问题 (1) 约瑟夫 ( Joeph) 问题的一种描述 : 编号为 1,2, ,n 的 n个人按顺时 针方向围坐一圈 , 每人持有一个密码 ( 正整数 ) 。 一开始任选一个正整数作为报 数上限

12、值 m, 从第一个人开始按顺时针方向自1开始顺序报数 , 报到 m时停止报 资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 数。 报 m的人出列 , 将她的密码作为新的m值, 从她在顺时针方向上的下一个人 开始重新从 1 报数, 如此下去 , 直至所有人全部出列为止。 (2) 编程实现约瑟夫环问题, 利用单向循环链表存储结构模拟此过程, 按照出列的顺序印出各人的编号。 (3) 试设计一个程序求出出列顺序。并设m的初值为 20; 密码: 3, 1, 7, 2, 4, 8, 4( 正确的结果应为 6, 1, 4, 7, 2, 3, 5) 。 3 、 完成实验报告。 三、 实验原理、

13、方法和手段 1、根据实验内容编程 , 上机调试、得出正确的运行程序。 2、 编译运行程序 , 观察运行情况和输出结果。 四、 实验条件 运行 Visual c+ 的微机一台 五、 实验结果与分析 对程序进行调试 , 并将运行结果进行截图、对所得到的的结果分析。 六、 实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见 和建议等 , 并将其写入实验报告中。 【附录 -简单链表的基本操作源程序】 /* 线性表实验程序 - 单链表 */ #include #include /* 抽象数据类型定义 */ 资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 typede

14、f int ElemType; typedef struct node ElemType data; struct node *next; *LKList,LNode; void InitList(LKList *L); /*初始化线性表 */ void CreateList(LKList *L); /*创立线性表 */ int GetLength(LKList *L); /*获得线性表的长度 */ int GetElem(LKList *L,int i,ElemType *e); /*取线性表第 i 个表元素 , 并放 在 e 指向的的内存中 */ int SetElem(LKList *L,int i,ElemType *e); /*修改第 i 个表元素 */ int InsertElem(LKList *L,int i, ElemType *e); /*在第 i 个位置插入元素 */ int DeleteElem(LKList *L,int i); /*删除第 i 个元素 */ int SearchElem(LKList *L,ElemType *e); /*查找元素 *e 的位置 i*/ int TraversList(LKList *L); /*遍历线性表 */ void ClearList(LKList *L); /*清除线性表 */ LKList