嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)課件.ppt

《嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章線性表2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一、單鏈表二、結(jié)點(diǎn)和單鏈表的C語言描述三、線性表的操作在單鏈表中的實(shí)現(xiàn)四、其它形式的鏈表用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。一、單鏈表以元素(數(shù)據(jù)元素的映象)+指針(指示后繼元素存儲位置)=結(jié)點(diǎn)(表示數(shù)據(jù)元素或數(shù)據(jù)元素的映象)以“結(jié)點(diǎn)的序列”表示線性表??稱作鏈表以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭指針。頭結(jié)點(diǎn)a1a2…...an^頭指針頭指針有時(shí)為了操作方便，在第一個結(jié)點(diǎn)之前虛加一個“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針?？罩羔樉€性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?Typ

2、edefstructLNode{ElemTypedata;//數(shù)據(jù)域structLnode*next;//指針域}LNode,*LinkList;二、結(jié)點(diǎn)和單鏈表的C語言描述LinkListL；//L為單鏈表的頭指針三、單鏈表操作的實(shí)現(xiàn)GetElem(L,i,&e)//取第i個數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,&e)//刪除數(shù)據(jù)元素ClearList(&L)//重置線性表為空表CreateList(&L,n)//生成含n個數(shù)據(jù)元素的鏈表L線性表的操作GetElem(L,i,&e)在單鏈表中的實(shí)現(xiàn):21

3、1830754256∧pppj123因此，查找第i個數(shù)據(jù)元素的基本操作為：移動指針，比較j和i。單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個數(shù)據(jù)元素，必須先找到第i-1個數(shù)據(jù)元素。令指針p始終指向線性表中第j個數(shù)據(jù)元素。StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第i個元素}//GetElem_L算法時(shí)間復(fù)雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&jnext;++j;}//順指針向后查找，直

4、到p指向第i個元素//或p為空if(!p

5、

6、j>i)returnERROR;//第i個元素不存在e=p->data;//取得第i個元素returnOK;ai-1線性表的操作ListInsert(&L,i,e)在單鏈表中的實(shí)現(xiàn)：有序?qū)?ai-1,ai>改變?yōu)?ai-1,e>和eaiai-1因此，在單鏈表中第i個結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:找到線性表中第i-1個結(jié)點(diǎn)，然后修改其指向后繼的指針?？梢姡阪湵碇胁迦虢Y(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個結(jié)點(diǎn)之前插入元素，修改的是第i-1個結(jié)點(diǎn)的指針。StatusListInsert_L(LinkLis

7、tL,inti,ElemTypee){//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法//在鏈表中第i個結(jié)點(diǎn)之前插入新的元素e}//LinstInsert_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))……p=L;j=0;while(p&&jnext;++j;}//尋找第i-1個結(jié)點(diǎn)if(!p

8、

9、j>i-1)returnERROR;//i大于表長或者小于1s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)s->data=e;s->next=p->next;p->next=s;//插入returnOK;ea

10、i-1aiai-1sp線性表的操作ListDelete(&L,i,&e)在鏈表中的實(shí)現(xiàn):有序?qū)?ai-1,ai>和改變?yōu)?ai-1,ai+1>ai-1aiai+1ai-1在單鏈表中刪除第i個結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個結(jié)點(diǎn)，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;e=q->data;free(q);pqStatusListDelete_L(LinkListL,inti,ElemType&e){//刪除以L為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個結(jié)點(diǎn)}//ListDelet

11、e_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p->next&&jnext;++j;}//尋找第i個結(jié)點(diǎn)，并令p指向其前趨if(!(p->next)

12、

13、j>i-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;操作ClearList(&L)在鏈表中的實(shí)現(xiàn):voidClearList(&L){//將單鏈表重新置為一個空表while(L->next){p=L->next;L->nex

14、t=p->next;}}//ClearListfre