当前位置：文档之家 › 线性表 PPT课件

线性表 PPT课件

  • 格式：ppt
  • 大小：3.25 MB
  • 文档页数：144

下载文档原格式

  / 144

合集下载

线性表PPT课件

线性表PPT课件

第21页/共40页
• 2.3.2 典型操作的算法实现 • (1)在链表的头部插入结点建立单链表
• LinkList Creat_LinkList1( )
• { LinkList L=NULL；/*空表L为表头*/
• Lnode *s;
• int x;
/*设数据元素的类型为int*/
• scanf(＂%d＂,&x);
•
/*在单链表L的第i个位置上插入值为x的元素*/
• { Lnode * p,*s;
• p=Get_LinkList(L,i-1); /*查找第i-1个结点*/
• if (p==NULL)
•
{ printf(＂参数i错＂);return 0; } /*第i-1个不存在不能插入*/
• else {
•
s=malloc(sizeof(LNode)); /*申请、填装结点*/
•
其中：L为线性表名称，习惯用大写书写；
•
ai为组成该线性表的数据元素，习惯用小写书写；
•
线性表中数据元素的个数被称为线性表的长度，当n=0时，线性
表为空，又称为空线性表。
第2页/共40页
•
举例
• int。
La=（34，89，765，12，90，-34，22） 数据元素类型为
•
Ls=(Hello,World, China, Welcome) 数据元素类型
2所示的形式存储：
第16页/共40页
存 储 地 址
100 ... 120 首 元 素 位 置 ... 144 ... 160 ...
内 容 直 接 后 继 存 储 地 址
b
120
...
...

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

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

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章线性表-PPT精品文档

第2章线性表-PPT精品文档

( ) a , a, a , x , a , a i n
2、顺序表的插入
{ if (i<1 ||i>L.length+1 ) return ERROR;
P24 算法2.4
Status ListInsert_Sq(SqList &L,int i,ElemType e) //i值不合法
2.2
二、线性表的顺序存储结构定义 ——动态
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct { ElemType *elem； //存储空间基址， 体现动态性 int length; //当前长度 int listsize; //当前分配的存储容量 }SqList;
M-1 或动态申请和释放内存 数据元素不是简单类型时,可定义结构体数组 ElemType *pData; pData = (ElemType *)malloc(M*sizeof(ElemType)); free(pData); 2019/3/26
二、线性表的顺序存储结构定义 ——静态
#define MAXSIZE 100 typedef struct { ElemType elem[MAXSIZE]; int length; }SqList;
#define LISTINCREMENT 10 typedef typedef struct struct { { ElemType *elem； ElemType elem[MAXSIZE]; int length; int length; int listsize; }SqList; }SqList;

数据结构线性表ppt课件

数据结构线性表ppt课件

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

线性表ppt

线性表ppt
由于C语言函数的参数仅能向被调函数传值，这个值在返 回时也不会改变，因此在上面的算法中，采用指针变量v做形 参，虽然从被调函数返回时指针v值不变，但是v地址中所代表 的结构体的内容发生了变化。这就是所谓的传址调用。
假设在主函数中已经建立了线性表结构体s，并且要在第3 个位置插入88，语句如下：
insert ( &s，3，88);
其他特 VIP专享精彩活动
权
VIP专属身份标识
开通VIP后可以享受不定期的VIP随时随地彰显尊贵身份。
专属客服
VIP专属客服，第一时间解决你的问题。专属客服Q全部权益：1.海量精选书免费读2.热门好书抢先看3.独家精品资源4.VIP专属身份标识5.全站去广告6.名
以用来说明结构体变量：
Sqlist1 a； 在正式使用a之前必须为数据成员elem分配足够的空间。 语句如下：
a.elem=(Sqlist1 *)malloc(MAXSIZE*sizeof(Sqlist1))； 对结构体内elem子域的访问与前文有所不同。在输入/输出时 的情况，也与前文有所不同。在程序运行结束之前，这些动态 分配的存储空间还要释放归还给系统，语句如下：
(5) Insert(L，i，x) 在线性表中第i个元素之后(或之前)插入一个新元素x；
(6) Delete(L，i) 删除线性表中的第i个元素；
(7) Empty(L)
判断线性表是否为空；
(8) Clear(L)
将已知的线性表清理为空表；
第2章 线 性 表
在上述的操作运算中，最基本最重要的是插入、删除。 线性表的其他复杂操作和运算还有：对有序表的插入和删除； 按某种要求重排线性表中各元素的顺序；按某个特定值查找 线性表中的元素；两个线性表的合并等。

线性表PPT课件

线性表PPT课件

顺序表上基本运算的实现(2)
插入运算:在第 i 个位置，插入元素e 思想：把从第i个位置开始的元素，依次后移 步骤：
1.当前表是否已经满？ 2.输入是否有效？ 3.插入元素。
插 入
顺序表上基本运算的实现(2)
元
素void SeqListInsert(SeqList L,int i,ElemType x)
ADT List{
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R={<ai-1,ai>|ai,ai-1∈D,i=2,…,n} 基本操作：
1. ListInit (L) ； 2. ListLength (L) ； 3. ListGet(L,i) ; 4. ListLocate (L,x) ; 5. ListClear (L) ; 6. ListEmpty (L) ； 7. ListPrior (L,e) ； 8. ListNext(L,e) ； 9. ListInsert(L,i,e) ; 10. ListDelete(L,i);
}ADT List
线性表举例1（遍历线性表）
ListTraverse(List L，visit()) {//遍历线性表
if(ListEmpty(L)) printf(“空表”); else
for(i=1;i<=ListLength(L);i++) visit(ListGet(L,i))； }
线性表举例2（合并线性表）
顺序表上基本运算的实现(3)
删除元素 :
void SeqListDelete(SeqList L,int i)
{//删除顺序表中的第i个元素
if(i<1||i>L.length)

数据结构课件之线性表(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
详细描述
二维数组是一种二维的数据结构，可以看 作是线性表的扩展。在二维数组中，每个 元素的位置由其行列索引确定，这使得二 维数组在表示矩阵等数学运算中非常方便 。同时，二维数组也可以通过行优先或列 优先的方式进行线性化处理，转化为线性 表的形式进行操作。
哈希表的设计与实现
总结词
哈希表是一种特殊的线性表，通过哈希函数将键映射到数组的索引上，实现快速的查找 操作。
线性表的分类
静态线性表
静态线性表是使用数组实现的线 性表，其大小在创建时确定，且 不可改变。
动态线性表
动态线性表是使用链表或动态数 组实现的线性表，其大小可以动 态地增加或减少储结构是指将线性表中 的元素按照一定的顺序存储在 一片连续的存储空间中。
顺序存储结构的特点是访问速 度快，可以通过索引直接访问 任意元素。

第2章线性表newppt课件

第2章线性表newppt课件

2018/11/14
10
第二章 第1节
例2：教材信息表
无直接前驱 数据元素 (记录) 第1个数据元素 直接前驱
第i个数据元素 直接后继 第n个数据元素 无直接后继
教材名称
面向对象系统分析与 设计 …… PowerBuilder应用 数据结构(C++ 描述) Java高级开发指南 …… JavaScript编程指南
前置条件：表已存在 输入：数据元素x 功能：在线性表中查找值等于x的元素 输出：如果查找成功，返回元素x在表中的序号，否则 返回0 后置条件：表不变
2018/11/14
14
第二章 第1节
Insert
前置条件：表已存在 输入：插入i；待插x 功能：在表的第i个位置处插入一个新元素x 输出：若插入不成功，抛出异常 后置条件：若插入成功，表中增加一个新元素
2018/11/14
17
第二章 第2节
一维数组 内存状态 元素在线性 下标 表中的位序 0 1 … i-1 … n-1 … listsize a1 a2 … ai … an … 1 线性表的顺序存储表示： 1)用一个一维数组存放 数据元素 2)该数组的容量应事先 设定 3)还要用一个变量存放 该线性表的长度
7
2018/11/14
第二章 第1节
二、线性表的逻辑结构的特征
1.有限性:线性表中数据元素的个数是有穷的. 2.相同性:线性表中的数据元素的类型是同一的. 3.顺序性:线性表中的相邻数据元素是一对序偶.即相 邻的数据元素ai-1，ai（1＜i≤n）存在序偶关系(ai-1， ai）；a1 无前驱，an无后继，其它每个元素有且仅 有一个前驱和一个后继。
•
熟练掌握这两类存储结构的描述方法。扎实的指针 操作和内存动态分配的编程技术是学好本章的基本要 求。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
数据结构
第二章 线性表
10:29
• 第 2章 • 第 3章 • 第 4章 义表
线性表 栈和队列 串、数组和广
线性结构
（逻辑、存储 和运算）
线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结 点和一个终端结点，并且所有结点都最多只有一个 直接前趋和一个直接后继。 可表示为：（a1 ,
a2
, ……,
10:29
例3 某校从1978年到1983年各种型号的计算机拥 有量的变化情况。 （6，17，28，50，92，188） 数据元素都是数字; 元素间关系是线性 例4一副扑克的点数 （2，3，4，…，J，Q，K，A） 数据元素都是字符; 元素间关系是线性
同一线性表中的元素必定具有相同特性
10:29
线性表特点：在数据元素的非空有限集中 – 存在唯一的一个被称作“第一个”的数据元素 – 存在唯一的一个被称作“最后一个”的数据元素 – 除第一个外，集合中的每个数据元素均只有一个 直接前驱 – 除最后一个外，集合中的每个数据元素均只有一 个直接后继
10:29
7. 检索值为e的数据元素 LocateELem(L,e) 判断线性表L中是否存在值为e的结点 8. 在线性表L中插入一个数据元素 ListInsert(&L,i,e) 向线性表L的第i个位置之前插入一个值为e的数据元素 9. 删除线性表L中第i个数据元素 ListDelete(&L,i,&e) 删除线性表L的第i个数据元素，并将该数据元素的值返回e中 10.返回前驱结点 PriorElem(L,cur_e,&pri_e) 返回L中当前数据元素cur_e的前驱结点 11.返回后继结点NextElem(L,cur_e,&next_e) 返回L中当前数据元素cur_e的的后继结点
存储内容 元素1 元素2 …….. 假设每个 元素所占 存储单元 个数为m
Lo
Lo+m
顺序存储
Lo+(i-1)*m
元素i
……..
Lo+（n-1)*m
元素n
Loc(元素i)=Loc(元素1)+（i-1)*m
10:29
– 顺序表：
• 定义：用一组地址连续的存储单元存放一个线性表 • 元素地址计算方法：
数据元素
线性起点
ai的直接前趋 ai的直接后继
n=0时称为 空表
10:29
线性终点
下标，是元素的 序号，表示元素 在表中的位置
n为元素总个
数，即表长
例1 分析26 个英文字母组成的英文表 （ A, B, C, D, …… , Z） 数据元素都是字母; 元素间关系是线性 例2 分析学生情况登记表
学号
041810205
姓名
于春梅
性别
女
年龄
18
班级
04级计算机1班
041810260
041810284 041810360 ：
何仕鹏
：
04级计算机2班
04级计算机3班 04级计算机4班 ：
1:1
数据元素都是记录;
元素间关系是线性
同一线性表中的元素必定具有相同特性
顺序表的类型定义
#define MAXSIZE 100 //预定义最大长度 typedef struct { ElemType Elem[MAXSIZE]; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList；
线性表基本运算操作有：
查找、插入、删除
由于线性表的长度是可变的，所需的存储空间不同， 所以在C语言中，可用动态分配的一维数组来描述。
10:29
2.2
线性表的顺序表示和实现
线性表的顺序表示又称为顺序存储结构或顺序映像。 顺序存储定义：把逻辑上相邻的数据元素存储在物理 上相邻的存储单元中的存储结构。
简言之，逻辑上相邻，物理上也相邻
顺序存储方法：用一组地址连续的存储单元依次存储 线性表的元素，可通过数组V[n]来实现。
10:29
存储地址 起始地址Lo
相邻结点间的关系
抽象数据类型的定义为
线性表的基本操作
1. 初始化线性表L InitList(L) 构造一个空的线性表L，即表的初始化。 2. 销毁线性表L DestoryList(L) 其作用是销毁当前线性表L 3. 清空线性表L ClearList(L) 清空L使之成为空表 4. 求线性表L的长度 ListLength(L) 返回L的长度，即线性表中数据元素的个数 5. 判断线性表L是否为空 IsEmpty(L) 判断L是否为空表，是返回true,否返回false 6. 获取线性表L中的某个数据元素内容 GetElem(L,i,&e) 将L中第i个数据元素的值返回到变量e中
10:29
存储地址 b b+l
内存 a a
1 2
元素序号
1 2
b+（n-1）l
a
n
n
备 用 空 间
b+(maxlen-1)l
– LOC(ai)=LOC(a1)+(i-1)*m
第i个元素的地址 起始地址，基地址
// 任意两个相邻元素间地址相差m – LOC(ai+1)=LOC(ai)+m • 特点： – 实现逻辑上相邻—物理地址相邻 – 实现随机存取
每一个数据元素的存储位置都和线性表的起 始位置相差一个和数据元素在线性表中的位序 成正比的常数，因此只要确定了起始位置，线 性表中任一数据元素都可随机存取。 顺序表可以随机存取，高级程序设计语言中 的数组也有随机存取的特性。 实现：可用C语言的一维数组实现
10:29
a n）
线性结构的特点：
① 只有一个首结点和尾结点； ② 除首尾结点外，其他结点只有一个直接前驱和一 个直接后继。
简言之，线性结构反映结点间的逻辑关系是 一对一 的
线性结构包括线性表、堆栈、队列、字符串、数 组等等，其中，最典型、最常用的是
线性表
10:29
第 2章
线性表
教学目标
1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种 存储结构的不同特点及其适用场合
10:29
教学内容
2.1 线性表的类型定义 2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 线性表的应用
10:29
2.1
线性表的类型定义
线性表的定义： 由 n （ n>=0 ）个类型相同的数
据元素组成的有限序列
L=（a1, a2, … ai-1，ai, ai＋1 ，…, an）