64653administrator-資料下載頁(yè)
2024-09-30 09:46本頁(yè)面
【導(dǎo)讀】將表中元素一個(gè)接一個(gè)的存入一組連續(xù)的存儲(chǔ)單。采用順序存儲(chǔ)結(jié)構(gòu)的線性表簡(jiǎn)稱為“順序表”。其中，L是元素占用存儲(chǔ)單元的長(zhǎng)度。step2將x插入到ai-1之后;step1判別指定的位置是否合法；數(shù)據(jù)連續(xù)存放、隨機(jī)存取。邏輯上相鄰，物理上也相鄰。存儲(chǔ)結(jié)構(gòu)簡(jiǎn)單、易實(shí)現(xiàn)。插入、刪除操作不便。存儲(chǔ)密度大，空間利用率高。鏈表存儲(chǔ)結(jié)構(gòu)在這兩個(gè)方面恰好是優(yōu)點(diǎn)：。–不需要預(yù)分空間。首元結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)。若沒(méi)有頭結(jié)點(diǎn),空表和非空表的表示形式。由食品組成的單鏈表。設(shè)指針變量p、q的定義為：NODE*p，*q；申請(qǐng)一個(gè)結(jié)點(diǎn)空間,并將地址送入p中.p=p->next指針p向后移動(dòng)一個(gè)結(jié)點(diǎn)。p->next=NULL將指針p所指結(jié)點(diǎn)與后繼結(jié)點(diǎn)斷開(kāi)。step2P非空且計(jì)數(shù)器小于i循環(huán)。step3每循環(huán)一次,P后移一個(gè)位置,step4循環(huán)結(jié)束,返回指向ai的指針P.step1找到ai-1的位置,使指針p指向ai-1
【正文】 up down 上指針 下指針 后繼結(jié) 點(diǎn)指針 前趨結(jié) 點(diǎn)指針 特點(diǎn)： 四個(gè)方向可 以自由移動(dòng) 鏈表結(jié)點(diǎn)及標(biāo)識(shí)符 約定： 設(shè)指針 p指向結(jié)點(diǎn) ai ， ? ai作為一個(gè)變量，其標(biāo)識(shí)符為 p? ? 由于 p?是記錄類型，它的分量分別表示為： 數(shù)據(jù)域標(biāo)識(shí)符為 p? .data 后繼結(jié)點(diǎn)指針域?yàn)? p?.next p p p?.data p?.next ai ai 鏈表結(jié)點(diǎn)及各分量標(biāo)識(shí)符 (雙鏈表 ) 約定： 設(shè)指針 p指向結(jié)點(diǎn) ai ， ? ai作為一個(gè)變量，其標(biāo)識(shí)符為 p? ? p?的分量分別表示為： 數(shù)據(jù)域標(biāo)識(shí)符為 p? .data, 后繼結(jié)點(diǎn)指針域?yàn)? p?.next , 前趨結(jié)點(diǎn)指針域?yàn)?p? .prior。 p ai1的標(biāo)識(shí)符為 : p?.prior, ai1的數(shù)據(jù)域?yàn)?: p?.prior ? .data ai+1的標(biāo)識(shí)符為 : p?.next, ai+1的數(shù)據(jù)域?yàn)?: p?. next ? .data a i+1 ai a i1 鏈表存儲(chǔ)結(jié)構(gòu)的特點(diǎn) ? 插入、刪除操作極為方便 ? 數(shù)據(jù)非連續(xù)存放、順序存取 ? 邏輯上相鄰，物理上不一定相鄰 ? 存儲(chǔ)結(jié)構(gòu)較復(fù)雜、需要額外的存儲(chǔ)空間 結(jié)論 ： 鏈表存儲(chǔ)結(jié)構(gòu)適合于表中元素頻繁變動(dòng)的線性表。 鏈表的動(dòng)態(tài)生成 ? 鏈表是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。因此，建立鏈表的過(guò)程是動(dòng)態(tài)生成的過(guò)程。 按鏈表結(jié)點(diǎn)建立的順序、方向不同，分為兩種方法： ? 從前往后的動(dòng)態(tài)生成法 （ 算法 26） ? 從后往前的動(dòng)態(tài)生成法 （算法 27） 鏈表動(dòng)態(tài)生成（方法一）從前往后 算法操作步驟： ? step1 初始化；頭指針置 NULL ? step2 輸入結(jié)點(diǎn)數(shù)據(jù)非 0循環(huán) 1)、 使 s指向新生成的結(jié)點(diǎn)， sdata = num 2)、 若 head=NULL(第 1個(gè)結(jié)點(diǎn) ) ,head=s 3)、 否則 pnext=s 4) 、 指針 p始終指向 s , p=s ? step3 結(jié)束循環(huán) ,pnext =NULL, 返回頭指針 head。 head s ^ ... p a i ai1 a2 a1 鏈表的動(dòng)態(tài)生成（方法二）從后往前 算法操作步驟： ? step1 初始化；頭指針置 NULL,線性表元素存于 A[N]中 ,i=N1 ? step2 i = 0 循環(huán) 1) 使 s指向新生成的結(jié)點(diǎn)， 2) sdata = A[i] ,snext = head 3) 指針 s始終指向頭指針 head=s ? step3 結(jié)束循環(huán) , 返回頭指針 head。 head ^ ... s ai1 ai an ai1 思考題 : 第 1章習(xí)題的 1~2題 2. 作業(yè)題 : 第 1章習(xí)題的 14,15題 3. 將課本上相關(guān)例子改為 VC版 上交 : 時(shí)間下周星期四之前 學(xué)號(hào) +姓名 .zip 棧與隊(duì)列 下一講
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1