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

　　 指出以下算法中的錯誤和低效之處並將它改寫為一個既正確又高效的算法

　　Status DeleteK(SqList &aint iint k)

　　{

　　//本過程從順序存儲結構的線性表a中刪除第i個元素起的k個元素

　　if(i<||k<||i+k>alength) return INFEASIBLE;//參數不合法

　　else {

　　for(count=;count<k;count++){

　　//刪除第一個元素

　　for(j=alength;j>=i+;j) aelem[ji]=aelem[j];

　　alength;

　　}

　　return OK;

　　}

　　解

　　Status DeleteK(SqList &aint iint k)

　　{

　　//從順序存儲結構的線性表a中刪除第i個元素起的k個元素

　　//注意i的編號從開始

　　int j;

　　if(i<||i>alength||k<||k>alengthi) return INFEASIBLE;

　　for(j=;j<=k;j++)

　　aelem[j+i]=aelem[j+i+k];

　　alength=alengthk;

　　return OK;

　　}

　　 設順序表va中的數據元素遞增有序試寫一算法將x插入到順序表的適當位置上以保持該表的有序性

　　解

　　Status InsertOrderList(SqList &vaElemType x)

　　{

　　//在非遞減的順序表va中插入元素x並使其仍成為順序表的算法

　　int i;

　　if(valength==valistsize)return(OVERFLOW);

　　for(i=valength;i>x<vaelem[i];i)

　　vaelem[i]=vaelem[i];

　　vaelem[i]=x;

　　valength++;

　　return OK;

　　}

　　 試寫一算法在帶頭結點的單鏈表結構上實現線性表操作Locate(Lx);

　　解

　　int LocateElem_L(LinkList &LElemType x)

　　{

　　int i=;

　　LinkList p=L;

　　while(p&&p>data!=x){

　　p=p>next;

　　i++;

　　}

　　if(!p) return ;

　　else return i;

　　}

　　 試寫一算法在帶頭結點的單鏈表結構上實現線性表操作Length(L)

　　解

　　//返回單鏈表的長度

　　int ListLength_L(LinkList &L)

　　{

　　int i=;

　　LinkList p=L;

　　if(p) p=pnext;

　　while(p){

　　p=p>next;

　　i++;

　　}

　　return i;

　　}

　　 已知指針ha和hb分別指向兩個單鏈表的頭結點並且已知兩個鏈表的長度分別為m和n試寫一算法將這兩個鏈表連接在一起假設指針hc指向連接後的鏈表的頭結點並要求算法以盡可能短的時間完成連接運算請分析你的算法的時間復雜度

　　解

　　void MergeList_L(LinkList &haLinkList &hbLinkList &hc)

　　{

　　LinkList papb;

　　pa=ha;

　　pb=hb;

　　while(pa>next&&pb>next){

　　pa=pa>next;

　　pb=pb>next;

　　}

　　if(!pa>next){

　　hc=hb;

　　while(pb>next) pb=pb>next;

　　pb>next=ha>next;

　　}

　　else{

　　hc=ha;

　　while(pa>next) pa=pa>next;

　　pa>next=hb>next;

　　}

　　}

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