【文章內(nèi)容簡介】 { char ch。 LinkList H,p,q。 H=NULL。 q=H。 scanf(ch)。 while(ch!=?\n39。) { p=(LinkList)malloc(sizeof(LNode))。 pdata=ch。 if(H= = NULL) H=p。 else qnext=p。 q=p。 scanf(ch)。 } pnext= NULL。 return H。 } head是頭指針 頭結(jié)點 空指針 head ? 頭指針： 用于存放線性鏈表中第一個結(jié)點的存儲地址 。 ? 空指針： 不指向任何結(jié)點，線性鏈表最后一個結(jié)點的指針通常是空指針 。 ? 頭結(jié)點： 線性鏈表的第一元素結(jié)點前面的一個附加結(jié)點，稱為頭結(jié)點； ? 帶頭結(jié)點的線性鏈表： 第一元素結(jié)點前面增加一個附加頭結(jié)點的線性鏈表稱為 帶頭結(jié)點的線性鏈表； an a1 a2 非空表 空表 二，線性鏈表基本操作的算法 如何在線性鏈表 上實現(xiàn)線性表的基本操作？ 如何建表 ?查找 ?如何插入 ?刪除 ? 約定用帶頭結(jié)點的線性鏈表 存儲線性表 head an a1 a2 1. 建立單鏈表 （前插法） L p X L pnext=Lnext。 Lnext=p。 L an a1 p X pnext=Lnext。 Lnext=p。 1. 建立單鏈表 （前插法） LinkList CreateList(int n) { LinkList L,p。 int i。 L=(LinkList)malloc(sizeof(LNode))。 Lnext=NULL。 for(i=n。i0。i) { p=(LinkList)malloc(sizeof(LNode))。 scanf(%d,amp。pdata)。 pnext=Lnext。 Lnext=p。 } return(L)。 } 2. 按序號查找 L an a1 LNode* Get_List_Node(LinkList head, int i) /* 在單鏈表中查找第 i個結(jié)點 ,返回其指針 ,若失敗返回空 */ { LNode *p。int j。 p=head。j=0。 while((pnext!=NULL)amp。amp。ji) { p=pnext。 j++。 } if(j= =i) return p。 else return NULL。 } 3. 按值查找 L an a1 LNode* Locate_List_Node(LinkList head,Etype x) /*在單鏈表中查找值為 x的結(jié)點 ,返回其指針 ,查找失敗返回空 */ { LNode *p。 p=headnext。 while((p!=NULL)amp。amp。(pdata!=x)) p=pnext。 /* 后移查找指針 */ if(p!=NULL) return p。 return NULL。 } 4. 插入操作 int ListInsert(LinkList L,int i,Etype e) 功能： 在線性鏈表的第 i個結(jié)點之前插入一個新結(jié)點； 插入操作主要步驟： 1）查找鏈表 L的第 i1個結(jié)點； 2）為新元素建立結(jié)點； 3）修改第 i1個元素結(jié)點的指針和新元素結(jié)點指 針完成插入； ② ① 注意 的順序！ ① ② head an ai1 ai a1 head an ai1 ai a1 插入前 插入后 x snext=pnext。 pnext=s。 int ListInsert(LinkList L,int i,Etype e) { LinkList p。 p=Get_List_Node(L,i1)。 if(p=NULL) return ERROR。 s=(LinkList)malloc(sizeof(LNode))。 sdata=e。 snext=pnext。 pnext=s。 return OK。 } 4. 插入操作 5. 刪除操作 int ListDelete(LinkList L,int i,Etype e) 功能： 刪除線性鏈表的第 i個結(jié)點； 刪除操作主要步驟： 1）查找鏈表的第 i1個元素結(jié)點 ,使指針 p指向它 , 將 指針 q指向第 i個結(jié)點； 2）修改第 i1個元素結(jié)點指針，使其指向第 i個元素 結(jié)點的后繼； 3）回收 q指針所指的第 i個結(jié)點空間； ai+1 head an ai1 ai a1 刪除前 刪除后 ai+1 head an ai1 ai a1 p q p q 插入操作圖示： pnext=qnext。 pnext=pnext next。 free(q)。 int ListDelete(LinkList L,int i,Etype e) { LinkList p,q。int j。ElemType e。 p=Get_List_Node(L,i1)。 if(p==NULL||pnext==NULL) return ERROR。 q=pnext。 pnext=qnext。 e=qdata。 free(q)。 return OK。 } 5. 刪除操作 演示 三、線性鏈表的其他操作的實現(xiàn) 例 1 將兩個遞增有序線性鏈表歸并成一個遞增有序表。 設(shè)線性表 A、 B分別用頭指針為 La 、 Lb 的兩個帶頭結(jié)點的線性鏈表存儲 , 歸并后的遞增有序表頭指針為 Lc, 將兩表數(shù)據(jù)較小的結(jié)點依次取出插入到新表。 演示 利用基本操作 直接對鏈表進行操作 LinkList MergeList(LinkList La,LinkList Lb) { LinkList Lc,pa,pb,pc。 pa=Lanext。 pb=Lbnext。 Lc=pc=La。 while (paamp。amp。pb) { if (padata=pbdata) { pcnext=pa。pc=pa。pa=panext。 } else { pcnext=pb。pc=pb。pb=pbnext。 } } pcnext=pa?pa:pb。 free(Lb)。 return(Lc)。 } 例 2 某倉庫中有一批電視機，按價格從低到高構(gòu)成一單鏈表存于計算機中。鏈表的每個結(jié)點指出同樣價格的若干臺，現(xiàn) 又到新 m臺價格為 h的電視機入庫。請寫出鏈表增加電視的算法。 Cost number next typedef struct LNODE { float cost。 int number。 struct LNODE *next。 }LNode,*LinkList。 LinkList TVSets(LinkList s,int m,float h) { LinkList p,q,t。 q=s。 p=snext。 while(p!=NULLamp。amp。pcosth) { q=p。 p= pnext。 } if (p!=NULLamp。amp。pcost==h) pnumber=pnumber+m。 else{ t=(LinkList)malloc(sizeof(LNode))。 tcost=h。 tnumber=