当前位置：文档之家 › 数据结构与算法--线性表(C++)PPT课件

数据结构与算法--线性表(C++)PPT课件

  • 格式：ppt
  • 大小：406.50 KB
  • 文档页数：59

下载文档原格式

  / 59

合集下载

数据结构课件第2章线性表

数据结构课件第2章线性表

27
线性表的顺序存储结构适用于数据 元素不经常变动或只需在顺序存取设备 上做成批处理的场合。为了克服线性表 顺序存储结构的缺点，可采用线性表的 链式存储结构。
28
2.3 线性表的链式存储结构
线性表的链式存储表示 基本操作在单链表上的实现 循环链表 双向链表 线性表链式存储结构小结
2.3.1 线性表的链式存储表示 29
2.1.1 线性表的定义
6
一个线性表（linear_list）是 n（n≥0）个具有相同属性的数 据元素的有限序列，其中各元素有着依次相邻的逻辑关系。
线性表中数据元素的个数 n 称为线性表的长度。当 n = 0 时 该线性表称为空表。当 n > 0 时该线性表可以记为：
（a1，a2，a3，…，ai，…，an）
数据域 指针域
结点 data next
31
(2) 线性表的单链表存储结构
通过每个结点的指针域将线性表中 n 个结点按其逻辑顺序链 接在一起的结点序列称为链表，即为线性表 ( a1, a2, a3, …, ai, …, an ) 的链式存储结构。如果线性链表中的每个结点只有一个指针域， 则链表又称为线性链表或单链表 (linked list)。
17
(2) 算法编写
#define OK 1
#define ERROR 0
Int InsList ( SeqList *L, int i, ElemType e ) /*在顺序线性表 L 中第 i 个位置插入新的元素 e。*/ /* i 的合法值为 1≤i ≤L->last+2*/ {
int k; if ( i < 1) ||( i > L->last+2)) /*首先判断插入位置是否合法*/ { printf(“插入位置i值不合法”）；

数据结构之线性表课件

数据结构之线性表课件
实现插入算法主要完成三个基本操作：
1) 在单链表上找到插入位置，即找到第i个结点。 可以用遍历的方法，即从表头起顺次访问单链
表的结点，直至找到第i个结点。 2) 生成一个以x为值的新结点。 可通过C的库函数malloc(size)来产生。 3) 将新结点链入单链表中。 需要改变相关结点的指针 ，如下面的图所示。
H
a1
an ^
空表
……
为了编程方便，一般在单链表的第一个 结点之前加一个“头结点”，如：
head
a1
an ^
当为空表时，即head->next=null, 如下图。
head
^
指针的概念
假设p是一个pointer类型，应正确区分指针型 变量、指针、指针所指的结点和结点的内容 这四个密切相关的不同概念：
2.1线性表的逻辑结构
线性表的定义 线性表是由n个结点a1，a2，…..,an 组成的有 限序列，当n=0时，线性表为空，即为空表。 若n>0, 则a1是第1个结点，an是最后一个结点。
其形式化的定义为： S=（D，R） 其中：D是由n个元素组成的集合， R是定义在集合D上的一种关系。
2.1线性表的逻辑结构
2. 元素的删除(Delete)
在顺序表L=（a1,a2,… ,ai,…,an）中删除第i个结 点，使成为
L=（a1,a2,…,ai-1, ai+1,…, an）
基本思想：要求删除第i个数据元素，由于线性 表元素在数组中必须连续排列，中间不能有空 单元，故将此元素删除后，它后面的所有元素 都需要向前移动一个单元，且数据元素总数由 原来的n减少到n-1.
数据结构之线性表课件
第二章 线性表
知 识 点

数据结构线性表ppt课件

数据结构线性表ppt课件

01
02
03
04
插入操作
在链表的指定位置插入一个新 节点，需要修改相邻节点的指
针。
删除操作
删除链表的指定节点，需要修 改相邻节点的指针。
查找操作
从链表的头节点开始，顺序遍 历链表，直到找到目标元素或
遍历到链表末尾。
遍历操作
从链表的头节点开始，顺序访 问每个节点，直到遍历到链表
末尾。
04 线性表应用举例 与问题分析
多项式表示与计算问题
01
02
03
多项式表示方法
数组表示法和链表表示法 。
数组表示法
将多项式的系数按次序存 放在一个数组中，通过下 标表示对应的幂次。
链表表示法
每个节点包含系数和指数 两个数据域，以及一个指 向下一个节点的指针域。
一元多项式相加算法设计
• 算法思想：将两个多项式中的同类项系数相加，得到新的 多项式。
删除操作
删除指定位置i的元素，需要将i之后的元素都向前移动 一个位置。
03 链式存储结构及 其实现
链式存储结构原理及特点
链式存储结构原理
使用一组任意的存储单元存储线 性表的数据元素（这组存储单元 可以是连续的，也可以是不连续 的）。
链式存储结构特点
逻辑上相邻的元素在物理位置上 不一定相邻，元素之间的逻辑关 系是通过指针链接来表示的。
...，an组成的有序序列。
性质
集合中必存在唯一的一个“第一元素 ”。
集合中必存在唯一的一个“最后元素 ”。
除最后元素之外，均有唯一的后继。
除第一元素之外，均有唯一的前驱。
线性表与数组关系
数组是线性表的一种表现和实现形式。
线性表更侧重于逻辑概念，而数组则是这种逻辑概念在计算机中的一种存储方式。

数据结构线性表ppt课件

数据结构线性表ppt课件
➢ 数组（Array）存储具有相同数据类型的元素集合。 一维数组占用一块内存空间，每个存储单元的地 址是连续的，计算第i个元素地址所需时间复杂度 是一个常量， 与元素序号i无关。
线性表的分类
线性表 ADT
顺序存储结构 （元素连续存储、
继承
顺序表类
排序顺序表类
随机存取结构）
继承
链式存储结构
（元素分散存储）
单链表 双链表
单链表类 循环单链表 双链表 循环双链表类
排序单链表类
继承 排序循环双链表类
线性表的存储结构
2.2 线性表的顺序存储和实现
线性表的顺序存储结构
数组 ：是实现顺序存储结构的基础。
数据结构
第 2 章 线性表
线性结构
线性结构是最常用、最简单的一种数据结构。而线性 表是一种典型的线性结构。其基本特点是线性表中的数据 元素是有序且是有限的。
线性结构基本特征： ① 存在一个唯一的被称为“第一个”的数据元素； ② 存在一个唯一的被称为“最后一个”的数据元素； ③ 除第一个元素外，每个元素均有唯一一个直接前驱； ④ 除最后一个元素外，每个元素均有唯一一个直接后 继。
其中LinearList称为线性表的名称 每个ai（n-1≥i≥0）称为线性表的数据元素，可以是整数、
浮点数、字符或类 表中相邻元素之间存在着顺序关系：将 ai-1 称为 ai 的前
驱（Predecessor），ai+1 称为 ai 的后继 （Successor）。a0没有前驱元素，an-1没有后继元素 具体n的值称为线性表中包含有数据元素的个数，也称 为线性表的长度（Length） 当n的值等于0时，表示该线性表是空表
2.1 线性表抽象数据类型
线性表的定义

第2章 线性表 (数据结构教程PPT课件)

第2章 线性表 (数据结构教程PPT课件)

3.在数组a中检索（查找）值为X的数据元素
int locate (int a[ ],int n, int x) { int i; i=0; while((i<=n-1)&&(a[i]!=x)) i++; if(i<=n-1) return (i); /*返回的是存储位置*/ else return (0);} }
(2)按值查找即定位 Locate_LinkList(L,x) Lnode * Locate_LinkList( LinkList L, datatype x) /*在单链表L中查找值为x的结点，找到后 返回其指针，否则返回空*/ { Lnode * p=L->next; while ( p!=NULL && p->data != x) p=p->next; return p; }
2.2.2 典型操作的算法实现
1. 初始化线性表L
SeqList *init_SeqList( )
{ SeqList *L; L=malloc(sizeof(SeqList)); L->last=-1; return L; }
2.在数组a第i个数据元素之（ai-1）前插入数据 元素X insert (int a[ ],int n,int i, int x) { int j; for(j=n-1;j>=i-1;j--) a[j+1]=a[j]; /* 结点移动 */ a[i-1]=x; /*新元素插入*/ n++; /*修改长度*/ }
4.删除数组a第i个数据元素（ai-1） delete (int a[ ],int n,int i) { int j; for(j=i;j<=n;j++) a[j-1]=a[j]; /* 结点移动 */ n--; /*修改长度*/ }

数据结构与算法(共11张PPT)

数据结构与算法(共11张PPT)

(b)入队3个元素(c)出队3个元素
(b) d, e, b, g入队
利用一组连续的存储单元(一维数组)依次存放从队 在循环队列中进行出队、入队操作时，队首、队尾指
队列示意图
在非空队列里，队首指针始终指向队头元素，而队
(b) d, e, b, g入队
8
Q.rear
a5
a4
Q.front
(d)入队2个元素
a1, a2, … , an
的指修针改 和是队依列先中进元先素出的Q的变.re原化a则情r 进况行。的，如图所示。
a3
Q.front
a2
a1
首到队尾的各个元素，称为顺序队列。
(c)
d, e出队Q.front
Q.front
◆出队：首先删去front所指的元素，然后将队首指针front+1，并
◆rear所指的单元始终为空(a。)空队列
i
i, j, k入队
(e)
1
2
3
k
r
01
j5
2
front
43
i
b, g出队
(f )
r, p,
p rear
s, t入队
循环队列操作及指针变化情况
入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针 ，故队空和队满时头尾指针均相等。因此，无法通过front=rear来 判断队列“空”还是“满”。解决此问题的方法是：约定入队前，
数据结构与算法
1算法基础 2数据结构
3栈
4队列
5链表 6树和二叉树
7查找
4队列
✓队列的基本概念 ✓队列运算
✓循环队列及其运算
4队列
1.队列的基本概念

数据结构线性表课件pptx

数据结构线性表课件pptx

顺序表基本操作实现
初始化顺序表
分配存储空间，设置初始状态
删除元素
删除指定位置的元素，需移动元素填补 空位
2024/1/28
插入元素
在指定位置插入元素，需移动元素以保 持连续性
查找元素
通过元素值查找其位置，可顺序查找或 折半查找
10
顺序表应用举例
01
一元多项式表示
用顺序表存储多项式的系数和 指数
02
25
06
总结回顾与拓展延伸
2024/1/28
26
关键知识点总结回顾
线性表的定义与性质
线性表是一种具有n个元素的有限序 列，具有顺序性、元素唯一性、元 素可变性等性质。
线性表的存储结构
包括顺序存储结构和链式存储结构 两种，其中顺序存储结构通过数组 实现，链式存储结构通过链表实现
。
2024/1/28
合理利用顺序存储结构的随机访问特点 ，避免不必要的元素移动。
对于频繁进行的操作，可以考虑使用特 殊的数据结构进行优化，如哈希表、二
叉搜索树等。
在链式存储结构中，尽量保持链表长度 适中，避免过长导致操作效率低下。
在实际应用中，可以根据具体需求和数 据特点选择合适的数据结构和算法来提 高操作效率。
2024/1/28
点。
循环链表和双链表简介
循环链表
尾节点的指针指向头节点，形成一个 环状的链表结构。适用于需要循环遍 历的场景。
双链表
每个节点包含两个指针，一个指向前 一个节点，另一个指向后一个节点。 可以双向遍历，但操作相对复杂。
2024/1/28
15
04
线性表应用案例分析与讨 论
2024/1/28
16

数据结构与算法线性表.ppt

数据结构与算法线性表.ppt

线性结构分类
按操作划分
线性表
• 所有表目都是同一类型结点的线性表 • 不限制操作形式 • 根据存储的不同分为：顺序表，链表
栈(LIFO, Last In First Out)
• 插入和删除操作都限制在表的同一端进行
队列(FIFO, First In First Out)
• 插入操作在表的一端， 删除操作在另一端
bool append(const T value); // 在表尾添加一个元素value，表的长度增1
bool insert(const int p, const T value);
// 在位置p上插入一个元素value，表的长度增1
bool delete(const int p);
// 删除位置p上的元素，表的长度减 1
bool getPos(int & p, const T value)
// 查找值为value的元素并返回其位置
bool getValue(const int p, T& value);
// 把位置p的元素值返回到变量value中
bool setValue(const int p, const T value);// 用value修改位置p的元素值
有序性：各数据元素在线性表中都有自己的位置，且 数据元素之间的相对位置是线性的
线性结构
包括：
简单的
• 线性表 •栈 • 队列 • 散列表
高级的
• 广义表 • 多维数组 • 文件
……
线性结构分类
按访问方式划分
直接访问型(direct access) 顺序访问型( sequential access) 目录索引型(directory access)

数据结构课件之线性表

数据结构课件之线性表
学C
我觉得老师讲解得非常详细，特别是对于一些难以理解的概念和算法 ，通过老师的讲解和示例，我很快就掌握了。
未来发展趋势预测
线性表作为基础数据结构，其重要性不言而喻。随着大数据、人工智能等领域的不 断发展，对线性表的处理能力和效率要求也越来越高。
未来可能会出现更多针对线性表的优化算法和技术，以满足不同应用场景的需求。
存储空间动态分配，可以充分利 用计算机内存空间，实现灵活的
内存动态管理。
插入、删除等操作不需要移动大 量元素，只需要修改相应的指针
即可，因此具有较高的效率。
逻辑结构与物理结构不一定一致 ，因此可以方便地实现各种复杂
的数据结构。
链式存储结构实现方式
每个节点包含两个指针域，分别 指向其前驱节点和后继节点。
从线性表的中间位置开始，同时 向前和向后遍历，直到遍历完整 个线性表。这种遍历方式在某些
算法中有特殊应用。
03
线性表顺序存储结构
Chapter
顺序存储结构定义
顺序存储结构是用一段连续的存储空间来依次存放线性表的 各个元素。
在这种存储结构中，线性表中第一个元素的存储地址作为线 性表的起始地址，每个元素的存储地址是其逻辑序号与元素 所占存储单元大小的乘积加上起始地址。
设置初始状态
将线性表的长度设为0，表示初始 时线性表为空。
插入操作
01
02
03
确定插入位置
根据需要插入元素的位置 ，确定该位置在线性表中 的序号。
移动元素
从线性表的最后一个元素 开始，依次将每个元素向 后移动一个位置，直到达 到插入位置。
插入新元素
在插入位置处插入新元素 ，并更新线性表的长度。
删除操作
线性表的操作算法

数据结构课件之线性表(ppt 86页)

数据结构课件之线性表(ppt 86页)

删除算法
int DelList(SeqList *L,int i,ElemType *e)
/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/
{ int k;
if((i<1)||(i>L->last+1))
{ printf(“删除位置不合法！”)； return(ERROR)； }
*e= L->elem[i-1]; /* 将删除的元素存放到e所指向的变量中*/
loc(ai) =loc(a1)+(i-1)×k
8
15.10.2019
顺序存储结构示意图
存储地址
Loc(a1) Loc(a1)+(2-1)k
…
loc(a1)+(i-1)k
…
loc(a1)+(n-1)k
...
loc(a1)+(maxlen-1)k
内存空间状态
a1 a2
…
ai
…
an
9
逻辑地址
1 2
…
i
操作前提：L为未初始化线性表。 操作结果：将L初始化为空表。 操作前提：线性表L已存在。 操作结果：将L销毁。 操作前提：线性表L已存在 。 操作结果：将表L置为空表。
………
}ADT LinearList
6
15.10.2019
2.2 线性表的顺序存储
2.2.1 线性表的顺序存储结构 2.2.2 线性表顺序存储结构上的基本运算
17
15.10.2019
删除算法示意
将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素 删除。
序号
1 2 3 4 5 6 7 8 9 10 4 9 15 21 28 30 30 42 51 62

数据结构课件线性表

数据结构课件线性表
数据结构课件线性表
目录
CONTENTS
• 线性表的基本概念 • 线性表的实现方式 • 线性表的基本操作 • 线性表操作的效率分析 • 线性表的应用案例
01 线性表的基本概念
线性表的定义
线性表：线性表是一种具有线性 关系的抽象数据类型，其元素之
间存在一对一的顺序关系。
线性表由n个元素组成，每个元 素都有一个唯一的标识符，称为
04 线性表操作的效率分析
顺序存储结构的效率分析
访问元素
顺序存储结构中，访问任意一个元素 的时间复杂度为O(1)，因为可以通过 索引直接访问。
插入和删除操作
顺序存储结构中，插入和删除操作的时 间复杂度为O(n)，因为需要移动元素来 保持线性表的连续性。
链式存储结构的效率分析
访问元素
链式存储结构中，访问任意一个元素的时间复杂度为O(n)，因为需要从头节点 开始遍历链表直到找到目标节点。
VS
详细描述
二维数组是一种二维的数据结构，可以看 作是线性表的扩展。在二维数组中，每个 元素的位置由其行列索引确定，这使得二 维数组在表示矩阵等数学运算中非常方便 。同时，二维数组也可以通过行优先或列 优先的方式进行线性化处理，转化为线性 表的形式进行操作。
哈希表的设计与实现
总结词
哈希表是一种特殊的线性表，通过哈希函数将键映射到数组的索引上，实现快速的查找 操作。
线性表的分类
静态线性表
静态线性表是使用数组实现的线 性表，其大小在创建时确定，且 不可改变。
动态线性表
动态线性表是使用链表或动态数 组实现的线性表，其大小可以动 态地增加或减少储结构是指将线性表中 的元素按照一定的顺序存储在 一片连续的存储空间中。
顺序存储结构的特点是访问速 度快，可以通过索引直接访问 任意元素。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

精选ppt
4
几点说明：
a1 a2 a3 a4 a5 a6
▪（4） 线性表中元素的个数n 称为线性表的长度，
n=0 时称为空表；
▪（5） ai是线性表的第i 个元素，称i 为数据元素ai 的
序号，每一个元素在线性表中的位置，仅取决于它的序 号。
精选ppt
5
线性表的基本操作
1．int Length() const 初始条件：线性表已存在。 操作结果：返回线性表元素个数。
Essential of Lecture Two ：
一、线性表的定义 二、线性表---顺序表 三、顺序表的基本操作 四、顺序表的优缺点 五、顺序表的应用
难点
精选ppt
重点
1
一、线性表的定义 ( Linear List )
▪ 【定义】：由n(n≧0)个数据元素(结点)a1，a2， …an组 成的有限序列。其中数据元素的个数n定义为表的长度。
线性表（a1,a2,a3, ... an） 的顺序存储结构
Loc(ai ) = Loc( a1 )+ ( i-1 ) * L
精选ppt
L个单元
a1 a2
…
ai-1
ai ai+1
…
an
Loc( a1) Loc( ai )
14
顺序表(SqList)类的定义
// 顺序表类
template <class elemType>
当n=0时称为空表，常常将非空的线性表(n>0)记作：
▪
(a1，a2， ... ... ， an)
▪ 例1、26个英文字母组成的字母表
（A，B，C ，... ... ， Z）
▪ 例2、某校从1978年到1983年各种型号的计算机拥有 量的变化情况。

（6，17，28，50，92，188）
精选ppt
2
例3、学生健康情况登记表
精选ppt
8
线性表的基本操作
5．StatusCode GetElem(int position, ElemType &e) const
初始条件：线性表已存在，1≤position≤Length()。 操作结果：用e返回第position个元素的值。
6．StatusCode SetElem(int position, const ElemType &e)
初始条件：线性表已存在。 操作结果：依次对线性表的每个元素调用函数 (*visit)。
精选ppt
7
为表示各种状态信息，定义枚举类型 StatusCode供使用，具体声明如下：
// 自定义类型 enum StatusCode {
SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR, NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED };
性表中的元素必须是同一类型的；
▪（2） 在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai
的直接前驱，ai+1 是ai 的直接后继；
▪（3） 在线性表中，除第一个元素和最后一个元素
之外，其他元素都有且仅有一个直接前驱，有且仅有
一个直接后继，具有这种结构特征的数据结构称为线
性结构；
为了存储线性表，至少要保存两类信息： 1）线性表中的数据元素； 2）线性表中数据元素的顺序关系；
精选ppt
11
线性表按存储分类：
1）顺序表 SqList 2）链表 线性链表 SimpleLinkList
循环链表 SimpleCircLinkList 双向链表 SimpleDblLinkList 静态链表 StLinkList
8．StatusCode Insert(int position, const ElemType &e) 初始条件：线性表已存在，1≤position≤Length()+1。 操作结果：在线性表的第position个位置前插入元素e， 长度加1。
精选ppt
10
如何在计算机中存储线性表？ 如何在计算机中实现线性表的 基本操作？
class SqList
{
protected:
// 顺序表实现的数据成员:
int count;
// 元素个数
int maxSize; // 顺序表最大元素个数
elemType *elems; // 元素存储空间
精选ppt
15
// 辅助函数 bool Full() const; // 判断线性表是否已满 void Init(int size); // 初始化线性表
2．bool Empty() const 初始条件：线性表已存在。 操作结果：如线性表为空，则返回true，否则返回 false。
精选ppt
6
线性表的基本操作
3．void Clear() 初始条件：线性表已存在。 操作结果：清空线性表。
4．void Traverse(void (*visit)(const ElemType &)) const
精选ppt
12
二、顺序表 Sequential List
顺序表的定义和特点
定义: 将线性表中的元素相继存放在一个 连续的存储空间中。
可利用一维数组描述存储结构 特点: 线性表的顺序存储方式 遍历: 顺序访问
精选ppt
13
二、顺序表 Sequential List
线性表的顺序表示，就是 用一组地址连续的内存单元依 次存放线性表的数据元素。
姓名 王小林 陈红 刘建平 张立立
学号 020631 020632 020633 020634
性别 男 女 男 男
年龄 18 20 21 17
……..
…….. ……. …….
健康情况 健康 一般 健康
神经衰弱 …….
精选ppt
3
几点说明：
a1 a2 a3 a4 a5 a6
▪ 设 A=（a1, a2, ... , ai -1, ai , ai+1, …, an ）是一线性表 ▪（1） 线性表的数据元素可以是各种各样的，但同一线
初始条件：线性表已存在，1≤position≤Length()。 操作结果：将线性表的第position个位置的元素赋 值为e。
精选ppt
9
线性表的基本操作
7．StatusCode Delete(int position, ElemType &e) 初始条件：线性表已存在，1≤position≤Length()。 操作结果：删除线性表的第position个位置的元素, 并用 e返回其值，长度减1。