《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件2-05頭插法建立單鏈表

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：簡(jiǎn)勇 頭插法建立單鏈表常州信息職業(yè)技術(shù)學(xué)院02三、鏈表的插入03頭插法建立單鏈表0.5算法步驟：要求：假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是字符型，逐個(gè)輸入這些字符，并以換行符n作為輸入結(jié)束的條件，使用頭插法動(dòng)態(tài)地建立單鏈表（不帶頭結(jié)點(diǎn)）。算法思路：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入換行符n為止。將頭指針head置為NULL，轉(zhuǎn)向。如圖2-3。讀取字符ch，判斷ch與n是否不相等，若是轉(zhuǎn)向，否則，返回head。生成一個(gè)新結(jié)點(diǎn)*s（即由s指向），轉(zhuǎn)向。如圖2-4。將ch寫

2、入新結(jié)點(diǎn)*s數(shù)據(jù)域，轉(zhuǎn)向。如圖2-5。圖2-3 頭指針head圖2-4 新結(jié)點(diǎn)ss圖2-5 值寫入數(shù)據(jù)域as04頭插法建立單鏈表0.556將新結(jié)點(diǎn)*s插入鏈表的前面（第1個(gè)重復(fù)進(jìn)行第步到第步，便可建立一個(gè)含有多個(gè)結(jié)點(diǎn)的不帶頭結(jié)點(diǎn)的單鏈表，如圖2-8。結(jié)點(diǎn)時(shí)是將*s指針域置為NULL），轉(zhuǎn)向。如圖2-6。將頭指針指向新結(jié)點(diǎn)，轉(zhuǎn)向。如圖2-7。圖2-6 新結(jié)點(diǎn)前插sasahead圖2-7 頭指針指向新結(jié)點(diǎn)頭插法建單鏈表重復(fù)進(jìn)行第步到第步，便可建立一個(gè)含有多個(gè)結(jié)點(diǎn)的不帶頭結(jié)點(diǎn)的單鏈表，如圖2-8。sdheadcba圖2-8 頭插法建單鏈表05頭插法建立單鏈表0.5LinkList CreatListF(void)/頭插法建立單鏈表DataType ch;LinkList head; ListNode *s; head=NULL; printf(請(qǐng)輸入鏈表各結(jié)點(diǎn)的數(shù)據(jù)(字符型):n);while(ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode );if(s=NULL)printf(申請(qǐng)存儲(chǔ)空間失敗!);return head;s-data=ch; /輸入的數(shù)據(jù)寫入結(jié)點(diǎn)數(shù)據(jù)域s-next=head; /將新結(jié)點(diǎn)*s插入鏈表的前面head=