數(shù)據(jù)結(jié)構(gòu)課件第二章線(xiàn)性表3講

2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室1/18第二章線(xiàn)性表

第3講2.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

1、鏈?zhǔn)讲檎?/p>

2、插入

3、刪除

4、單鏈表的建立

5、單鏈表特點(diǎn)2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室2/182.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息結(jié)點(diǎn) 數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域指針域結(jié)點(diǎn)2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室3/18ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線(xiàn)性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室4/18實(shí)現(xiàn)typedefstructLNode{

ElemType

data;structLNode*next;}LNode,*LinkList;LNode*h,*p;datanextp結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)(*p).data

p->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).next

p->next表示p指向結(jié)點(diǎn)的指針域生成一個(gè)LNode型新結(jié)點(diǎn)：p=(LinkList)malloc(sizeof(LNode));系統(tǒng)回收p結(jié)點(diǎn)：free(p)線(xiàn)性鏈表定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫~，也叫單鏈表2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室5/18頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫~頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€(xiàn)性表為空ha1a2頭結(jié)點(diǎn)an^…...h空表^2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室6/18單鏈表的基本運(yùn)算查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回指向X結(jié)點(diǎn)的指針；否則返回NULLWhile循環(huán)中語(yǔ)句頻度為若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)X在表中的序號(hào)否則，為n算法評(píng)價(jià)2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室7/18StatusGetElem_L(LinkListL,intpos,ElemType&e){//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)線(xiàn)性表中存在第pos個(gè)//元素存在時(shí)，則將第pos個(gè)數(shù)據(jù)元素的值賦給e并返回OK，//否則返回ERRORp=L->next;j=1;//初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<pos){//順指針向后查找，直到p指向第pos個(gè)元素或p為空p=p->next;++j;}if(!p||j>pos)returnERROR;//第pos個(gè)元素不存在e=p->data;//取第pos個(gè)元素returnOK;}//GetElem_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))查找2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室8/18C源代碼:LNode*dlbcz(LNode*h,intx){ LNode*p; p=h; while(p!=NULL&&p->data!=X) p=p->next; return(p);}2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室9/18插入：在線(xiàn)性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p指向apabxsp->next=s;s->next=p->next;單鏈表插入視頻演示算法評(píng)價(jià)2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室10/18//在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L中第i個(gè)位置之前插入元素eStatusListInsert_L(LinkList&L,inti,ElemTypee){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnOK;}//ListInsert_L插入2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室11/18C源代碼：voiddlbcr(LNode*p,intx){ LNode*s; s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=p->next; p->next=s;}2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室12/18pabc算法評(píng)價(jià)刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap->next=p->next->next;單鏈表刪除視頻演示2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室13/18//在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L中，刪除第i個(gè)元素，并由e返回其值StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}//ListDelete_L刪除2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室14/18C源代碼：voiddlbsc(LNode*p){ LNode*q; if(p->next!=NULL) {q=p->next; p->next=q->next; free(q); }}2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室15/18動(dòng)態(tài)建立單鏈表算法：設(shè)線(xiàn)性表n個(gè)元素已存放在數(shù)組a中，建立一個(gè)單鏈表，h為頭指針?biāo)惴ㄔu(píng)價(jià)h頭結(jié)點(diǎn)an^0h頭結(jié)點(diǎn)an-10an^a2…...h頭結(jié)點(diǎn)an-10an^ha1a2頭結(jié)點(diǎn)an^…...0Ch2_3.ch頭結(jié)點(diǎn)0^2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室16/18//逆位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表LvoidCreateList_L(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);p->next=L->next;L->next=p;}}//CreateList_L建單鏈表2023/9/17計(jì)算機(jī)科學(xué)與技術(shù)教研室17/18C源代碼：LNode*dlbjl(inta[],intn){ LNode*s,*h; inti; h=(LNode*)malloc(sizeof(LNode)); h->data=0; h->next=NULL; for(i=n;i>0;i--) {s=(LNode*)mallo