数据结构实例教程 第2章 线性表(习题解答).ppt

第2章 线性表 习题解答 1、?设计一个算法，对顺序表实现就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an,an-1,…，a1）。 解题思路分析：要利用原表的存储空间将顺序表（a1,a2,…,an）逆置为（an,an-1,…，a1）,我们只要设置一个临时变量temp，然后循环，再从表头、表尾两个方向开始，将元素对换即可。核心语句： temp=L-items [ i ]; L-items [ i ]=L-items [ j ]; L-items [ j ]=temp; 算法 Void?invesqlist(Sqlist *L)??{ /*将顺序表（a1,a2,…,an）逆置为（an,an-1,…，a1）*/ int?temp,i,j,m=(L-length -1)/2; ?for?(i=0;i=m;i++) { j= length -1 -i; ? temp=L-items [ i ]; //对换 L-items [ i ]=L-items [ j ]; L-items [ j ]=temp; } 2、设有一顺序表，请编写一算法求第i个元素的后继结点的值。 解题思路：通过数组下标找到第i+1个元素，如果没有越界，就返回值。 3.设顺序表L中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 解题思路：首先，查找x在顺序表L中的插入位置，即求items [i]=xitems [i+1]的i值（设i的初值为length）;然后，将顺序表中的length-i个元素后移；最后，将x插入到 items [i+1]中，表长length加1。 算法: SqList *InsertOrderSqList(Sqlist *L,DataType x) { //顺序表L中的元素依值递增有序，本算法将x插入其中适当位置，以保持有序性。 int i; if(L-length==LISTSIZE-1) printf(表已满); else { i=L-length; while(i=1xL-items [i]) i--; //查找x的插入位置 for(j=L-length;j=i+1;j--) L-items [j+1]=L-elem[j]; L-items [i+1]=x; printf(x已成功插入！); } return L; } // InsertOrderSqList 4.设计算法，删除顺序表中值为value的所有结点。 解题思路一： 从线性表的第一个数据元素开始到最后那个数据元素，依次判断线性表中的数据元素是否满足删除条件。若某个数据元素满足条件，则从线性表中删除该数据元素，然后修改线性表的长度（即当items [i]= value时，进行删除操作，将items[i+1]至items [length]元素前移，并使length减1）；否则，继续向后遍历，直至表尾。 算法一： void DeleteValue(SqList *L,DataType Value) { //删除线性表L中所有值为Value的数据元素 int i,j; for(i=1;i=L-length;i++) if(L-items [i]==Value) //若满足条件 { for(j=i;j=L-length-1;j++) L-items [j]=L-items [j+1]; --L-length; } } 算法思路二： 对于数据元素A[i]，如果它满足条件，将其从线性表中删除。由于从第i＋1个位置移到第i个位置的元素也可能满足条件，因此，此时的i值不能增加1，还需要原地等待以判断从后面移来的那个元素是否也满足删除条件(如果也满足删除条件，接着删除该元素)，只有当A[i]不满足删除条件时，i才向后移一个位置。 对算法一改进后的算法思路是：当判断某个数据元素A[i]并得知其满足删除条件时，先不马上对其做删除操作，只记录这样的数据元素的个数m，只是在当某个数据元素不是要删除的数据元素时，这时将该数据元素移到线性表的第i-m个位置。 算法二： Status DELValue (SqList *L, DateType Value) { //删除线性表L中所有值为Value的数据