下载文档原格式
《数据结构》实验指导书实验一、顺序表实验目的：熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。
实验要求：了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。
实验内容：编写程序实现下列的要求：(1) 设数据元素为整数，实现这样的线性表的顺序存储表示。
(2) 键盘输入10个数据元素，利用顺序表的基本操作，建立该表。
(3) 利用顺序表的基本操作，找出表中的最大的和最小的数据元素（用于比较的数据元素为整数）。
(4) * 若数据元素为学生成绩（含姓名、成绩等字段），重新编程，实现上面的要求。
要求尽可能少地修改前面的程序来得到新程序。
（这里用于比较的字段为分数）练习及思考题：（1）顺序表的操作上有什么特点？（2）不固定数据元素的个数，而通过特殊数据来标记输入数据的结束，实现这样的输入操作。
实验二、链表实验目的：熟悉链式表的逻辑特性、存储表示方法的特点和链式表的基本操作。
实验要求：了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。
实验内容：编写程序实现下列的要求：(1) 设学生成绩表中的数据元素为学生成绩（含姓名、成绩字段），实现这样的线性表的链式存储表示。
(2) 键盘输入若干个数据元素（用特殊数据来标记输入数据的结束），利用链表的基本操作（前插或后插算法），建立学生成绩单链表。
(3) 键盘输入关键字值x，打印出表中所有关键字值<=x的结点数据。
（用于比较的关键字字段为分数）。
(4) 输入关键字值x，删除表中所有关键字值<=x的结点。
（用于比较的关键字字段为分数）。
练习及思考题：（1）不同类型的数据元素所对应的链式表在类型定义和操作实现上有什么异同？（2）有头结点的链式表，有什么特点？实验三、栈的应用实验目的：熟悉栈的逻辑特性、存储表示方法和栈的基本操作。
实验要求：了解并熟悉栈的逻辑特性、顺序和链式存储表示方法和栈的基本操作的实现和应用。
实验内容：(1) 判断一个表达式中的括号（仅有一种括号，小、中或大括号）是否配对。
数据结构实验指导书信息科学与工程学院余腊生2014年1月目录前言 (1)实验一一元稀疏多项式的计算 (5)实验二长整数四则运算 (21)实验三停车场管理 (43)实验四算术表达式求值 (62)实验五文学研究助手实验指导书 (74)实验六多维数组 (97)实验七哈夫曼编/译码器实验指导书 (122)实验八最短路径实验指导书 (141)实验九 B-树及图书管理实验指导书 (153)实验十内部排序算法比较实验指导书 (187)前言数据结构是软件开发的基础。
数据结构课程是软件工程、计算机科学与技术、网络工程、信息安全等专业的必修技术基础课程。
该课程是在学生学习高级语言程序设计课程基础上，使学生掌握各种常用数据结构的逻辑表示、存储表示、处理方法及应用算法设计，学会常用数据分类和数据查找的技术，对所设计的算法会做定量或定性的分析比较，培养学生的算法设计与分析的能力。
通过该课程的学习，使学生学会分析数据对象特性，选择合适的数据结构、存贮结构及相应的基本处理算法；初步掌握算法的时间空间复杂度分析技巧。
既为学生学习后继课程打好基础，也为将来软件开发提供理论指导。
数据结构具有很强的实践性，只有通过编程上机实验，才能真正领会数据结构的真正内涵，并灵活运用数据结构的基本知识提高自己的软件开发能力。
本数据结构实验选择了具有一定难度的实验项目10个，涉及到线性表、栈、队列、字符串、数据、二叉树、图、数据查找、数据排序等全部教学内容。
学生不一定完成全部实验内容，根据课程的学分不同，可以选择不同数目的实验。
鼓励学生多做实验，如果学生所做实验数目超过规定数据，可以加分。
本实验是以标准C语言为背景，也可以使用C++语言进行编程实现。
为了使学生不仅掌握数据结构的一般原理，而且掌握具有一定实用性的程序的一般结构，实验指导书中给出了程序的总体框架和部分源程序代码，以及程序运行控制和交互式操作的基本方式。
通过程序总体框架，让学生学会如何组织程序。
《数据结构与算法》课程设计指导书一．目的通过本课程设计，使同学更加系统地理解和掌握数据结构的基本概念；能自如地根据实际要求，设计相应的数据结构，并运用C或C++语言实现所设计的算法，能够利用所学的基本知识和技能，分析和解决简单的程序设计问题，为后续其它专业课程的学习和应用打下良好基础。
二．题目根据指导教师的具体要求，从下面题目中选择1个来完成1．学生成绩管理系统2．简易客房管理系统3．人事档案管理系统4．进销存货物管理系统5．图书管理系统6．运动会分数统计7．民航订票系统8．校园导游咨询9．大数相乘问题10．长整数的加减法11．表达式的求值12．日历系统13．钱币的转换14．二叉树的应用——哈夫曼树15．银行排队系统模拟16．其他题目（需老师同意）注意，在实现相关管理系统题目时，需要设计良好的数据结构，代码编写时不允许运用现有的数据库管理系统，具体功能应通过对文件的读写操作实现。
三．任务完成形式1．完整的软件系统最终必须向指导老师提交完整的程序源代码(.c和.cpp以及.h为后缀的文件)、数据文件以及使用说明文件等。
源代码文件要特别注意编程规范、代码风格，关键代码需有合理的注释，不含任何无用代码；数据文件内要求有一定数量的“真实”数据（如对于记录文件，需要有5条以上记录）；使用说明文件的第一行，需要给出设计者的学号、姓名，后面为其它说明。
2．课程设计报告(详细要求请参考附录二)课程设计报告总体上主要包括以下几个部分：1）封面2）目录3）课程设计报告正文4）使用说明5）参考文献四．总体要求1．每道题目的程序代码总量不少于600行（其中不包括自动生成代码），有合理注释。
2．课程设计报告正文字数不少于8000字，概念清楚、叙述正确、内容完整、书写规范。
3．独立完成课程设计，不得抄袭他人。
4．功能正确、有一定实用性。
5．尽可能大量使用各种C或者C++语言程序设计技术，尤其在以下几个方面：指针及其运算、结构、指针数组、数组指针、字符数组与字符串、内存空间动态申请与释放、文件访问与操作、合理的常量与全局变量及函数接口变量定义、数据输入与数据格式检查、数据类型转换、错误处理、工程设计技术（整个系统由一个工程文件、若干个程序文件、若干头文件、甚至库文件等组成）。
数据结构⼤型实验任务书-2014年（第三稿）[⼤型实验基本要求]1.原则上可以1－３位同学组成实验⼩组，进⾏分⼯合作，但必需保证每位组员都充分参与实验过程，每位组员应对实验程序的结构、算法、主要技术完全掌握，⽅可参加实验验收。
但⼀个⼩组内最终只能⼀个⼈得到优秀成绩。
2.每组可参考下⾯⼤型实验题⽬和要求，选择⼀道实验题⽬，共同设计开发。
3.⼤型实验时间从第8周开始⾄16周，要求在考试之前全部验收结束。
原则上，申请⼤型实验验收后，若实验没有达到规定的要求，不可再次申请验收，故请⼤家务必确认程序正确（程序代码和运⾏结果）后，再申请验收。
[报告规范]实习报告的开头应该给出题⽬、班级、姓名、学号、和完成⽇期，如果是多⼈完成的，必须写明所有同组⼈员的班级、姓名和学号，并标明谁是主要负责⼈，其它为参与者。
实验报告要求有以下五个内容：1．实验内容分析：明确实验题⽬⽬的，设计实验的基本数据结构、类、以及程序的基本流程，程序流程要求以程序流程图明确表⽰，类及类间关系需明确图⽰，并给出各函数之间的调⽤关系。
可以适当粘贴关键代码进⾏说明；2．实验验证分析：（1）输⼊的形式和输⼊值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输⼊及其输出结果和含有错误的输⼊及其输出结果。
３．调试分析（1）讨论分析调试过程中的主要技术问题以及具体的解决⽅法（⾄少３个）；（2）技术难点分析（⾄少３个）；（3）印象最深刻的３个调试错误，及修正⽅法；４．测试结果：（1）展⽰程序的运⾏结果，包括输⼊和输出，分析数据的正确性；（2）应⽤边界数据、或极端数据测试系统，分析结果的正确性。
５．附录：附上源代码，并标明源代码的所属⽂件，并且源代码必须有注释。
[提交内容]1.电⼦压缩包：包括实验报告电⼦稿和所有源代码⽂件(包括.h⽂件和.cpp⽂件)。
2.压缩⽂件名为：“学号+姓名”；如果是多⼈合作的，则压缩⽂件名为：“负责⼈学号+负责⼈姓名+参与者1学号+参与者1姓名+参与者2学号+参与者2姓名”。
《数据结构》课程实验指导《数据结构》实验教学大纲课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统总学时/实验学时：64/16 总学分/实验学分：3.5/0.5一、课程简介数据结构是计算机各专业的重要技术基础课。
在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。
数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。
通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。
另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。
二、实验的地位、作用和目的数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。
另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。
三、实验方式与基本要求实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。
具体实验要求如下：1.问题分析充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。
2.数据结构设计针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。
对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。
*******************实践教学*******************兰州理工大学计算机与通信学院2014年春季学期算法与数据结构课程设计题目：1．排列比较2．递归替换3．跳马问题4．长整数的运算专业班级：姓名：学号：指导教师：成绩：目录摘要 (1)前言 (2)正文 (3)1.采用类C语言定义相关的数据类型 (3)2.各模块的伪码算法 (4)3.函数的调用关系图 (11)4.调试分析 (11)5.测试结果 ................................................................. 1错误！未定义书签。
6.源程序（带注释） (16)总结 (29)参考文献 (30)致谢 (31)附件Ⅰ基本算法实现 (32)摘要这次的课程设计是排序算法比较问题，递归替换问题，跳马问题和长整数运算问题。
其中排列算法中我只用到了三种排序方法，分别为冒泡，插入，选择。
而递归替换我选择了这学期所学的汉诺塔。
跳马问题则是在书籍上看到，加深其理解并实现程序。
长整数则是求助老师，贴吧上的人。
我对自己的课程设计有着较深的理解，前三种基本都是递归算法和回溯算法的体现，然而长整数却是用到了结构体和链表。
其中长整数难度较高，其理解较难，花了我相当长的时间。
关键字:数组，结构体,结构体指针,双向循环链表,前向指针,后向指针,头指针,数字字符,十进制数,动态分配存储空间前言课程设计是我们学习过程中一个非常重要的环节,它重在测试大家实践能力,知识应用能力和解决问题的能力.同时它又需要以扎实的理论知识为基础.在做课程设计时我们大家必须具备基本的程序设计知识,在平时的学习过程中多上机实习,试着用自己的思路去编程,调试及运行,在这过程中不断地积累经验,这样在做课程设计时就会比较得心应手.我在做此课程设计时花的时间比较长,但我自己认为这最大的可取之处在于我并没有用大多数的时间去编写源代码,而是用在如何构思上面,在经过深思熟虑之后再动手写源代码.因此整个课程设计进行得比较顺利,几乎没有出现”反工”的情况.但是其中也出现了一些解决不了的问题,具体见正文.同时我感触很深的一点是在编写代码时必须有一定的方法,这就涉及到计算机科学与技术这门学科所提到的方法论,其中很多的方法都具有很高的参考价值.正文1.采用类c语言定义相关的数据类型1.一维数组array[5]={3,1,2,5,4};2.参数盘子个数n，塔a，b，c3.一维数组横格Movel[8]={-2,-1,1,2,2,1,-1,-2};纵格Movev[8]={1,2,2,1,-1,-2,-2,-1};和二维数组int A[8][8];4.长整数的运算上述程序设计思想主要用到的数据结构是结构体和双向循环链表struct DuLNode //双向循环链表的结点;{int data;struct DuLNode *prior;struct DuLNode *next;};2.各模块的伪码算法1.排序算法比较问题：统一用三角替换方法void swap(int array[],int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}插入算法:void InsertSort(int array[],int n){for(int i=1;i<n;i++){for(int j=i;j>0;j--){if(array[j]>array[j-1])swap(array,j,j-1);elsebreak;}}}冒泡算法:void BubbleSort(int array[],int n) {for(int i=0;i<n-1;i++){for(int j=n-1;j>i;j--){if(array[j]<array[j-1])swap(array,j,j-1);}}}选择算法：void SelectionSort(int array[],int n) {for(int i=0;i<n-1;i++){int smallest=i;for(int j=i+1;j<n;j++){if(array[smallest]>array[j])smallest=j;}swap(array,i,smallest);}}}2.汉诺塔：递归部分void move(int n,char a,char b,char c){if(n==1)printf("\t%c->%c\n",a,c);else{move(n-1,a,c,b);printf("\t%c->%c\n",a,c);move(n-1,b,a,c);}}3.跳马问题：开始马的遍历for(int t=2;t<=64;t++)判断马的路线for(int p=0;p<=7;p++){l1=l+Movel[p];v1=v+Movev[p];if(l1>=0&&l1<=7&&v1>=0&&v1<=7&&A[l1][v1]==0) {d=0;for(int q=0;q<=7;q++){l2=l1+Movel[q];v2=v1+Movev[q];if(l2>=0&&l2<=7&&v2>=0&&v2<=7&&A[l2][v2]==0)d++;}if(b>=d){b=d;s=p;}}}if(b<=8){l+=Movel[s];v+=Movev[s];A[l][v]=t;}}4.长整数的运算：1.输入功能函数模块(具体实现时,把该函数命名为put_in，见源程序)该函数的参数是一个字符型数组,属于传址调用,在函数体里设置一个临时数字字符串数组,调用该函数时,便要求输入这个数字字符串,然后使用串拷贝分别把它赋值给形参表示的数组.在输入数据时一定要带上正负号,且必须以空格符作为结束符.2.转换功能函数模块(具体实现时,把该函数命名为Convert，见源程序)该函数参数是一个数字字符数组,功能是把该数字字符数组转变为相应长的十进制数,且用链表来表示,链表的一个结点存储一位十进制数,链表在构造过程中使用动态存储分配方式,在插入结点时采用前插法.最后函数的返回值是一个结构体指针.注意: 在进行数字字符到十进制的转换时使用了一个关键的关系式:“十进制值的ASCII码=相应数字字符的ASCII码-50+2”3加法功能函数模块(具体实现时,把该函数命名为Add，见源程序)该函数的参数是两个存储有任意长十进制的链表的表头指针,在进行加法运算时,从两链表的表尾指针开始按位运算,在每一位相加完后,把相加的结果用一个结构体来存储,再把该结构体使用前插法插入到新建的链表中,同时跟踪指针移到前一个结点,函数的返回值是指向结构体的指针.注意: 在具体实现按位加法运算时,用一个临时变量来存储该位的两位相加是否有进位,若有,则该临时变量置为1,否则置为0.在下一位按位加运算时还须加上该临时变量的值,同时重新设置该临时变量.因此可用一个循环结构来实现,循环结束的条件是:长度较短的操作数按位运算完毕.接着再用一个循环结构对较长的十进制数按位加上低位的进位,直到跟踪指针指向链尾结点为止.4.比较,交换功能函数模块(具体实现时,把该函数命名为Swap，见源程序)该函数的两个参数是两个数字字符数组,具体功能为:当第一个字符串的长度小于或等于第二个字符的长度时,把这两个数组交换一下,使第一个数组总是存储绝对值大的”十进制数”,第二个数组存储绝对值小的”十进制数”.函数属于传址调用,无返回值.5.减法功能函数模块(具体实现时,把该函数命名为Sub，见源程序)该函数的参数是两个存储有任意长十进制的链表的表头指针,函数的功能是从两链表的表尾结点开始实行按位相减运算,把相减的结果用一个结构体来存储,然后把该结构体用前插法插入到新的链表中,运算完后返回链表的表头指针.注意:在具体实现时设置两个临时变量t1,t11,t1来存放当前参加运算的位(即被减位)是否向高位有借位,若有则置为1,没有则置为0;t11用来存入当前参加运算的位的低位有没有向该借位,若有,则置为1,没有则置为0.其实t11的值总是等于上次按位运算时t1的值.当中用到了一个比较重要的运算公式是:”某位按位相减的结果=被减数+t1*10-t11-减数”.由于在减法运算前首先调用了Swap函数，因此被减数的绝对值一定大于减数的绝对值,绝对值相减完后得到结果的符号与被减数的符号相同.6.输出函数(具体实现时,把该函数命名为display，见源程序)该函数的参数是存储有十进制数链表的表头指针,调用该函数时便把该链表存储的十进制按要求输出,即从低位开始每四位为一组，组间用逗号分隔开.在具体实现,先计算出链表的结点数目n,再对n除以4取模为m,于是先输出前m 个结点的值,剩下的n-m个结点一定是4 的倍数,于是每输出四位便输出一个逗号.3.函数的调用关系图4.调试分析a、调试中遇到的问题及对问题的解决方法：1、长整数的代码输入时有乱码，只能固定两个长整数来调试2、有些代码重复出现，程序运行有些复杂。
《数据结构》实验指导书第一部分前言一、实验的目的《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。
本课程的另一重要教学目的是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，要做到这一点，上机实习是必须的。
数据结构实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
通常，实验课题中的问题比平时的习题复杂得多，也更接近实际。
实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，训练学生实际动手进行程序设计和调试程序的能力，加深对数据结构相关概念和算法的理解。
通过完成本实验课程的实验，学生应学会并掌握本课程的基本和重点知识，深刻理解逻辑结构、物理结构和算法设计之间的关系，初步学会算法分析的方法，并能在一定范围内运用所掌握的分析方法进行算法分析，培养软件工作所需要的动手能力和作为一个软件工作者所应具备的科学工作方法和作风。
二、实验前的准备工作1．每个学生需配备一台计算机，操作系统需Windows2000/XP以上版本，软件需Visual C++6.0以上版本。
2．实验前要求学生按实验要求编写好相关实验程序，准备上机调试运行。
三、实验的步骤（一）建立一个文件夹，如“数据结构”，用来存放自己的所有实验程序，在该文件夹中建立子目录用来存放每个项目（一个子目录一个项目），如“顺序表”，项目中需要的所有文件都存在该文件夹中。
（二）新建一个项目文件1．双击Visual C++ 6.0快捷图标，进入Visual C++ 6.0集成开发环境；或者点击“开始”→“程序”→“Microsoft Visual Studio 6.0”→“Microsoft Visual C++ 6.0”进入Visual C++ 6.0集成开发环境。
2．单击“File”菜单，选择“New”命令3．创建一个项目文件并保存在项目所在文件夹中；3. 创建源程序文件并保存在项目所在文件夹中；4．输入源程序；5．单击“保存”按钮保存源程序。
《数据结构》实验指导书软件学院2011年9月概述实习目的和要求《数据结构》在计算机科学中是一门实践性较强的专业基础课, 上机实习是对学生的一种全面综合训练, 是与课堂听讲、自习和练习相辅相成的必不可少的一个教学环节。
实习着眼于原理与应用的结合, 使学生学会把学到的知识用于解决实际问题, 起到深化理解和灵活掌握教学内容的目的。
同时, 通过本课程的上机实习, 使学生在程序设计方法及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
实习包括的步骤1. 简要描述题目要求, 对问题的描述应避开算法及所涉及的数据类型, 只是对所需完成的任务做出明确的陈述, 例如输入数据的类型、值的范围以及输入的形式, 输出数据的类型、值的范围以及输出的形式。
2. 选定数据结构, 写出算法, 根据自顶向下发展算法的方法, 首先描述算法的基本思想, 然后进行算法细化, 再对所设计的算法的时间复杂性和空间复杂性进行简单分析。
3. 准备好上机所需的程序, 选定一种程序设计语言（如C 语言）, 手工编好上机程序, 并进行反复检查, 使程序中的逻辑错误和语法错误减少到最低程度。
对程序中有疑问的地方, 应做出标记, 以便在上机时给予注意。
4．上机输入和调试程序, 在调试程序过程中除了系统的问题以外, 一般应自己独立解决。
在程序调试通过后, 打印输出程序清单和运行结果。
5．上机结束后, 总结和整理实习报告。
实习报告的内容1．简述题目要解决的问题是什么, 并说明输入和输出数据的形式。
2．简述存储结构和算法的基本思想。
3．列出调试通过的源程序。
4．列出上面程序对应的运行结果。
分析程序的优缺点、时空性能以及改进思想, 写出心得体会。
实验一线性表一. 目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现, 提高分析和解决问题的能力。
要求仔细阅读并理解下列例题, 上机通过, 并观察其结果, 然后独立完成后面的实习题。
《数据结构》实验指导书实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。
若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立线性表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。
二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立单链表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。
三、用C语言编程实现两个按递增顺序排列线性表的合并1、编程实现合并按递增顺序排列的两个顺序表算法；2、编程实现合并按递增顺序排列的两个单链表算法。
【思考问题】结合实验过程，回答下列问题：1、何时采用顺序表处理线性结构的问题为最佳选择；2、何时采用链表处理线性结构的问题为最佳选择。
【实验报告要求】1、根据对线性表的理解，如何创建顺序表和单链表；2、实现顺序表插入和删除操作的程序设计思路；3、实现链表插入和删除操作的程序设计思路；4、实现两表合并操作的程序设计思路；5、调试程序过程中遇到的问题及解决方案；6、本次实验的结论与体会。
湖北工程学院——计算机与信息科学学院《数据结构》实验指导书张凯兵目录实验一、线性表的顺序存储及其操作 (1)实验二、线性表的链式存储及其操作 (5)实验三、栈的顺序存储及其实现 (11)实验四、栈的链式存储及其实现 (15)实验五、队列的顺序存储及其实现 (19)实验六、队列的链式存储及其实现 (22)实验七、串的定长顺序存储结构及其实现 (26)实验八、树和二叉树的操作 (30)实验九、图的存储与实现 (36)实验十、各种查找操作 (39)实验十一、各种排序操作 (41)实验十二、数据结构课程设计(任选1题) (43)实验一、线性表的顺序存储及其操作一、实验目的（1）掌握线性表的特点（2）掌握线性表顺序存储结构基本运算。
（3）掌握顺序表的创建、插入、删除和显示线性表中元素等基本操作。
二、实验内容1．创建顺序存储结构的线性表2．线性表在顺序存储结构上的插入元素，删除元素运算三、实验要求1．C++/C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
四、程序实现写出每个操作的算法（操作过程）[参考源代码]#include <stdlib.h>#include <stdio.h>#include <iostream.h>#define MAXSIZE 20 //定义线性表最大容量typedef struct{int data[MAXSIZE];//线性表中数组元素int last;} SeqList;/************************************************************************* ** 函数名称：* Init_SeqList()* 参数:* 无* 返回值：指向线性表的指针* 说明:* 该函数用于创建顺序储存结构的空线性表**************************************************************************** /SeqList* Init_SeqList(){SeqList* L;L = new SeqList;if (L != NULL){L->last = -1 ;return L;}else{return NULL;}}/************************************************************************* ** 函数名称：* Insert_SeqList()* 参数:* SeqList*L：指向线性表的指针；int i: 插入位置；int x: 插入新元素数据* 返回值：插入成功：true插入失败：false* 说明:* 该函数用于在顺序储存结构的线性表插入一个新元素**************************************************************************** bool Insert_SeqList(SeqList* L, int i, int x){int j;if (L->last == MAXSIZE-1) //表已经满{cout<<"The list is full!"<<endl;return false;}if (i<1 || i>L->last+2) //插入位置不合法{cout<<"The position inserted is invaild!";return false;}for (j=L->last; j>= i-1; j--)//从最后一个元素开始到第i个元素全部后移1个位置{L->data[j+1] = L->data[j];}L->data[i-1] = x; //在第i个位置插入新元素L->last++; //表长加1return true;}/************************************************************************* ** 函数名称：* Create_SeqList()* 参数:* SeqList* L：指向线性表的指针；string fileName ;存放数据元素的文本文件名* 返回值：成功：true失败：false* 说明:* 该函数调用插入函数从一个文本文件中读入数据元素创建一个顺序表**************************************************************************** /bool Create_SeqList(SeqList* L,char* filename ){FILE *fin;int data;int i=0;bool ret=true;bool finished=false;if ((fin = fopen(filename, "r")) == NULL){return (NULL);}while (!finished){fscanf(fin,"%d",&data);if (data!=-1){i++;ret=Insert_SeqList(L,i,data);}else{finished = true;}}return ret;}/************************************************************************* ** 函数名称：* Delete_SeqList()* 参数:* SeqList* L：指向线性表的指针；int i ; 线性表中元素位置* 返回值：成功：true失败：false* 说明:* 该函数从顺序表中删除第i个位置上的元素**************************************************************************** /bool Delete_SeqList(SeqList* L,int i){int j=0;bool ret;if (L->last==-1){cout<<"The list is empty!"<<endl;return false;}if (i<1 || i>L->last+1) //删除位置不合法{cout<<"The position deleted is invaild!"<<endl;ret= false;}else{for (j=i;j<= L->last;j++){L->data[j-1]=L->data[j];}L->last--;ret =true;}return ret;}void OutPutList(SeqList* L){int i;for (i=0;i<=L->last;i++){cout<<L->data[i]<<" ";}cout<<endl;}void main(){SeqList *L;L=Init_SeqList();if (L!=NULL){Create_SeqList(L,"in.txt");OutPutList(L);Delete_SeqList(L,2);OutPutList(L);Insert_SeqList(L,5,100);OutPutList(L);}}五、程序运行情况在源程序所在文件夹下创建一个名称为in.txt的文本文件,输入数据如下: 1 2 3 4 5 6 7 8 -1作为线性表中的数据元素,其中-1表示输入数据元素的结束。
六、实验总结（1）（2）（3）实验二、线性表的链式存储及其操作七、实验目的（1）掌握线性表的特点（2）掌握线性表链式存储结构基本运算。
（3）掌握链式表的创建、插入、删除和显示线性表中元素等基本操作。
八、实验内容1．创建链式存储结构的线性表2．线性表在链式存储结构上的插入元素，删除元素运算九、实验要求4．C++/C完成算法设计和程序设计并上机调试通过。
5．撰写实验报告，提供实验结果和数据。
6．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
十、程序实现写出每个操作的算法（操作过程）[参考源代码]十一、程序运行情况#include <stdlib.h>#include <stdio.h>#include <iostream.h>//定义单链表结点类型typedef struct linkNode{int data;struct linkNode* next;}Node,*LinkList;/*************************************************************************** 函数名称：* outputLinkList()* 参数:* LinkList L：指向单链表的头指针；* 返回值：无* 说明:* 该函数输出单链表中所有的结点信息****************************************************************************/void outputLinkList(LinkList L){Node* p;p=L;//指向单链表中第一个结点printf("当前链表中的元素值分别为:\n");while (p!=NULL)//当结点存在时{printf("%2d\t",p->data);p=p->next;//指向p后继结点}}/*************************************************************************** 函数名称：* Length()* 参数:* LinkList L：指向单链表的头指针；* 返回值：单链表中结点的个数* 说明:* 该函数输出单链表结点的个数****************************************************************************/int Length(LinkList L){Node* p;int length=0;p=L;//指向单链表中第一个结点while (p!=NULL)//当结点存在时{length++;p=p->next;//指向p后继结点}return length;}/*************************************************************************** 函数名称：* CreateList()* 参数:* 无；* 返回值：指向单链表的头指针* 说明:* 该函数从键盘上顺序输入若干个整数，以－1结束，从表尾建立一个不带头结点的单链表（只有头指针）****************************************************************************/ LinkList CreateList(){Node *p,*s,*head;head=NULL;p=head;int finished=0;int x;int i=0;printf("－－－输入若干个整数，以回车键结束!如输入-1则结束整个输入!－－－\n");while (finished!=1)//当建立未结束{printf("输入第%d新元素:",++i);scanf("%d",&x);if (x!=-1)//判断输入是否结束{s=new Node;s->data=x;if (head==NULL) //对空表单独处理{head=s;}else//对非空表单独处理{p->next=s;}s->next=NULL;p=s;//指向最后一个结点}else{finished=1;}}return head; //返回头指针}/*************************************************************************** 函数名称：* Node* SearchLinkList(LinkList L,int i)* 参数:* LinkList L:指向链表的头指针* int i:第i个结点的编号* 返回值：指向第i个结点的指针* 说明:* 该函数从单链表L中查找第i个结点，并返回指向该结点的指针****************************************************************************/ Node* SearchLinkList(LinkList L,int i){Node* p;int j=1;p=L; //p指向第一个结点while (p!=NULL && j<i)//链表非空且还没后指向第i个结点时{p=p->next;//指向下一个结点j++;}return p;}/************************************************************************* ** 函数名称：* Node* InsertLinkList(LinkList L,int i,int x)* 参数:* LinkList L:指向链表的头指针* int i:第i个结点的编号* 返回值：失败：0成功：1* 说明:* 该函数从单链表L中查找第i个结点，并返回指向该结点的指针****************************************************************************/ int InsertLinkList(LinkList L,int i,int x){LinkList p,s;p=SearchLinkList(L,i-1);if (p==NULL)//第i个结点存在，p指向的是第i个结点的前驱结点的指针{return 0;}else //新建结点并执行两步插入{s=new Node;s->data=x;s->next=p->next;p->next=s;return 1;}}/************************************************************************* ** 函数名称：* int DeleteLinkList(LinkList L,int i)* 参数:* LinkList L:指向链表的头指针* int i:第i个结点的编号* 返回值：第i－1个结点不存在：-1第i个结点不存在：0成功：1* 说明:* 该函数从单链表L中查找第i个结点，并返回指向该结点的指针****************************************************************************/ int DeleteLinkList(LinkList L,int i){LinkList p,s;p=SearchLinkList(L,i-1);//查找第i-1个结点if (p==NULL)//第i－1个结点存在，p指向的是第i个结点的前驱结点的指针{return -1;}else{if (p->next==NULL)//第i个结点不存在{return 0;}else//删除第i个结点{s=p->next;//指向第i个结点p->next=s->next;delete s;s=NULL;return 1;}}}void main(){LinkList Head;Head=CreateList();//创建带头指针的单链表outputLinkList(Head);//输出单链表详细信息printf("\n单链表的长度%d\n",Length(Head));if (InsertLinkList(Head,4,400))//在单链表中插入一个元素{printf("\n插入成功...!\n");outputLinkList(Head);//输出单链表详细信息}else{printf("\n插入失败...!\n");}if (DeleteLinkList(Head,4)==1)//在单链表中删除一个元素{printf("\n删除成功...!\n");outputLinkList(Head);//输出单链表详细信息}else{printf("\n删除失败...!\n");}}十二、实验总结（1）（2）（3）实验三、栈的顺序存储及其实现一、实验目的1、掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构，以便在实际问题背景下灵活应用。
