线性表习题讲解32页PPT

2). 删除操作：
删除第 i（1≦i≦n) 个元素e
思想：把第i＋1个元素（下标为i）开始的元素，
依次前移
步骤：
1.要检查删除位置的有效性。 2.依次移动元素 3.长度减1
顺序表上的删除元素操作
请看教材P.24.图2-4 ElemType SeqListDelete(SeqList L,int i)
线性表的逻辑结构典型题解析
选择题 【说明】：本节内容比较简单， 只需注意线性表的定义和逻辑特 征。
线性表的逻辑结构典型题解析
选择题1： 线性表是具有n个（ ）的有限序 列。
A．数据
B．字符
C．数据元素 D．数据项
【解答】 C
【分析】 数据的逻辑结构是指数据元素之间逻
辑关系的整体。线性表中数据元素之间的逻辑
第二章 线性表
有序（次序）表， 不是值有序
基本知识点：线性表的逻辑结构特点，线性表的 两种存储结构以及在这两种存储结构下线性表基 本运算的实现算法，顺序表与链表的优缺点比较。
线性结构是一个数据元素的有限序列
重点：掌握线性表的定义和特点，线性表的存储 结构，顺序表和链表的组织方法和相关算法设计。
请与教材 p.31.算法进 行比较
顺序表按值查找算法
int SeqListLocate(SeqList L, ElemType x)
{ //在顺序表L中查找第一个与x值相等的元素。若查找 //成功，则返回它在顺序表中的位置；否则，返回0。
for(i=0; i<L.length; i&#x) return i+1;
i 1
设在第i个 位置删除的概率为pi；
pi 1 n
n
1n
n 1
Ede pi(n i) (n i)

构造原理
用一组地址连续的存储单元依次存储线性表的数据元素，数 据元素之间的逻辑关系通过数据元素的存储位置直接反映。
k个单元 (a1,a2,a3,... ...,an)
a1 a2 a3
……
an
LOC(ai)
d1+k=d2 d3
………
dn
所谓一个元素的地址是指该元素占用的
若干(连续的)存储单元的第一个单元的地址。
LOC(a5)=100+(5-1)*4=116
线性表 11
顺序存储结构示意图
(a1,a2,a3,... ...,an)
当前已经占用的空间
尚未使用的空间
a1 a2 a3 … … an-1 an
01 2
n-2 n-1 n
……
n+1
M-1
事先分配给线性表的空间
线性表 12
一般来说，长度为n的线性表(a1,a2,…,an)在计算机中 的结构如下：
INSERT(L,x,i)。 6.删除线性表中第i个数据元素DELETE(L,i)。 7.对线性表中的数据元素进行升序或者降序排序。 8.将两个或两个以上的线性表合并成为一个线性表。 9.将一个线性表分解为两个或两个以上的线性表路】 依次输出线性表中的每个元素的值。
编写在线性表A中删除线性表B中出现的元素的算法。
1 3 57 9
12346
579
【算法思路】 依次检查线性表B中的每个元素，看它是否在线性表
A中。若在A中，则将其从A中删除。
线性表
5
void delete(Sqlist *A,Sqlist *B) {
int i,k;
datatype x;
for(i=1;i<=LENGTH(B);i++) {

一个(尾)结点。
.
4
a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接 前驱; ai+1，ai+2，…an都是ai(1≦i ≦n-1)的后继，其中ai+1是ai的 直接后继。
2.1.2 线性表的逻辑结构
线性表中的数据元素ai所代表的具体含义随具体应 用的不同而不同，在线性表的定义中，只不过是一个抽 象的表示符号。
以下将对几种主要的操作进行讨论。

1 顺序线性表初始化
Status Init_SqList( SqList *L )
{ L->elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ;
if ( !L -> elem_array ) return ERROR ;
ListInsert ( L, i, &e )
初始条件：线性表L已存在，1≦i≦ListLength(L) ；
操作结果：在线性表L中的第i个位置插入元素e；
…
.
8
} ADT List
2.2 线性表的顺序存储
2.2.1 线性表的顺序存储结构
顺序存储 ：把线性表的结点按逻辑顺序依次存放在 一组地址连续的存储单元里。用这种方法存储的线性表 简称顺序表。
在具体的机器环境下：设线性表的每个元素需占用L 个存储单元，以所占的第一个单元的存储地址作为数据元素 的存储位置。则线性表中第i+1个数据元素的存储位置 LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足 下列关系：
LOC(ai+1)=LOC(ai)+L
线性表的第i个数据元素ai的存储位置为：

③ 将该位置后的元素依次向前移动一个位置；
④ 修改当前表的长度；
17
2.2 线性表的顺序表示和实现--顺序表
/*在顺序表中删除第i个元素*/ int ListDelete_sq(SqList &L,int i,ElemType &e){ int k; /*删除位置不合法*/
if(i<1||i>L.length) return ERROR;
a1 a2 a3
……
ai-1
ai L.length L.listsize
10
2.2 线性表的顺序表示和实现--顺序表
3 顺序表的基本操作
顺序表的初始化
为顺序表分配一个预定义大小的一段连续单元， 并将其初始长度设为0。
int InitList_sq(SqList &L) { L.elem=(ElemType *)malloc( LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) return ERROR; //初始化失败 L.length=0; //置空表长度为0 L.listsize=LIST_INIT_SIZE; //置初始空间容量 return OK; // 初始化成功，返回1 } //InitList_sq
采用一组任意的存储单元来存放线性表中的数据元 素，这些存储单元可以是连续的，也可以是不连续的。 数据元素间的逻辑关系通过附加信息－指针来描述。 数据元素除了具有代表其本身信息的数据域外，还 有一个用来指示逻辑关系的指针域。这两部分信息组成 数据元素的存储映像，称为结点。
数据域 data 指针域 next
}
O(La_len×Lb_len)
5
2.2 线性表的顺序表示和实现--顺序表

}// Delete_Between
第十五页，共23页。
例2、有一单链表（不带头结点）头指针为head，试设计一算法使得单链表
插入x后仍递增有序。
Status Insert(Linklist &head, Elemtype x){ //不带头结点单链表插入x后仍递增有序 s=(LinkList)malloc(sizeof(Lnode)); s->data=x; s->next=NULL; if(head=NULL||x<head->data)
第六页，共23页。
3、线性表的单链表存储结构
（1）存储结构的定义
typedef struct LNode{
Elemtype data;
struct LNode *next;
}Lnode, *LinkList;
第七页，共23页。
（2）操作的实现
Status GetElem_L(LinkList L,int i,ElemType &e){ //L为带头结点的单链表的头指针
//带头结点的单链表head就地逆置
LNode *p, *q;
p=head->next;
//指向开始结点
head->next=NULL;
//逆置后初表为空
while(p)
//p为NULL，表示已经全部逆置
{q=p->next;
//p指向下一个需要逆置的结点
p->next=head->next; //将需要逆置结点插入头结点后面
}// CreatList_L
第十一页，共23页。
二、作业点评
2.11 设顺序表va中的数据元素递增有序。试编写一算法，将x插入到顺序表的适当位

2024/1/30
顺序存储定义
用一段地址连续的存储单元依次 存储线性表的数据元素。
存储方式
逻辑上相邻的元素，其物理存储 位置也相邻。
8
顺序表基本操作实现
初始化操作
创建一个空表，分配存储空间。
插入操作
在指定位置插入一个元素，需移动插入位置后的所有元素。
删除操作
删除指定位置的元素，需移动删除位置后的所有元素。
数据结构线性表ppt课 件
2024/1/30
1
目录
2024/1/30
• 线性表基本概念与特点 • 顺序存储结构及其实现 • 链式存储结构及其实现 • 线性表应用与案例分析 • 线性表性能分析与优化策略 • 总结回顾与拓展延伸
2
01
线性表基本概念与特点
2024/1/30
3
线性表定义及性质
线性表定义：由n（n>=0）个具有相 同类型的数据元素（结点）a1，a2，
动态分配
如果使用动态数组或链表实现线性表，空间复杂度为O(n)，其中n为当前线性表中的元素数量。这种 实现方式可以灵活应对元素数量的变化。
2024/1/30
26
优化策略探讨
使用更高效的数据结构
例如，可以使用哈希表或二叉搜索树等数据结构 来优化查找操作的时间复杂度。
批量操作优化
对于批量插入、删除或查找操作，可以通过一次 性处理多个元素来减少操作次数，从而提高效率 。
任何一种逻辑结构都可以用多种存储结构表示。
03
5
线性表基本操作
插入操作
在指定位置插入一 个元素。
查找操作
查找指定元素的位 置。
初始化操作
建立一个空的线性 表。
2024/1/30

2
因此插入算法的平均时间复杂度为O(n)。
(9) 删除数据元素ListDelete(L,i,e)
删除顺序表L中的第i(1≤i≤ListLength(L))个元 素。
思路：如果i值不正确,则显示相应错误信息； 否则将线性表第i个元素以后元素均向前移动一个 位置,这样覆盖了原来的第i个元素,达到删除该元 素的目的,最后顺序表长度减1。
2.2.2 顺序表基本运算的实现
一旦采用顺序表存储结构,我们就可以用C/C++ 语言实现线性表的各种基本运算。为了方便,假设 ElemType为char类型,使用如下自定义类型语句:
typedef char ElemType;
1. 建立顺序表 其方法是将给定的含有n个元素的数组的
每个元素依次放入到顺序表中，并将n赋给顺 序表的长度成员。算法如下：
void unionList(List LA,List LB,List &LC) {
int lena,lenc,i; ElemType e; InitList(LC); for (i=1;i<=ListLength(LA);i++)
/*将LA的所有元素插入到Lc中*/ { GetElem(LA,i,e);
int ListEmpty(SqList *L) {
return(L->length==0); }
本算法的时间复杂度为O(1)。
(4) 求线性表的长度ListLength(L)
该运算返回顺序表L的长度。实际上只需返回 length成员的值即可。
int ListLength(SqList *L) {
} }
由 于 LocateElem(LA,e) 运 算 的 时 间 复 杂 度 为 O(ListLength(LA)),所以本算法的时间复杂度为:

（二）线性表的删除(1)
1﹑删除下标为i的 数据元素
例2.3 为在V[0]到V[99] 中删除一个元素 V[i],引用del1函数。 删除前后的线性表 的示意图如右
举例（续）
分析： ①初始条件： 数组V，
删除下标i ②删除条件：0≤i≤99 ③执行结果：1成功,0
不成功 ④N-S流程图如右:
举例（续）
(一)线性表插入操作(1)
1、在数组中下标为i的元 素前插入一个新元素。
例2.1 某Ｃ语言程序中， 整型数组Ｖ的９９个元数 Ｖ［０］～Ｖ［９８］组 成一个线性表。为了在Ｖ ［i］位置前插入一个新元 素b，可用如下函数inst1 来实现，当插入成功时返 回1，否则返回0，所以该 函数的返回值类型是整型。 插入前后的线性表的示意 图如右：
第二章 线性表
2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3线性表的链式存储结构 2.4 典型例题
线性表的特点是：在数据元素的非空有
限集中，（1）存在唯一的一个被称为 “第一个”的数据元素；（2）存在唯一
的一个被称为“最后一个”的数据元素； （3）除第一个以外，集合中的每一个数 据元素均有且只有一个前驱；（4）除最
V[99]=0; /*数组最后一个元素清0或某种结束标记*/ return 1; /*删除成功 */ }
线性表的删除操作(2)
2﹑在有序顺序表 中删除一个数据 元素
例2.4 在有序表中 删除一个值为x的 数据元素。当x的 值为78时删去前 后的线性表的
示意图如右：
举例（续）
分析： ①初始条件：数组
return 0; /*插入失败*/
} for (j=99；j>i；j--) v[j]=v[j-1];/*后移*/ v[i]=b； /*插入*/ return 1； /*插入成功 */ ｝

线性表与数组关系
联系
数组是一种特殊的线性表，其元素按照顺序存储在连续的内存空 间中，可以通过下标直接访问元素。
区别
线性表是一种更为抽象的数据结构，它只规定了元素之间的逻辑 关系，而并没有规定元素的具体存储方式。数组则是一种具体的 存储结构，它规定了元素在内存中的存储方式和访问方式。此外 ，线性表还支持动态调整大小，而数组的大小在定义时需要确定 ，不能动态调整。
80%
复杂度分析
多项式计算的复杂度与多项式的 项数有关，通常为O(n)，其中n 为多项式的项数。
一元多项式相加问题
问题描述
01
给定两个一元多项式，求它们的和。
解决方案
02
将两个多项式分别用线性表表示，然后遍历两个线性表，将相
同指数的项相加，得到新的线性表表示的和多项式。
示例代码
03 略
稀疏矩阵压缩存储问题
数据结构线性表pptppt课件
目
CONTENCT
录
• 线性表基本概念与特点 • 顺序存储结构及其操作 • 链式存储结构及其操作 • 线性表应用举例与问题分析 • 线性表性能评价与改进策略 • 总结回顾与拓展延伸
01
线性表基本概念与特点
线性表定义及逻辑结构
线性表定义
线性表是一种具有n个元素的有限序 列，其中元素按照顺序排列，每个元 素有且仅有一个前驱和一个后继（除 首尾元素外）。
删除操作
删除指定位置的元素，需要移 动删除位置之后的元素，时间 复杂度为O(n)。
查找操作
顺序查找的时间复杂度为O(n) ，二分查找的时间复杂度为 O(log n)（针对有序线性表） 。
空间复杂度分析
静态分配
预分配固定大小的数组空间，空间复 杂度为O(1)。

删除算法
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

//返回数据元素的位置 return 0; //退出循环，说明查找失败 }
注意返回的 是位置，而 不是下标， 即返回逻辑 序号，而不 是物理序号
27
线性表的顺序存储结构及其实现
• 考核知识点 5. 顺序表的优缺点(★★★)
优点：
算法简单，容易实现；
可以实现随机存取。
缺点：
插入和删除操作复杂，移动大量的数据元素（大约是 表长的一半），在插入操作时，还要涉及到重新分 配大块空间的问题（表的容量难以确定）。
1.当前表是否已经满？ 2.输入是否有效？ 3.插入元素
18
顺序表上的插入操作 该算法注意检查边界条件。
如位置i＝length＋1时，即插
入在最后一个元素后；而i＝
void SeqListInsert(SeqList L,int i,ElemType x)
1时，表示插入在表头
{ //在顺序表中的第 i 个位置插入元素 x
L.data[j+1]=L.data[j]; //第i个位置后的数组元素逐一后移
L.data[i-1]=x;
//新元素插入到第i个位置
L.length++;
//顺序表长度加1
}
插入结果看教材P.23.图2-3
思考：如果for循环改为如下： for(j=i-1；j<=L.length-1;;j++)
结果将如何？
10
线性表的逻辑结构典型题解析
• 选择题3：关于线性表，下列说法中正确的是（ ）。 A．线性表中每个元素都有一个直接前驱和一个直接后继； B．线性表中的数据元素可以具有不同的数据类型； C．线性表中数据元素的类型是确定的； D．线性表中任意一对相邻的数据元素之间存在序偶关系； 【解答】 D 【分析】 线性表的第一个元素无前驱，最后一个元素无后继；线