第2章后练习.docVIP

第2章练习 1、在顺序表表示的集合中查找最小值X，并将之删除。 2、统计带头结点的单链表中值域为X的节点个数并返回。 3、A和B是两个带头结点的递增有序的单链表，写算法将两表合并成一个带头结点的递减有序单链表C，利用原表空间。 1. [题目分析]在顺序表中查找指定值, 要从头到尾的查， ElemType MiniDelete(SeqList s) //在顺序表中删除最小值元素,空出的位置由最后一个元素填补,返回最小值元素 {ElemType min; //min记最小值元素 k=0; //k记最小值元素下标,先假定第一个元素最小 for(i=0;i=s.last;i++) { if (s.data[i]s.data[k] k=i; } min=s.data[k]; s.data[k]= s.data[s.last]; //集合中,无序 s.last--; return min; }//算法结束 2. [题目分析]求带头结点的单链表中给定元素个数，通过遍历链表完成。 int count(LinkedList l,elemtype X) //遍历单链表，如果值域=X，计数器加1 {Lnode * p；//p为工作指针 p=l-next; int count; while (p) //p!=null { if(p-data==X) count++; p=p-next; } return count; }//算法结束 3. [题目分析] 因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。 LinkedList Union(LinkedList ha,hb) ∥ha,hb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。 { pa=ha-next; pb=hb-next;∥pa，pb分别是链表ha和hb的工作指针 ha-next=null; ∥ha作结果链表的头指针，先将结果链表初始化为空。 while(pa!=null pb!=null) ∥当两链表均不为空时作 if(pa-data=pb-data) { r=pa-next; ∥将pa 的后继结点暂存于r。 pa-next=ha-next; ∥将pa结点链于结果表中，同时逆置。 ha-next=pa; pa=r; ∥恢复pa为当前待比较结点。 } else {r=pb-next;∥ 将pb 的后继结点暂存于r。 pb-next=ha-next; ∥将pb结点链于结果表中，同时逆置。 ha-next=pb; pb=r; ∥恢复pb为当前待比较结点。 } if (pa) pb=pa; //为了下面算法统一,不再单独处理pa while(pb!=null) {r=pb-next; pb-next=ha-next; ha-next=pb; pb=r; } free(hb); return(ha); }∥算法Union结束。 【算法讨论】上面两链表均不为空的表达式也可简写为while(pa pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后while语句，哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。