数据结构讲义第二章.ppt

表初始化 求表长度 按序号求元素* 查找元素* 插入元素* * 删除元素* * 2.2.2 顺序表运算的实现 * back 插入运算list_insert(L,i,x)** 定义： 在第i（1?i ? n+1）个元素前插入一个新的数据元素x，使长度为n的线性表 (a1，a2，……，ai-1，ai，……，an) 变成长度为n+1的线性表 (a1，a2，……，ai-1，x，ai，……，an) 算法分析： back a1 a2 a3 a4 a5 a7 a6 a8 b a1 a2 a3 a4 a5 a7 a6 a8 b 顺序表的插入： 表的长度+1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 back void list_insert (seqlist L,int i,elementtype x) { int j; if(i1||iL.listlen+1) error(position error); if(L.listlen=maxlen) error (overflow);} for(j=L.listlen-1；j=i-1；j--) L.data[j+1]=L.data[j]; //插入位置之后元素后移 L.data[i-1 ]=x; ++L.listlen; } back 插入算法时间复杂度T(n) 设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的期望值（平均次数）为： back back 顺序表的删除运算 list_delete(L,i)** 定义： 线性表的删除是指将第i（1?i ? n）个元素删除，使长度为n的线性表 (a1，a2，……，ai-1，ai，ai+1，……，an) 变成长度为n-1的线性表 (a1，a2，……，ai-1， ai+1， ……，an) 算法分析： 需将第i+1至第n共（n-i）个元素前移 back a1 a2 a3 a4 a5 a7 a6 a8 顺序表的删除： 0 1 2 3 4 5 6 7 i=4 a1 a2 a3 a4 a5 a7 a6 a8 0 1 2 3 4 5 6 7 i=4 表长-1 back void list_delete(seqlist L,int i) { int k; if(i1||iL.listlen) error(删除位置错); for(k=i;k=L.listlen-1;++k) L.elem[k-1]=L.elem[k]; // 被删除元素之后的元素左移 - -L.listlen; // 表长减1 } 顺序表删除第i位置元素的算法： back back 删除结点的算法时间复杂度 设去qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的(期望值）平均次数为： back 查找运算list_locate(L,x) int list_locate(seqlist L,elementtype x) {//返回元素x在顺序表L中的序号 int i; for( i=0 ; iL.listlen ; i++) if (L.data[i]==x) return i+1; return 0; } back 思考： 如果在一个有序的顺序表中在插入一个新的元素，让表仍为有序表，算法如何写？怎样的算法时间复杂度能最小 2.3 线性表的链式存储结构 1 2 2.3.1 链表结构的定义 3 2.3.2 链表运算的实现 * * 2.3.3 其他形式的链表结构 * 上一层 2.3.1 链表结构的定义 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 数据域 指针域 结点 back ZHAO QIAN SUN LI ZHOU WU ZHENG WANG