数据结构上机实验答案
数据结构上机实验报告
数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名：
学号： 教师：饶鲜日期：
目录 实验一线性表................................................. - 4 - 一、实验目的................................................ - 4 - 二、实验代码................................................ - 4 - 三、实验结果............................................... - 14 - 四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 - 一、实验目的............................................... - 15 - 二、实验代码............................................... - 16 - 三、实验结果............................................... - 24 - 四、个人思路............................................... - 25 -实验三数组.................................................. - 26 - 一、实验目的............................................... - 26 - 二、实验代码............................................... - 26 - 三、实验结果............................................... - 28 - 四、个人思路............................................... - 28 -实验四树.................................................... - 29 - 一、实验目的............................................... - 29 - 二、实验代码............................................... - 29 -
数据结构上机实验答案
《数据结构实验指导书》答案 实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单 元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include
数fun、输出结果。 #define N 10 #include 《数据结构》上机题（C语言程序） 北京科技大学数据结构上机实验 ivince 上机题1．输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。 例如输入：2 6 4 7 3 0（0为结束符），建立： 所求结果=4 程序结构：类型说明； 建表函数：Creatlist(L); 求值函数：Adjmax(L); main( ) { 变量说明； 调用Creatlist(L)建表；调用Adjmax(L)求值； 打印数据；释放链表空间； Y 继续？ N 停止} //ivince //启动程序后输入字符（每输入一个字符，都要回车结束），如果字符不是"@"和"0"，字符就会进队。输入"0",则队头元素出队；输入"@",所有元素出队。 //特殊情况：直接输入"0"，或直接输入"@"都已经做了相应处理 #include { if(q->front==q->rear) return(1); else return (0); } void Enqueue(linkqueue *q,char e) //元素e进队 { Qlink p=(Qlink)malloc(sizeof(Qnode)); //申请进队节点 p->ch=e; p->next=NULL; q->rear->next=p; q->rear=p; } intDequeue(linkqueue *q) //出队 { Qlink p; if (Emptyqueue(q)) return(NULL); //队空处理 else { p=q->front ; q->front=p->next ; free(p); return(q->front->ch); } } void main(void) //主函数 { linkqueue q; charch='0',ch2; Creatqueue(&q); printf("请输入字符，字符0出队字符@全部出队：\n"); while(ch!='@') { scanf("%c",&ch); fflush(stdin); //清除缓存字符 if(ch=='0') { ch2=Dequeue(&q); if(ch2!=NULL) printf("%c\n",ch2); else printf("目前队列中不存在任何元素!,请您先存入!!\n"); 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出 现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 上机实验要求及规范 《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下： 1.问题分析与系统结构设计 充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。 编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。 4.上机调试程序 调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。 数据结构实验报告 一．顺序表 要求：实现顺序表的初始化、在指定位置插入和删除元素。 算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表，而且删除点后面的元素要往前移动一个位。 程序代码： #include for(i=0;i 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 《数据结构与算法》课程实验内容与要求 一、课程简介 本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法③典型内部排序算法。 二、实验的作用、地位和目的 数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水准的应用程序的能力。 三、实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。 ②实验时，每位学生使用一台微机，独立调试，完成程序。 ③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据，运行结果及源程序。 ⑤在一周内完成实验报告。 四、考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照首页附件中实验报告模版书写。实验报告中应包括如下内容： ?实验内容按任课教师下达的实验任务填写（具体实验题目和要求）； ?实验过程与实验结果应包括如下主要内容： 算法设计思路简介 算法描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 ?源程序清单与实验结果或其它说明可打印，并装订在实验报告首页之后。 ?实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分 五、实验的软硬件环境 硬件环境：PⅡ以上微型计算机 软件环境：Windows98/2000, VC++6.0或turbo C 六、实验内容安排 实验一线性表应用 实验时间：2016年3月14日1-4节（地点：7-215） 实验目的：理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。 具体实验题目与要求：（任课教师根据实验大纲自己指定） 每位同学可从下面题目中选择1-2题实现： 1．一元稀疏多项式简单的计算器 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2）要求: （1）采用单链表存储结构一元稀疏多项式 （2）输入并建立多项式 （3）输出多项式 （4）实现多项式加、减运算 2．单链表基本操作练习 1）问题描述：在主程序中提供下列菜单： 1…建立链表 2…连接链表 3…输出链表 0…结束 2）实验要求：算法中包含下列过程，分别完成相应的功能： CreateLinklist(): 从键盘输入数据，创建单链表 ContLinklist()：将前面建立的两个单链表首尾相连 OutputLinklist()：输出显示单链表 3．约瑟夫环问题 1）问题描述：有编号为1, 2…n 的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。 2）要求: 采用顺序和链式两种存储结构实现 实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四） 《数据结构》课程上机实验指导书 实验一 【实验名称】顺序表的基本算法 【实验目的】 创建一个顺序表，掌握线性表顺序存储的特点。设计和验证顺序表的查找、插入、删除算法。 【实验要求】 （1）从键盘读入一组整数，按输入顺序形成顺序表。并将创建好的顺序表元素依次打印在屏幕上。 设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素（2）的功能。 当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；3（）当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。 （4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 上机编写程序。2、编译。3、调试。4、 综合实例！，2-62-8！带菜单的主函数参考书上2.5，，，书上参考算法例程：2-12-42-5注意：顺序表的结构体！typedef struct { datatype items[listsize]; int length; }SpList; 实验二 【实验名称】单链表的基本算法 【实验目的】 创建一个单链表，掌握线性表链式存储的特点。设计和验证链表的查找、插入、删除、求表长的算法。【实验要求】 （1）从键盘读入一组整数，按输入顺序形成单链表。并将创建好的单链表元素依次打印在屏幕上。（注意：选择头插法或者尾插法！） 设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找（2）数据元素，和求单链表表长等几项功能。 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插）（3入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。 （4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 、上机编写程序。2 编译。3、调试。4、 综合实例！！带菜单的主函数参考书上，2-132-15，2-172.5，，书上参考算法例程：2-102-12 另外，注意，指针的初始化！指针的操作必须谨慎！链表的结构体如下：typedef struct Node { Datatype ch; struct Node *next; }LNode, *Pnode, *Linklist; 实验三 【实验题】 1．狐狸逮兔子 围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到１号洞找，第二次隔１个洞（即3号洞）找，第三次隔２个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？ （提示：这实际上是一个反复查找线性表的过程。） 【数据描述】 定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的一个洞，下标为洞的编号。 #define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位） }SqList; 【算法描述】 status InitList_Sq(SqList &L) { //构造一个线性表L L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType)); If(!L.elem) return OVERFLOW; //存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; } //InitList_Sq status Rabbit(SqList &L) { //构造狐狸逮兔子函数 int current=0; //定义一个当前洞口号的记数器，初始位置为第一个洞口 for(i=0;i 2013-03-08 上机实验题 1.构建两个顺序表示的非空线性表LA和LB (数据元素为整型，其值自行确定)； 2.从线性表LA中删除第i 个元素； 3.将元素e插入到线性表LB中的第i个元素之后； 4.假设LA中不含重复的元素 (LB同)，将线性表LA和LB合并，并输出结果，要求结 果中不含重复的元素。 //构建两个顺序表（定义、初始化） //在一个顺序表中删除指定位置的元素 //在一个顺序表中指定位置插入一个新元素 //将两个线性表LA和LB进行合并 //遍历LB, 如果其中的数据元素不在LA中，则将其插入LA，否则不予处理 //打印线性表LA #define List_Init_Size 100 #define LISTINCREMENT 10 typedef int Status; typedef struct { int * elem; int length; // 当前长度 int ListSize; // 当前分配的存储容量 }SqList; Status Initialize_table (SqList &L) {// 初始化线性表 int i, m, data; L.elem=(int *)malloc(List_Init_Size *sizeof(int)); if (!L.elem) { // 为线性表分配空间 printf("Overflow"); return FAILURE; } L.ListSize=List_Init_Size; L.length=0; printf ("Please input the size of linear table (<=%d): "+ List_Init_Size); scanf_s("%d",&m); for (i=0;i 实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统 —— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法，分析各种排序算法的时间复杂度；改进教材中的快速排序算法，使得当子集合小于10个元素师改用直接插入排序；使用随即数发生器产生大数据集合，运行上述各排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，两路合并排序Merge()，快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示： 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列，并进行性能的比较，除此之外还对快速排序进行了改进。下图为主函 数main的流程图： —— main() 2.核心算法 1)简单选择排序： 简单选择排序的基本思想是：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到 数据结构上机题目 第二次:sqlist-顺序表 2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。 第三次:LinkList-单链表 2.15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后)，假设指针hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 2.19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 第四次:cdLinkList-循环链表 2.33已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为 三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 2.38设有一个双向循环链表，每个结点中除有prior，data和next 三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的算法。 第五次:outqueue-实验1线性表 实验目的 熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现，其中重点熟悉链表的各种操作。 时间要求：4学时 问题描述： 约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码〈正整数〉，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求: 利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。数据结构上机实验
数据结构课程实验指导书
数据结构实验报告全集
数据结构课程设计题目及要求
计10--数据结构专题实验rev2
数据结构上机实验报告
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
经典数据结构上机题_答案解析
《数据结构与算法》上机实验要求
数据结构上机实验指导
数据结构实验题参考答案
数据结构 上机实验题及题解
南邮数据结构上机实验四内排序算法的实现以及性能比较
数据结构上机题目