数据结构_线性表.ppt

线性表
线性表的定义和运算
线性表的概念
线性表的逻辑结构是n个数据元素的有限序列:
L=(a1, a2 ,...,an)
L为线性表,ai(i=1,...,n)是属于某数据对象的元素,n为线性表的长度(n≥0),n=0的表称为空表。
2. 线性表的定义
L=(D,R)
1
第二章常用数据结构及其运算
3. 线性表的结构特点
表中的数据元素为同一数据类型
数据元素之间是线性关系
每个元素有且只有一个前趋元素(第一个元素除外),每个元素有且只有一个后继元素(最后一个元素除外)
线性表的定义和运算
线性表
2
第二章常用数据结构及其运算
有序表与无序表的概念
若线性表中的数据元素相互之间可以比较,且ai≥ai+1 ,i=2,3,...,n(或ai≤ai+1 ,i=1,2,...,n-1),则称该线性表为有序表,否则称为无序表。
线性表的基本运算
插入、删除、查找、排序等。(按位置、按值)
线性表的定义和运算
线性表
3
第二章常用数据结构及其运算
顺序存储线性表(顺序表)
一、顺序存储结构
用一组地址连续的存储单元存放线性表的数据元素(也称为向量式存储结构)
该结构用高级语言中的一维数组类型表示。例如:可用一维数组A[n]来存储线性表: (a1, a2 ,...,an)。
地址计算: addr(ai)=addr(a1)+(i-1)*L
特点:随机存储结构(查找方便)。
线性表
4
第二章常用数据结构及其运算
例:
a1
a2
a3
a4
a5
a6
…
2000H
2001H
……
2005H
addr(a4) = addr(a1) + (i-1)×L = 2000H+(4-1)×1=2003H
5
第二章常用数据结构及其运算
二、顺序存储结构的插入与删除

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所示。
线性表
顺序存储线性表
6
第二章常用数据结构及其运算
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); //执行成功,返回}
线性表
顺序存储线性表
7
第二章常用数据结构及其运算
2. 删除
1)概念:删除第i个位置上的元素,使线性表的长度由n变为n-1。
2)删除过程:ai+1~an依次前移一个位置(共移动n-i个元素) 。(合法位置:1<=i<=n)参见教材27页图2-4所示。
线性表
顺序存储线性表
8
第二章常用数据结构及其运算
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);  }
线性表
顺序存储线性表
9
第二章常用数据结构及其运算
运算的时间分析
在插入和删除运算中,时间主要消耗在移动元素上。
设pi-在第i个元素前插入一个元素的概率,则在长度为n的线性表中插入一个元素所需的平均移动次数为:
线性表
顺序存储线性表
10
第二章常用数据结构及其运算