数据结构实验汇总第2章实验.doc

《数据结构实验汇总第2章实验.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第2章实验（2学时）1.验证性实验（满分80）以下两个验证性实验都做（1）顺序表l顺序表的C语言描述l基本运算的算法——置空表、求表的长度、取结点、定位运算、插入运算、删除运算、建立顺序表、输出顺序表（2）链表l单链表的C语言描述l基本运算的算法——置空表、求表的长度、取结点、定位运算、插入运算、删除运算、建立不带头结点的单链表（头插入法建表）、建立带头结点的单链表（尾插入法建表），输出带头结点的单链表2.设计性实验（满分90）集合的交、并和差运算的实现（1）问题描述用有序单链表表示集合，实现集合的交、并和差运算。（2）基本要求l对集合中的元素，用有序单链表进行存储。

2、l实现交、并、差运算时，不另外申请存储空间。l充分利用单链表的有序性，算法有较好的时间性能。（3）设计思想首先，建立两个带头结点的有序单链表表示集合A和B。须注意的是：利用头插入法建立有序单链表，实参数组应该是降序排列。其次，根据集合的运算规则，利用单链表的有序性，设计交、并和差运算。l根据集合的运算规则，集合A∩B中包含所有既属于集合A又属于集合B的元素。因此，须查找单链表A和B中的相同元素并保留在单链表A中。l根据集合的运算规则，集合A∪B中包含所有或属于集合A或属于集合B的元素。因此，对单链表B中的每个元素x，在单链表A中进行查找，若不存在和x相同的元素，则将该

3、结点插入到单链表A中。l根据集合的运算规则，集合A－B中包含所有属于集合A而不属于集合B的元素。因此，对单链表B中的每个元素x，在单链表A中进行查找，若存在和x相同的元素，则将该结点从单链表A中删除。（4）思考：如果表示结合的单链表是无序的，应如何实现集合的交、并和差运算？3.综合性实验（满分100）约瑟夫环问题（1）问题描述设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，

4、设计算法求n个人出圈的次序。（2）基本要求l建立模型，确定存储结构。l对任意n个人，密码为m，实现约瑟夫环问题。l出圈的顺序可以依次输出，也可以用一个数组存储。（3）设计思想首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：structNode{intdata;Node*next;};其次，建立一个不带头结点的循环链表并由头指针first指示。最后，设计约瑟夫环问题的算法。（4）思考：l采用顺序存储结构如何实现约瑟夫环问题？l如果每个人持有的密

5、码不同，应如何实现约瑟夫环问题？