实验一 线性表的基本操作实现.doc

实验 一 线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现。2、会用线性链表解决简单的实际问题。二、实验内容题目一 链表基本操作该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示：please input the operation： 1.初始化 2.清空 3.求链表长度 4.检查链表是否为空 5.检查链表是否为满 6.遍历链表（设为输出元素）7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置 9.向链表中插入元素 10. 从链表中删除元素 其他键退出。 题目二 约瑟夫环问题设编号为1，2，3，n的n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。struct node /结点结构 int number; /* 人的序号 */ int cipher; /* 密码 */ struct node *next; /* 指向下一个节点的指针 */;题目三 Dr.Kong的机器人Dr.Kong设计了一个可以前进或后退机器人，该机器人在每个位置i会得到一个移动步数的指令Ki (i=1,2N),聪明的机器人自己会判断是要前进Ki步还是后退Ki步。例如：给定指令序列(3 3 1 2 5)，表示机器人在第1个位置时，可以前进3步到第4个位置，此时后退是不起作用的，出界；机器人在第2个位置时，可以前进3步到第5个位置，此时后退是不起作用的，出界；机器人在第3个位置时，可以前进1步到第4个位置，也可以后退1步到第2个位置等等。你认为，对给定的两个位置A,B, 聪明的机器人从A位置走到B位置至少要判断几次？【标准输入】第一行: M 表示以下有M组测试数据（0M=8）接下来每组有两行数据头一行：N A B ( 1 N 50, 1A,B N )下一行: K1 K2.Kn ( 0=Ki=N )【标准输出】输出有M行，第i行为第i组测试数据的最少判断次数, 若无法到达，则输出-1。【 样 例 】标准输入标准输出25 1 53 3 1 2 58 5 31 2 1 5 3 1 1 13-1题目四 艺术品Dr.Kong设计了一件艺术品，该艺术品由N个构件堆叠而成，N个构件从高到低按层编号依次为1，2，,N。艺术品展出后，引起了强烈的反映。Dr.Kong观察到，人们尤其对作品的高端部分评价甚多。狂热的Dr.Kong一激动，对组成该艺术品的N个构件重新组合，比如：把第6层到第12层的构件搬下来，想一想，然后整体放到剩下构件的第7层下面；过一会儿，又把第2层到第9层的构件搬下来，整体放到剩下构件的第1层下面等等。于是，Dr.Kong在进行了连续若干次“搬来搬去”后，还是这N个构件，又诞生了一件新的艺术品。编程：请输出新的艺术品最高十层构件的编号。【标准输入】 第一行: N K 表示构件的总数和“搬来搬去”的总次数第2K+1行：A B C 表示要搬动的构件（即从第A层到第B层）整个放在第C层下面；如果C等于0，则要搬动的构件将放到最高层。【标准输出】由十行组成，分别为组成新艺术品的第一层到第十层构件的编号。【约束条件】（1） 10N20000 1k1000（2） 1ABN， 0CN-(B-A+1)【 样 例 】标准输入标准输出13 36 12 12 9 010 13 86789101112234三、实验步骤、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode DataType data; struct LNode *next;LNode,*LinkedList;2、初始化单链表 LinkedList LinkedListInit() / 每个模块或函数应加注释，说明函数功能、入口及出口参数 3、清空单链表 void LinkedListClear(LinkedList &L)/ 每个模块或函数应加注释，说明函数功能、入口及出口参数4、 检查单链表是否为空 int LinkedListEmpty(LinkedList L) 5、 遍历单链表void LinkedListTraverse(LinkedList L) 6、 求单链表的长度int LinkedListLength(LinkedList L) 7、 从单链表表中查找元素 LinkedList LinkedListGet(LinkedList L,int i) /L是带头结点的链表的头指针， 返回第 i 个元素 8、从单链表表中查找与给定元素值相同的元素在链表中的位置 LinkedList LinkedListLocate(LinkedList L, DataType x) 9、 向单链表中插入元素 void LinkedListInsert(LinkedList &L,int i,DataType x) / L 为带头结点的单链表的头指针，本算法 / 在链表中第i 个结点之前插入新的元素 x 10、 从单链表中删除元素 void LinkedListDel(LinkedList &L,DataType x) 删除以 L 为头指针的单链表中第 i 个结点 11、 用尾插法建立单链表 LinkedLis