(4)效率评价 顺序表的插入和删除算法的执行时间主要用在元素 的前后移动上 以插入为例:当I=0时,(即在排首插入)则需要移动 二N个元素,当1=1时,则需要移动N1个元素,当L=N-1 时,则需要移动1个元素,设插入新元素在表中的各位置 概率相等,则插入时,平均移动元素的次数是 M(D)=[(n-1)+(n-2)+…+(n-1)]/(n+1)=n/2 删除时,平均移动元素的次数是 M(D)=)=[(n-1)+(n-2)+…+n-)/n=(n-1)2 这说明,在顺序表上进行一次插入或删除平均需要移 动一半的元素,这两个算法的执行时间的时间复杂度为 O(N)。 (5)应用举例:两个有序表合并 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 顺序表的插入和删除算法的执行时间主要用在元素 的前后移动上. （4）效率评价 以插入为例：当I=0时，（即在排首插入）则需要移动 N个元素，当I=1时，则需要移动N－1个元素，当I=N-1 时，则需要移动1个元素，设插入新元素在表中的各位置 概率相等，则插入时，平均移动元素的次数是 M(I)=[(n-1)+(n-2)+…..+(n-i)]/(n+1)=n/2 删除时，平均移动元素的次数是 M(D)= )=[(n-1)+(n-2)+…..+(n-i)]/n=(n-1)/2 这说明，在顺序表上进行一次插入或删除平均需要移 动一半的元素，这两个算法的执行时间的时间复杂度为 O(N)。 （5）应用举例：两个有序表合并
23线性表的链接存储结构及运算 231链表和指针 (1)链表的定义用链接方法存储的线性表称为线性 链表简称链表。 (2)表示方法每一个结点的存储内容分成两个部分 一部分用来存储结点的值,称为数值字段(又称数值 域),一部分用来存储结点之间关系的,称为指针字段 (又称指针域)。 (3)链表的类型按每个结点所含指针字段的个数, 分为:单链表和双链表两种。 指针:存储其他结点位置信息的域称为指针域,指 针城中存储的信息称为指针或链 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 （1）链表的定义 用链接方法存储的线性表称为线性 链表,简称链表。 （2）表示方法 每一个结点的存储内容分成两个部分： 一部分用来存储结点的值，称为数值字段（又称数值 域），一部分用来存储结点之间关系的，称为指针字段 （又称指针域）。 （3）链表的类型 按每个结点所含指针字段的个数， 分为 ：单链表和双链表两种。 2.3 线性表的链接存储结构及运算 2.3.1 链表和指针 指针：存储其他结点位置信息的域称为指针域，指 针域中存储的信息称为指针或链