数据结构_第2章.pptVIP

析构函数 template class T SingleListT::~SingleList() { NodeT *p; while( first ) { p=first-link; delete first; first=p; } } a0 a1 first a2 ∧ 单链表 p p=∧ first=∧ 4. 在单链表上实现线性表上定义的操作 （1） 查找第k个元素 （2） 插入操作 （3） 删除操作 （1） 查找元素ai a0 a1 a2 an-1 … first ∧ 单链表 由于链表失去了随机查找元素的特性,所以必须从头指针开始沿链逐个计数查找。 查找元素ai的算法 templateclass T bool SingleListT::Find(int i,T x)const { if (i0 || in-1 ) { cout Out Of Bounds; return false; } NodeT *p=first; for (int j=0; ji; j++) p=p-link; x=p-element; return true; } 渐近时间复杂度：O(n) （2） 插入操作 在给定元素ai之后插入值为x的元素。 插入算法步骤为： ①生成数据域为x的新结点，q指向新结点; ②从first开始找第i+1个结点，p指向该结点； ③将q插入p之后。 ④表长加1。 (a0,a1,...,ai,ai+1,...,an-1) 即在此处插入x q 插入时只要修改二个指针： q-link=p-link p-link=q 能否对调上述2语句的执行顺序？ 不能，会“断链”现象 ai ai+1 x p ai ai+1 x q p “断链”现象 将q插入p之后: templateclass T bool SingleListT::Insert(int i,T x) { if ( i-1 || in-1 ) { cout Out Of Bounds; return false; } NodeT *q=new NodeT; q-element=x; //生成新结点q NodeT *p=first; for (int j=0; ji; j++) p=p-link; if(i-1) { q-link=p-link；p-link=q; //在p之后插入q } else { q-link=first；first=q; //插字第一个元素之前 } n++; return true; } 渐近时间复杂度：O(n) a0 a1 a2 an-1 … first ∧ （3）删除操作 删除元素ai。(a0,a1,...,ai...,an-1) 即删除该元素 删除算法步骤为： ①从first开始找第i+1个结点，p指向该结点，q指向p之前驱结点; ②从单链表中删除p； ③释放p之空间； ④表长减1。 ai ai+1 ai-1 q p 删除时只要修改一个指针： q-link=p-link 删除p: templateclass T bool SingleListT::Delete(int i) { if ( !n ) { coutUnderFlowendl; return false; } if ( i0 || in-1 ) { cout Out Of Boundsendl; return false； } NodeT *p=first,*q=first; for (int j=0; ji-1; j++) q=q-link; if (i==0) first=first-link; else { p=q-link; q-link=p-link; } delete p; n--; return true; } 渐近时间复杂度：O(n) a0 a1 a2 an-1 … first ∧ 5. 单链表的应用——集合求“交” 求集合A和B的并 两集合求交的算法思想是： ⑴ 置i=0； ⑵ 若i小于集合LA中当前元素的个数，则做⑶，否则转⑹； ⑶ 取出集合LA中i位置的元素x； ⑷ 若x不在集合LB中，则将其从集合LA中删除，否则i++； ⑸ 转⑵继续; ⑹ 结束。 求集合A和B的并 例2.2 求集合A和B的交A＝Ａ∩Ｂ 分析：集合可以看成是线性表，用单链表LA和LB分别表示集合A和B，“交”的结果放在LA中。