《数据结构与算法设计》d(4)
- 格式：pptx
- 大小：1.14 MB
- 文档页数：15
下载文档原格式
合集下载
罗文劼《数据结构与算法》第4版-第1章课后习题参考答案
第1章绪论1.选择题（1）C （2）B （3）C （4）D （5）B2.判断题（1）√（2）Ⅹ（3）Ⅹ（4）Ⅹ（5）√3.简答题（1）根据数据元素之间的不同逻辑关系，通常将其划分为哪几类结构？【解答】常见的四种逻辑结构有：①集合结构：数据元素间的关系是“属于同一个集合”。
②线性结构：数据元素之间存在着一对一的关系。
③树型结构：数据元素之间存在着一对多的关系。
④图型结构：数据元素之间存在着多对多的关系。
（2）请描述线性结构中数据元素与数据元素之间的关系特点？【解答】线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。
在线性结构中，有且仅有一个元素被称为“第一个”，除第一个元素之外其他元素均有唯一一个“前驱”；有且仅有一个元素被称为“最后一个”，除最后一个元素之外其他元素均有唯一一个“后继”。
（3）请描述树形结构中数据元素与数据元素之间的关系特点？【解答】树形存储结构，就是数据元素与元素之间存在着一对多关系的数据结构。
在树形存储结构中，树的根节点没有前驱结点，其余的每个节点有且只有一个前驱结点，除叶子结点没有后续节点外，其他节点的后续节点可以有一个或者多个。
（4）常用的存储结构有哪几种，各自的特点是什么？【解答】常见的四种存储结构有：①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。
顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
②链接存储：对逻辑上相邻的元素不要求不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。
③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点其它信息。
④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。
（5）简述算法和程序的区别。
【解答】一个算法若用程序设计语言来描述，则它就是一个程序。
算法的含义与程序十分相似，但又有区别。
一个程序不一定满足有穷性。
数据结构与算法教学大纲
《数据结构》教学大纲一、课程基本信息课程名称：数据结构总学时：64（理论课内学时48,上机课内学时16）课程设计：24课程类型：必修课考试形式：半开卷考试讲课对象：计算机本科建议教材：《数据结构》（C语言版）陈明编著清华大学出版社课程简介：数据结构课程介绍如何组织各种数据在计算机中的存储、传递和转换。
内容包括：数组、链接表、栈和队列、串、树与森林、图、排序、查找、索引与散列结构等。
课程以结构化程序设计语言C语言作为算法的描述工具，强化数据结构基本知识和结构化程序设计基本能力的双基训练。
为后续计算机专业课程的学习打下坚实的基础。
二、课程的教学目标“数据结构”是计算机相关专业的一门重要专业基础课，是计算机学科的公认主干课。
课程内容由数据结构和算法分析初步两部份组成。
数据结构是针对处理大量非数值性程序问题而形成的一门学科，内涵丰富、应用范围广。
它既有完整的学科体系和学科深度，又有较强的实践性。
通过课程的学习，应使学生理解和掌握各种数据结构（物理结构和逻辑结构）的概念及其有关的算法；熟悉并了解目前常用数据结构在计算机诸多领域中的基本应用。
算法分析强调最基本的算法设计技术和分析方法。
要求学生从算法和数据结构的相互依存关系中把握应用算法设计的艺术和技能。
经过上机实习和课程设计的训练，使学生能够编制、调试具有一定难度的中型程序；以培养良好的软件工程习惯和面向对象的软件思维方法。
“数据结构”的前序课是《离散数学》、《C语言程序设计与算法初步》。
三、理论教学内容的基本要求及学时分配1、序论（2学时）学习目标：熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。
重点与难点：本章无。
知识点：数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度。
2、线性表(4学时)学习目标：(1)了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。
《数据结构与算法(C++语言版)》第4章_串
串函数与串的类定义
• 常用的 常用的C++串函数 串函数 • C++的串库（string.h）中提供了许多字符串的操作函数，几 个常用的C++字符串函数及其使用方法如下。 •假设已有以下定义语句：
串函数与串的类定义
• （1）串拷贝函数 • char *strcpy(char *s1, const char *s2)，将字符串s2复制到字 符串数组s1中，返回s1的值。 • char *strncpy(char *s1, const char *s2, size_tn)将字符串s2中最 多n个字符复制到字符串数组s1中，返回s1的值。 • 例如：
串函数与串的类定义
• （3）串比较函数 • int strcmp(const char *s1, const char *s2)，比较字符串s1和字 符串s2。函数在s1等于、小于或大于s2时，分别返回0、小 于0或者大于0的值。 • int strncmp(const char *s1, const char *s2, size_tn)比较字符串 s1中的n个字符和字符串s2。函数在s1等于、小于或大于s2 时，分别返回0、小于0或者大于0的值。 • 例如：
串模式匹配
• 无回溯的匹配算法 • 在上面介绍的匹配算法中，某趟匹配失败时，下一趟的匹 配相当于将子串P后移1位再从头与主串中对应字符进行比 较，即相当于i指示器回溯到上趟（最近失败的一趟）匹配 的起点的下一个位置，这样，主串中每个字符都要与子串 中的第1个字符对应一次，再向后比较。因此，主串中每个 字符参加比较的次数最多可达n次（n为子串长度），因此 时间复杂度为O(nm)。那么，能否使目标串中每个字符只参 加一次比较呢？也就是说，能否不回溯i指示器？回答是肯 定的。这个问题是由D.E.Knoth与V.R.Pratt和J.H.Morris同时 解决的，所以有的文献也称这种思想的串匹配算法为KMP 算法。
罗文劼《数据结构与算法》第4版-第1章 绪论
第1章 数据结构与算法
⒈教学内容：
(1)数据结构的概念 (2)抽象数据类型 (3)算法和算法分析 (4)递归
⒉ 教学目的：
(1)领会数据、数据元素和数据项的概念及其相互间关系 (2)清楚数据结构的逻辑结构、存储结构的联系与区别 (3)理解抽象数据类型的概念 (4)掌握进行简单算法分析的方法 (5)理解递归的特点，会分析什么样的问题适合用递归解决；领会递归调 用的执行过程； 了解递归的优缺点
下图为表示上述四类基本结构的示意图。
（a）集合结构
（b）线性结构
（c）树结构
（d）图结构 四类基本结构的示意图
1.2.2 抽象数据类型
1、数据类型
数据类型是一个值的集合和定义在这个值集上的一 组操作的总称。
2、抽象数据类型
抽象数据类型（Abstruct Data Type，简称ADT） 是指一个数学模型以及定义在该模型上的一组操作。
1.3 算法
1.3.1 算法及其特性
算法（Algorithm）是对特定问题求解步骤的一种描述， 是指令的有限序列。其中每一条指令表示一个或多个操作。
算法特性： ⑴ 有穷性。 ⑵ 确定性。 ⑶ 可行性。 ⑷ 输入。 ⑸ 输出。
算法要求： ⑴正确。 ⑵可读。 ⑶健壮。 ⑷高效。
2022年2月21日
1.3.2 算法描述
将一个算法转换成程序并在计算机上执行时，其运行所需 要的时间取决于下列因素：
⑴ 硬件的速度。 ⑵ 书写程序的语言。 ⑶ 编译程序所生成目标代码的质量。 ⑷ 问题的规模。
本课程的任务：
在基础方面，要求学生掌握常用数据结构的 基本概念及其不同的实现方法；在技能方面，通过 系统学习能够在不同存储结构上实现不同的运算， 并对算法设计的方式和技巧有所体会。
《数据结构与算法》期末练习题3
数据结构与算法一选择题1．算法的计算量的大小称为计算的（）。
A．效率 B. 复杂性 C. 现实性 D. 难度2．下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)3. 连续存储设计时，存储单元的地址（）。
A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续4. 下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表6．下面的叙述不正确的是（）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关7．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。
A. O(0)B. O(1)C. O(n)D. O(n2)8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）(^.相当于—>)A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q;9．下列排序算法中，其中（）是稳定的。
《数据结构与算法》第四章-学习指导材料
《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。
4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。
一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。
２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。
包含子串的串相应地称为主串。
子串的位置：子串的第一个字符在主串中的序号称为子串的位置。
串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。
4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。
4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。
如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。
如图4.1所示。
s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。
《数据结构、算法与应用(C++语言描述)》习题参考答案doc
第1章概论1.数据、数据元素、数据结构、数据类型的含义分别是什么？数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。
数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。
数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。
数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。
数据类型包含取值范围和基本运算等概念。
2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。
数据的逻辑结构包含下面两个方面的信息：①数据元素的信息；②各数据元素之间的关系。
物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。
数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。
采用不同的存储结构，其数据处理的效率是不同的。
因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。
3.数据结构的主要操作包括哪些？对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有：●创建：建立一个数据结构；●清除：清除一个数据结构；●插入：在数据结构中增加新的结点；●删除：把指定的结点从数据结构中删除；●访问：对数据结构中的结点进行访问；●更新：改变指定结点的值或改变指定的某些结点之间的关系；●查找：在数据结构中查找满足一定条件的结点；●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。
4.什么是抽象数据类型？如何定义抽象数据类型？抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
《数据结构与算法》习题与答案
《数据结构与算法》习题与答案（解答仅供参考）一、名词解释：1. 数据结构：数据结构是计算机存储、组织数据的方式，它不仅包括数据的逻辑结构（如线性结构、树形结构、图状结构等），还包括物理结构（如顺序存储、链式存储等）。
它是算法设计与分析的基础，对程序的效率和功能实现有直接影响。
2. 栈：栈是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out, LIFO）原则。
在栈中，允许进行的操作主要有两种：压栈（Push），将元素添加到栈顶；弹栈（Pop），将栈顶元素移除。
3. 队列：队列是一种先进先出（First In First Out, FIFO）的数据结构，允许在其一端插入元素（称为入队），而在另一端删除元素（称为出队）。
常见的实现方式有顺序队列和循环队列。
4. 二叉排序树（又称二叉查找树）：二叉排序树是一种二叉树，其每个节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
这种特性使得能在O(log n)的时间复杂度内完成搜索、插入和删除操作。
5. 图：图是一种非线性数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象之间的多种关系。
根据边是否有方向，可分为有向图和无向图；根据是否存在环路，又可分为有环图和无环图。
二、填空题：1. 在一个长度为n的顺序表中，插入一个新元素平均需要移动______个元素。
答案：(n/2)2. 哈希表利用______函数来确定元素的存储位置，通过解决哈希冲突以达到快速查找的目的。
答案：哈希（Hash）3. ______是最小生成树的一种算法，采用贪心策略，每次都选择当前未加入生成树且连接两个未连通集合的最小权重边。
答案：Prim算法4. 在深度优先搜索（DFS）过程中，使用______数据结构来记录已经被访问过的顶点，防止重复访问。
答案：栈或标记数组5. 快速排序算法在最坏情况下的时间复杂度为______。
数据结构与算法 经典书籍
数据结构与算法经典书籍1. 《算法导论》《算法导论》是计算机科学领域中经典的教材，由Thomas H. Cormen等人合著。
该书详细介绍了各种常用的数据结构和算法，包括排序、查找、图算法等。
它以清晰的语言和丰富的实例展示了算法的设计和分析方法，对于理解和掌握算法设计与分析的基本原理具有重要意义。
2. 《数据结构与算法分析：C++语言描述》该书由Mark Allen Weiss编写，是一本介绍数据结构和算法的经典教材。
它以C++语言为基础，详细讲解了各种常用的数据结构（如链表、栈、队列、树、图等）和算法（如排序、查找、图算法等），并给出了具体的代码实现。
同时，该书还重点讲解了算法的分析和性能评估，帮助读者理解算法的时间复杂度和空间复杂度。
3. 《算法》《算法》是Sedgewick和Wayne合著的一本数据结构和算法教材。
该书系统地介绍了各种常用的数据结构和算法，并通过大量的示例和习题帮助读者巩固所学知识。
它涵盖了排序、查找、图算法等领域，并提供了Java和C++两种语言实现的代码。
这本书以其简洁明了的风格和深入浅出的讲解方法，深受学生和专业人士的喜爱。
4. 《编程珠玑》《编程珠玑》是Jon Bentley所著的一本经典之作，介绍了一系列有关程序设计和算法的问题及解决方法。
该书通过实际问题的分析和解决过程，展示了一种高效的编程思维方式。
它以具体的案例引入问题，然后通过分析和优化算法，给出了高效的解决方案。
这本书不仅适合程序员和软件工程师，也对于对算法和数据结构感兴趣的读者具有很高的参考价值。
5. 《数据结构与算法分析：Java语言描述》该书由Mark Allen Weiss编写，是一本使用Java语言描述的数据结构和算法教材。
它以清晰的语言和丰富的实例介绍了各种常用的数据结构和算法，并给出了具体的代码实现。
同时，该书还讲解了算法的分析和性能评估，帮助读者理解算法的时间复杂度和空间复杂度。
6. 《剑指Offer：名企面试官精讲典型编程题》《剑指Offer》是一本专注于面试编程题的书籍，该书由左程云所著。
《数据结构与算法》(张晓莉)习题：选择题、判断题
第一章绪论1. 从逻辑上可以把数据结构分为( C ）两大类。
A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2。
在下面的程序段中,对x的赋值语句的频度为（ C ）。
For（k=1;k〈=n；k++)For（j=1；j〈=n；j++）x=x＋1；A．O(2n）B．O(n) C．O(n2) D．O(log2n）3。
采用顺序存储结构表示数据时,相邻的数据元素的存储地址( A )。
A．一定连续B．一定不连续C．不一定连续D．部分连续、部分不连续4。
下面关于算法的说法，正确的是（ D ）.A．算法的时间复杂度一般与算法的空间复杂度成正比B．解决某问题的算法可能有多种,但肯定采用相同的数据结构C．算法的可行性是指算法的指令不能有二义性D．同一个算法，实现语言的级别越高，执行效率就越低5。
在发生非法操作时，算法能够作出适当处理的特性称为（ B ）。
A．正确性B．健壮性C．可读性D．可移植性第二章线性表1。
线性表是( A ).A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列,可以为空D．一个无限序列，不能为空2．对顺序存储的线性表,设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的（ A ）个元素.A．n/2 B．(n＋1)/2 C．（n－1）/2 D．n3．线性表采用链式存储时，其地址( D ）.A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以4．用链表表示线性表的优点是（C）。
A．便于随机存取B．花费的存储空间较顺序存储少C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同5．链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( C ）存储方式最节省运算时间.A．单链表B．双链表C．单循环链表D．带头结点的双向循环链表6．下面关于线性表的叙述，错误的是（ B )。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
InitList (&L)
操作结果：构造一个空的线性表L。
DetroyList (&L)
初始条件：线性表L已经存在。
操作结果：销毁线性表L。
......
} ADTList
ppt课件
第5页
2.1 线性表的基本概念
对线性表的基本操作
1 初始化操作 InitList (&L)
功能：建立空的线性表L；
2 销毁操作 DetroyList (&L)
功能：回收为线性表L动态分配的存储空间；
3 置空操作 ClearList (&L)
功能：L中已存在，重新将其置成空表；
4 判空操作 ListEmpty (L)
功能：判断线性表L是否为空表，若为空表返回
TRUE，否则返回FALSE；
5 求表长操作 ListLength (L)
功能：返回线性表L的表长；
ppt课件
第9页
2.1 线性表的基本概念
利用基本操作进行算法设计
例1：若有两个集合 A 和 B 分别用两个线 性表 LA 和 LB 表示，即：线性表中的数据 元素即为集合中的成员。现要求一个新的集 合：A＝A∪B。
问题分析
上述问题可以演绎为：扩大线性表 LA，将 存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。
10 插入操作 ListInsert ( &L, i, e ) 功能：在线性表L的第i个元素之前插入1个新元素e；
11 删除操作 ListDelete ( &L, i, &e ) 功能：删除线性表L的第i个元素，并用 e 返回；
12 遍历操作 ListTraverse ( &L,visit( ) ) 功能：依次对线性表L的每个元素调用函数visit()。 若visit()失败，则返回 ERROR，否则返回 OK；
线性表是类型相同的元素有限序列，记作： ppt课件 （a1, ..., ai-1, ai, ai+1, …, an） 第 3 页
2.1 线性表的基本概念
设 A=（a1, a2, ... , ai-1, ai , ai+1, …, an）是一线性表 1）线性表的数据元素可以是各种各样的，但同一线性
ppt课件
第 11 页
2.1 线性表的基本概念
利用基本操作进行算法设计
void union ( List &La, List Lb ) { La_len = ListLength (La); // 求线性表的长度 Lb_len = ListLength (Lb); for ( i = 1; i <= Lb_len; i++ ) {
ppt课件
第8页
2.1 线性表的基本概念
说明
1、基本操作是一种数据结构中最常见的操 作，它具有明确的逻辑意义，其处理的结果不 破坏逻辑意义完整性。
2、可以使用基本操作来解决新的问题，设 计新的算法。使我们可以在更高的层次上进行 抽象，在更高的基础上进行设计。
3、在算法的程序实现的过程中，基本操作 需要通过编制公共函数进行具体实现。可以为 基本操作建立公共函数库。
GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if ( ! LocateElem ( La, e, equal( ) ) )
ListInsert ( La, ++La_len, e ); // La中不存在和 e 相同的数据元素，则插入之 }
} // union
每个元素在线性表中的位置，仅取决于它的序号。
6）可在表的任意位置进行插入和删除操作。
ppt课件
第4页
2.1 线性表的基本概念
对线性表的ADT描述
ADT List {
数据对象：
D = { ai | ai ElemSet, i=1,…,n，n≥0 } 数据关系：
R1 = { <ai-1, ai> | ai-1,ai D, i=2, …,n } 基本操作：
ppt课件
第 10 页
2.1 线性表的基本概念
利用基本操作进行算法设计
1．从线性表LB中依次察看每个数据元素； GetElem ( LB, i ) → e
2．依值在线性表LA中进行查访； LocateElem ( LA, e, equal( ) )
3．若不存在，则插入之。 ListInsert ( LA, n+1, e )
表中的元素必须是同一类型的；
2）在表中 ai-1 领先于 ai ，ai 领先于 ai+1，称 ai-1 是 ai 的直接前趋， ai+1 是ai 的直接后继；
3）在线性表中，除第一个元素和最后一个元素之外， 其他元素都有且仅有一个直接前趋，有且仅有为表的长度，n=0时称为空表； 5）ai 是表的第 i 个元素，称 i 为数据元素 ai 的序号，
ppt课件
第2章 线性表
2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 线性表应用实例
ppt课件
第2页
2.1 线性表的基本概念
线性表特点：在数据元素的非空有限集中 ◆ 存在唯一的一个被称作“第一个”的数据元 素 ◆ 存在唯一的一个被称作“最后一个”的数据 元素 ◆ 除第一个外，集合中的每个数据元素均只有 一个前驱 ◆ 除最后一个外，集合中的每个数据元素均只 有一个后继
8 查找前驱 PriorElem ( L, cur_e, &pre_e ) 功能：若 cur_e 是 L 中的数据元素且不是第一个， 则用 pre_e 返回它的前驱，否则失败，pre_e无定 义。
ppt课件
第7页
2.1 线性表的基本概念
9 查找后继 NextElem ( L, cur_e, &next_e ) 功能：若 cur_e 是L中的数据元素且不是最后一个， 则用next_e返回它的后继，否则失败，next_e无定义。
ppt课件
第6页
2.1 线性表的基本概念
6 取元素操作：GetElem ( L, i, &e) 功能：将线性表L中第 i 个元素赋值给 e；
7 查找操作 LocateElem ( L, e, compare() ) 功能：在线性表 L 中查找与元素e 满足compare() 的第 1 个元素，返回该元素在表中的序号（或位 置），若表中不存在这样的元素，则返回 0；