nullnull第二章 常用数据结构及其运算*2.2 线 性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
2.2.1 线性表的定义和运算线性表的概念
线性表的逻辑结构是n个数据元素的有限序列:
L=(a1, a2 ,...，an)
L为线性表，ai(i=1,...，n)是属于某数据对 象的元素，n为线性表的长度(n≥0)，n=0的表称为空表。
2. 线性表的定义
L=（D，R）
null第二章 常用数据结构及其运算*3. 线性表的结构特点
表中的数据元素为同一数据类型
数据元素之间是线性关系
每个元素有且只有一个前趋元素(第一个元素除外)，每个元素有且只有一个后继元素(最后一个元素除外)2.2.1 线性表的定义和运算2.2 线 性 表null第二章 常用数据结构及其运算*有序表与无序表的概念
若线性表中的数据元素相互之间可以比较，且ai≥ai+1 ，i=2，3，...，n（或ai≤ai+1 ，i=1，2，...，n-1），则称该线性表为有序表，否则称为无序表。
线性表的基本运算
插入、删除、查找、排序等。(按位置、按值)2.2.1 线性表的定义和运算2.2 线 性 表null第二章 常用数据结构及其运算*2.2.2 顺序存储线性表（顺序表）一、顺序存储结构
用一组地址连续的存储单元存放线性表的数据元素（也称为向量式存储结构）
该结构用高级语言中的一维数组类型表示。 例如：可用一维数组A[n]来存储线性表： （a1, a2 ,...，an）。
地址计算： addr(ai)=addr(a1)+(i-1)*L
特点：随机存储结构(查找方便)。2.2 线 性 表null第二章 常用数据结构及其运算*例：addr(a4) = addr(a1) + (i-1)×L = 2000H+(4-1)×1=2003Hnull第二章 常用数据结构及其运算*二、顺序存储结构的插入与删除
1.插入
1)概念：有线性表(a1,a2 ,...，an)，长度为n，要在第i-1与第i个元素之间插入一个新元素。使得线性表变为：(a1,a2 ,... ai-1,x, ai,...,an), 长度为n+1。
2)插入过程：将ai至an依次后移一个位置(共移动n-i+1个元素)，然后将新元素插入在第i个位置上(合法位置：1<=i<=n+1)。请参见教材27页图2-3所示。2.2 线 性 表2.2.2 顺序存储线性表null第二章 常用数据结构及其运算*3)算法描述
int InsertList(L[m],n,i,x) //形式参数 { if (i<1 || i>n+1) return(0); //位置非法 for (j=n;j>=i;j--) L[j+1]=L[j]; //移动元素 L[i]=x; //插入元素 n++; //长度加1 return(1); //执行成功，返回 }2.2 线 性 表2.2.2 顺序存储线性表null第二章 常用数据结构及其运算*2. 删除
1）概念：删除第i个位置上的元素，使线性表的长度由n变为n-1。
2）删除过程：ai+1～an依次前移一个位置(共移动n-i个元素) 。(合法位置：1<=i<=n)参见教材27页图2-4所示。2.2 线 性 表2.2.2 顺序存储线性表null第二章 常用数据结构及其运算*3）算法描述
int DeleteList(L[m],n,i) { if (i<1 || i>n) return(0); //参数不合法 for (j=i;j<=n-1;j++) L[j]=L[j+1]; //前移 n--; //表长减1 return(1); }2.2 线 性 表2.2.2 顺序存储线性表null第二章 常用数据结构及其运算*运算的时间分析
在插入和删除运算中，时间主要消耗在移动元素上。
设pi－在第i个元素前插入一个元素的概率，则在长度为n的线性表中插入一个元素所需的平均移动次数为： 2.2 线 性 表2.2.2 顺序存储线性表null第二章 常用数据结构及其运算*在等概率情况下，pi=1/(n+1)，则有： 同理，删除时有： 在等概率情况下，qi=1/n，则有：2.2 线 性 表2.2.2 顺序存储线性表问题：顺序表插入、删除的时间复杂度？O(n)null第二章 常用数据结构及其运算* 4.顺序表特点：
优点：存储效率高、查找方便。
缺点：
1)插入删除代价高(插入或删除一个元素，平均需要移动表中一半的元素),仅适用于不经常进行插入和删除运算以及表中元素相对稳定的场合。
2)要求连续存储区，管理不灵活，元素删除后不能释放空间。2.2 线 性 表2.2.2 顺序存储线性表null第二章 常用数据结构及其运算*2.2 线 性 表2.2.2 顺序存储线性表三、顺序存储结构的应用举例
1.约瑟夫环问题 设有n个人围坐一圆桌，现从第S个人开始报数，数到第m个人出列，然后从下一个人重新报数，数到第m个人又出列，……直到全部出列为止。对任意给定n、s、m，求出列得到的n个人的出列顺序表。null第二章 常用数据结构及其运算*2.2 线 性 表 解：(1) 置初值 S1<－S, ( S1=1)
(2) 报数出列
循环 i 以(-1)为步长从 n 到 2 执行
S1 <－ (S1+m-1) MOD i
若S1＝0，则S1<－i ;
W <－ P[S1] ; // W记录出列者
循环 j 从S1到 (i-1) 执行
P[j] <－ P[j+1] ; P[i] <－ W ; //前移
(3) 逆转向量
循环 k 从 1 到 [n/2](向下取整)，执行
W <－ P[x]; P[k] <－ P[n-k+1]; P[n-k+1] <－ W
(4) 算法结束n=8, s=1, m=4……null第二章 常用数据结构及其运算*2.2 线 性 表2.2.2 顺序存储线性表三、顺序存储结构的应用举例
2.顺序表合并 将两个有序顺序表A（有m个元素）和B（有n个元素），合并为一个有序线性表C。null第二章 常用数据结构及其运算*2.2 线 性 表解：LINK (A, m, B, n, C)
{ i=0; j=0; t=0; k=0;
while (i
B[j]) C[k++]=B[j++];
else { C[k++]=B[j++]; //相等者只保存一个
i++; }
}
if ( i= =m) //B未完，将B余下的元素赋给C
for (t=j; tdata); s->next=NULL; //生成结点并赋值 if (h==NULL) h=s; else pre->next=s; pre=s; //结点指针链接 } return(h); //返回链表头指针 }2.2.3 线性链表2.2 线 性 表三、单链表
3.线性链表的建立（补充）null第二章 常用数据结构及其运算*
1）问题描述：在值为a的结点前插入一个值为x的结点。若链表为空，则x成为其头结点；若表中无a元素，则将x插入表尾。2.2.3 线性链表2.2 线 性 表三、单链表
4.插入运算null第二章 常用数据结构及其运算*2）算法描述
InsertList(head,a,x) { GETNODE(p); data(p) <- x; //取得一个新结点p if (head==nil) then { //空表 head=p; next(p) <- nil; return; } if (data(head)==a)then{ //a为头结点 next(p) <- head; head <- p; return; } q=head; while (next(q)!=nil) && data(next(q))!=a) q <- next(q); //查找a之前的结点q next(p) <- next(q); next(q) <- p; //完成插入 }2.2.3 线性链表2.2 线 性 表null第二章 常用数据结构及其运算*
1）问题描述：将值为a的结点删除。2.2.3 线性链表2.2 线 性 表三、单链表
5.删除运算null第二章 常用数据结构及其运算*2）算法描述
DeleteList(head,a) { if (head==nil) return; //空表 if (data(head)==a)then{ //a为头结点 p<-head; head<-next(head); RET(p); return; } LOOKFOR(head,a,q); if (next(q)= =nil) then {return;} p<-next(q); next(q)<-next(p); RET(p); //完成删除 return;
}2.2.3 线性链表2.2 线 性 表null第二章 常用数据结构及其运算*
2.2.3 线性链表2.2 线 性 表三、单链表
5.算法运算时间分析
在单链表中插入或删除一个结点时，仅需改变 一个或两个指针，而无需移动元素。null第二章 常用数据结构及其运算* 1）在链表的第一个结点之前附加一个头结点2.2.3 线性链表2.2 线 性 表四、线性链表的其他形式
1.带头结点的线性链表 头结点：
数据域－不 用，或用于存放其它信息，如表长。
指针域－指向链表的第一个结点。null第二章 常用数据结构及其运算* 2）头结点的用处：可简化算法的形式，例如在插入运算中，当表空时尚有头结点存在，因此头指针非空，当a为表中第一个元素时，因有头结点存在，则在a结点之前插入一元素时不必修改头指针。2.2.3 线性链表2.2 线 性 表null第二章 常用数据结构及其运算* 表中最后一个结点指向表的第一个结点，整个链表形成一个环。（只要给定循环链表中任一结点的地址，就可以查遍表中所有的结点，而不必从头指针开始）2.2.3 线性链表2.2 线 性 表四、线性链表的其他形式
2.循环链表null第二章 常用数据结构及其运算* 优点：提高查找效率
思考：如何判断循环链表的表尾？
（单链表：判断指针域为空）2.2.3 线性链表2.2 线 性 表四、线性链表的其他形式
2.循环链表null第二章 常用数据结构及其运算* 逻辑结构:2.2.3 线性链表2.2 线 性 表四、线性链表的其他形式
3.双向链表null第二章 常用数据结构及其运算*2.2.3 线性链表2.2 线 性 表四、线性链表的其他形式
3.双向链表 特点：一个结点有两个指针域，容易找到前驱。
双向链表的插入：在P结点之后插入值为y的结点GETNODE(q);
data(q)<－y;
next(q)<－next(p);
next(p)<－q;
prior(next(q))<－q;
prior(q)<－p;null第二章 常用数据结构及其运算*2.2.3 线性链表2.2 线 性 表四、线性链表的其他形式
3.双向链表 双向链表的删除：删除结点P。next(prior(p))<－next(p);
prior(next(p))<－prior(p);
RET(p);null第二章 常用数据结构及其运算*2.2.3 线性链表2.2 线 性 表五、链表应用举例
1.一元多项式相加 结点结构：每一个非零项构成链表中的一个结点， 结点由两个数据域和一个指针域构成：null第二章 常用数据结构及其运算* 链表结构：采用带头结点的线性链表表示多项式A(x)、B(x)，相加后结果在线性链表C(x)中。
运算过程：A(x)－头指针ha， p的初始位置指向第一项。
B(x)－头指针hb， q的初始位置指向第一项。 比较p、q所指结点中的指数项，若： exp(p)exp(q)，则q所指的结点为C(x)中的一项，令p 指针后移一个结点；
exp(p)==exp(q)，则将两个结点中的系数相加，当和不为 零时，修改p结点中的系数，释放q结点； 否则，删去p结点，同时释放p、q结点。2.2.3 线性链表2.2 线 性 表null第二章 常用数据结构及其运算*AddPoly(ha,hb) { p<-next(ha); q<-next(hb); pre=ha; hc=ha; //有关指针变量赋初值 while (p!=nil && q!=nil){ if(exp(p)exp(q)){ //大于 u<-next(q); next(q)<-p; next(pre)<-q; pre<-q; q<-u; } if (exp(p)=exp(q)){ //等于 x<-coef(p)+coef(q); if (x!=0){ coef(p)<-x; pre<-p; } else{ next(pre)<-next(p); RET(p); } p<-next(pre); u<-q; q<-next(q); RET(u); }
}
if (q!=nil) next(pre)<-q;//剩余
结点链接 RET(hb); }null第二章 常用数据结构及其运算*2.2.3 线性链表2.2 线 性 表五、链表应用举例
2.在带表头结点的单链表结构上查找值为x的结点LOOKFOR(head, x, p)
{
p<－next(head);
for( ; p!=nil && dada(p)!=x)
p<－next(p);
return;
}null第二章 常用数据结构及其运算*2.2.3 线性链表2.2 线 性 表五、链表应用举例
3.将两个有序单链表合并为一带表头的有序单链表Merge (P1, P2)
{ GETNODE(ch);
p<-ch; next(p)<-nil;
while((P1!=nil)&&(P2!=nil))
{ if(data(P1)
本文档为【数据结构_线性表】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483