線性表順序表鏈表順序表與鏈表的比較-文庫吧資料
2024-10-25 11:38本頁面
【正文】 +an1xn1 +anxn g(x)= 8x 9x8 + 22x9 f(x)= 7+3x +9x8 +5x17 7 0 3 1 9 8 5 17 ? f 8 1 9 8 22 9 ? g 方法一： 依次將 g中每個結(jié)點(diǎn) “ 插入 ” 到 f中。 struct node *next。 結(jié)點(diǎn)結(jié)構(gòu)： 系數(shù) 指數(shù) 指針 coef exp next 結(jié)點(diǎn)數(shù)據(jù)類型： typedef struct node { float coef。 pnext== ? p pnext=L2。 L1 a1 a2 am1 am ? （ 1）確定 L1的最后一個結(jié)點(diǎn) p。 rnext=p。 pdata=x。 設(shè)置 r總是指向 q的前驅(qū) 例 3 在按值有序的單鏈表中插入一個新元素 x，使其仍有序。 刪除結(jié)點(diǎn) q 注：要先確定 q的前驅(qū)結(jié)點(diǎn) r rnext=qnext。 Lnext=p。 return true。 //p指向第 i個結(jié)點(diǎn) pnext=qnext。 //確定第 i1個結(jié)點(diǎn)的前驅(qū) if ( p==NULL ) return false。 （ 2）確定第 i個結(jié)點(diǎn)； （ 3）刪除該結(jié)點(diǎn)，并釋放； int ListDelete (LinkList *L, int i) //將在鏈表中第 i 個結(jié)點(diǎn)刪除 { LinkList *p,*q。 free(q)。 //將 p插入 r之后 return true。 //生成新結(jié)點(diǎn) p并賦值 snext=pnext。//插入失敗 s=(LinkList *)malloc(sizeof(LinkList))。 GetElem (head,i1,p)。 } 掃描單鏈表 尋找第 i個結(jié)點(diǎn) i初值 ? bool ListInsert (LinkList *amp。 } if(p==NULL) return false。 p!=NULL) //不是第 i個結(jié)點(diǎn) { p=pnext。 while( ji amp。 p=L。p) //取單鏈表中第 i個結(jié)點(diǎn) { LinkList *p。 生成新結(jié)點(diǎn) s=malloc( ) pnext 在單鏈表中第 i個位置插入一個新元素 （ 1）確定第 i1個結(jié)點(diǎn) GetElem(L, i1)。 s 插入 p s p 注意：先確定 s的直接前驅(qū) r,在 p之后插入新結(jié)點(diǎn) p。 //r總是指向表尾 } rnext=NULL。 rnext=s 。//生成新結(jié)點(diǎn) sdata=a[i]。i=n。 //建立一個空表 r= L。L,Elemtype a[ ], int n ) //利用尾插法建立單鏈表 { LinkList *L, *s, *r。 （ 2）依次將每個新結(jié)點(diǎn)插入鏈表中。 return(h)。L ) //建立一個空表 { L=(LinkList *)malloc(sizeof(LinkList))。 r = p。 p=malloc( )。 ? 依次將新結(jié)點(diǎn)插入在鏈表的表尾。 } return n。 //計數(shù)器初值 while ( p != NULL ) { n++。 //移動 p指向下一個結(jié)點(diǎn) } 鏈表的基本操作形式 p L a1 a2 a3 ? n= 1 p L a1 a2 a3 ? n= 2 p L a1 a2 a3 ? n= 3 P=^ L a1 a2 a3 ? 求單鏈表長度 n= 0 int ListLength ( LinkList *L ) { LinkList *p = Lnext。 //p指向下一個結(jié)點(diǎn) 直到 p== ? 結(jié)束 P ? p=Lnext。 ? 設(shè)置表頭結(jié)點(diǎn)的目的是 ? 統(tǒng)一空表與非空表的操作 ? 簡化鏈表操作的實(shí)現(xiàn) 非空表 ? an a1 L ? 空表 頭指針 頭結(jié)點(diǎn) L a1 a2 a3 a4 ? L 活動指針 單鏈表的基本操作 p=Lnext。 表隨意可擴(kuò)充。 注： 結(jié)點(diǎn)可以連續(xù)，可以不連續(xù)存儲。 LinkList *list。 //結(jié)點(diǎn)數(shù)據(jù)域 struct LNode *next。e) O(n) *時間性能 隨機(jī)存取效率高 ,但插入和刪除移動工作量大 . *空間性能 無需額外增加空間來表示數(shù)據(jù)元素之間的關(guān)系 . 但要預(yù)先分配存儲空間 ,將會出現(xiàn)溢出或浪費(fèi)現(xiàn)象 . 鏈表（ Linked List） 鏈表是線性表的鏈接存儲表示 鏈表的種類 (1)實(shí)現(xiàn)方式 : 動態(tài)鏈表和靜態(tài)鏈表 (2)鏈接形式 單鏈表．雙向鏈表和循環(huán)鏈表 單鏈表的存儲映像 (a) 可利用存儲空間 a1 a3 a2 a4 ? list (b) 經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu) 2020 2020 2050 2080 2050 2080 2020 單鏈表 (Singly LinkeList) data next 一、結(jié)點(diǎn)結(jié)構(gòu) 二、單鏈表的表示 list a1 a2 a3 a4 a5 ? 空指針 NULL 空表 list= (list=NULL) ? 數(shù)據(jù)元素 指向下一個結(jié)點(diǎn) 三、結(jié)點(diǎn)的數(shù)據(jù)類型 typedef int ElemType。L， i， e) O(n) ? ListDelete (amp。L） O(1) ? ListLength（ L） O(1) ? GetElem（ L， i, amp。 return ture。 j Llength1。 e=Ldata[i]。e) { //在表中刪除已有元素 x if ( i 1 || i Llength) return false。 //插入成功 } } 221)(1)(1 0)1(11)(11=nnnnnn1inn1n1i????????????????A M N時間性能分析 最好情況：插入在 n+1 上，移動 0次 T(n)=O(1) 最壞情況：插入在首位，移動 n次 T(n)=O(n) 通過移動次數(shù)來衡量 平均情況： T(n)=O(n) 元素的刪除 25 34
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1