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

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