当前位置：文档之家 › 第二章 线性表和数组

第二章 线性表和数组

  • 格式：ppt
  • 大小：842.50 KB
  • 文档页数：79

下载文档原格式

  / 79

合集下载

数据结构第二章课后答案

数据结构第二章课后答案

数据结构第二章课后答案数据结构第二章课后答案1. 线性表1.1 数组实现线性表Q1. 请说明线性表的定义，并结合数组实现线性表的特点进行解释。

线性表是由n(n≥0)个数据元素构成的有序序列，其中n表示线性表的长度。

数组实现线性表的特点是使用一组具有相同数据类型的连续存储空间存储线性表中的元素，通过下标访问和操作元素。

A1. 线性表的定义指出，线性表是由若干个数据元素组成的有序序列。

具体地，在数组实现线性表中，我们将元素存储在一组连续的内存空间中，通过下标访问和操作元素。

由于数组的存储空间具有连续性，这样的实现方式可以在O(1)的时间复杂度下进行元素的访问和修改操作。

1.2 链表实现线性表Q2. 请说明链表实现线性表的特点，并与数组实现进行比较。

链表实现线性表的特点是通过指针将线性表中的元素按照节点的形式连接起来，每个节点包含了存储的元素和指向下一个节点的指针。

与数组实现相比，链表的插入和删除操作更为高效，但是访问某个位置的元素需要从头开始遍历，时间复杂度较大。

A2. 链表实现线性表的特点是通过使用节点和指针将线性表中的元素连接起来。

每个节点中包含了一个存储的元素和指向下一个节点的指针。

链表的插入和删除操作的时间复杂度为O(1)，因为只需要改变指针的指向即可。

但是，访问某个位置的元素需要从头开始遍历链表，所以时间复杂度为O(n)。

2. 栈和队列2.1 栈的定义和基本操作Q3. 请给出栈的定义和基本操作。

栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作，该端称为栈顶。

栈的基本操作包括入栈(push)和出栈(pop)，分别用于将元素压入栈和将栈顶元素弹出。

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

这个特定的一端称为栈顶，而另一端称为栈底。

栈的基本操作包括入栈(push)和出栈(pop)。

入栈操作将一个元素压入栈顶，出栈操作将栈顶元素弹出。

2.2 队列的定义和基本操作Q4. 请给出队列的定义和基本操作。

数据结构各章概要

数据结构各章概要

数据结构各章概要数据结构是计算机科学中非常重要的一个学科，其主要研究各种数据的组织方式和操作方法。

善于运用合适的数据结构可以提高算法的效率，并优化程序的性能。

本文将对数据结构的各个章节进行概要介绍，帮助读者了解不同章节的主要内容和应用。

第一章：引论在引论章节，我们将引入数据结构的基本概念和术语，例如什么是数据、数据项、数据对象等等。

同时，还将介绍数据结构的分类和基本操作，如搜索、遍历、插入、删除和排序。

这些基础知识是后续章节的基础。

第二章：线性表线性表是数据结构中最简单、最基本的一种结构。

其特点是数据元素之间的前驱和后继关系非常明确。

线性表可以用数组和链表两种方式实现。

在本章节中，我们将分别介绍顺序表和链表的实现原理、插入、删除、合并以及应用场景。

第三章：栈和队列栈和队列是两种特殊的线性表结构，它们对数据的访问具有限制性。

栈具有“先进后出”的特点，而队列则具有“先进先出”的特点。

在本章节中，我们将介绍栈和队列的实现方式以及常见的应用场景，如递归、表达式求值、广度优先搜索等。

第四章：串串是由零个或多个字符组成的有限序列，其长度可以为零。

在本章节中，我们将介绍串的定义和操作，包括字符串的模式匹配、模式识别和编辑操作。

串的相关算法在文本处理、计算机网络等领域具有广泛的应用。

第五章：数组和广义表数组是一种在内存中以连续方式存储的数据结构，它具有高效的随机访问特性。

广义表是线性表的一种扩展，可以包含表结构、原子结构以及其他广义表。

本章节将介绍数组和广义表的定义、操作和应用。

第六章：树树是一种非线性的数据结构，具有分层次、递归和层次遍历等特点。

在本章节中，我们将介绍树的基本概念、二叉树、树的遍历算法、平衡树以及树的应用，如编译器中的语法树、文件系统的目录结构等。

第七章：图图是一种复杂的非线性数据结构，由顶点集合和边集合组成。

在本章节中，我们将介绍图的各种表示方式，图的遍历算法、最短路径算法以及常用的图算法，如最小生成树算法和拓扑排序。

《数据结构》课后习题答案(第2版)

《数据结构》课后习题答案(第2版)

《数据结构》课后习题答案(第2版)数据结构课后习题答案（第2版）第一章：基本概念1. 什么是数据结构？数据结构是指数据元素之间的关系，以及相应的操作。

它研究如何组织、存储和管理数据，以及如何进行高效的数据操作。

2. 数据结构的分类有哪些？数据结构可以分为线性结构和非线性结构。

线性结构包括数组、链表、栈和队列；非线性结构包括树和图。

3. 什么是算法？算法是解决特定问题的一系列有序步骤。

它描述了如何输入数据、处理数据，并产生期望的输出结果。

4. 算法的特性有哪些？算法具有确定性、有限性、输入、输出和可行性这五个特性。

5. 数据结构和算法之间的关系是什么？数据结构是算法的基础，算法操作的对象是数据结构。

第二章：线性表1. 顺序表的两种实现方式是什么？顺序表可以通过静态分配或动态分配的方式实现。

静态分配使用数组，动态分配使用指针和动态内存分配。

2. 单链表的特点是什么？单链表由节点组成，每个节点包含数据和一个指向下一个节点的指针。

它的插入和删除操作效率高，但是查找效率较低。

3. 循环链表和双向链表分别是什么？循环链表是一种特殊的单链表，在尾节点的指针指向头节点。

双向链表每个节点都有一个指向前一个节点和后一个节点的指针。

4. 链表和顺序表的区别是什么？链表的插入和删除操作效率更高，但是查找操作效率较低；顺序表的插入和删除操作效率较低，但是查找操作效率较高。

第三章：栈和队列1. 栈是什么？栈是一种特殊的线性表，只能在表的一端进行插入和删除操作。

后进先出（LIFO）是栈的特点。

2. 队列是什么？队列是一种特殊的线性表，只能在表的一端进行插入操作，在另一端进行删除操作。

先进先出（FIFO）是队列的特点。

3. 栈和队列的应用有哪些？栈和队列在计算机科学中有广泛的应用，例如浏览器的前进后退功能使用了栈，操作系统的进程调度使用了队列。

4. 栈和队列有哪些实现方式？栈和队列可以使用数组或链表来实现，还有更为复杂的如双端队列和优先队列。

实用数据结构电子教案第二章 数组与线性表

实用数据结构电子教案第二章 数组与线性表
当i=n时，则循环一次也不执行，只是将 元素数目n比原来减少一个，而第n个数 据元素不必再考虑，其余的各单元的元 素均维持不变，这是最好的情况。
第二章 数组与线性表
3. 算法的时间复杂性
可以用数据元素的移动次数来度量这两个算 法的时间复杂性。
插入时，最少循环0次，最多循环n次，如i 的各种取值概率相同，则平均循环次数为 n/2；
else {
x=ST[top]; top=top-1; /*栈顶位置下移*/ } }
第二章 数组与线性表
2.3.2 堆栈的应用
1. 堆栈在函数调
A1
用中的应用:
设有三个函数A1，
A2
A2，A3，这三个 r
函数有如下的调 用关系：函数A1
在其函数体的某
A3 t
处r调用函数A2，
函数A2又在其函
数体某处t调用函
计算机处理表达式时，常把运算符放在两个 运算数的后面或前面。
1. 把运算符放在两个运算数的后面，例如 AB+ ， 称为后缀形式，也叫做波兰式 。
2. 把运算符放在两个运算数的前面，例如 +AB， 则称做前缀形式，也叫做逆波兰表达式。
第二章 数组与线性表
算术表达式的不同运算符有不同的运算优先 顺序，如，在没有括号时，乘除运算（*或/） 要比加减运算（+或-）优先进行。
数据结构数据结构第二章数组与线性表第二章数组与线性表第第二数组与线性表数组与线性表数组的基本特点及寻址方式线性数据结构的基本特征和基本运算堆栈的定义和基本运算队列的定义和基本运算循环队列的特征运算以及判断溢出的条件与普通队列的差别堆栈队列的简单应用循环队列的特点及判断溢出的条件利用本章的基本知识设计有效的算法解决与线性相关的应用问题第二章数组与线性表熟练掌握以下内容

数据结构第二章：线性表

数据结构第二章：线性表
实现逻辑上相邻—物理地址相邻 实现逻辑上相邻— 实现随机存取 实现随机存取
实现：可用C 实现：可用C语言的一维数组实现
6
V数组下标 0 1
内存 a1 a2
元素序号 1 2
typedef int DATATYPE; #define M 1000 DATATYPE data[M]; 例 typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }DATATYPE; DATATYPE library[M];
4
{加工型操作 加工型操作} 加工型操作
ClearList( &L ) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 PutElem( &L, i, &e ) 初始条件：线性表L已存在，1≤i≤LengthList(L)。 操作结果：L 中第 i 个元素赋值同 e 的值 ListInsert( &L, i, e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。 操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。 ListDelete( &L, i, &e ) 初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。 操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。 }ADT LIST
3
PriorElem( PriorElem L, cur_e, &pre_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回 它的前驱，否则操作失败，pre_e 无定义。 NextElem( NextElem L, cur_e, &next_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返 回它的后继，否则操作失败，next_e 无定义。 GetElem( GetElem L, i, &e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)。 操作结果：用 e 返回 L 中第 i 个元素的值。 LocateElem( LocateElem L, e, compare( ) ) 初始条件：线性表 L 已存在，compare( ) 是元素判定函数。 操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元 素的位序。若这样的元素不存在，则返回值为0。 ListTraverse(L, visit( )) ListTraverse 初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。 操作结果：依次对 L 的每个元素调用函数 visit( )。 一旦 visit( ) 失败，则操作失败。

《数据结构与算法(C++语言版)》第2章 线性表

《数据结构与算法(C++语言版)》第2章 线性表
• 以下是一个使用类LinearList的C++程序，它假定之前的程 序均存储在LinearList.h之中，且异常类定义位于文件 exception.h之中。该示例完成以下操作：创建一个大小为5 的整数线性表L；输出该表的长度（为0）；在第0个元素之 后插入2；在第一个元素之后插入6和8（至此，线性表为2， 6，8）；寻找并输出第一个元素（为2）；输出当前表的长 度（为3）；删除并输出第一个元素。
数据结构与算法 （C++语言版）
第2章 线性表
线性表的类型定义
• 基本概念 • 线性表是由n（n≥0）个类型相同的数据元素组成的有限序 列，通常表示为L=(a1, …, ai–1, ai, ai+1, …, an)。其中，L为线 性表名称，ai为组成该线性表的数据元素，ai–1领先于ai，ai 领先于ai+1，称ai–1是ai的直接前驱元素，ai+1是ai的直接后继 元素。当i=1, 2, …, n–1时，ai有且仅有一个直接后继；当 i=2, 3, …, n时，ai有且仅有一个直接前驱。 • 线性表的长度就是线性表中元素的个数n（n≥0）。当n=0时， 称为空表。在非空表中的每个数据元素都有一个确定的位 置，如a1是第一个数据元素，an是最后一个数据元素，ai是 第i个数据元素。称i为数据元素ai在线性表中的位序。
线性表的类型定义
Prev_Elem(L, cur_e, &pre_e) //返回当前元素的前一个元素值 输入：线性表L。 输出：若cur_e是线性表L的数据元素，且不是第一个，则用 pre_e返回它的直接前驱元 素；否则操作失败，pre_e无定义。 Next_Elem(L, cur_e, &next_e) //返回当前元素的后一个元素值 输入：线性表L。 输出：若cur_e是线性表L的数据元素，且不是最后一个，则用 next_e返回它的直接后继元素；否则操作失败，next_e无定 义。

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)【第一章绪论】1. 数据结构是计算机科学中的重要基础知识，它研究的是如何组织和存储数据，以及如何通过高效的算法进行数据的操作和处理。

本章主要介绍了数据结构的基本概念和发展历程。

【第二章线性表】1. 线性表是由一组数据元素组成的数据结构，它的特点是元素之间存在着一对一的线性关系。

本章主要介绍了线性表的顺序存储结构和链式存储结构，以及它们的操作和应用。

【第三章栈与队列】1. 栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作。

本章主要介绍了栈的顺序存储结构和链式存储结构，以及栈的应用场景。

2. 队列也是一种特殊的线性表，它的特点是只能在表的一端进行插入操作，而在另一端进行删除操作。

本章主要介绍了队列的顺序存储结构和链式存储结构，以及队列的应用场景。

【第四章串】1. 串是由零个或多个字符组成的有限序列，它是一种线性表的特例。

本章主要介绍了串的存储结构和基本操作，以及串的模式匹配算法。

【第五章数组与广义表】1. 数组是一种线性表的顺序存储结构，它的特点是所有元素都具有相同数据类型。

本章主要介绍了一维数组和多维数组的存储结构和基本操作，以及广义表的概念和表示方法。

【第六章树与二叉树】1. 树是一种非线性的数据结构，它的特点是一个节点可以有多个子节点。

本章主要介绍了树的基本概念和属性，以及树的存储结构和遍历算法。

2. 二叉树是一种特殊的树，它的每个节点最多只有两个子节点。

本章主要介绍了二叉树的存储结构和遍历算法，以及一些特殊的二叉树。

【第七章图】1. 图是一种非线性的数据结构，它由顶点集合和边集合组成。

本章主要介绍了图的基本概念和属性，以及图的存储结构和遍历算法。

【总结】1. 数据结构是计算机科学中非常重要的一门基础课程，它关注的是如何高效地组织和存储数据，以及如何通过算法进行数据的操作和处理。

本文对《数据结构》第二版严蔚敏的课后习题作业提供了参考答案，涵盖了第1-7章的内容。

第2-5章 线性结构

第二章线性表2-1 设有一个线性表（e0, e1, …, e n-2, e n-1）存放在一个一维数组A[arraySize]中的前n个数组元素位置。

请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为（e n-1, e n-2, …, e1, e0）。

2-2 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]（10）存放在什么位置？脚注（10）表示用10进（10）制表示。

2-3 设有一个n n的对称矩阵A，如图（a）所示。

为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。

前者称为上三角矩阵，后者称为下三角矩阵。

我们把它们按行存放于一个一维数组B中，如图（b）和图（c）所示。

并称之为对称矩阵A的压缩存储方式。

试问：(1) 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素a ij在只存上三角部分的情形下（图(b)）应存于一维数组的什么下标位置？给出计算公式。

(3) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素a ij在只存下三角部分的情形下（图(c)）应存于一维数组的什么下标位置？给出计算公式。

2-4 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。

用适当的测试数据来验证这个算法。

2-5 利用顺序表的操作，实现以下的函数。

(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。

空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

(3) 向顺序表中第i个位置插入一个新的元素x。

如果i不合理则显示出错信息并退出运行。

(8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

2-6 字符串的替换操作replace ( String& s, String& t, String& v) 是指：若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。

《数据结构》课程课件第二章线性表


Step2：数据域赋值
插入后： Step3：插入（连接）
X q
(1)式和(2)式的顺序颠倒，可以吗？
4、插入元素（在第i个元素之前插入元素e）
为什么时间复杂度不再是O(1)？
第i－1个元素
第i个元素
p
s
新插入元素
5、删除p所指元素的后继元素
P
删除前：
P->next P->next->next
删除：
五、线性表ADT的应用举例
Void mergelist(list La，list Lb,list &Lc)
{ //已知线性表La和Lb中的数据元素按值非递减排列
//归并La和Lb得到新的线性表Lc，Lc中的元素也按值非递减排列
例: 将两个各有n个元素的有序表归并成一个有序表， 其最小的比较次数是（ ）。 A、n B、2n-1 C、2n D、n-1
三、线性表的ADT
四、线性表的分类
五、线性表ADT的应用举例
例1：已知有线性表L，要求删除所有X的出现
五、线性表ADT的应用举例
例2: 已知有两个分别有序的线性表（从小到大），要 求合并两个线性表，且合并后仍然有序。——归并 方法1: 合并，再排序O((m+n)2)
方法2： 归并，利用分别有序的特点O((m+n))
二、线性表上常见的运算
8、删除 Delete(L,i):删除线性表的第i个元素 删除前 a1 a2 … ai-1 ai ai+1 … an 删除后 a1 a2 … ai-1 ai+1 … an 9、判断是否为空 Empty(L):线性表空,则返回TRUE, 否则FALSE 10、输出线性表 Print(L):输出线性表的各个元素 11、其它操作 复制、分解、合并、分类等

第2章 线性表


【例2】巳知有两个按元素值递增有序的顺序表La和 Lb，设计一个算法将表La和表Lb的全部元素归并 为一个按元素值递增有序的顺序表Lc。

算法思路：用i扫描顺序表La，用j扫描顺序表Lb。 当表La和表Lb都未扫描完时，比较两者的当前元 素，将较小者插入表Lc的表尾，若两者的当前元 素相等，则将这两个元素依次插入表Lc的表尾。 最后，将尚为扫描完的顺序表的余下部分元素依 次插入表Lc的表尾。算法如下： void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)

表中ai-1领先于ai，称ai-1是ai的直接前驱，ai+1是 ai的直接后继。

线性表的抽象数据类型定义 （参见教材）
返回本章目录
2.2 线性表的顺序存储结构

线性表的顺序存储是指在内存中用地址连续的一块存储空间 依次存放线性表的数据元素，用这种存储形式存储的线性表 称其为顺序表。 假设每个数据元素占d个存储单元，且将ai的存储地址表示为 Loc(ai)，则有如下关系： Loc(ai)=Loc(a1)+(i-1)*d Loc(a1)是线性表的第一个数据元素a1的存储地址，通常 称作线性表的基地址。

【例1】 编写一算法，从顺序表中删除自第i个元素开 始的k个元素。 算法思路： 为保持顺序表的逻辑特性，需将i+k ~ n位 置的所有元素依次前移k个位置。算法如下：

int deleteK(Sqlist &sq,int i,int k)
{ if (i<1||k<1||i+k-1>sq.len) return 0; for (j=i+k-1;j<=sq.len-1;j++) sq.data[j-k]=sq.data[j]; sq.len-=k; return 1; }// deleteK
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

特点： 特点：链表中结点的逻辑次序和物理次序不一定相
同。即：逻辑上相邻未必在物理上相邻。 即 每个元素(表项)由结点(Node)构成，它包含两个域： 一个数据域 数据域——用来存储数据元素信息，另一个是 数据域 指针域（ 指针域（链域）——用来存储直接后继的存储位置 2．单链表：每个结点只有一个链域。 开始结点——（无前趋）用头指针指向header。 最后一个结点(尾结点)——指针为空（无后继）， 用^或NULL表示。
张三 ８５
李四 ６０
赵五 ７４
钱六 ５５
王七 ９０
2.2 线性表的定义 1．定义：具有相同类型 相同类型的n个(n≥0)数据元素（结点） 相同类型 a1,a2,a3,……an组成的有限序列 有限序列。 有限序列 2．线性表的特性 1）线性表中的所有数据元素的数据类型 数据类型是一致的。 数据类型 2）结点间的逻辑关系是线性 线性的。 线性
删除算法与插入算法类似，不在详述。
2.4 线性表链式存储结构的实现 引入：顺序表的缺点： （1）插入和删除平均须移动一半结点。 （2）存储分配只能预先进行（静态）。过大：浪费； 过小：溢出。 基于以上原因：采用链式存储结构 基于以上原因： 线性链表（ 定义： 1．线性链表（linked list）定义： 定义 线性表链式存储结构是用一组任意的 意的存储单元存储 意的 线性表的数据元素（这组存储单元可以是连续的， 也可以是不连续的）。
2.1 线性表的引入 2.2 线性表的类型的定义 2.3 线性表顺序存储结构的实现 2.4 线性表链式存储结构的实现 2.5 数组的定义 2.6 数组的顺序表示和实现 2.7 特殊矩阵的压缩存储 2.8 小结与习题
2.1 线性表的引入 例 1:奇数序列： (1,3,5,7,9,11) 例 2：随机的学生成绩序列
（3）删除操作
算法说明： 算法说明：在线性表中指定位置，删除与其类型一 致的某元素。 若i=n,只需删除终端结点，不用移动结点； 若表长度n<=0或删除位置不适当，则输出错误信息， 并返回-1； 当1<=i<n时，则将表中结点ai+1,ai+2,…,an依次向前 移动一个位置（共需移动n-i个数据元素)。 上述算法for循环语句的执行次数为n-i;
data p （结点*p） next
说明： 说明： (*p).data或p->data——表示数据域 (*p).next或p->next——表示p所指向结点的指针域。 P=（Lnode*）malloc(sizeof(Lnode))：对指针p赋值 使其指向Lnode类型的新结点。 其中：Sizeof(Lnode)---求结点需用占用的字节数。 函数malloc分配了一个类型为Lnode的结点变量的空 间，并将其首地址放入指针变量p中。 一旦p所指的结点变量不再需要了，又可通过标准函 数free(p)——系统回收p结点，（动态）释放所指的 结点变量空间。
q = L-> elem +(i -1) ; /*q为插入位置*/ for(p= L-> elem + (L.len-1);p>=q; --p) *(p + 1)= *p; /*插入位置及以后的元素右移*/ *q = x; /* 插入x */ ++ L->len; /* 表长加一 */ return(1); }
顺序表的插入算法
例 ：以随机学生成绩序列为例插入元素 75。插入位置为 i=3
for(j=L.length；j>i；j--) L.data[j+1]=L.data[j]； L.len算法for循环语句的执行次数为n-i+1; 若i=1,需移动全部n个结点（最坏：O(n)） 若i=n+1（在表尾插入）,无需用移动结点，直接插 入即可。（最好O(1)） 按等概率考虑,可能的插入位置为i=1,2,…n,n+1共 n+1个，则pi=1/(n+1), 所以由公式导出Ein=n/2,即顺序表插入算法平均约需 移动一半结点。 （Ein为平均移动次数）， 若表长为n，则算法的时间复杂度 O(n) 时间复杂度为O(n) 时间复杂度 O(n)。
插入算法的程序实现 int insert_Sq(Sqlist L,int i,Elemtype x) { intj; if(L.length >= MAXSIZE) {printf(“表长错误\n");return(-1);} if (i<1||i> L.length +1) {printf(“插入位置I不适当\n");return(-1);} for(j=L.length;j>i;j--) L.data[j+1]=L.data[j]; L.length++; L.data[i]=x; return(0); }
线性表的查找操作
算法模拟（随机学生成绩序列的查找算法演示过程） 算法模拟
int j=1,i=0； while(j<=L.length) if(L.data[j]!=x) j++； else i=j
初始化
74
85 60 74 55 90
i=3 j=3
L.length=5
（2）插入操作
在第i（1<=i<=n+1）个元素之前插入一个新的 数据元素x。使：长度为n的线性表变为长度为n+1 使 的线性表，即由（a1,a2,…,ai-1,ai,…,an）→ （a1,a2,…,ai-1,x,ai,…,an） 插入算法的思想 思想： 思想 若i=n+1,则将x插入到表尾； 若表长度n<0或插入位置不适当，则输出错误信息， 并返回-1； 当1<=i<= L.length时，则从表尾开始到i依次向后 移动一个位置（共需移动n-i+1个数据元素）。 最后将x存入data[i]中，表长n增1插入成功，函数 最后 返回值为0。
★ 建立单链表（头插法）： 建立单链表（头插法）： Lnode *CreatList( ) { char ch; Lnode *head,*p; head= ( Lnode * ) malloc( sizeof ( Lnode ) ; head->next=NULL; ch=getchar(); while(ch!=‘#’) { p= ( Lnode * ) malloc( sizeof ( Lnode ) ); p->data=ch; p->next=head->next; head->next=p; ch=getchar(); } return (head); } 思考：尾插法如何进行？ 思考：尾插法如何进行？
3．线性表的基本名词 (1)线性表的长度 长度：线性表的所包含元素的个数 n ； 长度 (2)空线性表(空表)：线性表的长度 n=0 ； (3)（直接）前驱和后继 前驱和后继：在相邻元素中，ai是 前驱和后继 ai+1的直接前驱（除a1外），在相邻元素中，ai+1 是ai的直接后继（除an外）; 4．线性表的基本操作 线性表可以看作 除第一个元素无前驱，最后 看作是除 看作 一个元素无后继外，其余元素 其余元素都有唯一的直接前驱 其余元素 和直接后继的元素构成的集合。对线性表的操作有 在线性表中查找 查找某个元素；在线性表的指定位置插 查找 插 删除元素等。 入元素；在线性表的指定位置删除 删除
3.表的几种基本运算
（1）查找操作
算法说明： 算法说明：在已知线性表中，查找与其类型一致的 某元素是否存在。 算法模拟( 算法模拟(随机学生成绩序列的查找算法演示过程) Sqlistsearch ( Sqlist L,Elemtype x) { int j=1,i=0 ; 不讨论数 while(j<=L.length) 组下标为0 的元素 if(L.data[j]!=x)j++; else i=j; return(i); } i的值在1～L.length 之间，否则i=0。
顺序表的删除算法
删除算法的模拟(以随机学生成绩序列为例)
i=3, L.length=5 ； L.length - - ； for(j=i；j<=L.length；j++) L.data[j]=L.data[j+1]；
FLASH 演示
★ 动态分配的顺序存储结构
由于： 由于：1、利用数组实现线性表的操作，对于存储空间只能
1、初始化线形表：分配预定义的存储空间，并 、初始化线形表：分配预定义的存储空间，
将线形表的当前长度定义为零。 将线形表的当前长度定义为零。
int Init_List ( DySqList *L ) /*构造一个空线性表*/
{ L->elem = (ElemType *) malloc ( INIT_SIZE * sizeof (ElemType) ) /*分配存储空间*/ if (! L->elem ) exit ( 0 ) ; L->len = 0; L->cursize = INIT_SIZE; return 1 ; } /*存储分配失败*/ /*空表长度为0*/ /*初始存储容量*/
结点定义： 结点定义： typedef struct Lnode /*结点类型定义*/ {ElemType data; /*数据域*/ struct Lnode *next; /*next为指针域，指向 该结点的后继*/ } Lnode； Lnode *head,*p；/*指针类型说明*/ 表示空表的单链表只有一个单元，即表头单元header， 其中的指针是空指针NULL。 指针p与指向的结点关系示意图：
表中其它结点——由其前趋的指针域指向。 单链表的逻辑结构如图所示。 head 是指向表头结点 的指针。 线性表为空表时， 头指针 头指针 头结点的指针域为空 空指针 head
头结点
∧
a1