第二章线性表 线性结构特点:在数据元素的非空有限集中 ★存在唯一的一个被称作“第一个”的数据元素 ★存在唯一的一个被称作“最后一个”的数据元素 ★除第一个外,集合中的每个数据元素均只有一个 前驱 ★除最后一个外,集合中的每个数据元素均只有 个后继
第二章线性表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个 前驱 除最后一个外，集合中的每个数据元素均只有一 个后继
§2.1线性表的逻辑结构 ★定义:一个线性表是n个数据元素的有限序列 如(a12c2 例英文字母表(A,BC2)是一个线性表 例 学号 姓名 年龄数 数据元素 001 张三 18 002 李四 19 ★特征 今元素个数n一表长度,n=0空表 1<i<n时 a的直接前驱是a1a1无直接前驱 ●a的直接后继是a1,an元直接后继 今元素同构,且不能出现缺项
§2.1 线性表的逻辑结构 定义：一个线性表是n个数据元素的有限序列 如(a1 ,a2,,ai , an ) 例 英文字母表（A,B,C,…..Z)是一个线性表 例 学号 姓名 年龄 001 张三 18 002 李四 19 …… …… …… 数据元素 特征： ❖元素个数n—表长度，n=0空表 ❖1<i<n时 ⚫ai的直接前驱是ai-1，a1无直接前驱 ⚫ai的直接后继是ai+1，an无直接后继 ❖元素同构，且不能出现缺项
§2.2线性表的顺序存储结构 ★顺序表: 今定义:用一组地址连续的存储单元存放一个线性表叫 今元素地址计算方法 o LOC(a)=LOC(a)+(i-1)*L ●Loc(ar)=Loc(a)+L ●其中 ◆L一一个元素占用的存储单元个数 ◆LOC(a)-线性表第个元素的地址 特点: ●实现逻辑上相邻—物理地址相邻 ●实现随机存取 实现:可用C语言的一维数组实现
§2.2 线性表的顺序存储结构 顺序表： ❖定义：用一组地址连续的存储单元存放一个线性表叫~ ❖元素地址计算方法： ⚫LOC(ai)=LOC(a1)+(i-1)*L ⚫LOC(ai+1)=LOC(ai)+L ⚫其中： ◆L—一个元素占用的存储单元个数 ◆LOC(ai)—线性表第i个元素的地址 ❖特点： ⚫实现逻辑上相邻—物理地址相邻 ⚫实现随机存取 ❖实现：可用C语言的一维数组实现
V数组下标 内存 元素序号 a typedef int DATATYPE a2 2 #define m 1000 DATATYPE data MI 例 typedef struct card int num n-1 char name 201 char author 101 备用空间 char publisher 30 float price SDATATYPE DATATYPE libraryIMI 或动态申请和释放内存 DATATYPE pData=(DATATYPE")malloc(M*sizeof(DATATYPE)) free(pData)
a1 a2 an 0 1 n-1 1 2 n V数组下标 内存 元素序号 M-1 typedef int DATATYPE; #define M 1000 DATATYPE data[M]; 例 typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }DATATYPE; DATATYPE library[M]; 备 用 空 间 数据元素不是简单类型时,可定义结构体数组 或动态申请和释放内存 DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE)); free(pData);
★插入 令定义:线性表的插入是指在第(1≤i≤n+1)个元素 之前插入一个新的数据元素X,使长度为∩的线性表 15c2 变成长度为n+1的线性表 需将第i至第n共(n-i+1)个元素后移 今算法 Ch2 1.txt Ch2 1.c
插入 ❖定义：线性表的插入是指在第I（1i n+1）个元素 之前插入一个新的数据元素x，使长度为n的线性表 (a1 ,a2,,ai−1 ,ai , an ) 变成长度为n+1的线性表 (a1 ,a2,,ai−1 , x,ai , an ) 需将第i至第n共（n-i+1)个元素后移 ❖算法 Ch2_1.c
V数组下标内存元素序号V数组下标内存元素序号 0 a 0 ar a 2 a a i ai a i ai+ n-1 an n n an-1 n+1 n n+1
内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 an-1 x
算法时间复杂度T(n) ●设P是在第个元素之前插入一个元素的概率,则在长度为n 的线性表中插入一个元素时,所需移动的元素次数的平均次 数为: Es=∑P(n-l+1) 若认为P n+ 则Eis= +1 ∑(n-+1) T
❖算法时间复杂度T(n) ⚫设Pi是在第i个元素之前插入一个元素的概率，则在长度为n 的线性表中插入一个元素时，所需移动的元素次数的平均次 数为： + = = − + 1 1 ( 1) n i i Eis P n i T(n) O(n) n n i n Eis n P n i i = − + = + = + = + = 1 1 2 ( 1) 1 1 1 1 则 若认为
★删除 ☆定义:线性表的删除是指将第i(1si≤n)个元素删除, 使长度为∩的线性表 变成长度为n-1的线性表 19 i15i+15 需将第i+1至第n共(ni)个元素前移 今算法 Ch2 2.txt Ch2 2.c
删除 ❖定义：线性表的删除是指将第i（1i n）个元素删除， 使长度为n的线性表 (a1 ,a2,,ai−1 ,ai , an ) 变成长度为n-1的线性表 (a1 ,a2,,ai−1 ,ai+1 , an ) 需将第i+1至第n共（n-i)个元素前移 ❖算法 Ch2_2.c
V数组下标内存元素序号V数组下标内存元素序号 0 a 0 ar a 2 a a i ai ai ai+2 n-1 an n n- n n+1 n
内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai+1 V数组下标 0 1 i-1 n-2 i n-1 1 2 i 元素序号 i+1 n-1 n an ai+2
今算法评价 设Q是删除第元素的概率,则在长度为n的线性表中删除 个元素所需移动的元素次数的平均次数为 E=∑Q,(n-1) 若认为Q=1 则E ∑(n-1) (n)=O(m) 故在顺序表中插入或删除一个元素时,平均移动表的 半元素,当n很大时,效率很低
❖算法评价 ⚫设Qi是删除第i个元素的概率，则在长度为n的线性表中删除 一个元素所需移动的元素次数的平均次数为： = = − n i de i E Q n i 1 ( ) T(n) O(n) n n i n E n Q n i d e i = − = − = = =1 2 1 ( ) 1 1 则 若认为 故在顺序表中插入或删除一个元素时，平均移动表的一 半元素，当n很大时，效率很低