第二章线性表例题.ppt

第二章 线性表 线性表顺序存储 typedef struct { ElemType *elem;//存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }SqList; 例1：已知长度为n的线性表A采用顺序存储结构，请写一算法，删除该线性表中所有值为item的数据元素。 算法思路一： 从线性表的第一个数据元素开始到最后那个数据元意，依次判断线性表中的数据元素是否满足删除条件。若某个数据元素满足条件，则从线性表中删除该数据元素，然后修改线性表的长度。 算法一： Status DELItem(SqList a, ElemType item) { //删除线性表A中所有值为item的数据元素 i=0; while(ia.length) if(a.elem[i]== item) { //若满足条件 for( j=i+1; j a.length; j++) a.elem[j-1]=a.elem[j]; a.length= a.length-1; } else i=i+1; } 算法思路二： 对于数据元素A[i]，如果它满足条件，将其从线性表中删除。由于从第i＋1个位置移到第i个位置的元素也可能满足条件，因此，此时的i值不能增加1，还需要原地等待以判断从后面移来的那个元素是否也满足删除条件(如果也满足删除条件，接着删除该元素)，只有当A[i]不满足删除条件时，i才向后移一个位置。 对算法一改进后的算法思路是：当判断某个数据元素A[i]并得知其满足删除条件时，先不马上对其做删除操作，只记录这样的数据元素的个数m，只是在当某个数据元素不是要删除的数据元素时，这时将该数据元素移到线性表的第i-m个位置。 算法二： Status DELItem(SqList a, ElemType item) { //删除线性表A中所有值为item的数据元素 m=0 for( i=0; ia.length; i++) if(a.elem[i] = =item ) m=m+1; else a.elem[i-m]=a.elem[i]; a.length=a.length-m; //修改线性表的长度 } 例2：设顺序表va中的数据元素递增有序，试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 算法思路： （1）查找x在顺序表a.elem[a.length]中的插入位置，即满足条件：a.elem[i]=xa.elem[i+1]的i值（i的初值为a.length-1）; （2）将顺序表中的a.length-i-1个元素a.elem[i+1…a.length-1]后移一个位置； （3）将x插入到a.elem[i+1]中且将表长a.length加1。 上述算法正确执行的参数条件为：0=a.lengtha.listsize。 算法： Status InsertOrderList(SqList a, ElemType x) { //顺序表a中的元素依值递增有序，本算法将x插入其中适当位置，以保持有序性。0=a.lengtha.listsize if(a.length==a.listsize ) return(OVERFLOW); else { i=a.length-1; while(i=0 xa.elem[i] ) i--; //查找x的插入位置 // i0 || x=a.elem[i] for( j=a.length-1; j=i+1; j--) a.elem[j+1]=a.elem[j]; a.elem[i+1]=a.elem[i]; a.length++; return OK; } } // InsertOrderList 例3.设有一个顺序表L，其元素为整型数据，设计一个算法将L中所有小于0的整数放在前半部分，大于等于0的整数放在后半部分。 算法思路 从L的两端查找，前端找大于等于0的元素（位置为i），后端找小于0的元素（位置为j），然后将两位置的元素交换。 Status Move(SqList L) { ElemType temp; int i=0,j=L.length-1; whi