1作業(yè)：1、簡(jiǎn)述邏輯結(jié)構(gòu)和存放結(jié)構(gòu)聯(lián)絡(luò)？2、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型有什么區(qū)分？3、分析以下算法時(shí)間復(fù)雜度

voidfunc(intn){inti=0,s=0;while(s<n){i++;s=s+i;}}第1頁(yè)22025/5/15次序表算法設(shè)計(jì)練習(xí)：

已知一個(gè)次序表L，其中元素遞增有序排列，設(shè)計(jì)一個(gè)算法插入一個(gè)元素x后保持該次序表仍遞增有序排列。第2頁(yè)32025/5/15參考算法：Voidinsert(Sqlist&L,ElemTypex){inti=0,j;if(L.length+1>L.listsize)p24while(i<L.length&&x>=L.elem[i])i++;for(j=L.length-1;j>=i;j--)L.elem[j+1]=L.elem[j];L.elem[i]=x;L.length++;}第3頁(yè)42025/5/15次序表算法設(shè)計(jì)練習(xí)：試寫(xiě)一個(gè)算法，實(shí)現(xiàn)次序表就地逆置，即利用原表存放空間將線性表。（a1,a2,…,an）逆置為（an,an-1,…,a1）。第4頁(yè)52025/5/15參考算法：Voidreverse(Sqlist&L){inti=0,j=L.length-1;while(i<j){L.elem[i]<->L.elem[j];i++;j--;}}第5頁(yè)62025/5/15次序表算法設(shè)計(jì)練習(xí)：試設(shè)計(jì)一個(gè)高效算法，刪除線性表L中全部值為x元素。第6頁(yè)72025/5/15參考算法：Voiddeletelist(Sqlist&L,ElemTypex){intcount=0;for(i=0;i<=L.length-1;i++)if(L.elem[i]==x)count++;elseL.elem[i-count]=L.elem[i];}第7頁(yè)82025/5/15鏈表算法設(shè)計(jì)練習(xí)：設(shè)計(jì)一個(gè)算法刪除帶頭結(jié)點(diǎn)單鏈表L中值為x結(jié)點(diǎn)直接前驅(qū)結(jié)點(diǎn)。第8頁(yè)92025/5/15參考算法：Intdelx(Linklist&L,ElemTypex){LinkListp=L,q=p->next,r;If(q!=Null)r=q->next;Elsereturn0;While(r!=Null&&r->data!=x){p=q;q=r;r=r->next;}if(r!=Null){p->next=q->next;free(q);}elsereturn0;return1;}第9頁(yè)102025/5/15鏈表算法設(shè)計(jì)練習(xí)：設(shè)計(jì)一個(gè)算法，在帶頭結(jié)點(diǎn)單鏈表head中刪除一個(gè)data域值最小結(jié)點(diǎn)，假設(shè)該結(jié)點(diǎn)唯一。第10頁(yè)112025/5/15參考算法：VoidDelMinNode(Linklisthead){Linklistp=head->next,pre=head;Linklistminp,minpre;Elemtypemin=p->data;minp=p;minpre=pre;While(p!=NULL){If(p->data<minp->data){min=p->data;minp=p;minpre=pre;}pre=p;p=p->next;}minpre->next=minp->next;Free(minp);}第11頁(yè)122025/5/151、假設(shè)表示式中允許包含3種括號(hào)：圓括號(hào)、方括號(hào)和大括號(hào)。設(shè)計(jì)一個(gè)算法采取次序棧判斷表示式中括號(hào)是否正確配對(duì)。Intmatch(charexp[],intn){charst[Maxsize];inttop=-1;inti=0,tag=1;while(i<n&&tag==1){if(exp[i]==‘(’||exp[i]==‘[‘||exp[i]==‘{’){top++;st[top]=exp[i];}if(exp[i]==‘)’)if(st[top]==‘(’top--;elsetag=0;if(exp[i]==‘]’)if(st[top]==‘[’top--;elsetag=0;if(exp[i]==‘}’)if(st[top]==‘{’top--;elsetag=0;第12頁(yè)132025/5/152、假設(shè)用一個(gè)循環(huán)單鏈表表示隊(duì)列，而且只設(shè)一個(gè)指針rear指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，設(shè)計(jì)出對(duì)應(yīng)隊(duì)初始化、入隊(duì)算法。VoidinitQu(Qnode*&rear){rear=NULL;}VoldEnQu(Qnode*&rear,ElemTypex){Qnode*s;s=(Qnode*)mallaoc(sizeof(Qnode));s->data=x;if(rear==NULL){s->next=s;rear=s;}else{s->next=rear->next;rear->next=s;rear=s}}第13頁(yè)142025/5/15作業(yè)：1、設(shè)一系列正整數(shù)存放在一個(gè)數(shù)組中，試設(shè)計(jì)算法，將全部奇數(shù)存放在數(shù)組前半部分，將全部偶數(shù)放在數(shù)組后半部分。要求盡可能少用暫時(shí)存放單元并使時(shí)間最少。2、設(shè)計(jì)一個(gè)算法，計(jì)算一個(gè)三元組表表示稀疏矩陣對(duì)角線元素之和。第14頁(yè)15例：設(shè)樹(shù)T度為4，其中度為1，2，3和4結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中葉子數(shù)為（）A．5B．6C．7D．8提醒：因?yàn)槊總€(gè)結(jié)點(diǎn)都有一條枝指向它，分支數(shù)為1*4+2*2+3*1+4*1全部結(jié)點(diǎn)數(shù)為分支數(shù)+1，所以1*4+2*2+3*1+4*1=4+2+1+1+xx=8例：若一棵二叉樹(shù)含有10個(gè)度為2結(jié)點(diǎn)，5個(gè)度為1結(jié)點(diǎn)，則度為0結(jié)點(diǎn)個(gè)數(shù)是（）A．9B．11C．15D．不確定提醒：

n0=n2+1第15頁(yè)16例3：已知某二叉樹(shù)先序序列{ABHFDECKG}和中序序列{HBDFAEKCG},畫(huà)出該二叉樹(shù)。HBDFEKCGAEKCGABHDFEKCGABHFDEABHFDCKGAKCGEBHFDA第16頁(yè)17例1：統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)StatusCountLeaf(BiTreeT,int&count){if(T){if((T->lchild==NULL)&&(T->rchild==NULL)){count++;returnOK;}CountLeaf(T->lchild,count);//統(tǒng)計(jì)左子樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)

CountLeaf(T->rchild,count);//統(tǒng)計(jì)右子樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)

}elsereturnERROR;}第17頁(yè)18例2：求二叉樹(shù)深度intDepth(BiTreeT){if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+max(depthLeft,depthRight);}returndepthval;}第18頁(yè)19例3：按先序序列建立二叉樹(shù)二叉鏈表已知先序序列：ABC00DE0G00F000（其中0表示空格字符,空指針）建立對(duì)應(yīng)二叉鏈表ABCDEFG第19頁(yè)20例：對(duì)于前序遍歷與中序遍歷結(jié)果相同二叉樹(shù)（）;對(duì)于前序遍歷和后序遍歷結(jié)果相同二叉樹(shù)為（）。A．普通二叉樹(shù)B．只有根結(jié)點(diǎn)二叉樹(shù)C．根結(jié)點(diǎn)無(wú)左孩子二叉樹(shù)D．根結(jié)點(diǎn)無(wú)右孩子二叉樹(shù)E．全部結(jié)點(diǎn)只有左子數(shù)二叉樹(shù)F．全部結(jié)點(diǎn)只有右子樹(shù)二叉樹(shù)例：某二叉樹(shù)前序序列和后序序列恰好相反，則該二叉樹(shù)一定是（）二叉樹(shù)。A．空或只有一個(gè)結(jié)點(diǎn)B．任一結(jié)點(diǎn)無(wú)左子樹(shù)C．高度等于其結(jié)點(diǎn)數(shù)D．任一結(jié)點(diǎn)無(wú)右子樹(shù)FB√第20頁(yè)21例：一棵左子樹(shù)為空二叉樹(shù)在先序線索化后，其中空鏈域個(gè)數(shù)是：()A．不確定B.0C.1D.2例：一棵左右子樹(shù)均不空二叉樹(shù)在先序線索化后，其中空鏈域個(gè)數(shù)是：()。A.0B.1C.2D.不確定√左子樹(shù)為空二叉樹(shù)根結(jié)點(diǎn)左線索為空（無(wú)前驅(qū)），先序序列最終結(jié)點(diǎn)右線索為空（無(wú)后繼），共2個(gè)空鏈域√只有最終一個(gè)葉結(jié)點(diǎn)沒(méi)有后繼第21頁(yè)22例：線索二叉樹(shù)是一個(gè)（）結(jié)構(gòu)。A．邏輯B．邏輯和存放C．物理D．線性例：n個(gè)結(jié)點(diǎn)線索二叉樹(shù)上含有線索數(shù)為（）A．2nB．n－1C．n＋1D．n√√N(yùn)個(gè)結(jié)點(diǎn)共有2n個(gè)指針域，二叉鏈表用了n-1個(gè)，剩下n+1個(gè)第22頁(yè)23練習(xí)：寫(xiě)出下列圖所表示樹(shù)先序和后序遍歷序列并將之轉(zhuǎn)換成一棵二叉樹(shù)ABCDEFHGI先根遍歷：ABDEGHICF后根遍歷：DGHIEBFCAABGDCFHEI第23頁(yè)246.4.2森林和二叉樹(shù)轉(zhuǎn)換－規(guī)則設(shè)森林F={T1,T2,……Tm}，二叉樹(shù)B=（root，LB，RB）(1)森林轉(zhuǎn)化成二叉樹(shù)規(guī)則

若F為空(m=0)，B為空;

若F不空(m≠0)，B根root(B)是F中第一棵樹(shù)T1根root(T1)；左子樹(shù)LB從T1根結(jié)點(diǎn)子樹(shù)森林(T11,T12,…,T1m)轉(zhuǎn)換來(lái)；右子樹(shù)RB是從森林F’={T2,T3,…,Tm}轉(zhuǎn)換而來(lái)。(2)二叉樹(shù)轉(zhuǎn)換為森林規(guī)則若B為空，F(xiàn)為空；

若B非空，則F中第一棵樹(shù)T1根為二叉樹(shù)根root(B)；

T1根子樹(shù)森林F1由B左子樹(shù)LB轉(zhuǎn)換而來(lái)；

F中除T1外其余樹(shù)組成森林F’={T2,T3,…,Tn}由B右子樹(shù)RB轉(zhuǎn)換而來(lái)。第24頁(yè)25森林轉(zhuǎn)換成二叉樹(shù)步驟1：轉(zhuǎn)換－將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)步驟2：加線－將每棵樹(shù)根結(jié)點(diǎn)用線相連步驟3：旋轉(zhuǎn)－以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，組成二叉樹(shù)ABCDEFGHIJ森林FABCDEFGHIJF中每棵樹(shù)對(duì)應(yīng)二叉樹(shù)第25頁(yè)26森林轉(zhuǎn)換成二叉樹(shù)步驟1：轉(zhuǎn)換－將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)步驟2：加線－將每棵樹(shù)根結(jié)點(diǎn)用線相連步驟3：旋轉(zhuǎn)－以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，組成二叉樹(shù)ABCDEFGHIJABCDEFGHIJ森林F第26頁(yè)27森林轉(zhuǎn)換成二叉樹(shù)步驟1：轉(zhuǎn)換－將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)步驟2：加線－將每棵樹(shù)根結(jié)點(diǎn)用線相連步驟3：旋轉(zhuǎn)－以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，組成二叉樹(shù)ABCDEFGHIJABCDEFGHIJ森林FF轉(zhuǎn)換二叉樹(shù)BABCDEFGHIJ第27頁(yè)28二叉樹(shù)轉(zhuǎn)換成森林步驟1：抹線－將二叉樹(shù)根結(jié)點(diǎn)與其右孩子連線、沿右分支搜索到全部右孩子間連線全部抹掉，使之變成多棵二叉樹(shù)步驟2：還原－將孤立二叉樹(shù)還原成樹(shù)二叉樹(shù)BABCDEFGHIJ第28頁(yè)29二叉樹(shù)轉(zhuǎn)換成森林步驟1：抹線－將二叉樹(shù)根結(jié)點(diǎn)與其右孩子連線、沿右分支搜索到全部右孩子間連線全部抹掉，使之變成多棵二叉樹(shù)步驟2：還原－將孤立二叉樹(shù)還原成樹(shù)二叉樹(shù)BABCDEFGHIJABCDEFGHIJ第29頁(yè)30二叉樹(shù)轉(zhuǎn)換成森林步驟1：抹線－將二叉樹(shù)根結(jié)點(diǎn)與其右孩子連線、沿右分支搜索到全部右孩子間連線全部抹掉，使之變成多棵二叉樹(shù)步驟2：還原－將孤立二叉樹(shù)還原成樹(shù)ABCDEFGHIJ二叉樹(shù)BABCDEFGHIJABCDEFGHIJ第30頁(yè)31二叉樹(shù)轉(zhuǎn)換成森林步驟1：抹線－將二叉樹(shù)根結(jié)點(diǎn)與其右孩子連線、沿右分支搜索到全部右孩子間連線全部抹掉，使之變成多棵二叉樹(shù)步驟2：還原－將孤立二叉樹(shù)還原成樹(shù)B轉(zhuǎn)換成森林F二叉樹(shù)BABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第31頁(yè)32練習(xí)：寫(xiě)出下列圖所表示森林先序和中序遍歷序列并將之轉(zhuǎn)換成一棵二叉樹(shù)EABCDFIJHGK先序遍歷：中序遍歷：ABCDEFIKJGHBEFDCIAJGHK第32頁(yè)33例：設(shè)F是一個(gè)森林，B是由F變換得二叉樹(shù)。若中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭战Y(jié)點(diǎn)有（）個(gè)。A．n-1B．nC．n+1D．n+2每一個(gè)非終端結(jié)點(diǎn)孩子中都會(huì)貢獻(xiàn)出一個(gè)空右指針√例：設(shè)F是由T1,T2,T3三棵樹(shù)組成森林,與F對(duì)應(yīng)二叉樹(shù)為B,已知T1,T2,T3結(jié)點(diǎn)數(shù)分別為n1,n2和n3則二叉樹(shù)B左子樹(shù)中有

個(gè)結(jié)點(diǎn)，右子樹(shù)中有

個(gè)結(jié)點(diǎn)。n1-1n2+n3第33頁(yè)34結(jié)構(gòu)最優(yōu)二叉樹(shù)說(shuō)明1在選取兩棵根結(jié)點(diǎn)權(quán)值為最小和次小二叉樹(shù)時(shí)，假如出現(xiàn)權(quán)值相同情況，能夠在相同權(quán)值二叉樹(shù)中任選一棵。2當(dāng)兩棵根結(jié)點(diǎn)權(quán)值為最小和次小二叉樹(shù)組成新二叉樹(shù)左右子樹(shù)時(shí)，誰(shuí)是左子樹(shù)誰(shuí)是右子樹(shù)沒(méi)有特殊要求。3在最優(yōu)二叉樹(shù)中沒(méi)有度為1結(jié)點(diǎn)，依據(jù)二叉樹(shù)性質(zhì)3可知有n個(gè)葉子結(jié)點(diǎn)二叉樹(shù)有n-1個(gè)非終端結(jié)點(diǎn)共有2*n-1個(gè)結(jié)點(diǎn)。a7b5c2d461118a7b5d4c261118第34頁(yè)35怎樣得到最短二進(jìn)制前綴碼（赫夫曼編碼）？為了設(shè)計(jì)電文總長(zhǎng)最短二進(jìn)制前綴編碼，以n種字符出現(xiàn)頻率作權(quán)，設(shè)計(jì)一棵赫夫曼樹(shù)，從根節(jié)點(diǎn)至即全部葉子節(jié)點(diǎn)，按左分支為0，右分支為1標(biāo)準(zhǔn)即可得到最短二進(jìn)制前綴編碼即赫夫曼編碼。例：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,設(shè)計(jì)赫夫曼編碼。解：設(shè)權(quán)w=(5，29，7，8，14，23，3，11)第35頁(yè)360231411529378000000111111110058428291519編碼：3（0111）5（0110）7（1110）

8（1111）11（010）14（110）

23（00）29（10）第36頁(yè)37練習(xí)：用于通信電文由8個(gè)字母c1,c2,c3,c4,c5,c6,c7,c8組成,各字母在電文中出現(xiàn)頻率分別為5,25,3,6,10,11,36,4。試設(shè)計(jì)不等長(zhǎng)Huffman編碼,并給出該電文總碼數(shù)。00000001001010001010111011電文總碼數(shù)=4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257第37頁(yè)382025/5/15練習(xí)（1）設(shè)無(wú)向圖頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。（2）一個(gè)有n個(gè)結(jié)點(diǎn)圖，最少有（）個(gè)連通分量，最多有（）個(gè)連通分量。（3）在一個(gè)無(wú)向圖中，全部頂點(diǎn)度數(shù)之和等于全部邊數(shù)____倍。（4）要連通含有n個(gè)頂點(diǎn)有向圖，最少需要（）條邊。（5）若無(wú)向圖G=（V，E）中含7個(gè)頂點(diǎn)，則確保圖G在任何情況下都是連通，則需要邊數(shù)最少是（）。第38頁(yè)392025/5/15無(wú)向圖鄰接表表示V1V2

V4

V5

V3

頂點(diǎn)度：該頂點(diǎn)所在單鏈表中表結(jié)點(diǎn)個(gè)數(shù)V1V2V3V4V50123413∧04∧202∧12∧14∧3與頂點(diǎn)V1相鄰接頂點(diǎn)在數(shù)組中下標(biāo)第39頁(yè)402025/5/15V1V2

V4

V5

V3

254311鄰接表表示V1V2V3V4V501234123∧4024∧521114∧133042∧3152∧1權(quán)值無(wú)向網(wǎng)第40頁(yè)412025/5/15V1V2

V3

V4

鄰接表表示12∧V1V2∧V3V401233∧0∧以頂點(diǎn)V1為始點(diǎn)弧終點(diǎn)頂點(diǎn)在數(shù)組中下標(biāo)頂點(diǎn)出度該頂點(diǎn)所在單鏈表中表結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)入度查詢整個(gè)鄰接表中表結(jié)點(diǎn)，與該頂點(diǎn)序號(hào)（數(shù)組下標(biāo)）一致表結(jié)點(diǎn)個(gè)數(shù)有向圖第41頁(yè)422025/5/15圖鄰接表表示問(wèn)題：含有n個(gè)頂點(diǎn)e條邊無(wú)向圖鄰接表中有多少個(gè)表頭結(jié)點(diǎn)？有多個(gè)表結(jié)點(diǎn)（邊結(jié)點(diǎn)）？

有向圖呢？第42頁(yè)432025/5/15練習(xí):

請(qǐng)畫(huà)出下列圖鄰接矩陣和鄰接表第43頁(yè)442025/5/157.3.1深度優(yōu)先搜索-舉例1234V1V3V4V2datafirstarc2783^^^adjvexnextarc5V5641^51282^V6V7V8678736354^^^V1V2V4V5V3V7V6V8深度遍歷：V1

V3V7V6V2V5V8V4給定存放結(jié)構(gòu)，圖遍歷序列唯一第44頁(yè)452025/5/157.3.2廣度優(yōu)先搜索-舉例廣度遍歷：V1V3V2V7V6V5V4V81234V1V3V4V2datafirstarc2783^^^adjvexnextarc5V5641^51282^V6V7V8678736354^^^V1V2V4V5V3V7V6V8給定存放結(jié)構(gòu)，圖遍歷序列唯一第45頁(yè)462025/5/15以下相關(guān)圖遍歷說(shuō)法中不正確是（）A．連通圖深度優(yōu)先搜索是一個(gè)遞歸過(guò)程B．圖廣度優(yōu)先搜索中鄰接點(diǎn)尋找含有“先進(jìn)先出”特征C.圖遍歷要求每一頂點(diǎn)僅被訪問(wèn)一次D．對(duì)圖進(jìn)行一次深度優(yōu)先遍歷能夠訪問(wèn)圖中全部頂點(diǎn)第46頁(yè)472025/5/15給定有向圖以下：

給出其鄰接表存放結(jié)構(gòu)基于鄰接表，給出DFS序列和BFS序列第47頁(yè)482025/5/15練習(xí)：已知一個(gè)圖頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到各條邊。

【答】用克魯斯卡爾算法得到最小生成樹(shù)為：

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20第48頁(yè)492025/5/15練習(xí)：設(shè)有沒(méi)有向圖G，要求給出用普里姆算法結(jié)構(gòu)最小生成樹(shù)所走過(guò)邊集合。

【答】E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}第49頁(yè)502025/5/157.5.1拓?fù)渑判?實(shí)現(xiàn)步驟C1C3C2C7C5C6C4編號(hào)課程名稱(chēng)C1數(shù)學(xué)C2程序設(shè)計(jì)C3離散數(shù)學(xué)C4匯編程序設(shè)計(jì)C5數(shù)據(jù)結(jié)構(gòu)C6結(jié)構(gòu)程序設(shè)計(jì)C7編譯原理C1C3C2C7C5C6C4拓?fù)溆行蛐蛄校篊1=>C3=>C2=>C4=>C6=>C5=>C7邏輯結(jié)構(gòu)上：拓?fù)湫蛄胁晃ㄒ坏?0頁(yè)512025/5/157.5.2關(guān)鍵路徑AOE-網(wǎng)(ActiveOnEdge)：在帶權(quán)有向無(wú)環(huán)圖中，頂點(diǎn)表示事件，弧表示工程一個(gè)活動(dòng)，弧上權(quán)值表示活動(dòng)連續(xù)時(shí)間。用來(lái)估算工程完成時(shí)間。源點(diǎn)：入度為0頂點(diǎn)。匯點(diǎn)：出度為0頂點(diǎn)。路徑長(zhǎng)度：AOE網(wǎng)中路徑上各活動(dòng)連續(xù)時(shí)間之和。關(guān)鍵路徑：路徑長(zhǎng)度最長(zhǎng)路徑。V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7說(shuō)明：（1）完成工程最短時(shí)間是從開(kāi)始點(diǎn)到完成點(diǎn)最長(zhǎng)路徑長(zhǎng)度。（2）關(guān)鍵路徑改變會(huì)影響整個(gè)工期。第51頁(yè)522025/5/15設(shè)活動(dòng)ai在有向無(wú)環(huán)圖G有向邊<j,k>上：事件vj最早發(fā)生時(shí)間ve(j):從源點(diǎn)v0到vj最長(zhǎng)路徑長(zhǎng)度。ve(0)=0;ve(j)=從源點(diǎn)到頂點(diǎn)j最長(zhǎng)路徑長(zhǎng)度。ve(k)=Max{ve(j)+dut(<j,k>)}事件vj最遲開(kāi)始時(shí)間vl(j)：確保匯點(diǎn)vn-1在ve(n-1)時(shí)刻完成前提下，事件vj最遲允許開(kāi)始時(shí)間。vl(n-1)=ve(n-1)＝從源點(diǎn)到匯點(diǎn)最長(zhǎng)路徑長(zhǎng)度;vl(k)=從匯點(diǎn)到頂點(diǎn)k最短路徑長(zhǎng)度。vl(j)=Min{vl(k)-dut(<j,k>)}kjdut(<j,k>)ai7.5.2關(guān)鍵路徑—定義和術(shù)語(yǔ)第52頁(yè)532025/5/157.5.2關(guān)鍵路徑—定義和術(shù)語(yǔ)設(shè)活動(dòng)ai在有向邊<j,k>上,有：活動(dòng)ai最早開(kāi)始時(shí)間e(i)：從源點(diǎn)v0到vj最長(zhǎng)路徑長(zhǎng)度。e(i)=ve(j);活動(dòng)ai最遲開(kāi)始時(shí)間l(i)：是不推遲工程完成前提下，該活動(dòng)允許最遲開(kāi)始時(shí)間。l(i)=vl(k)-dut(<j,k>)活動(dòng)ai時(shí)間余量：l(i)-e(i)關(guān)鍵活動(dòng)：滿足l(i)=e(i)活動(dòng)。關(guān)鍵路徑上活動(dòng)都是關(guān)鍵活動(dòng)。kjdut(<j,k>)ai第53頁(yè)542025/5/157.5.2關(guān)鍵路徑—求關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)e(i)=l(i)e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)ve(j)、vl(j)求頂點(diǎn)（事件）vk最早開(kāi)始時(shí)間：從ve(0)=0向匯點(diǎn)方向遞推

求頂點(diǎn)（事件）vj最遲開(kāi)始時(shí)間：從vl(n-1)=ve(n-1)向源點(diǎn)遞推

V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7ve(k)=Max{ve(j)+dut(<j,k>)}vl(j)=Min{vl(k)-dut(<i,j>)}在拓?fù)溆行蚯疤嵯逻M(jìn)行在逆拓?fù)溆行蚯疤嵯逻M(jìn)行第54頁(yè)552025/5/15由匯點(diǎn)至源點(diǎn)由源點(diǎn)至匯點(diǎn)1814161078660vl(i)181416775460ve(i)V9V8V7V6V5V4V3V2V1iV1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7關(guān)鍵路徑是V1,V2,V5,V7,

V9和V1,V2,V5,V8,V9ve(k)=Max{ve(j)+dut(<j,k>)}vl(j)=Min{vl(k)-dut(<j,k>)}e(i)=ve(j);l(i)=vl(k)–dut(<j,k>)14161077866320l(i)000000差1416777546000e(i)a11a10a9a8a7a6a5a4a3a2a1注意：關(guān)鍵路徑可有多條?？s短工期必須縮短關(guān)鍵活動(dòng)所需時(shí)間第55頁(yè)562025/5/15怎樣求關(guān)鍵路徑？(算法思想)（1）輸入e條弧<j,k>，建立AOE網(wǎng)存放結(jié)構(gòu)；（2）從源點(diǎn)v0出發(fā)，令ve[0]=0，按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)最早發(fā)生時(shí)間ve[i](1

i

n-1)。假如得到拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說(shuō)明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止，不然執(zhí)行步驟（3）；（3）從匯點(diǎn)vn出發(fā)，令vl[n-1]=ve[n-1]，按逆拓?fù)溆行蚯笥喔黜旤c(diǎn)最遲發(fā)生時(shí)間vl[i](n-2

i

2)（4）依據(jù)各頂點(diǎn)ve和vl值，求每條弧s最早開(kāi)始時(shí)間e(s)和最遲開(kāi)始時(shí)間l(s).若某條弧滿足條件e(s)=l(s),則為關(guān)鍵活動(dòng)。第56頁(yè)572025/5/15以下關(guān)于AOE網(wǎng)敘述中，不正確是（）

A.關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程完成時(shí)間

B.一些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成

C.全部關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成

D.任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成第57頁(yè)582025/5/159.2.1二叉排序樹(shù)二叉排序樹(shù)(二叉查找樹(shù)）(BinarySortTree,BST)：空樹(shù)或具有以下性質(zhì)二叉樹(shù):根左子樹(shù)若非空，則左子樹(shù)上全部結(jié)點(diǎn)關(guān)鍵字值均小于根結(jié)點(diǎn)值。根右子樹(shù)若非空，則右子樹(shù)上全部結(jié)點(diǎn)關(guān)鍵字值均大于根結(jié)點(diǎn)值。它左右子樹(shù)一樣是二叉排序樹(shù)。中序遍歷二叉排序樹(shù)可得到一個(gè)關(guān)鍵字有序序列第58頁(yè)592025/5/159.2.1二叉排序樹(shù)插入例：序列45、24、53、12、90組成一棵二叉排序樹(shù)建BST樹(shù)過(guò)程：一個(gè)無(wú)序序列能夠結(jié)構(gòu)二叉排序樹(shù)前提：查找失敗插入結(jié)點(diǎn)是一個(gè)葉子結(jié)點(diǎn)，且是查找失敗時(shí)查找路徑上訪問(wèn)最終一個(gè)結(jié)點(diǎn)左孩子或右孩子。插入算法：二叉排序樹(shù)存放結(jié)構(gòu)使用鏈表首先執(zhí)行查找算法，找出被插入結(jié)點(diǎn)父親結(jié)點(diǎn)。若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)左、右孩子。將結(jié)點(diǎn)插入4553902412第59頁(yè)602025/5/159.2.1二叉排序樹(shù)-刪除設(shè)二叉排序樹(shù)上被刪除結(jié)點(diǎn)是p，PL是p左子樹(shù)，PR是p右子樹(shù)，p雙親結(jié)點(diǎn)是f，不失普通性，設(shè)p是f左孩子。有三種情況：被刪除結(jié)點(diǎn)p是葉子結(jié)點(diǎn)；被刪除結(jié)點(diǎn)p只有左子樹(shù)或者只有右子樹(shù)；被刪除結(jié)點(diǎn)現(xiàn)有左子樹(shù)，也有右子樹(shù)。對(duì)二叉排序樹(shù)，刪去一個(gè)結(jié)點(diǎn)相當(dāng)于刪去有序序列中一個(gè)統(tǒng)計(jì)。第60頁(yè)612025/5/159.2.1二叉排序樹(shù)-刪除1）被刪除結(jié)點(diǎn)p是葉子結(jié)點(diǎn)：修改雙親結(jié)點(diǎn)指針，令

f->lchild=NULL4553902412pf45539024f例：刪除葉子結(jié)點(diǎn)12第61頁(yè)622025/5/159.2.1二叉排序樹(shù)-刪除2）被刪除結(jié)點(diǎn)p只有左子樹(shù)或者只有右子樹(shù)：令PL或PR直接為其雙親結(jié)點(diǎn)f左子樹(shù)即可，f->lchild=p->lchild||p->rchild。4553902412pf45539012f例：刪除結(jié)點(diǎn)24第62頁(yè)632025/5/159.2.1二叉排序樹(shù)-刪除3）被刪除結(jié)點(diǎn)現(xiàn)有左子樹(shù)，也有右子樹(shù)。在刪去p結(jié)點(diǎn)前，中序遍歷該二叉樹(shù)得到序列為{…CLC…QLQSLSPPRF…}，即S是中序遍歷序列中被刪結(jié)點(diǎn)p直接前驅(qū)結(jié)點(diǎn)。方法一：令P左子樹(shù)為F左子樹(shù)，P右子樹(shù)為S右子樹(shù)FPPLPRFPCQSPRCLQLSLFCQSPRCLQLSL第63頁(yè)642025/5/159.2.1二叉排序樹(shù)-刪除3）被刪除結(jié)點(diǎn)現(xiàn)有左子樹(shù)，也有右子樹(shù)。在刪去p結(jié)點(diǎn)前，中序遍歷該二叉樹(shù)得到序列為{…CLC…QLQSLSPPRF…}，即S是中序遍歷序列中被刪結(jié)點(diǎn)p直接前驅(qū)結(jié)點(diǎn)。方法二：令p直接前驅(qū)S替換p，再?gòu)亩媾判驑?shù)中刪去S。FPPLPRFPCQSPRCLQLSLFSCQPRCLQLSL第64頁(yè)652025/5/159.2.1二叉排序樹(shù)-刪除舉例刪除454553123732410061907845123732453100619078第65頁(yè)662025/5/159.2.1二叉排序樹(shù)-刪除舉例刪除45451233724531006190783745531237324100619078第66頁(yè)672025/5/15練習(xí)：假定一棵二叉排序樹(shù)采取二叉鏈表存放結(jié)構(gòu)，其根結(jié)點(diǎn)指針為T(mén),設(shè)計(jì)一個(gè)算法輸出該二叉排序樹(shù)中最大鍵值和最小鍵值。第67頁(yè)682025/5/15statusmaxmindata(){if(!T)returnerror;p=q=T;while(p->lchild!=NULL)p=p->lchild;printf(“Theminimumdatais:%d”,p->data);while(q->rchild!=NULL)q=q->rchild;printf(“Theminimumdatais:%d”,q->data);}第68頁(yè)692025/5/159.3哈希表查找表特點(diǎn)：統(tǒng)計(jì)關(guān)鍵字和在結(jié)構(gòu)中位置之間無(wú)確定關(guān)系查找過(guò)程是給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字比較查找效率取決于和給定值進(jìn)行比較關(guān)鍵字個(gè)數(shù)。希望不經(jīng)比較，直接能夠找到所查統(tǒng)計(jì)哈希函數(shù)：在統(tǒng)計(jì)關(guān)鍵字和其在表中位置之間建立一個(gè)函數(shù)關(guān)系，即以f(key)作為關(guān)鍵字為key統(tǒng)計(jì)在表中位置。第69頁(yè)702025/5/159.3哈希表定義和術(shù)語(yǔ)沖突：不一樣關(guān)鍵字得到同一哈希地址，key1

key2，f(key1)=f(key2)同義詞：在一個(gè)哈希函數(shù)中含有相同函數(shù)值不一樣關(guān)鍵字。

哈希表：依據(jù)設(shè)定哈希函數(shù)H(key)和所選中處理沖突方法，將一組關(guān)鍵字映象到一個(gè)有限、地址連續(xù)地址集(區(qū)間)上，并以關(guān)鍵字在地址集中“象”作為對(duì)應(yīng)統(tǒng)計(jì)在表中存儲(chǔ)位置，這種表被稱(chēng)為哈希表。哈希造表或散列：映象過(guò)程。哈希地址或散列地址：所得存放位置。結(jié)構(gòu)哈希表要注意問(wèn)題：考慮選擇一個(gè)“好”哈希函數(shù);

選擇一個(gè)處理沖突方法。第70頁(yè)712025/5/159.3.3處理沖突方法1開(kāi)放定址法：Hi=(H(key)+di)MODmi=1,2,…,k(k≤m-1)，H(key)為哈希函數(shù)；m：哈希表長(zhǎng)，di是增量序列，有三種取法di=1,2,…m-1，稱(chēng)為線性探測(cè)再散列di=12,-12,22,-22,…,±k2(k≤m/2)稱(chēng)為二次探測(cè)再散列di=偽隨機(jī)數(shù)列，稱(chēng)為隨機(jī)探測(cè)再散列第71頁(yè)722025/5/15處理沖突方法舉例例：一組關(guān)鍵字19,14,23,01,68,20,84,27,55,11,10,79；按H(key)=keymod13和線性探測(cè)再散列方法處理沖突結(jié)構(gòu)表長(zhǎng)為16哈希表。0123456789101112131415311931134121比較次數(shù)200820023010沖突次數(shù)ASLss=1/12（1*6+2+3*3+4+9）=2.5

14

0168275519208479231110第72頁(yè)732025/5/159.3.3處理沖突方法例：用哈希函數(shù)H(key)=keyMOD13和鏈地址法處理沖突求一組關(guān)鍵字19,14,23,01,68,20,84,27,55,11,10,79哈希表：0123456789101112∧∧∧∧∧∧∧01142779∧5568∧1984∧∧1023∧11∧20∧ASLss=1/12(1*6+2*4+3+4)=1.75第73頁(yè)742025/5/15練習(xí)：已知關(guān)鍵字序列為：（75,33,52,41,12,88,66,27），哈希表長(zhǎng)為10，哈希函數(shù)為：H(k)＝k%9，處理沖突用線性探測(cè)法，請(qǐng)：（1）結(jié)構(gòu)出哈希表；（2）計(jì)算等概率下查找成功平均查找長(zhǎng)度。第74頁(yè)752025/5/15TypedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域

}LNode,*LinkList;二、結(jié)點(diǎn)和單鏈表C語(yǔ)言描述LinkListL；//L為單鏈表頭指針第75頁(yè)762025/5/15TypedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域

}LNode,*LinkList;二、結(jié)點(diǎn)和單鏈表C語(yǔ)言描述LinkListL；//L為單鏈表頭指針第76頁(yè)772025/5/15三、單鏈表操作實(shí)現(xiàn)GetElem(L,i,&e)//取第i個(gè)數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,e)//刪除數(shù)據(jù)元素ClearList(&L)//重置線性表為空表CreateList(&L,n)//生成含n個(gè)數(shù)據(jù)元素鏈表第77頁(yè)782025/5/15L

線性表操作

GetElem(L,i,&e)

在單鏈表中實(shí)現(xiàn):211830754256∧pppj123第78頁(yè)792025/5/15

所以，查找第i個(gè)數(shù)據(jù)元素基本操作為：移動(dòng)指針，比較j和i。

單鏈表是一個(gè)次序存取結(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)據(jù)元素。

令指針p一直指向線性表中第j個(gè)數(shù)據(jù)元素。第79頁(yè)802025/5/15StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)鏈表頭指針，以e返回第i個(gè)元素}//GetElem_L算法時(shí)間復(fù)雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<i){p=p->next;++j;}//

順指針向后查找，直到p指向第i個(gè)元素

//

或p為空if(!p||j>i)

returnERROR;//第i個(gè)元素不存在e=p->data;//取得第i個(gè)元素returnOK;第80頁(yè)812025/5/15ai-1

線性表操作ListInsert(&L,i,e)

在單鏈表中實(shí)現(xiàn)：

有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1第81頁(yè)822025/5/15

所以，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入基本操作為:

找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼指針。

可見(jiàn)，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個(gè)結(jié)點(diǎn)之前插入元素，修改是第i-1個(gè)結(jié)點(diǎn)指針。第82頁(yè)832025/5/15StatusListInsert_L(LinkListL,inti,ElemTypee){

//L為帶頭結(jié)點(diǎn)單鏈表頭指針，本算法

//在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新元素e

}//LinstInsert_L算法時(shí)間復(fù)雜度為:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

尋找第i-1個(gè)結(jié)點(diǎn)if(!p||j>i-1)

returnERROR;//

i大于表長(zhǎng)或者小于1第83頁(yè)842025/5/15s=(LinkList)malloc(sizeof(LNode));

//生成新結(jié)點(diǎn)s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp第84頁(yè)852025/5/15線性表操作ListDelete(&L,i,&e)在鏈表中實(shí)現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>

改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1第85頁(yè)862025/5/15

在單鏈表中刪除第

i個(gè)結(jié)點(diǎn)基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq第86頁(yè)872025/5/15StatusListDelete_L(LinkListL,inti,ElemType&e){

//刪除以L為頭指針(帶頭結(jié)點(diǎn))單鏈表中第i個(gè)結(jié)點(diǎn)

}//ListDelete_L算法時(shí)間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;第87頁(yè)882025/5/15操作ClearList(&L)在鏈表中實(shí)現(xiàn):voidClearList(&L){//將單鏈表重新置為一個(gè)空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListfree(p);算法時(shí)間復(fù)雜度：O(ListLength(L))第88頁(yè)892025/5/15逆位序輸入n個(gè)數(shù)據(jù)元素值，建立帶頭結(jié)點(diǎn)單鏈表。操作步驟：一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入；ananan-1四、依次類(lèi)推，直至輸入a1為止。第89頁(yè)902025/5/15voidCreateList_L(LinkList&L,intn){//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)單鏈表}//CreateList_L算法時(shí)間復(fù)雜度為:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入}第90頁(yè)912025/5/15時(shí)間復(fù)雜度為O（La.length+Lb.length）。兩個(gè)有序線性表合并為一個(gè)有序線性表算法：voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){ pa=La->next;pb=Lb->next;

Lc=pc=La; while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; free(Lb);}第91頁(yè)922025/5/155.3.2稀疏矩陣稀疏矩陣：設(shè)m行n列矩陣含t個(gè)非零元素，則δ=t/(m*n)稱(chēng)為稀疏因子，通常認(rèn)為

0.05矩陣為稀疏矩陣。抽象數(shù)據(jù)類(lèi)型稀疏矩陣定義：書(shū)96頁(yè)稀疏矩陣壓縮存放稀疏矩陣中非零元素位置無(wú)規(guī)律記住非零元素行i，列j，值aij稀疏矩陣中存在多個(gè)非零元素三元組C語(yǔ)言描述

typedefstruct{inti,j;ElemTypee;}Triple三元組次序表C語(yǔ)言描述#defineMAXSIZE125000typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix第92頁(yè)932025/5/15三元組表表示稀疏矩陣轉(zhuǎn)置設(shè)M和T分別是MM和TT三元組表，怎樣由M得到T？將矩陣行列值(即m和n)相互交換將每個(gè)三元組中i和j對(duì)換重排三元組次序第93頁(yè)942025/5/15StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)

if(M.data[p].j==col)

{T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e;++q;}}returnOK;}//TransposeSMatrix三元組表表示稀疏矩陣轉(zhuǎn)置算法1評(píng)價(jià)：O(nu*tu)，優(yōu)點(diǎn):節(jié)約空間，tu<<mu*nu適用對(duì)MM每一列掃描一遍全部非零元第94頁(yè)952025/5/15三元組表表示稀疏矩陣轉(zhuǎn)置方法2思想：按M.data三元組次序轉(zhuǎn)置，再將三元組置入T中適當(dāng)位置。問(wèn)題：轉(zhuǎn)置前需知MM每列中非零元素個(gè)數(shù)及第一個(gè)非零元素在T.data中位置。處理方案：設(shè)num和cpot兩個(gè)向量，num[col]：矩陣MM第col列中非零元素個(gè)數(shù)，cpot[col]:矩陣MM第col列第一個(gè)非零元在T.data中位置cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1](2<=col<=M.nu)第95頁(yè)StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}returnOK;}//TransposeSMatrix

時(shí)間復(fù)雜度為O(nu+tu),若tu~mu*nu則為O(mu*nu)，與經(jīng)典算法相同，多用了兩個(gè)輔助向量。三元組表表示稀疏矩陣轉(zhuǎn)置方法2統(tǒng)計(jì)M中每一列非零元個(gè)數(shù)初始化M中每一列第一個(gè)非零元應(yīng)該在T中位置M中col列下一個(gè)非零元應(yīng)該在T中位置第96頁(yè)972025/5/15稀疏矩陣壓縮存放—行邏輯鏈接次序表需求：隨機(jī)存取任一行非0元方法：記住矩陣每一行第一個(gè)非0元在三元組表中位置設(shè)數(shù)組rpos[1..n]:矩陣中每行第一個(gè)非零元素起始位置。

rpos[1]=1;rpos[row]=rpos[row-1]+第row-1行非零元素個(gè)數(shù)行邏輯鏈接次序表:在稀疏矩陣存放結(jié)構(gòu)中固定指示行信息輔助數(shù)組rpos行邏輯鏈接表存放結(jié)構(gòu)Ｃ語(yǔ)言描述：typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXRC+1];//各行第一個(gè)非零元素位置表

intmu,nu,tu;}RLSMatrix

第97頁(yè)982025/5/15

0210-2400N=ijv22111-2324行邏輯鏈接表舉例row1234rpos[row]1235N三元組表

Nrpos向量第98頁(yè)992025/5/15基于行邏輯鏈接表表示稀疏矩陣相乘（1）對(duì)于每個(gè)元素M.data[p](p=1,2……,M.tu)，找到N中滿足條件N.data[q]，在查找過(guò)程中，用到rpos數(shù)組，rpos數(shù)組含義是稀疏矩陣中每行第一個(gè)非零元素在三元組當(dāng)中位置數(shù)組，rpos[row]：第row行第一個(gè)非零元素在N.data中序號(hào)，rpos[row+1]-1：第row行最終一個(gè)非零元素在N.data中序號(hào)，最終一個(gè)非零元素在N.data中位置序號(hào)是N.tu。求乘積M.data[p].v

N.data[q].v，然后累加。為操作方便，應(yīng)對(duì)每個(gè)元素設(shè)一個(gè)乘積和變量數(shù)組ctemp[]