程序設(shè)計綜合實踐課件-線性表的鏈?zhǔn)酱鎯?單鏈表的概念

四、線性表的鏈?zhǔn)酱鎯Σ捎面準(zhǔn)酱鎯Y(jié)構(gòu)，有利于線性表的插入、刪除操作，每個結(jié)點中只有一個“鏈”時，稱為單鏈表，每個結(jié)點中有兩個“鏈”時，稱為雙向鏈表。“鏈”通常用指針來表示，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)也是實現(xiàn)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。12圖1.2單鏈表結(jié)點和單鏈表示例4.1單鏈表的概念一般結(jié)點類型定義如下：structNode{

DataElemdata;

structNode*next;};structNode*p，*q;//聲明指針型變量p、q3特別需要注意指針變量p和p所指結(jié)點的區(qū)別。指針變量p和p所指結(jié)點是獨立存在的當(dāng)p是空指針時，禁止通過空指針訪問結(jié)點內(nèi)數(shù)據(jù)域或指針域通過非空指針變量p可訪問結(jié)點的數(shù)據(jù)域p->data和指針域p->nextp->data和p->next既可作為右值、又可作為左值出現(xiàn)在表達式中。右值和左值是表達式中語法單位，意味著可出現(xiàn)在賦值運算符右邊和左邊p->next還是一個指針，只要它非空，可以繼續(xù)通過它訪問所指結(jié)點的數(shù)據(jù)域和指針域，如p->next->data和p->next->next指針變量p未初始化時，不可訪問p->next或p->data，否則，可能造成程序崩潰C/C++語言中，動態(tài)分配的結(jié)點必須釋放，否則造成內(nèi)存泄漏4常見的指針操作效果示意圖p=(structNode*)malloc(sizeof(structNode));p->data=20;p->next=NULL;20^pq=p;？20qpq=p->next;qp………20…操作前操作后操作？p？qp…2030…qp…2030…（待續(xù)）

p=p->next;p…2030…p…2030…q->next=p;q…2030…q…2030…p15p15操作前操作后操作（待續(xù)）q->next=p->next;q…2030…q…2030…p10p106…6…操作前操作后操作線性表中插入元素時，需要在鏈表中增加結(jié)點，用下述語句動態(tài)分配：p=(structNode*)malloc(sizeof(structNode));動態(tài)分配失敗時，返回空指針（NULL），現(xiàn)代面向?qū)ο蟪绦蛟O(shè)計語言中，如C++，一般按異常處理。下列語句完成將p所指結(jié)點插入q所指結(jié)點后:p->next=q->next;//p后繼結(jié)點設(shè)為原q后繼結(jié)點q->next=p;//q后繼結(jié)點設(shè)為p下列語句刪除p所指結(jié)點后繼結(jié)點:q=p->next;//保存后繼結(jié)點指針p->next=q->next;//鏈