大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第二章：線性表-第三節(jié)-線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二）

第三節(jié)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二）二、單鏈表上的基本運(yùn)算（考試最重要的內(nèi)容）1、單鏈表的建立動(dòng)態(tài)建立單鏈表的常用方法有兩種：一種是頭插法，另一種則是尾插法。（1）頭插法建表：從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。算法描述：LinkListCreateListF(){LinkListhead；ListNode*p；．charch；head=NULL；//置空單鏈表ch=getchar()；//讀入第一個(gè)字符while(ch!='\n')//讀入字符不是結(jié)束標(biāo)志符時(shí)作循環(huán){p=(ListNode*)malloc(sizeof(ListNode))；//分配一個(gè)類(lèi)型為L(zhǎng)istNode的結(jié)點(diǎn)的地址空問(wèn)，并將其首地址存入指針變量p中。p->data=ch;//數(shù)據(jù)域賦值p->next=head；//指針域賦值head=p；//頭指針指向新結(jié)點(diǎn)ch=getchar();//讀入下一個(gè)字符}returnhead；//返回鏈表的頭指針}（2）尾插法：將新結(jié)點(diǎn)插入在當(dāng)前鏈表的表尾上，因此需要增設(shè)一個(gè)尾指針rear，使其始終指向鏈表的尾結(jié)點(diǎn)。算法描述：LinkListCreateListR(){LinkListhead，rear；ListNode*p；charch；head=NULL；rear=NULL；//置空單鏈表ch=getchar()；//讀入第一個(gè)字符while(ch!='\n')//讀入字符不是結(jié)束標(biāo)志符時(shí)作循環(huán){p=(ListNode*)malloc(Sizeof(ListNode))；//申請(qǐng)新結(jié)點(diǎn)p->data=ch；//數(shù)據(jù)域賦值if(head==NULL)head=p;//新結(jié)點(diǎn)*p插入空表elserear->next=p；//新結(jié)點(diǎn)*p插入到非空表的表尾結(jié)點(diǎn)*rear之后rear=p，//表尾指針指向新的表尾結(jié)點(diǎn)ch=getchar()；//讀入下一個(gè)字符}if(rear!=NULL)rear->next=NULL；//終端結(jié)點(diǎn)指針域置空returnhead；}帶頭結(jié)點(diǎn)的單鏈表：作用是可以簡(jiǎn)化單鏈表的算法在引入頭結(jié)點(diǎn)之后，尾插法建立單鏈表的算法可簡(jiǎn)化為：LinkListCreateLlstRl()//尾插法建立帶頭結(jié)點(diǎn)的單鏈表算法{LinkListhead=(ListNode*)malloc(Sizeof(ListNode));//申請(qǐng)頭結(jié)點(diǎn)ListNode*p，*r；DataTypech；r=head；//尾指針初始指向頭結(jié)點(diǎn)while((ch=getchar())!='\n'){p=(ListNode*)malloc(sizeof(ListNode))；//申請(qǐng)新結(jié)點(diǎn)p->data=ch；r->next=p；//新結(jié)點(diǎn)連接到尾結(jié)點(diǎn)之后r=p;//尾指針指向新結(jié)點(diǎn)}r->next=NULL；//終端結(jié)點(diǎn)指針域置空returnhead;}真題選解（例題·單選題）1、在帶頭結(jié)點(diǎn)的單鏈表h中，若要向表頭插入一個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行()。A．h=p；p->next=h；B．p->next=h；h=p；C．p->next=h；p=h；D．p->next=h->next；h->next=p；隱藏答案【答案】D【解析】向表頭插入，即在第一個(gè)結(jié)點(diǎn)之前插入，這就要把第一個(gè)結(jié)點(diǎn)鏈接到p結(jié)點(diǎn)之后，而將p結(jié)點(diǎn)鏈接到頭結(jié)點(diǎn)之后。2、查找運(yùn)算（1）在單鏈表中要查找第i個(gè)結(jié)點(diǎn)算法描述ListNode*GetNodei(LinkListhead，inti){//head為帶頭結(jié)點(diǎn)的單鏈表的頭指針，i為要查找的結(jié)點(diǎn)序號(hào)ListNode*p；intj;p=head->next;j=1；//使p指向第一個(gè)結(jié)點(diǎn)，j置1while(p!=NULL&&j<i)//順指針向后查找，直到p指向第i個(gè)結(jié)點(diǎn)或p為空為止{p=p->next；++j；}if(j==i)//若查找成功，則返回查找結(jié)點(diǎn)的存儲(chǔ)地址(位置)，否則返回NULLreturnp；e1sereturnNULL；}算法分析①最好情況是查找第1個(gè)元素，循環(huán)執(zhí)行0次②最壞情況是查找第n+1個(gè)元素，循環(huán)執(zhí)行n次。③在等概率情況下，循環(huán)執(zhí)行次數(shù)為：（n+（n-1）+（n-2）+…+2+1+0）/（n+1）=n/2。故算法平均時(shí)間復(fù)雜性是O（n）。（2）在單鏈表中查找值為k的結(jié)點(diǎn)算法描述LiStNode*LocateNodek(LinkListhead，DataTypek){//head為帶頭結(jié)點(diǎn)的單鏈表的頭指針，k為要查找的結(jié)點(diǎn)值ListNode*p=head->next；//p指向開(kāi)始結(jié)點(diǎn)while(p&&p->data!=k)//循環(huán)直到p等于NULL或p->data等于k為止p=p->next；//指針指向下一個(gè)結(jié)點(diǎn)returnp；//若找到值為k的結(jié)點(diǎn)，則p指向該結(jié)點(diǎn)，否則p