北理工数据结构实验-线性表.doc

本科实验报告 实验名称： 线性表 课程名称： 数据结构 实验时间： 任课教师： 实验地点： 良乡机房 实验教师： 实验类型： □ 原理验证 ■ 综合设计 □ 自主创新 学生姓名： 学号/班级： 组 号： 学 院： 同组搭档： 专 业： 成 绩： 实验目的 1、熟悉VC环境，学习使用C语言实现链表的存储结构。 2、通过编程、上机调试，进一步理解线性表、链表、环表的基本概念。 3、锻炼动手编程，独立思考的能力。 二、实验题目 1. 采用单向环表实现约瑟夫环。 请按以下要求编程实现： 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。 从键盘输入整数s（1=s=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。 例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。 2. 归并顺序表。 请按以下要求编程实现： 从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。 将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka和linkb为空表。输出linkc。 对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。 例如：linka输入为：10 20 30 40 50 0 linkb输入为：15 20 25 30 35 40 45 50 0 归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50 删除重复后的linkc为：10 15 20 25 30 35 40 45 50 三、实验基础知识 线性表、链表、环表的基本概念的熟练掌握并实际运用。 四、实验设计方法 题目一：约瑟夫环 1、概要设计 应用单向环表寄存数字序列。 (1)、单项环表的抽象数据类型定义为： ADT ListLink { 数据对象： D = { ai | ai ?ElemSet, i=1, …,n，n≥0 } 数据关系： R1 = { ai-1, ai | ai-1,ai ?D, i=2, …,n } 基本操作： Creat( L, m ) 操作结果：构造一个有m个结点的单向环表L。若申请空间失败返回错误信息 FindInitPostion( L, m, s ) 初始条件：单向环表L已经存在。 操作结果：找到单向环表L的第s个结点。 OutNum( L, n ) 初始条件：单向环表L已经存在。 操作结果：进行约瑟夫环的计算并输出相应编号。 } ADT ListLink (2)、主程序流程 主程序首先调用create(L,m)函数创建含有m个结点的单向环表L，随后调用 FindInitPostion(L,m,s)函数找到初始位置第s个结点，最后调用OutNum(L,n)函数计算结果并在屏幕上输出。 (3)、模块调用关系： 由主函数模块调用创建模块，查找模块与计算模块。 由计算模块将结果输出。 (4)、流程图 题目二：归并顺序表 (1)、概要设计 void MergeList(List La,List Lb,List Lc) { //已知线性表La和Lb中的数据元素按值非递减排序 //归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列 InitList(Lc); //实际程序中我写为了input（Lc） i = j = 1;k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while((2)、主程序流程(i= La_len)(j= Lb_len)){ //La和Lb非空 GetElem(La,i,ai)(j= Lb_Len) ; if(ai= bj) {ListInsert(Lc,++k,ai); ++i;} else {ListInsert(Lc,++k,bj);++j} } while(i=La_len){ GetElem(La,i++,ai); ListInsert(Lc,++k,ai); } while(j=