第章线性表(3.4)解读.ppt

图2.4 顺序表中删除元素 例如：线性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)删除第5个元素，则需将第6个元素到第10个元素依次向前移动一个位置，如图2.4所示。 算法描述： Status ListDelete_Sq(SqList L,int i,ElemType e){ if( (i1) || (iL.length) ) return ERROR; p=(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p; p=q; ++p) *(p-1)=*p; --L.length; return OK; } 时间效率分析: 插入算法花费的时间，主要在于循环中元素的后移 当插入位置为1时，需n次移动; 当插入位置为n+1时，不需移动元素; 当插入位置为i时，移动次数为n-i+1。 假定在表中任意位置插入元素都是等概率的，在第i个位置上插入元素的概率p(i)=1/(n+1) 插入操作时间效率（平均移动次数） 删除操作时间效率（平均移动次数） 删除算法花费的时间，主要在于循环中元素的前移 当删除位置为1时，需n-1次移动; 当删除位置为n时，不需移动元素; 当删除位置为i时，移动次数为n-i。 假定在表中任意位置删除元素都是等概率的，则删除第i个位置上元素的概率q(i)=1/n 5.在顺序表中查找元素的算法： LocateElem_Sq(La,e,equal); int LocateElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType, ElemType)){ i=1; p=L.elem; while (i=L.length !(*compare)(*p++,e)) ++i; if (i=L.length) return i; else return 0; } 6. 有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。例如LA=(2, 2, 3)，LB=(1, 3, 3, 4)，则LC=(1, 2, 2, 3, 3, 3, 4)。 算法思想：为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，将所指元素中较小者插入到表LC中。 void MergeList_Sq(SqList La, SqList Lb, SqList Lc ){ pa=La.elem; pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe)); if (!Lc.elem) exit (OVERFLOW); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while (pa=pa_last pb=pb_last){ if (*pa=*pb) *pc++=*pa++; else *pc++=*pb++; } while(pa=pa_last) *pc++=*pa++; while(pb=pb_last) *pc++=*pb++; } O(La.length+Lb.length) 由上面的讨论可知， 线性表顺序表示的优点是：  (1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；  (2）可方便地随机存取表中的任一元素。  其缺点是： （1）插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低; （2）预分配空间（浪费）； （3）表的扩充不方便。 2.3 线性表的链式表示和实现 2.3.1 单链表 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。 单链表中第一个结点无前趋，应设一个头指针H指向第一个结点。 单链表中最后一个结点没有直接后继，则指定最后一个结点的指针域为“空”（NULL）。 整个链表的存取必须从头指针开始。 例如：图2.5所示为线性表（A,