數(shù)據(jù)結(jié)構(gòu)第2章典型例題解析-閱讀頁
2025-04-09 03:01本頁面
【正文】 值相同的元素。 if (L amp。 Lnext){ q=L。 p=L。 pnext=Q。 } return L。返回的L指向原鏈表的第二個(gè)結(jié)點(diǎn)。4．試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別，并說明頭指針和頭結(jié)點(diǎn)的作用。如鏈表H，鏈表L等，表示鏈表中第一個(gè)結(jié)點(diǎn)的地址存放在H和L中。當(dāng)該鏈表表示一個(gè)非空的線性表時(shí)，頭結(jié)點(diǎn)的指針域指向第一個(gè)元素結(jié)點(diǎn)，為空表時(shí)，該指針域?yàn)榭?。頭指針的作用是用來唯一標(biāo)識一個(gè)單鏈表。二是使得在鏈表的第一個(gè)位置上的操作和在其他位置上的操作一致，無需特殊處理。時(shí)間復(fù)雜度為O(1)；若結(jié)點(diǎn)p無后繼結(jié)點(diǎn)，則不可以實(shí)現(xiàn)。單循環(huán)鏈表：像單鏈表那樣進(jìn)行操作，也可以從p開始，找結(jié)點(diǎn)p的直接前驅(qū)，然后再刪除p結(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)。試寫一算法，將x插入到線性表的適當(dāng)位置上，以保持線性表的有序性?！痉治觥恐苯佑妙}目中所給定的數(shù)據(jù)結(jié)構(gòu)（順序存儲的思想是用物理上的相鄰表示邏輯上的相鄰，不一定要將一維數(shù)組和表示線性表長度的變量封裝成一個(gè)結(jié)構(gòu)體），因?yàn)槭琼樞虼鎯?，分配的存儲空間是固定大小的，所以首先確定是否還有存儲空間，若有，則根據(jù)原線性表中元素的有序性確定插入元素的插入位置，后面的元素為它讓出位置（也可以從高下標(biāo)端開始一邊比較，一邊移位），然后插入x，最后修改表示表長的變量。 if (*num==arrsize1) return 0。 while (i=0amp。A[i]x){ //邊找位置邊移動 A[i+1]=A[i]。 } A[i+1]=x。 return 1。2．假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針?！痉治觥坷醚h(huán)單鏈表的特點(diǎn)，通過s指針可循環(huán)找到其前驅(qū)結(jié)點(diǎn)p及p的前驅(qū)結(jié)點(diǎn)q，然后可刪除結(jié)點(diǎn)p。 p=s。 p=pnext。 delete p?！痉治觥拷患傅氖莾蓚€(gè)單鏈表的元素值相同的結(jié)點(diǎn)的集合，為了操作方便，先讓單鏈表C帶有一個(gè)頭結(jié)點(diǎn)，最后將其刪除掉。【算法】LinkNode *inter(LinkList A,B){ LNode *q,*p,*r,*s,*C。 r=C。 q=B。amp。 else if (pdata==qdata){ s=new LNode。 rnext=s。 p=pnext。 } else q=qnext。 r=Cnext。 return r。并分析算法的時(shí)間復(fù)雜度?！舅惴ā縇inkList delete(LinkList L,int min,int max){ //設(shè)L為帶頭結(jié)點(diǎn)的循環(huán)鏈表 LNode *p,*q,*s,*k。 s=L。 p=pnext。amp。 //p 指向第一個(gè)值不大于min的結(jié)點(diǎn) while (snext!=p){ //刪除*s 的后繼至* p的前驅(qū)之間的結(jié)點(diǎn) k=snext。 delete k。編寫一個(gè)算法，將一個(gè)頭結(jié)點(diǎn)指針為a的單鏈表A分解為兩個(gè)單鏈表A和B，其頭結(jié)點(diǎn)指針分別為a和b，使得A鏈表中含有原鏈表A中序號為奇數(shù)的元素（頭結(jié)點(diǎn)緊接的下一個(gè)元素為第1個(gè)元素），而B鏈表中含有原鏈表A中序號為偶數(shù)的元素，且保持原來的相對順序?！舅惴ā縄nt split(LNode *a,LNode *b)//若成功分解，返回1，否則，返回0//a為指向單鏈表a的指針，b為指向單鏈表B的指針{ LNode *cur_a,cur_b,temp。 cur_b=Init_List()。 } *b=cur_b。amp。next)!=NULL){ cur_a224。next。next。next=temp。next。next=NULL。 }
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1