數(shù)據(jù)結構課件線性表-資料下載頁
2025-07-21 21:19本頁面
【正文】 t=L。 while (scanf(%d,amp。x), x!=0 ) { p=(LinkList)malloc(sizeof(LNode))。 pdata=x。 pnext = Lnext。 Lnext = p。 } } 顯示輸出算法（帶頭結點） —— 循環(huán)鏈表 void PrintList_LC(LinkList L) { LinkList p。 p=Lnext。 printf(L)。 while (p!=L) { printf(%d,pdata)。 p=pnext。 } printf(L\n)。 } (Doubly Linked List) ? 雙向鏈表是指在前驅和后繼方向都能游歷 (遍歷 )的線性鏈表。 1) 雙向鏈表的結點結構： 前驅方向 ?(a)結點結構 ? 后繼方向 雙向鏈表通常采用帶表頭結點的循環(huán)鏈 表形式。 pp rr ii oo rr (( 左左 鏈鏈 指指 針針 )) dd aa tt aa (( 數(shù)數(shù) 據(jù)據(jù) )) nn ee xx tt (( 右右 鏈鏈 指指 針針 )) ? 對雙向循環(huán)鏈表中任一結點的指針，有： p == p→ prior→ next == p→ next→ prior ? 置空表： p→ prior = p 。 p→ next = p。 (b) 非空雙向循環(huán)鏈表 (c) 空表 2）雙向循環(huán)鏈表存儲結構的 描述 p35~p36 typedef struct DuLNode{ ElemType data。 struct DuLNode *prior。 struct DuLNode *next。 }DuLNode, *DuLinkList。 DuLinkList d,p。 p→ prior = current。 (1) p→ next =current→ next。 (2) current→ next = p。 (3) p→ next→ prior = p。 (4) 雙向循環(huán)鏈表的插入算法（插入 p） current→ next→ prior = current→ prior。 current→ prior→ next = current→ next。 雙向循環(huán)鏈表的刪除算法 (刪除 current) 3）基本操作： 雙向循環(huán)鏈表的建立 void CrtList_DuL(DuLinkList amp。L) { DuLinkList p。 int x。 L=p=(DuLinkList)malloc(sizeof(DuLNode))。 L next=L。 Lprior =L。 while (scanf(%d,amp。x),x!=0){ pnext=(DuLinkList)malloc(sizeof(DuLNode))。 pnextprior =p。 p=pnext。//開頭插入 pdata=x。 } pnext=L。 Lprior =p。 } 顯示輸出 void PrtList_DuL(DuLinkList L) { DuLinkList p。 p=Lnext。 printf(L)。 while (p!=L){ printf(%d,pdata)。 p=pnext。 } printf(\n)。 } iniinnnxaxaxaxaaxP????????02210 )( ? 一元多項式的表示和相加 ? n階多項式 Pn(x)有 n+1項。 ? 系數(shù) a0, a1, a2, …, an ? 指數(shù) 0, 1, 2, …, n。按升冪排列 ? 在計算機中，可以用一個線性表來表示 ?P=(a0,a1, … , an) 1. 第一種表示方法 Pn=(a0,a1, … , an) 適用于指數(shù)連續(xù)排列、 “ 0”系數(shù)較少的情況 。但對于指數(shù)不全的多項式，如 P20220(x) = 3 + 5x50 + 14x20220, 會造成系統(tǒng)空間的巨大浪費。 2. 第二種表示方法 一般情況下，一元多項式可寫成： Pn(x)=p1xe1+p2xe2+…+p mxem 其中： pi是指數(shù)為 ei的項的非零系數(shù)， 0≤e1 ≤e2 ≤… ≤em ≤n 二元組表示 ((p1,e1),(p2,e2), … ,(p m,em)) 例： P999(x) = 7x3 2x12 8x999 表示成 : ((7,3),(2,12),(8,999)) ADT Polynomial { 數(shù)據(jù)對象 : D={ai|ai ∈ TermSet, i=1,2,…,m, m ≥0 TermSet中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù) } 數(shù)據(jù)關系： R1={ai1,ai|ai1,ai ∈ D,且ai1中的指數(shù)值 ai中的指數(shù)值 , i=2,…n} 基本操作： }ADT Polynomial 3. 一元多項式的抽象數(shù)據(jù)類型定義 typedef struct { float coef。 int expn。 }term, ElemType。 //term用于本 ADT, ElemType為 LinkList的數(shù)據(jù)對象名 typedef LinkList polynomial。 4. 抽象數(shù)據(jù)類型 (Polynomial)的實現(xiàn) 多項式鏈表的相加 AH = 1 10x6 + 2x8 +7x14 BH = x4 + 10x6 3x10 + 8x14 +4x18 兩個多項式的相加 ? 結果多項式另存 ? 掃描兩個相加多項式，若都未檢測完： ? 若當前被檢測項指數(shù)相等，系數(shù)相加。若未變成 0，則將結果加到結果多項式。 ? 若當前被檢測項指數(shù)不等，將指數(shù)小者加到結果多項式。 ? 若有一個多項式已檢測完，將另一個多項式剩余部分復制到結果多項式。
規(guī)章制度相關推薦
鄂ICP備17016276號-1