數據結構與算法線性表復習習題【4】

　　 已知指針la和lb分別指向兩個無頭結點單鏈表中的首元結點下列算法是從表la中刪除自第i個元素起共len個元素後將它們插入到表lb中第i個元素之前試問此算法是否正確？若有錯請改正之

　　Status DeleteAndInsertSub(LinkedList laLinkedList lbint iint jint len)

　　{

　　if(i<||j<||len<) return INFEASIBLE;

　　p=la;k=;

　　while(k<i){p=p>next;k++;}

　　q=p;

　　while(k<=len){q=q>next;k++;}

　　s=lb; k=;

　　while(k<j){s=s>next;k++;}

　　s>next=p; q>next=s>next;

　　return OK;

　　}

　　解

　　Status DeleteAndInsertSub(LinkList &laLinkList &lbint iint jint len)

　　{

　　LinkList pqsprev=NULL;

　　int k=;

　　if(i<||j<||len<) return INFEASIBLE;

　　// 在la表中查找第i個結點

　　p=la;

　　while(p&&k<i){

　　prev=p;

　　p=p>next;

　　k++;

　　}

　　if(!p)return INFEASIBLE;

　　// 在la表中查找第i+len個結點

　　q=p;k=;

　　while(q&&k<len){

　　q=p>next;

　　k++;

　　}

　　if(!q)return INFEASIBLE;

　　// 完成刪除注意i=的情況需要特殊處理

　　if(!prev) la=q>next;

　　else prev>next=q>next;

　　// 將從la中刪除的結點插入到lb中

　　if(j=){

　　q>next=lb;

　　lb=p;

　　}

　　else{

　　s=lb;k=;

　　while(s&&k<j){

　　s=s>next;

　　k++;

　　}

　　if(!s)return INFEASIBLE;

　　q>next=s>next;

　　s>next=p; //完成插入

　　}

　　return OK;

　　}

　　 已知線性表中的元素以值遞增有序排列並以單鏈表作存儲結構試寫一高效的算法刪除表中所有值大於mink且小於maxk的元素（若表中存在這樣的元素）同時釋放被刪結點空間並分析你的算法的時間復雜度（注意mink和maxk是給定的兩個參變量它們的值可以和表中的元素相同也可以不同）

　　解

　　Status ListDelete_L(LinkList &LElemType minkElemType maxk)

　　{

　　LinkList pqprev=NULL;

　　if(mink>maxk)return ERROR;

　　p=L;

　　prev=p;

　　p=p>next;

　　while(p&&p>data<maxk){

　　if(p>data<=mink){

　　prev=p;

　　p=p>next;

　　}

　　else{

　　prev>next=p>next;

　　q=p;

　　p=p>next;

　　free(q);

　　}

　　}

　　return OK;

　　}

　　 同題條件試寫一高效的算法刪除表中所有值相同的多余元素（使得操作後的線性表中所有元素的值均不相同）同時釋放被刪結點空間並分析你的算法的時間復雜度

　　解

　　void ListDelete_LSameNode(LinkList &L)

　　{

　　LinkList pqprev;

　　p=L;

　　prev=p;

　　p=p>next;

　　while(p){

　　prev=p;

　　p=p>next;

　　if(p&&p>data==prev>data){

　　prev>next=p>next;

　　q=p;

　　p=p>next;

　　free(q);

　　}

　　}

　　}

From:http://tw.wingwit.com/Article/program/sjjg/201311/23408.html