大连理工大学：《数据结构》课程教学课件（PPT讲稿）第二章 线性表

第二章线性表 线性结构特点：在数据元素的非空有限集中 ★存在唯一的一个被称作“第一个”的数据元素 ★存在唯一的一个被称作“最后一个”的数据元素 ★除第一个外，集合中的每个数据元素均只有一个 前驱 ★除最后一个外，集合中的每个数据元素均只有一 个后继

第二章线性表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个 前驱 除最后一个外，集合中的每个数据元素均只有一 个后继

§2.1线性表的逻辑结构 ★定义：一个线性表是个数据元素的有限序列 例英文字母表(A,B,C,.Z是一个线性表 例 学号 姓名 年龄 数据元素 001 张三 18 002 李四 19 ★特征： 冬元素个数n一表长度，n=0空表 1<i<n时 ●a的直接前驱是ai,a1无直接前驱 ●a的直接后继是a+i,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线性表的顺序存储结构 ★顺序表： 冬定义：用一组地址连续的存储单元存放一个线性表叫~ 元素地址汁算方法： LOC(a)=LOC(a)+(i-1)*L ●LOC(a+)=LOC(a)+L ●其中： ◆L一一个元素占用的存储单元个数 ◆LOC(a)一线性表第i个元素的地址 特点： ●实现逻辑上相邻—物理地址相邻 ·实现随机存取 必实现：可用C语言的一维数组实现

§2.2 线性表的顺序存储结构 顺序表： ❖定义：用一组地址连续的存储单元存放一个线性表叫~ ❖元素地址计算方法： ⚫LOC(ai)=LOC(a1)+(i-1)*L ⚫LOC(ai+1)=LOC(ai)+L ⚫其中： ◆L—一个元素占用的存储单元个数 ◆LOC(ai)—线性表第i个元素的地址 ❖特点： ⚫实现逻辑上相邻—物理地址相邻 ⚫实现随机存取 ❖实现：可用C语言的一维数组实现

V数组下标 内存 元素序号 0 ar 1 typedef int DATATYPE; a2 2 #define M 1000 DATATYPE data[M]; 例typedef struct card int num; n-1 an n char name[20]; char author[10]; 备 char publisher[30]; float price, 空 DATATYPE; 间 M-1 DATATYPE library[M]; 或动态申请和释放内存 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(1≤ⅰ≤n+1)个元素 之前插入一个新的数据元素X,使长度为的线性表 (a1,a2.,a,-1,a,.an） 变成长度为n+l的线性表 a1,a2.,a,-1,x,a1,.an) 需将第i至第n共(n-i+l)个元素后移 必算法 闺 Ch2 1.txt Ch2_1.c D>

插入 ❖定义：线性表的插入是指在第I（1i  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 ar 0 a 1 a 2 1 a2 2 i-1 ai i-1 X i+1 a i+l ai+l n-】 an n-1 an-I n n n+1 n an 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是在第个元素之前插入一个元素的概率，则在长度为门 的线性表中插入一个元素时，所需移动的元素次数的平均次 数为： Ei= i=1 若认为=1 +1 1 n+1 则Ei= n+1 (n-i+1)= i=1 ∴.T(n)=O(n)

❖算法时间复杂度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 则 若认为

★删除 冬定义：线性表的删除是指将第ⅰ（1≤≤门)个元素删除 使长度为n的线性表 (a1,a2.2a,-12a,.an） 变成长度为n-1的线性表 (a1a2.a-1,a+1,.am) 需将第i+l至第n共(n-i)个元素前移 必算法 Ch2 2.txt Ch2 2.c

删除 ❖定义：线性表的删除是指将第i（1i  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 ar 0 a 1 a2 2 1 a 2 i-1 ai i-1 ai+ i aitl i+1 i a+2 计1 n-1 an n n-2 an n-1 n n+1 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是删除第i个元素的概率，则在长度为门的线性表中删除 一个元素所需移动的元素次数的平均次数为： Ee=∑，(n-i) i=l 1 若认为Q,= n 则E=之0m-)=” n j=1 2 ∴.T(n)=On) 故在顺序表中插入或删除一个元素时，平均移动表的一 半元素，当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很大时，效率很低