数据结构实验与课程方案指导书 .pdf

《数据结构实验与课程方案指导书 .pdf》由会员分享，可在线阅读，更多相关《数据结构实验与课程方案指导书 .pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、个人资料整理仅限学习使用数据结构实验指导书数据结构课程组精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 13 页个人资料整理仅限学习使用广东工业大学计算机学院2018 年 4 月第 1 章概述1.1 课程、教材和实验数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。数据结构不仅是计算机专业的核心课程，而且已成为其他理工专业的热门选修课。课程的教案要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯, 其重要程度决不亚于知识传授。因此，在数据结构的整个教案过程中,

2、 完成习题作业和上机实习是两个至关重要的环节。习题的作用在于帮助学生深入理解教材内容, 巩固基本概念, 达到培养良好程序设计能力和习惯的目的。从认知的程度划分，数据结构的习题通常可分为三类：基础知识题、算法设计题和综合实习题。基础知识题主要是检查对概念知识的识记和理解，一般可作为学生自测题。算法设计题的目的是练习对原理方法的简单应用，多数是要求在某种数据存储结构上实现某一操作，是数据结构的基础训练，构成了课外作业的主体。综合实习题则训练对知识的综合应用和软件开发能力，主要是针对具体应用问题，选择、设计、和实现抽象数据类型ADT ）的可重用模块，并以此为基础开发满足问题要求的小型应用软件，应将其

3、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 13 页个人资料整理仅限学习使用看作软件工程的综合性基础训练的重要一环，给予足够的重视。本实验指导书为采用下列教材的数据结构课程而编写：1 严蔚敏，吴伟民. 数据结构C 语言版，含光盘）. 清华大学出版社，2002.9 2 严蔚敏，吴伟民. 数据结构题集C 语言版） . 清华大学出版社，1999.2 其中，数据结构题集实际上是一本较全面的学习和实验指导书。本实验指导书根据教案计划给予一些补充，与上述两本教材配合使用。数据结构题集的第一篇为习题篇，含有三百余道习题，组织成十二章，分别对应教科

4、书中各章内容，并在每章之前给出该章的内容提要和学习要求。这些习题是作者在多年教案过程中所积累资料的基础上，参考大量国外教材之后精心设计而成的。书中对特别推荐的题目作了标记，并对每道习题的难易程度按五级划分法给出了难度系数。第二篇为实习篇，分别以抽象数据类型、线性表、栈和队列、串、数组和广义表、树和图以及查找和排序为核心，设置了七组上机实习题，每组有3 至 9 个题目供学生自由选择。期望这些实习题能对习题起到良好的扩充作用，使学生受到涉及“从问题到程序”的应用软件设计的完整过程的综合训练，培养合作能力，成为将来进行软件开发和研究工作的“实践演习”。数据结构是实践性很强的课程，光是“听”和“读”是

5、绝对不够的。在努力提高课堂教案的同时，必须大力加强对作业实践环节的要求和管理。国内外先进院校一般都要求修读数据结构的学生每周应不少于4 个作业机时，而且有一套严格的作业和实习规范和成绩评定标准，形成行之有效的教案质量保证体系。数据结构题集强调规范化在算法设计基本训练中的重要地位。在习题篇中给出了算法书写规范，在实习篇中给出了实习步骤和实习报告的规范。教案经验表明，严格实施这些貌似繁琐的规范，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将能起到显著的促进作用。数据结构及其算法的教案难点在于它们的抽象性和动态性。虽然在书本教材和课堂授课板书或投影胶片）中采用图示可以在一定程度上化抽象

6、为直观，但很难有效展现数据结构的瞬间动态特性和算法的作用过程。在随教科书配发的光盘中，“数据结构的算法动态模拟辅助教案软件DSDEMO ”是为学习并掌握数据结构中各类典型算法而开发的一个辅助教案软件，可对教科书中八十余个典型算法进行动态交互式跟踪演示，在算法执行过程中实现数据结构和算法的动态同步可视化，使学生获得仅从教材文字说明中无法获得的直观知识。软件既可用于课堂讲解演示，又能供个人课外反复观察、体会和理解，对提高教案质量和效率有显著效果。在习题篇的每一章列举了与该章相关的算法清单，并在数据结构题集附录中提供该软件完整的使用说明。1.2 实验安排根据教案计划，数据结构课程的实验和上机由三部分

7、构成：1 算法设计实验和上机30 机时）在“数据结构算法设计作业系统”上机完成40 道题，学有余力的同学还可以选做另外40 道题。2 抽象数据类型的实现6 学时设计性实验）实现一个抽象数据类型，并对所采用的存储结构和相关操作的实现进行讨论。3 课程设计 一周综合性实验）完成数据结构题集中的一个实习题。第 2 章算法设计实验和上机2.1 数据结构习题概述数据结构题集把数据结构的习题分为“基础知识题”和“算法设计题”两类。“基础知识题”主要供学生进行自测和复习之用，目的是帮助学生深化理解教科书的内容，澄清基本概念、理解和掌握数据结构中分析问题的基本方法和算法要点，为完成算法设计题做准备。“算法设计

8、题”则侧重于基本程序设计技能的训练，相对于实习题而言，这类编程习题属于偏重于编写功能单一的“小”程序的基础训练，然而，它是进行复杂程序设计的基础，是本课程习题作业的主体和重点。各章的题量根据教案内容的多少和重要程度而定，几乎对教科书的每一小节都安排了对应的习题。但对每个学生来说，不必去解全部习题，而只须根据自己的情况从中选择若干求解即可。为了表明题目的难易程度，便于学生选择，在每个题的题号之后注了一个难度系数，难度级别从至逐渐加深，其区别大精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 13 页个人资料整理仅限学习使用致如下：难度系数为

9、和的习题以基础知识题为主；难度系数为的习题以程序设计基础训练为主要目的，如强化对“指针”的基本操作的训练等；习题中也收纳了不少难题，其难度系数设为和，解答这些题可以激起学习潜力较大的学生的兴趣，对广泛开拓思路很有益。但习题的难度系数也只是一个相对量，学生的水平将随学习的进展而不断提高，因此没有必要去比较不同章节的习题的难度系数，此外，该难度系数值的假设是以学生没有参照习题的解答或提示为前提的。“循序渐进”是最基本的学习原则。学习者不应该片面追求难题。对于解难度系数为i 的习题不太费力的学生，应试试难度系数为i+1 的习题，但不要把太多的时间浪费在难度系数为i+2 的习题上。“少而精”和“举一反

10、三”是实践证明行之有效的。解答习题应注重于“精”，而不要求“多”。为此，在一些值得向学生推荐的“好题”题号前加注了标记。把握住这些“关键点”，就把握住了数据结构习题、乃至数据结构课程的总脉络。2.2 算法设计的上机作业要求1使用 Anyview C 语言和算法书写规范写出书面作业的算法函数），作为上机前的准备。需要强调的是“算法的可读性”。算法是为了让人来读的，而不是供机器读的。初学者总是容易忽视这一点。算法的真正意图主要在于提供一种在程序设计者之间交流解决问题方法的手段。因此，可读性具有头等的重要性。不可读的算法是没有用的，由它得到的程序极容易产生很多隐藏很深的错误，且难以调试正确。一般地说

11、，宁要一个可读性好、逻辑清晰简单、但篇幅较长的算法，也不要篇幅较小但晦涩难懂的算法。算法的正确性力求在设计算法的过程中得到保证，然而一开始做不到这一点也没多大关系，可以逐步做到。算法设计的正确方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略逐一地解决子问题，最后严格按照和使用本章后面提供的算法书写规范和类C 语言完成算法的最后版本。按照规范书写算法是一个值得高度重视的问题。在基础训练中就贯彻这一规范，不但能够有助于写出“好程序”，避免形成一系列难以纠正且遗害无穷的程序设计坏习惯，而且能够培养软件工作者应有的严谨的科学工作作风。2对函数进行静态检查

12、修改，形成准备上机的程序文本。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，查纠错误是上机的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过50 行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地分析理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。3在“ Anyview C 数据结构算

13、法设计作业系统”编辑提交程序，并在系统的自动测试和提示下，调试程序，直到能通过系统的测试。“ Anyview C 数据结构算法设计作业系统”提供了程序可视化运行和调试的环境，为进行数据结构教案的师生提供了算法设计作业程序的可视化自动测试环境。可在该集成环境编辑C 源程序，并对其进行可视化运行、分析和调试。通过设置断点、单步或变换速度的连续运行，可在多个窗口上动态观察程序执行时的数据变量的物理和逻辑2D 或 3D 视图，使得程序运行期间本来不可见的程序对数据的处理过程和数据之间的动态抽象关系全部可视化。在提交算法设计作业程序时，系统自动进行可视化测试，评判作业程序的正确性。通过对比“标准结果视图

14、”和“作业结果视图”，作业者可对自己的程序进行直观的分析和排错。关于该作业系统的使用，请参阅系统的帮助文档。在调试过程中可以不断借助系统的可视DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，这时不应“苦思冥想”，而应动手确定疑点，通过修改程序来证实它或绕过它。4在调试程序的过程中，做好调试笔记，记录心得体会。调试正确后，认真整理源程序及其注释，记录带有完整注释的且格式良好的源程序清单和结果。一道算法设计作业文档包括：1）上机前编写并经过静态检查的程序文本；2）调试笔记；3）最后程序文本，及通过时间。2.3 算法设计上机作业1作业内容和机时40 道必做题， 40 道

15、选做题。每年作适当调整更换。6 个课内实验机时，教师现场指导答疑。24 个课外训练机时，实验教师指导答疑。学生平时可以在互联网上登录系统，做选做题。2算法设计题目文档精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 13 页个人资料整理仅限学习使用系统为每道算法设计题提供一个题目文档，包括以下内容：1）题目；2）算法的函数原型；3）可用的类型定义和函数原型。做题前，必须仔细阅读题目文档，正确理解题目和做题要求。第 3 章抽象数据类型的实现3.1 实验概要实验工程名称: 抽象数据类型的实现实验工程性质: 设计性实验所属课程名称: 数据结构实

16、验计划学时: 6 3.2 实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。3.3 预习与参考1确定要实现的抽象数据类型，并对基本操作做适当的选取和增加；2选择存储结构，并写出相应的类型定义；3设计各基本操作的实现算法，并表达为函数形式；4设计测试方案，编写主函数；5将上述4 步的结果写成预习报告。3.4 实验要求和设计指标以教材中线性表，串，稀疏矩阵，广义表，二叉树，树，图以及查找表等抽象数据类型为对象，利用

17、C语言的数据类型表示和实现其中某个抽象数据类型。可选的抽象数据类型如下表所列：编号抽象数据类型基本难度教材页码1 复数1.0 数据结构题集P.762 有理数1.0 数据结构题集P.763 海龟作图1.2 数据结构题集P.774 一元稀疏多项式1.2 数据结构 P.405 稀疏矩阵1.3 数据结构 P.966 广义表1.4 数据结构 P.1077 树1.5 数据结构 P.1188 二叉树1.5 数据结构 P.1219 图1.4 数据结构 P.15610 静态查找表1.2 数据结构 P.21611 动态查找表1.3 数据结构 P.226注：如果基本操作数量较多，可选择实现其中一个基本操作子集。实验

18、要求如下：1参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 13 页个人资料整理仅限学习使用3. 实验时严肃认真，要严格按照要求独立进行设计

19、，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。3.5 实验仪器设备和材料软件实验室。编程环境： Anyview C 可视化编程环境、TC+ 、C+Builder或者 VC+ 。3.6 调试及结果测试调试内容应包括：调试过程中遇到的问题是如何解决的以及对实验的讨论与分析；基本操作的时间复杂度和空间复杂度的分析和改进设想。列出对每一个基本操作的测试结果，包括输入和输出，测试数据应完整和严格。3.7 考核形式考核形式以实验过程和实验报告相结

20、合的方式进行。在实验完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算实验部分的结束。实验报告作为整个设计性实验评分的书面依据。设计性实验的成绩评定以选定题目的难易度、完成情况和实验报告为依据综合评分。从总体来说，所实现的抽象数据类型应该全部符合要求，类型定义，各基本操作的算法以及存储结构清晰；各模快测试运行正确；程序的结构合理；设计报告符合规范。3.8 实验报告要求实验结束后要写出实验报告，以作为整个设计性实验评分的书面依据和存档材料。实验报告是反映学生实验效果的最主要的依据，也是学生正确地表达问题、综合问题和发现问题的能力的基本培养手段，因而是非常重要的内容。本设计性实验的报

21、告要包括以下几项内容：1）设计任务、要求及所用软件环境或工具；2）抽象数据类型定义以及各基本操作的简要描述；3）所选择的存储结构描述及在此存储结构上各基本操作的实现；4）程序清单 计算机打印），输入的数据及各基本操作的测试结果；5）实验总结和体会。实验报告以规定格式的电子文档书写、打印并装订，排版及图表要清楚、工整。3.9 思考题对设计性实验进行总结和讨论，包括本实验的优、缺点，数据存储结构的特点，与其它存储结构之间的比较等。通过总结，可以对抽象数据类型有更全面、深入的认识，这是设计性实验不可缺少的重要内容。这部分内容应作为实验报告中的一个组成部分。3.10 示例1. 题目采用字符类型为元素类

22、型和无头结点单链表为存储结构，实现抽象数据类型List。 ADT List 数据对象 ：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系 ：R1 |ai-1,aiD, i=2,.,n 基本操作 ： SetEmpty(&L 操作结果：构造一个空的线性表L。 Destroy(&L 初始条件：线性表L 已存在。操作结果：销毁线性表L。 Length(L 初始条件：线性表L 已存在。操作结果：返回L 中元素个数。 Get(L, i, &e 初始条件：线性表L 已存在， 1i LengthList(L。操作结果：用e 返回 L 中第 i个元素的值。 Locate(L, e, c

23、ompare( 初始条件：线性表L 已存在， compare(是元素判定函数。操作结果：返回L 中第 1 个与 e 满足关系compare(的元素的位序。若这样的元素不存在，则返回值为0。 Insert(&L, i, e 初始条件：线性表L 已存在， 1i LengthList(L+1。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 13 页个人资料整理仅限学习使用操作结果：在L 的第 i个元素之前插入新的元素e，L 的长度加1。 Delete(&L, i, & e 初始条件：线性表L 已存在且非空，1i LengthList(L。操作

24、结果：删除L 的第 i个元素，并用e 返回其值， L 的长度减1。Display(L 初始条件：线性表L 已存在。操作结果：依次输出L 的每个元素。 ADT List 2存储结构定义公用头文件DS0.h: #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define IBFEASIBLE -1 #define OVERFLOW -2 #define MAXLEN 20#define MAXSIZE 20 typedef int St

25、atus。typedef char ElemType。 /* 元素类型为字符类型*/ （1）顺序存储结构#define LIST_INIT_SIZE 20 /*线性表存储空间的初始分配量*/ #define LISTINCREMENT 10 /*线性表存储空间的分配增量*/ typedef struct ElemType *elem。 /*存储空间基址*/ int length。 /*当前长度 */ int listsize。 /*当前分配的存储容量*/ SqList。（2）无头结点单链表存储结构typedefstruct LNode ElemType data。struct LNode *n

26、ext。 LNode, *LList。 /* 不带头结点单链表类型*/ （3）带头结点单链表存储结构typedefstruct LNode /* 结点类型 */ ElemType data。struct LNode *next。 LNode, *Link, *Position。typedefstruct LinkList /* 链表类型 */ Link head,tail。 /* 分别指向线性链表中的头结点和最后一个结点 */ int len。 /* 指示线性链表中数据元素的个数 */ LinkList。3. 算法设计（1）顺序存储结构Status SetEmpty(SqList &L /*构

27、造一个空的顺序线性表 */ L.elem=(ElemType*malloc(LIST_INIT_SIZE*sizeof(ElemType。if(!L.elem 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 13 页个人资料整理仅限学习使用return OVERFLOW。 /* 存储分配失败 */ L.length=0。 /* 空表长度为0 */ L.listsize=LIST_INIT_SIZE。 /* 初始存储容量 */ return OK 。 Status Destroy (SqList &L /* 销毁顺序线性表L */ fre

28、e(L.elem。 L.elem=NULL。 L.length=0。 L.listsize=0。return OK 。 int Length(SqList L /* 求表长 */ return L.length。 Status Get(SqList &L, int i, ElemType &e /* 获取第 i 元素 */if(iL.length return ERROR。 e=*(L.elem+i-1。return OK 。 int Locate(SqList L, ElemType x /* 确定 x 在表中的位序 */ ElemType *p。int i=1。 /* i的初值为第1 个元

29、素的位序 */ p=L.elem。 /* p的初值为第1 个元素的存储位置 */ while(i +i 。if(i return i。else return 0 。 Status Insert(SqList &L, int i, ElemType e /* 操作结果：在L 中第 i 个位置之前插入新的数据元素e， L 的长度加1 */ ElemType *newbase,*q,*p。if(iL.length+1 /* i值不合法 */ return ERROR。if(L.length= L.listsize /* 当前存储空间已满, 增加分配 */ newbase=(ElemType *rea

30、lloc(L.elem, (L.listsize+LISTINCREMENT*sizeof(ElemType。if(!newbasereturn OVERFLOW。 /* 存储分配失败 */ L.elem=newbase。 /* 新基址 */ L.listsize+=LISTINCREMENT。 /* 增加存储容量 */ q=L.elem+i-1。 /* q为插入位置 */ for(p=L.elem+L.length-1。 p=q。 -p *(p+1=*p。 /* 插入位置及之后的元素右移 */ *q=e。 /* 插入 e */ +L.length。 /* 表长增 1 */ return OK

31、 。 Status Delete(SqList &L, int i, ElemType &e /* 初始条件：顺序线性表L 已存在， 1i ListLength(L */ /* 操作结果：删除L 的第 i 个数据元素，并用e 返回其值， L 的长度减1 */ ElemType *p,*q。if(i L.length /* i值不合法 */ return ERROR。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 13 页个人资料整理仅限学习使用 p= L.elem+i-1。 /* p为被删除元素的位置 */ e=*p。 /* 被删除元素

32、的值赋给e */ q= L.elem+L.length-1。 /* 表尾元素的位置 */ for(+p 。 p /* 被删除元素之后的元素左移 */ *(p-1=*p。 L.length-。 /* 表长减 1 */ return OK 。 Status Display(SqList L /* 依次显示表中元素 */ ElemType *p。int i。 p=L.elem。 printf( 。for(i=1。 i printf(%c,*p+。 printf( n。return OK 。 （2）无头结点单链表void SetEmpty(LList &L /* 置无头结点的空单链表*/ L=NULL

33、。 Status Destroy (LList &L /* 销毁链表 */ LList q=L。while(L L=L-next。 free(q。 q=L。 return OK 。 int Length(LList L /* 求表长 */ int n=0。while(L!=NULL n+。 L=L-next。 return n 。 Status Get(LList L, int i, ElemType &e /* 获取第 i 元素 */ int j=1。while (j L=L-next。 j+。 if(L!=NULL e=L-data。return OK 。elsereturn ERROR。

34、 /* 位置参数 i 不正确 */ int Locate(LList L, ElemType x /* 确定 x 在表中的位序 */ int n=1 。while (L!=NULL & L-data!=x L=L-next。 n+。 if (L=NULL return 0 。else return n 。 Status Insert(LList &L, int i, ElemType e /* 插入第 i 元素 */精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 13 页个人资料整理仅限学习使用int j=1。 LList s,q。 s

35、=(LListmalloc(sizeof(LNode。 s-data=e。 q=L。if (i=1 s-next=q。 L=s。return OK 。else while(jnext!=NULL q=q-next。 j+。 if (j=i-1 s-next=q-next。 q-next=s。return OK 。 elsereturn ERROR。 /* 位置参数i 不正确 */ Status Delete(LList &L, int i, ElemType &e /* 删除第 i 元素 */int j=1。 LList q=L,t。if (i=1 e=q-data。 L=q-next。 fr

36、ee(q。return OK 。 else while (jnext!=NULL q=q-next。 j+。 if (q-next!=NULL & j=i-1 t=q-next。 q-next=t-next。e=t-data。 free(t。return OK 。 else return ERROR 。 /* 位置参数i 不正确 */ void Display(LList L /* 依次显示表中元素 */ printf(单链表显示 : 。if (L=NULL printf(链表为空 !。elseif (L-next=NULL printf(%cn, L-data。else while(L-ne

37、xt!=NULL printf(%c-, L-data。 L=L-next。 printf(%c, L-data。 printf(n。 （3）带头结点单链表精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 13 页个人资料整理仅限学习使用Status SetEmpty(LinkList &L /* 置带头结点的空单链表*/ Link p。 p=(Linkmalloc(sizeof(LNode。 /* 生成头结点 */ if(p p-next=NULL。 L.head=L.tail=p。 L.len=0。 return OK。 else

38、return ERROR。 Status Destroy(LinkList &L /* 销毁线性链表L，L 不再存在 */ Link p,q。if(L.head!=L.tail /* 不是空表 */ p=q= L.head-next。 L.head-next=NULL。while(p!=L.tail p=q-next。 free(q。 q=p。 free(q。 free(L.head。 L.head=L.tail=NULL。 L.len=0。return OK 。 int Length(LinkList L /* 返回线性链表L 中元素个数 */ return L.len。 Status Ge

39、t(LinkList L, int i, ElemType &e /* 获取第 i 元素 */ /* i=0为头结点 */ Link p。int j。if(iL.len return ERROR。else p=L.head。for(j=1。 j p=p-next。 e=p-data。return OK 。 int Locate(LinkList L, ElemType x /* 确定 x 在表中的位序 */int i=0。 Link p=L.head。do p=p-next。 i+。 while(p & p-data!=x。 /* 没到表尾且没找到满足关系的元素 */ if (!p retur

40、n 0 。else return i。 Status Insert(LinkList &L, int i, ElemType e /* 插入第 i元素 */精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 13 页个人资料整理仅限学习使用int j=0。 Link s,q。 s=(Linkmalloc(sizeof(LNode。 s-data=e。 q=L.head。while(jnext!=NULL q=q-next。 j+。 if (j=i-1 s-next=q-next。 q-next=s。if (L.tail=q L.tail=

41、s。 L.len+。return OK 。 elsereturn ERROR。 /* 位置参数i 不正确 */ Status Delete(LinkList &L, int i, ElemType &e /* 删除第 i 元素 */ int j=0。 Link q=L.head,t。while (jnext!=NULL q=q-next。 j+。 if (q-next!=NULL & j=i-1 t=q-next。 q-next=t-next。e=t-data。if(L.tail=t L.tail=q。 free(t。 L.len-。return OK 。 else return ERROR。

42、 /* 位置参数i 不正确 */ void Display(LinkList L /* 依次显示表中元素 */ Link p。 printf(单链表显示 : 。if (L.head=L.tail printf(链表为空 !。else p=L.head-next。while(p-next!=NULL printf(%c-, p-data。 p=p-next。 printf(%c, p-data。 printf(n。 4测试（1）顺序存储结构SqList head。void main( /* 主函数 */ char e,c。int i,n,select,x1,x2,x3,x4,m,g。精选学习资料

43、 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 13 页个人资料整理仅限学习使用SetEmpty(head。 n=random(8。 /* 随机产生表长 */ for (i=1。 i /* 将数据插入到顺序表中 */ c=A+random(26。Insert(head,i,c。 doDisplay(head。 printf(select 1 求长度 Length(n。 printf(select 2 取结点 Get(n。 printf(select 3 求值查找 Locate(n。 printf(select 4 删除结点 Delete(n。printf(input your select: 。scanf(%d,&select。switch(select case 1: x1=Length(head。 printf(顺序表的长度 :%d ,x1。break。case 2: printf(请输入要取的结点序号: 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 13 页