[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)課件吳偉民編著-展示頁
2024-10-28 04:12本頁面
【正文】 i 元素序號(hào) i+1 n1 n an ai+2 Void deleteList(Sqlist*L， int i) { int j。（最好 O(1)） 移動(dòng)結(jié)點(diǎn)的平均次數(shù)： 按等概率考慮： 可能的插入位置為 i=1,2,……n,n+1 共 n+1個(gè)，則 pi=1/(n+1) 所以 順序表插入算法平均約需移動(dòng)一半結(jié)點(diǎn)。 } 插入算法分析： 上述算法 for循環(huán)語句的執(zhí)行次數(shù)為 ni+1。 Ldata[i1]=x。j=i1。 exit(overflow)。 return ERROR。 演示 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標(biāo) n1 i n 1 2 i 元素序號(hào) i+1 n n+1 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標(biāo) n1 i n 1 2 i 元素序號(hào) i+1 n n+1 an1 x Void InsertList(Sqlist*L， ElemType x， int i) { int j。 插入 線性表的插入運(yùn)算是指在表的第i(1≦ i≦ n+1)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x， 使長(zhǎng)度為 n的線性表 (a1， …a i1， ai， … ， an) 變成長(zhǎng)度為 n+1的線性表 (a1， …a i1， x， ai， … ， an) 插入算法的思想： 將 ai,ai+1,...,an依次后移一個(gè)位置，使第 i位置留空 將新元素 x放在空出的位置上。 注意： C語言中的數(shù)組下標(biāo)從“ 0”開始，因此，若 L是 Sqlist類型的順序表，則表中第 i個(gè)元素是 [i1]。 } Sqlist。 typedef struc{ ElemType data[ListSize]。又因?yàn)槌擞脭?shù)組來存儲(chǔ)線性表的元素之外，順序表還應(yīng)該用一個(gè)變量來表示線性表的長(zhǎng)度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。 一個(gè)一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個(gè)數(shù)組元素用相鄰的 ５個(gè)字節(jié) 存儲(chǔ)。 顯然，數(shù)據(jù)元素在順序表中位置取決于數(shù)據(jù)元素在線性表中的位置。 若一個(gè)數(shù)據(jù)元素占 L個(gè)存儲(chǔ)單元，則其存儲(chǔ)方式參見下圖。 （ 1）存取 （ 2）插入 （ 3）刪除 （ 4）查找 （ 5）合并 （ 6）分解 （ 7）排序 （ 8）求線性表的長(zhǎng)度 基本運(yùn)算 線性表的順序存儲(chǔ)結(jié)構(gòu)（順序表） ： 用一組連續(xù)的存儲(chǔ)單元（地址連續(xù)）依次存放線性表的各個(gè)數(shù)據(jù)元素。 a 1 a 2 …… a n 圖 2 1 線性表邏輯結(jié)構(gòu)示意圖 線性表的形式化定義為： linear_list=(D,R) 其中 D={ai ∣ 1≤i≤n,n≥0,ai∈ elemtype} R={ai,ai+1 ∣ 1≤i≤n1} 例 26個(gè)英文字母組成的字母表 （ A， B， C、 … 、 Z） 例 某校從 1978年到 1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。 （ 2）數(shù)據(jù)元素 在線性表中的位置只取決于它的序號(hào)。 （ 4） ai是屬于某個(gè)數(shù)據(jù)對(duì)象的元素，它可以是一個(gè)數(shù)字、一個(gè)字母或一個(gè)記錄。 當(dāng) n=0 時(shí)，稱為 空表 。 ? 線性表的定義及運(yùn)算 ： 是由 n(n=0)個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）a1,a2,a3, ……a n組成的有限序列。第二章 線性表 線性結(jié)構(gòu) 特點(diǎn) ：在數(shù)據(jù)元素的非空有限集中 ?存在 唯一 的一個(gè)被稱作“ 第一個(gè) ”的數(shù)據(jù)元素 ?存在 唯一 的一個(gè)被稱作“ 最后一個(gè) ”的數(shù)據(jù)元素 ?除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均 只有一個(gè)前驅(qū) ?除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均 只有一個(gè)后繼 第二章 線性表 教學(xué)目的 ： （ 1） 了解線性表的邏輯結(jié)構(gòu)特性 ， 以及線性表的兩種存儲(chǔ)實(shí)現(xiàn)方式； （ 2） 熟練掌握順序表的定義與實(shí)現(xiàn) ， 包括查找 、 插入 、 刪除算法的實(shí)現(xiàn)； （ 3） 熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法 ， 能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu) 。 教學(xué)的 重點(diǎn)和難點(diǎn) ：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1