当前位置：文档之家 › 数据结构与算法_ 线性结构_

数据结构与算法_ 线性结构_

  • 格式：pdf
  • 大小：2.39 MB
  • 文档页数：49

下载文档原格式

  / 49

合集下载

罗文劼《数据结构与算法》第4版-第1章课后习题参考答案

罗文劼《数据结构与算法》第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）简述算法和程序的区别。

【解答】一个算法若用程序设计语言来描述，则它就是一个程序。

算法的含义与程序十分相似，但又有区别。

一个程序不一定满足有穷性。

数据结构与算法java版第五版

数据结构与算法java版第五版

数据结构与算法java版第五版一、引言数据结构与算法是计算机科学的基础，是程序员必须掌握的核心知识。

如何高效地使用数据结构和算法解决实际问题，是每个程序员都需要思考和学习的事情。

本文将介绍《数据结构与算法java版第五版》这本书的内容，从数据结构和算法的基础知识到高级应用进行探讨。

二、基础知识1. 数据结构的概念及分类•线性结构•树形结构•图形结构2. 算法的概念及分类•基本概念•算法的复杂度分析3. Java基础•Java基本语法•面向对象编程•集合框架三、线性结构1. 数组•数组的定义和使用•数组的常见操作•数组的应用场景2. 链表•链表的定义和基本操作•单向链表和双向链表的区别•链表的应用场景3. 栈和队列•栈的定义和基本操作•队列的定义和基本操作•栈和队列的应用场景4. 哈希表•哈希表的原理和实现•哈希函数的选择•哈希表的应用场景四、树形结构1. 二叉树•二叉树的定义和基本操作•二叉树的常用遍历算法•二叉树的应用场景2. AVL树•AVL树的定义和性质•AVL树的插入和删除操作•AVL树的应用场景3. 红黑树•红黑树的定义和性质•红黑树的插入和删除操作•红黑树的应用场景4. B树和B+树•B树和B+树的定义和性质•B树和B+树的插入和删除操作•B树和B+树的应用场景五、图形结构1. 图的表示和基本操作•图的表示方法•图的遍历算法•图的最短路径算法2. 拓扑排序•拓扑排序的原理和算法•拓扑排序的应用场景3. 最小生成树•最小生成树的定义和算法•最小生成树的应用场景4. 图的搜索•图的深度优先搜索•图的广度优先搜索•图的搜索算法的应用场景六、高级应用1. 排序算法•冒泡排序•插入排序•选择排序•快速排序•归并排序2. 查找算法•顺序查找•二分查找•哈希查找•插值查找3. 动态规划•动态规划的基本概念•动态规划的应用场景•动态规划问题的解决步骤七、总结《数据结构与算法java版第五版》是一本全面介绍数据结构和算法的书籍，从基础知识到高级应用等多个方面进行了深入的探讨。

计算机科学第5章 数据结构与算法

计算机科学第5章 数据结构与算法
开始 开始 开始 处理步骤1 处理步骤1 处理步骤1
处理步骤2
符合条件
分支条件 不符合条件 符合条件 进入循环
循环条件 不符合条件 循环结束
„
分支1
分支2
循环体
处理步骤N
处理步骤N
处理步骤N
结束
(a)顺序结构
结束
(b)分支结构
结束
(c)循环结构
图 5-3 算法基本结构示意图
5.1 数据结构概述
5.1.2 算法
在大多数情况下，时间和空间因素可以进行相应转换，具体选择时可根
据实际需要和成本因素确定选择什么策略。 另外，需要提醒一点，不是时间复杂度高，算法的数学复杂程序就高。
使用更高级的数学方法，能够以更少的时间和空间代价获取处理结果。
这时，用于算法执行的时间虽然少了，但是用于算法设计的时间会大大 增加。如果设计出的程序有足够多的使用率，代价总体上是值得的。
5.1 数据结构概述
5.1.2 算法
用计算机解决一个复杂的实际问题，大体需要如下的步骤。 （1）将实际问题数学化，即把实际问题抽象为一个带有一般性的数学 问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的 已知条件、所要求的结果、以及在已知条件和所要求的结果之间存在着 的隐式或显式的联系。 （2）对于确定的数学问题，设计其求解的方法，即所谓的算法设计。 这一步要建立问题的求解模型，即确定问题的数据模型并在此模型上定 义一组运算，然后借助于对这组运算的调用和控制，从已知数据出发导 向所要求的结果，形成算法并用自然语言来表述。这种语言还不是程序 设计语言，不能被计算机所接受。 （3）用计算机上的一种程序设计语言来表达已设计好的算法。换句话 说，将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。 这一步叫程序设计或程序编制。 （4）在计算机上编辑、调试和测试编制好的程序，直到输出所要求的 结果。

大学计算机科学知识点归纳

大学计算机科学知识点归纳

大学计算机科学知识点归纳1. 计算机科学基础1.1 计算机组成原理- 计算机硬件：CPU、内存、I/O设备、存储器等- 计算机指令：机器指令、汇编指令、高级指令等- 计算机体系结构：冯诺依曼结构、哈佛结构等1.2 数据结构与算法- 线性结构：数组、链表、栈、队列、串等- 非线性结构：树、图、哈希表等- 算法：排序算法、查找算法、图算法等1.3 计算机网络- 网络结构：OSI七层模型、TCP/IP四层模型等- 网络设备：交换机、路由器、网关等1.4 操作系统- 进程管理：进程、线程、进程调度、死锁等- 内存管理：内存分配、回收、虚拟内存等- 文件系统：文件、目录、文件系统结构等- 设备管理：设备驱动、I/O调度等2. 编程语言与编译原理2.1 编程语言- 高级语言：C、C++、Java、Python等- 低级语言：汇编、机器码等2.2 编译原理- 词法分析：词法单元、词法分析器等- 语法分析：语法规则、语法分析树、分析算法等- 中间代码生成与优化：三地址码、SSA等- 目标代码生成：汇编代码、机器代码等3. 软件工程- 软件开发过程：需求分析、设计、编码、测试、维护等- 软件设计模式：面向对象设计模式、架构模式等- 软件项目管理：项目计划、进度控制、风险管理等- 软件质量保证：代码审查、测试策略等4. 数据库系统- 数据库概念：数据模型、实体-关系模型、关系模型等- 数据库设计：范式、E-R图、SQL等- 数据库查询：SQL查询、视图、索引等- 数据库事务：ACID属性、并发控制、故障恢复等5. 人工智能与机器- 人工智能基础：知识表示、推理、搜索算法等- 机器算法：线性回归、决策树、神经网络等- 自然语言处理：分词、词性标注、命名实体识别等- 计算机视觉：图像处理、目标检测、人脸识别等6. 计算机科学其他领域- 并行与分布式系统：进程并发、分布式算法、云计算等- 网络安全：加密算法、防火墙、入侵检测等- 物联网：传感器、嵌入式系统、物联网协议等- 人机交互：用户界面设计、交互技术、虚拟现实等以上是对大学计算机科学知识点的简要归纳，希望对您有所帮助。

数据结构与算法基础知识总结

数据结构与算法基础知识总结

数据结构与算法基础知识总结1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

3 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

北京林业大学《数据结构与算法》课件PPT 第2章 线性表

北京林业大学《数据结构与算法》课件PPT 第2章 线性表

线性表P = (p0,p1,p2,…,pn)
P(x) = 10 + 5x - 4x2 + 3x3 + 2x4
指数 （下标i）
0
1
2
3
系数p[i] 10
5
-4
3
数组表示
（每一项的指数i隐含 在其系数pi的序号中）
4
2
北京林业大学信息学院
Rn(x) = Pn(x) + Qm(x)
线性表R = (p0 + q0,p1 + q1,p2 + q2,…,pm + qm,pm+1,…,pn)
数，即表长
例1 分析26 个英文字母组成的英文表
（ A, B, C, D, …… , Z） 数据元素都是字母; 元素间关系是线性 例2 分析学生情况登记表
学号
041810205 041810260 041810284 041810360
：
姓名
于春梅 何仕鹏 王爽 王亚武
：
性别
女 男 女 男 ：
年龄
下标i 0
1
2
系数 b[i]
8
22 -9
指数 1
7
8
线性表P =((p1, e1), (p2, e2),…,(pm, em))
创建一个新数组c 分别从头遍历比较a和b的每一项
✓指数相同，对应系数相加，若其和不为零，则在c中增加一个新项 ✓指数不相同，则将指数较小的项复制到c中 一北个京多林项业大式学已信遍息历学完院毕时，将另一个剩余项依次复制到c中即可
线性表
北京林业大学信息学院
第2章 线性表
教学目标
1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、创建、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种存储结

数据结构与算法的联系与区别

数据结构与算法的联系与区别数据结构与算法的联系与区别一、数据结构的概念数据结构是指数据对象中元素之间的关系，以及数据元素本身的特点。

它是计算机组织和存储数据的一种方式，直接影响到算法的设计和性能。

1.1 线性数据结构线性数据结构是数据元素之间存在一对一的关系，例如：数组、链表、栈和队列等。

这些数据结构在存储和访问数据时具有一定的规律性。

1.2 非线性数据结构非线性数据结构是数据元素之间存在一对多或多对多的关系，例如：树和图等。

这些数据结构的存储和访问方式相对复杂，需要特殊的算法来处理。

二、算法的概念算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列。

算法通过操作数据结构来实现对数据的操作，并得到预期的结果。

2.1 算法的特性算法具有以下特性：●输入：算法具有输入，可以是零个或多个输入。

●输出：算法至少有一个输出。

●有穷性：算法在有限的步骤内必须终止。

●确定性：算法中每一步的执行必须具有唯一确定的效果。

●可行性：算法的每一步都必须是可行的，即能够通过执行有限次数完成。

三、数据结构与算法的联系数据结构和算法紧密相关，它们互为补充，相互依赖。

3.1 数据结构对算法的影响不同的数据结构适用于不同种类的问题和算法。

选择合适的数据结构能够有效地提高算法的效率。

3.2 算法对数据结构的选择算法的设计基于特定的问题和已有的数据结构。

在算法设计过程中，根据问题的特点选择合适的数据结构是至关重要的。

四、数据结构与算法的区别数据结构和算法虽然有联系，但也存在一些明显的区别。

4.1 抽象层次不同数据结构是对数据的组织和存储方式的抽象，而算法是对解决问题的步骤和过程的抽象。

4.2 解决问题的角度不同数据结构关注如何组织和存储数据，而算法关注如何通过操作数据得出结果。

4.3 面向不同的目标数据结构的目标是提供高效的存储和访问数据的方式，而算法的目标是寻求有效的解决问题的方法。

附件：本文档未涉及任何附件。

法律名词及注释：无。

数据结构与算法

数据结构与算法第一节数据结构及算法概述一、数据结构图、四类基本结构的示意图【要点】 1 .数据元素是数据的基本单位。

2 .数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

3 .4类基本的规律结构:集合、线性结构、树形结构和网状结构。

4 .4种数据存储方式：挨次、链式、索引和散列。

【例题•单选题】(2022年义省信用社聘请考试真题)下列说法不正确的是()OA.数据元素是数据的基本单位B.数据项是数据中不行分割的最小标志单位 C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成『正确答案』D『答案解析』数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进 行考虑和处理。

一个数据元素可由若干个数据项组成。

数据项是不行分割的、含有独立 意义的最小数据单位。

因此D 选项不正确。

二、算法O ——O ——O ——O ——O ⑹树型结构⑹线性结构 (d)图形结构算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

算法的特性：有穷性、确定性、可行性、输入和输出。

【要点】评价算法优劣标准：正确性、可读性、健壮性、高效率与低存储量需求。

其次节线性表线性表是n (n≥0)个数据元素al, a2,…，an组成的有限序列,n=0时称为空表。

非空的线性表，有以下特征：L有且仅有一个开头结点al,没有直接前趋，有且仅有一个直接后继a2。

2.有且仅有一个终结结点an,没有直接后继，有且仅有一个直接前趋a-。

3.其余的内部结点ai (2WiWnT)都有且仅有一个直接前趋a-和一个直接后继3i+ι o线性表的链式存储包括单链表、循环链表和双链表。

head 头结点百结点尾结点【留意】与单链表的插入和删除操作不同的是，在双链表中插入和删除须同时修改两个方向上的指针。

第三节栈和队列一、栈栈是一种“特别的”线性表，这种线性表中的插入和删除运算限定在表的某一端进行。

不含任何数据元素的栈称为空栈。

23秋国家开放大学数据结构与算法形考任务1-2参考答案

国家开放大学《数据结构与算法》形考任务1-2参考答案《数据结构与算法》是“数据科学与大数据技术”专业（本科）的一门统设必修课。

课程编号：04692形考任务1一、单项选择题1.下面说法错误的是（）。

A.数据结构是指互相之间存在着一种或多种关系的数据元素的集合B.数据(Data)是指客观事物的符号表示C.数据元素是表示数据的不可分割的最小标识单位D.数据的基本单位是数据元素2.数据结构中的线性结构是指（）。

A.数据元素之间属于同一个集合B.数据元素之间存在着一对一的线性关系C.数据元素之间存在着一对多的线性关系D.数据元素之间存在着多对多的线性关系3.下列有关递归的说法错误的是（）。

A.递归需要有边界条件、递归方程两部分构成。

B.递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算。

C.递归通常把一个复杂问题层层转化为一个与原问题相似的规模较小的问题来求解。

D.只有在函数中直接调用自身才能叫做递归函数。

4.根据数据元素之间关系的不同，数据结构分为（）。

A.物理结构，逻辑结构B.集合结构，线性结构，树结构，图结构C.顺序结构，链表结构D.递归结构，普通结构5.栈S最多能容纳4个元素。

现有6个元素按A、B、C、D、E、F的顺序进栈，下列（）序列是可能的出栈序列。

A.E、D、C、B、A、FB.B、C、E、F、A、DC.B、D、C、F、E、AD.A、D、F、E、B、C6.顺序循环队列容量为50，队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为31，队尾为8的时候，队列中共有（）个元素。

A.25B.26C.27D.287.对线性表，在下列（）情况下应当采用链表表示。

A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变8.若用一个大小为8的数组来实现循环队列，且当tail和head的值分别为6，0。

当从队列中删除两个元素，再加入一个元素后，tail和head的值分别为（）。

算法和数据结构的关系

算法和数据结构的关系算法和数据结构是计算机科学中最基本的两个概念，它们的关系密不可分。

算法是解决问题的方法，数据结构是数据的组织形式。

算法和数据结构的设计和选择直接关系到程序的效率和质量。

算法和数据结构的关系算法和数据结构是密切相关的，它们相互依存，彼此支持。

算法是基于数据结构的，数据结构是算法的基础。

算法需要数据结构来存储和处理数据，而数据结构则提供了算法所需要的数据操作接口。

因此，算法和数据结构是相互依存，彼此支持的关系。

在程序设计中，算法的效率和质量直接受到数据结构的影响。

数据结构的选择和设计对算法的效率和质量有着重要的影响。

因此，算法和数据结构的设计和选择是程序设计中最基本的问题之一。

数据结构的种类数据结构是计算机科学中的重要概念，它是指数据元素之间的关系以及数据元素的组织形式。

数据结构分为线性结构和非线性结构两种。

线性结构是指数据元素之间的关系是一对一的关系，其中包括线性表、栈、队列、串等。

线性表是最基本的数据结构，它是一种有序的数据元素集合。

栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作。

队列也是一种特殊的线性表，它只允许在表的一端进行插入操作，在另一端进行删除操作。

串是由零个或多个字符组成的有限序列，它是一种特殊的线性表。

非线性结构是指数据元素之间的关系不是一对一的关系，其中包括树、图等。

树是一种非线性结构，它由若干个节点组成，节点之间的关系是一对多的关系。

图是一种非线性结构，它由若干个节点和连接这些节点的边组成，节点之间的关系是多对多的关系。

算法的设计与实现算法的设计与实现是程序设计中最基本的问题之一。

算法的设计需要考虑到问题的特点、数据结构的选择和算法的效率等因素。

算法的实现需要考虑到语言的特点、程序的可读性、可维护性和可扩展性等因素。

算法的设计过程包括问题分析、算法设计、算法评估和算法改进等步骤。

问题分析是指对问题进行深入的分析和理解，找出问题的本质和特点。

算法设计是指根据问题的特点和数据结构的选择，设计出符合要求的算法。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

L->elem[k-1]=L->elem[k];
L->length--;
/*顺序表长度减1*/
return 1;
}
删除元素算法时间复杂度分析
for(k=i;k<L->length;k++) /*元素前移*/
L->elem[k-1]=L->elem[k]; v 分析：移动元素操作次数和删除元素位置i的关系
v 分析：移动元素操作次数和插入元素位置i的关系 i=L.length+1时，执行次数= 0 i=1时，执行次数= n 执行次数=（n-i+1)
v 在长度为n的顺序表表中插入一个元素的平均移动次数
n1
Eis pi (n i 1) i 1
假定在线性表任何位置上插入元素是等概率的
pi = 1/(n + 1)
顺序表常用算法
int LocateElem_Sq(SqList L,ElemType e, int (*compare)(ElemType,ElemType) )
{
for(i=0;i<L.length;i++)
{
if( (*compare)(L.elem[i],e) )
break;
}
if(i>=L.length) return 0; //未找到满足指定关系的元素
/*置初始空间容量*/
return 1;
/*初始化成功，返回1*/
}
顺序表常用算法
要求：在第i个元素之前插入一个新元素e
a1 a2 ... ai-1 ai ... an
插入后 a1 a2 ... ai-1 e
ai
... an
思考：如何实现？
a1 a2 ... ai-1 aei
... an
注意：C语言中数组的下标由0开①始，而线性表中②数据元素的位 序由1开始，因此an对应的数组元素下标为length-1，而ai对应 的数组元素下标为i-1。
else return i+1;
//找到满足指定关系的元素，返回其位序
}
复习回顾——线性链表的存储表示
typedef struct LNode{ ElemType data; //结点的数据域 struct LNode *next; //结点的指针域
}LNode, *LinkList;
线性链表基本运算的实现
线性表的顺序表示与实现
线性表的顺序存储实现
特点：动态分配顺序表的大小。源自a1 a2 ... ai ... an
L.length
#define LIST_INIT_SIZE 50 #define LISTINCREMEMT 10
L.listsize
typedef struct { ElemType *elem; int length; int listsize;
i=L.length时，执行次数= 0 i=1时，执行次数= n-1 执行次数=（n-i)
v 在长度为n的顺序表表中删除一个元素的平均移动次数
n
Edl qi (n i) i 1
假定在线性表任何位置上删除元素是等概率的
qi = 1/n
Edl
1 n
n i 1
(n
i)
n1 2
删除算法的时间复杂度为 O(n)
LIST_INIT_SIZE*sizeof(ElemType));
if②(!L如->e果lem分)配re空tu间rn失0;败，退出/*初函始数化失败*/
L③->le空ng间th分=0配; 成功，设置顺序/*置表空L的表l长i度st为si0*z/e数据域和
L->lilsetsnizget=Lh数IST据_域IN的IT值_SIZE;
Eis
1 n1
n1
(n i
i 1
1)
n 2
插入算法的时间复杂度为 O(n)
顺序表常用算法
删除后
要求：删除顺序表中第i个位置的元素。
a1 a2 ... ai ai+1 ... an
a1 a2 ... ai+1 ... an
思考：如何实现？
a1
a2
...
ai ai+1
... an
e=ai
顺序表常用算法
L->elem[k+1]= L->elem[k];
L->elem[i-1]= e;
/*插入元素*/
L->length++;
/*顺序表长度加1*/
return 1;
}
插入元素算法时间复杂度分析
for(k=L->length-1;k>=i-1;k--) /*元素后移*/ L->elem[k+1]= L->elem[k];
LISTINCREMENT)*sizeof(ElemType));
if(!newbase) return 0; /*存储分配失败*/
L->elem=newbase;
L->listsize+=LISTINCREMENT; /*修改存储空间大小*/
}
for(k=L->length-1;k>=i-1;k--) /*元素后移*/
}SqList;
/*存储空间的基地址*/ /*顺序表的当前长度*/ /*当前分配的存储空间*/
顺序表常用算法
顺序表常用算法
LIST_INIT_SIZE
length
listsize
顺序表常用算法
int InitList_sq(SqList *L) {
L①->e为lem顺=序(E表lemLT分yp配e 一*)m个a预llo定c(义大小的一段连续单元
访问线性链表 void ListTraverse_L(LinkList L, void (*visit)(ElemType))
线性链表的读取 int GetElem_L(LinkList L, int i, ElemType *e)
线性链表元素的插入 int ListInsert_L(LinkList L, int i, ElemType e)
int ListDelete_sq(SqList *L,int i,ElemType *e){
int k;
/*删除位置不合法*/
if(i<1||i>L->length) return 0;
*e=L->elem[i-1]; /*取出欲删除元素*/
for(k=i;k<L->length;k++) /*元素前移*/
顺序表常用算法
int ListInsert_sq(SqList *L,int i,ElemType e){
if(i<1 || i>L.length+1) return 0;
/*位置合法性判断*/
if(L->length>=L->listsize){
/*空间满，重新分配*/
ElemType *newbase=(ElemType*)realloc(L->elem,(L->Listsize+