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

第2章实验(2学时)(满分80)以下两个验证性实验都做(1)顺序表顺序表的C语言描述基本运算的算法——置空表、求表的长度、取结点、定位运算、插入运算、删除运算、建立顺序表、输出顺序表(2)链表单链表的C语言描述基本运算的算法——置空表、求表的长度、取结点、定位运算、插入运算、删除运算、建立不带头结点的单链表(头插入法建表)、建立带头结点的单链表(尾插入法建表),(满分90)集合的交、并和差运算的实现(1)问题描述用有序单链表表示集合,实现集合的交、并和差运算。(2)基本要求对集合中的元素,用有序单链表进行存储。实现交、并、差运算时,不另外申请存储空间。充分利用单链表的有序性,算法有较好的时间性能。(3)设计思想首先,建立两个带头结点的有序单链表表示集合A和B。须注意的是:利用头插入法建立有序单链表,实参数组应该是降序排列。其次,根据集合的运算规则,利用单链表的有序性,设计交、并和差运算。根据集合的运算规则,集合A∩B中包含所有既属于集合A又属于集合B的元素。因此,须查找单链表A和B中的相同元素并保留在单链表A中。根据集合的运算规则,集合A∪B中包含所有或属于集合A或属于集合B的元素。因此,对单链表B中的每个元素x,在单链表A中进行查找,若不存在和x相同的元素,则将该结点插入到单链表A中。根据集合的运算规则,集合A-B中包含所有属于集合A而不属于集合B的元素。因此,对单链表B中的每个元素x,在单链表A中进行查找,若存在和x相同的元素,则将该结点从单链表A中删除。(4)思考:如果表示结合的单链表是无序的,应如何实现集合的交、并和差运算?(满分100)约瑟夫环问题(1)问题描述设有编号为1,2,…,n的n(n>0)个人围成一个圈,每个人持有一个密码m。从第一个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报