《数据结构-02 线性表》由会员分享，可在线阅读，更多相关《数据结构-02 线性表（186页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加,2. 1 线性表的概念,线性表（Linear List）：n(n0)个数据元素a1, a2, , an 组成的有限序列，一般记作 List=(a1，a2，an) 其中， List为线性表的名字。数据元素的个数n定义为表的长度。 当 n=0 时称为空表，记作 ( ) 或 ,一般要求元素的类型相同。二元组表示 List = 其中 D = ai | ai ElemSet, i=1, 2, . n, n 0 S = R R = | ai-1, ai D, i=1,
2、2, . n, n 0 ,定义,同构,线性,姓名 电话号码蔡颖 63214444陈红 63217777刘建平 63216666王小林 63218888张力 63215555.,例1 数列（11，13，15，17，19，21）。 例2 英文字母表（A, B, C, D, E Z ）。 例3 电话号码表。,ADT List 数据对象： D = ai | ai ElemSet, i=1, 2, . n, n 0 数据关系：R = | ai-1, ai D, i=1, 2, . n, n 0 基本操作：InitList( /遍历表 ADT List,例2-1 求并集 LA=LALB void unio
3、n(List ,用基本运算构造算法,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A,La,例2-1 求并集 LA=LALB v
4、oid union(List ,用基本运算构造算法,Q W E R T Y V P Z A,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A S,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A S,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q
5、W E R T Y V P Z A S D,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A S D,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A S D,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A S D,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z
6、A S D,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A S D,La,例2-1 求并集 LA=LALB void union(List ,用基本运算构造算法,Q W E R T Y V P Z A S D K,La,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb,
7、List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, Lis
8、t Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List L
9、a, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,例2-2 有序表归并 void MergeList(
10、List La, List Lb, List ,例2-2 有序表归并 void MergeList( List La, List Lb, List ,2. 2 线性表的顺序表示和实现,1 顺序存储 顺序表 2 链式存储 链表,顺序表(Sequential List) ：用顺序存储的线性表，即把线性表的结点按逻辑次序依次存放到一组地址连续的存储单元里 。,顺序表通过 元素的存储顺序 反映逻辑关系,Loc(i)Loc(1)( i1 ) c,2. 2 线性表的顺序表示和实现,typedef int Elemtype ; /结点的数据类型，假设为intconst int maxsize=100 ; /
11、最大表长度，假设为100typedef struct Elemtype elemmaxsize ; /第一个结点是elem0int length; /当前长度 Sqlist1 ; /顺序表类型,typedef int Elemtype ; /结点的数据类型，假设为inttypedef struct Elemtype *elem ; /第一个结点是elem0int length; /当前长度int listsize ; /当前分配容量 Sqlist ; /顺序表类型,1构造空表,在表的第i（1in+1）个位置上，插入一个新结点x，使长度为n的线性表(a1,ai1,ai,an)变为长度为n+l的线
12、性表(a1,ai1,x,ai,an)。,2插入,先将表中位置in上的结点全部后移一位以空出第i个位置，然后在该位置上插入新结点x，最后表长加1。 注意：移动只能从后向前进行，即按n,n1,i的次序进行。,int ListInsert ( Sqlist *L, ElemType x, int i )/将x插入到顺序表L的第 i 个位置上int j ;if ( Ln = maxsize ) cout Ln+1 ) cout n ; j=i ; j )Lelem j = L elem j1 ; /结点后移L elem i1 = x ; /插入x，第i个结点的数组下标是i1Ln+; /修改表长retu
13、rn 1; /插入成功 ,移动次数Ci=ni+1。最少0（i=n+1）最多n（i=1）。 设Pi=1/(n+1) ，平均,3删除,将表的第i（1in）个结点删去，使长度为n的线性表(a1,ai1,ai,ai+1,an)变为长度为n1的线性表(a1,ai1,ai+1,an-1)。,先将表中位置i+1n上的结点全部前移一位以填补删除操作造成的空缺。最后表长减1。 注意：移动只能从前向后进行，即按 i+1, i+2, , n 的次序进行。,int ListDelete( Sqlist *L, int i ) /从顺序表中删除第i个位置上的结点int j;if ( L length = 0 ) cout Ln ) cout n ; j+ )Lelemj2=Lelemj1 ; /结点前移Ln; /修改表长return 1; /删除成功 ,
