《算法设计.docVIP

1.试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。 【题目分析】 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。 LinkedList Delete（LinkedList L） ∥L是带头结点的单链表，本算法删除其最小值结点。 {p=L-next； ∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L； ∥pre指向最小值结点的前驱。 q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p-next!=null） {if（p-next-dataq-data）{pre=p；q=p-next；} ∥查最小值结点 p=p-next； ∥指针后移。 } pre-next=q-next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。 2.将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 void MergeList_L(LinkList La,LinkList Lb,LinkList Lc){ pa=La-next; pb=Lb-next; Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa pb){ if(pa-datapb-data){ pc-next=pa;pc=pa;pa=pa-next;} else if(pa-datapb-data) {pc-next=pb; pc=pb; pb=pb-next;} else {// 相等时取La的元素，删除Lb的元素 pc-next=pa;pc=pa;pa=pa-next; q=pb-next;delete pb ;pb =q;} } pc-next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点} 3.已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。 【题目分析】 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。 void Delete（ElemType A[ ]，int n） ∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。 {i=1；j=n；∥设置数组低、高端指针（下标）。 while（ij） {while（ij A[i]!=item）i++； ∥若值不为item，左移指针。 if（ij）while（ij A[j]==item）j--；∥若右端元素值为item，指针左移 if（ij）A[i++]=A[j--]； } 4.已知一个带有表头结点的单链表，结点结构为： 假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第K位置的结点（K为正整数），若查找成功，算法输出该结点 data域的值，并返回1，否则只返回0；要求： （1）简述算法的基本设计思想； （2）描述算法的详细实现步骤（使用C，或C++实现 ），关键之处给出详细解释。 ?int?LocateElement(linklist?list,int?k)? {? ????P1=list-link;?????P=list;?????i=1;?while(P1)?{? ?????P1=P1-link;??????i++;? ?????if(ik)??P=P-next;?//如果ik,则p也往后移?}? ??if(P==list)?return?0;??//说明链表没有k个结点??? else????{?? ?????printf(“%d\n“,P-data);???? ???return?1;???}?? } 5. 已知非空线性链表第一个结点的指针为list，请写一