[ppt模板]數(shù)據(jù)結(jié)構(gòu)線性表試題-文庫吧資料
2025-01-21 06:15本頁面
【正文】 st_Intersect_Delete(SqList *A,SqList B,SqList C) { i=0。試對順序表編寫實現(xiàn)上述操作的算法，并分析你的算法的時間復雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。 Anext=pc。 } pre=pc。pbnext=pre。 } else /*將B的元素插入新表*/ { pc=pb。panext=pre。 while(pa||pb) { if(padatapbdata||!pb) /*將A的元素插入新表*/ { pc=pa。pb=Bnext。 【算法源代碼】 void reverse_merge(LinkList A,LinkList B,LinkList *C) { LinkList pa,pb,pre。 /*指針p和q同時后移*/ }/*while*/}/*merge1 */9．假設(shè)有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構(gòu)，請設(shè)計一個算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即 A表和B表）的結(jié)點空間構(gòu)造C表。 /*若A非空，將A的元素插入*/ } p=s。 /*將B的元素插入*/ if (s) { t=qnext。q) { s=pnext。 while(pamp?！ =Bnext。注意：單鏈表的長度值m和n均未顯式存儲。}/*LinkList_reverse*/8．設(shè)線性表A=（a1，a2，…，am） 和 B=（b1，b2，…，bn），試設(shè)計一個按下列規(guī)則合并A，B為線性表C的算法，即使得 C=（a1，b1，…，am，bm，bm+1 ，…，bn ）當 m≤n時； 或者 C=（a1，b1，…，an，bn，an+1 ，…，am ）當m＞n時?！ next=q。s=snext。p=q。 pnext=NULL。 q=pnext。 【算法源代碼】 void LinkList_reverse(LinkList L){ if(!Lnext||!Lnextnext) return。 }/*else*/ }/*while*/}/*Delete_Equal */7．試設(shè)計一個算法，對帶頭結(jié)點的單鏈表實現(xiàn)就地逆置。p=q。 free(r)。 } else { while(qdata==pdata) /*當相鄰元素相等時刪除多余元素*/ { r=q。 /*p和q指向相鄰的兩個元素*/ while(pnext) { if(pdata!=qdata) /*若相鄰兩元素不相等時，p和q都向后推一步*/ { p=pnext。 【算法源代碼】 void Delete_Equal(LinkList *L) { p=(*L)next。試設(shè)計一個高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時釋放被刪結(jié)點空間。 /*q是第一個不小于maxk的元素*/ pnext=q。 /*p是最后一個不大于mink的元素*/ if(pnext) /*如果還有比mink更大的元素*/ { q=pnext。 【算法源代碼】 void Delete_Between(LinkList *L,int mink,int maxk){ p=*L。它們的值可以和表中的元素相同，也可以不同）。 }}/*Insert */5．已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。 newnext=pnext。 } else { /*插入在第i個元素的位置*/ p=*L。 if(i==1) {/*插入在鏈表頭部*/ Newnext=*L。 new=(LinkList*)malloc(sizeof(LNode))。 【算法分析】 1）生成新結(jié)點存放元素b，由指針new指向； 2）將new插入在單鏈表的第i個元素的位置上：若i==1，new插在鏈表首部；否則查找第i1個結(jié)點，由指針p指向，然后將new插在p之后。 free(hb)。/*由指針p指向ha的尾元結(jié)點*/ p=pnext。 【算法分析】 1）單鏈表ha的頭結(jié)點作為連接后的鏈表的頭結(jié)點，即hc=ha； 2）查找單鏈表ha的最后一個結(jié)點，由指針p指向，即pnext==NULL； 3）將單鏈表hb的首元結(jié)點（非頭結(jié)點）連接在p之后，即pnext=hbnext； 4）回收單鏈表hb的頭結(jié)點空間 【算法源代碼】 void ListConcat(LinkList ha,LinkList hb,LinkList *hc)/*把鏈表hb接在ha后面形成鏈表hc*/{ *hc=ha。 /*當兩個順序表可以互相比較的部分完全相同時，哪個較長， 哪個就較大*/ }/*ListComp */3．已知指針 ha和 hb分別指向兩個單鏈表的頭結(jié)點，并且已知兩個鏈表的長度分別為m和n。 if(==) return 0。i=。i=amp。 【算法分析】比較順序表A和B，并用返回值表示結(jié)果，值為1，表示AB；值為1，表示AB；值為0，表示A=B。 ++。i) [i+1]=。amp。 for(i=。 【算法源代碼】 void Insert_SqList(SqList va,int x)/*把x插入遞增有序
試題試卷相關(guān)推薦
鄂ICP備17016276號-1