【文章內容簡介】 性鏈表操作的實現 (5) LinkedList LinkedListLocate(LinkedList L, LNode *p) {//在單鏈表 L中求 p指向的結點 (假定存在）的前驅 if(Lnext==p) {printf(“p指向第一元素結點，無前驅 ” )。exit(0)。} pre=L。 while(pre!=NULL amp。amp。 prenext!=p) pre=prenext。 if(pre) return pre。 else return null。 } 查找結點的前驅 : 2022/10/23 34 線性鏈表操作的實現 (6) LinkedList LinkedListLocate(LinkedList L, LNode *p) {//在單鏈表 L中求 p指向的結點 (假定存在）的后繼 pre=L。 while(pre!=NULL amp。amp。 prenext!=p) pre=prenext。 if(pnext==null) {printf(“p指向最后元素結點，無后繼 ” )。exit(0)。} else return p。 } 查找結點的后繼 : 2022/10/23 35 線性鏈表操作的實現 (7) p表示當前結點， pre表示前一個結點 (的指針 )。 在 p前插入元素 s snext = prenext。 prenext = s。 ak next 插入元素： ai1 next ai next pre 2022/10/23 36 線性鏈表操作的實現 (7) 插入算法 : void LinkedListInsert(LinkedList L,LNode *p,ElemType x) {//在結點 p之前插入元素為 x的結點 pre=L。 while (pre!=NULL amp。amp。 prenext!=p) pre=prenext。 //找 p的直接前驅 if(!pre) {printf(“不存在 *p結點 ” )； exit(0)。} s=(LNode*)malloc(sizeof(LNode))。 //創(chuàng)建新結點 sdata=x。 //設置新結點的元素值 snext=prenext。 prenext=s。 //插入新結點 } 2022/10/23 37 線性鏈表操作的實現 (8) p表示當前結點， pre表示前一個結點。 prenext = pnext。 free( p )。 //p = prenext。 刪除元素 : ai1 next ai next ai+1 next 2022/10/23 38 線性鏈表操作的實現 (8) 刪除元素 : void LinkedListDel (LinkedList L， int i) {//刪除單鏈表 L上的第 i個結點 if (i1) {printf(“參數錯誤” )。exit(0)。} p=L。j=1。 while(pnext amp。amp。 ji) {p=pnext。 j++} if(pnext==NULL || ji) {printf(“刪除位置不正確 ” )； exit(0)。} q=pnext。 pnext=qnext。 //從鏈表中刪除 free(q)。 //釋放被刪除結點 } 2022/10/23 39 線性鏈表操作的實現 (9) 建立單鏈表－－頭插法 : ∧ L 36 ∧ L 36 ∧ 45 L 10 36 ∧ 45 L 23 10 36 ∧ 45 L 36 ∧ 45 10 23 67 L 2022/10/23 40 線性鏈表操作的實現 (9) LinkedList LinkedListCreat1( ) {//用頭插法建立帶頭結點的單鏈表 LinkedList L。 L=(LNode *)malloc(sizeof(LNode))。 Lnext=NULL。 //初始化一個空鏈表， L為頭指針 scanf(amp。x)。 //x是和鏈表元素具有相同類型的變量 while (x!=flag) //flag為結束輸入的標志 {//生成新結點 p=(LNode *)malloc(sizeof(LNode))。 pdata=x。 //輸入元素值 pnext=Lnext。 Lnext=p。 //插入到表頭 scanf(amp。x)。 //讀入下一個元素的值 } return L。 } 頭插法建立單鏈表算法: 2022/10/23 41 線性鏈表操作的實現 (10) 建立單鏈表－－尾插法 : 67 r L 23 67 r L 10 23 67 r L 36 ∧ 45 10 23 67 r L 45 10 23 67 r L 2022/10/23 42 線性鏈表操作的實現 (10) LinkedList LinkedListCreat3( ) {//用尾插法建立帶頭結點的單鏈表 LinkedList L。 L=(LNode*)malloc(sizeof(LNode))。 Lnext=NULL。 r=L。 scanf(amp。x)。 while (x!=flag) //設置結束標志 {p=(LNode*)malloc(sizeof(LNode)。 pdata=x。 //賦值元素值 rnext=p。 //在尾部插入新結點 r=p。 //r 指向新的尾結點 scanf(amp。x)。 } rnext=NULL。 //最后結點的指針域放空指針 return L。 } 尾插法建立單鏈表算法: 2022/10/23 43 鏈表的遍歷 void print(LinkedList la) //非遞歸 {LinkedList p=lanext。 while (p) {printf(“%c”,pdata)。 p=pnext。 } } void out(LinkedList p) //遞歸 {if(p) {out(pnext)。 printf(“%c”,pdata)。 } } 2022/10/23 44 鏈表算法舉例 合并單鏈表 ? LinkedList Union(LinkedList la， LinkedList lb) ? {∥ 將非遞減有序的單鏈表 la和 lb合并成新的非遞減有序單鏈表 lc，并要求利用原表空間 ? lc=(LNode*)malloc(sizeof(LNode)。 ∥ 申請結點 ? lcnext=NULL。 ∥ 初始化鏈表 lc ? pa=lanext。 ∥ pa是鏈表 la的工作指針 ? pb=lbnext。 ∥ pb是鏈表 lb的工作指針 ? pc=lc。 ∥ pc是鏈表 lc的工作指針 ? while(pa amp。amp。 pb) ∥ la和 lb均非空 ? if(padata=pbdata) ? {pcnext=pa。 pc=pa。 ? pa=panext。 ? }∥ la中元素插入 lc 2022/10/23 45 鏈表算法舉例 （接上頁） else ? {pcnext=pb。 ? pc=pb。 ? pb=pbnext。 ? }∥ lb中元素插入 lc ?