數(shù)據(jù)結(jié)構(gòu) (特詳細(xì)2)課件

第2章線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4應(yīng)用舉例1例1：兩個(gè)鏈表的歸并（教材P31例）例2：一元多項(xiàng)式的計(jì)算

(教材P39–43)例3：試用C或類C語(yǔ)言編寫一個(gè)高效算法，將一循環(huán)單鏈表就地逆置。

微軟亞洲研究院去年來(lái)校招聘的筆試題操作前：（a1,a2,…ai-1，ai,ai+1，…,an）操作后：（an,…ai+1

，ai,ai-1，…,a2,a1）2分析：要想讓an指向an-1,……a2指向a1，一般有兩種算法：①替換法：掃描a1……an,將每個(gè)ai-1的指針域送入ai+1的指針域。實(shí)際上是鏈棧的概念操作后：（an,…ai+1

，ai,ai-1，…,a2,a1）^a1heada2思路：后繼變前驅(qū)思路：頭部變尾部②插入法：掃描a1……an,將每個(gè)ai插入到鏈表首部即可。3就地逆置程序段的改進(jìn)（周小明課后提交）//主程序被降到8行，因?yàn)閷?duì)空表的檢測(cè)可以不要。q=head->Next;//有頭結(jié)點(diǎn)pCur=q->Next;q->Next=(List*)head;

//第一結(jié)點(diǎn)處理while(pCur!=(List*)head)//空表或只有一個(gè)結(jié)點(diǎn)均會(huì)跳過(guò){ q=pCur->Next;//保存原后繼 pCur->Next=head->Next; head->Next=pCur; pCur=q;}5例4：試用C或類C語(yǔ)言編寫一高效算法，將一順序存儲(chǔ)的線性表（設(shè)元素均為整型量）中所有零元素向表尾集中，其他元素則順序向表頭方向集中。深圳華為公司去年來(lái)校招聘面試題常見(jiàn)做法：①?gòu)那巴髵呙?，?jiàn)到0元素則與尾部非0元素互換；②從后往前掃描，見(jiàn)到0元素則后面元素統(tǒng)統(tǒng)前移；③從前往后掃描，見(jiàn)到0元素先計(jì)數(shù)，再將后續(xù)的一個(gè)非0元素前移，全部掃完后再把后續(xù)部分（長(zhǎng)度為0元素的個(gè)數(shù)）清0。××√（a1,a2,…ai-1，ai,ai+1，…,an）6解：voidSortA(sqlist&L){inti=0,zerosum=0;if(L.length==0)return(0);//空表則結(jié)束else{for(i=1;i<=L.length;i++){if(L.v[i]<>0)L.v[i-zerosum]=L.v[i];elsezerosum++;}}for(i=L.length-zerosum+1;i<=L.length;i++)L.v[i]=0;//表的后部補(bǔ)0return(ok)；}//SortA若表完全不空，也要移動(dòng)n次？7解：

voidSortA(sqlist&L){inti=0,zerosum=0;if(L.length==0)return(0);

//空表則不執(zhí)行for(i;i<=L.length;i++){if(L.v[i]<>0&zerosum!=0)L.v[i-zerosum]=L.v[i];elsezerosum++};//適當(dāng)移動(dòng)非零元素,是零則增加計(jì)數(shù)for(i=L.length-zerosum+1;i<=L.length;i++)L.v[i]=0;//表的后部補(bǔ)0return(ok)；}若考慮表完全非空的情況，則程序要變長(zhǎng)很多。8動(dòng)態(tài)鏈表樣式：靜態(tài)鏈表樣式：指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)數(shù)組中每個(gè)元素都至少有兩個(gè)分量，屬于結(jié)構(gòu)型數(shù)組。常用于無(wú)指針類型的高級(jí)語(yǔ)言中。10前例2：一線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用靜態(tài)鏈表如何表示？——教材P32例題data0123456…1000cur說(shuō)明1：假設(shè)S為SLinkList型變量，則S[MAXSIZE]為一個(gè)靜態(tài)鏈表；S[0].cur則表示第1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。說(shuō)明2：如果數(shù)組的第i個(gè)分量表示鏈表的第k個(gè)結(jié)點(diǎn)，則：S[i].data表示第k個(gè)結(jié)點(diǎn)的數(shù)據(jù)；S[i].cur表示第k+1個(gè)結(jié)點(diǎn)(即k的直接后繼)的位置。i頭結(jié)點(diǎn)12例6：在雙向鏈表中如何實(shí)現(xiàn)插入和刪除運(yùn)算？單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點(diǎn)上增加一個(gè)指針域，用來(lái)存結(jié)點(diǎn)的直接前驅(qū)，這樣的鏈表，稱為雙向鏈表。其結(jié)點(diǎn)的結(jié)構(gòu)為：typedefstructDuLNode{

ElemTypedata;//數(shù)據(jù)域

structDuLNode*prior;

//前驅(qū)指針域structDuLNode*next;//后繼指針域}DuLNode,*DuLinkList;

雙向鏈表類型的定義如下：14雙向鏈表的插入操作：設(shè)p已指向第i元素，請(qǐng)?jiān)诘趇元素前插入元素x①ai-1的后繼從ai(指針是p)變?yōu)閤（指針是s):s->next=p;

p->prior->next=s;

②ai的前驅(qū)從ai-1(指針是p->prior)變?yōu)閤(指針是s);s->prior=p->prior;p->prior=s;

注意：要修改雙向指針！x

sai-1

ai

p指針域的變化：15指針域的變化：后繼方向：ai-1的后繼由ai(指針p)變?yōu)閍i+1(指針p->next

);

p->prior->next

=

p->next;前驅(qū)方向：ai+1的前驅(qū)由ai(指針p)變?yōu)閍i-1(指針p->prior

);

p->next->prior

=p->prior;

ai-1

ai+1

ai

p雙向鏈表的刪除操作：設(shè)p指向第i個(gè)元素，刪除第i個(gè)元素注意：要修改雙向指針！16本章小結(jié)線性結(jié)構(gòu)(包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。2.線性表邏輯結(jié)構(gòu)：“一對(duì)一”或“1:1”存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn)算：修改、插入、刪除[查找和排序另述]3.順序存儲(chǔ)特征：邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：隨機(jī)查找修改快

O(1)缺點(diǎn)：插入、刪除慢O(n)改進(jìn)方案：鏈表存儲(chǔ)結(jié)構(gòu)17循環(huán)鏈表的特點(diǎn)：從任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)雙向鏈表的特點(diǎn)：可方便找到任一結(jié)點(diǎn)的前驅(qū)靜態(tài)鏈表的特點(diǎn)：不用指針也能實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)和運(yùn)算4.鏈?zhǔn)酱鎯?chǔ)特征：邏輯上相鄰，物理上未必相鄰；優(yōu)點(diǎn)：插入、刪除快

O(1)缺點(diǎn)：隨機(jī)查找修改慢O(n)5.幾種特殊鏈表的特點(diǎn)：18討論2：什么是指針？指針的作用？指針—即變量的內(nèi)存地址。指針主要功能有二：①提供了一種快速訪問(wèn)數(shù)組單元的途徑；②使C語(yǔ)言函數(shù)可以修改其調(diào)用的參數(shù)。

&---指針操作符（單目），返回操作數(shù)地址；

*---運(yùn)算符（單目），是對(duì)&的補(bǔ)充，返回位于這個(gè)地址內(nèi)的變量之值。例：q=*m意即“q取地址m中的值”。如果數(shù)值100存儲(chǔ)在內(nèi)存地址2000中，而這一地址又存在m中，則q=(2000)=100討論3：與指針有關(guān)的符號(hào)&和*之間有何區(qū)別？20P43程序中，switch(*cmp(a,b))的cmp(a,b)一定是個(gè)特殊變量，它的值是一個(gè)內(nèi)存地址，而-1,0,+1這三種可能的執(zhí)行結(jié)果會(huì)放入該地址中，所存結(jié)果再由*cmp來(lái)尋址。那么，P42定義為intcmp(a,b)又怎么理解？意即cmp中地址（指針）存儲(chǔ)的是一個(gè)整型變量討論4：

P43程序中，switch(*cmp(a,b))的意思？21編制遞歸算法要注意些什么？遞歸進(jìn)行是有條件的。一般常把判斷語(yǔ)句加在遞歸語(yǔ)句以前。遞歸的最底層應(yīng)該有返回值，以供上層遞歸的調(diào)用。否則會(huì)死循環(huán)。遞歸調(diào)用需要利用堆棧。參量的初始化應(yīng)該在遞歸以前。 每次調(diào)用要把本次調(diào)用的參數(shù)和局部變量保存在棧頂。每次從下一層調(diào)用返回到上一層調(diào)用時(shí)，從棧頂恢復(fù)本層調(diào)用的參數(shù)和局部變量的值。23例2：設(shè)正整數(shù)a的前驅(qū)為PRIOR(a)，后繼為NEXT(a)，用遞歸算法計(jì)算a+b。

平常我們可以用循環(huán)來(lái)實(shí)現(xiàn)，但根據(jù)本題題意不能用循環(huán)，而要用遞歸。設(shè)計(jì)要點(diǎn)有二：①遞歸算法的形式化描述；②不能