數(shù)據(jù)的邏輯結(jié)構(gòu)(編輯修改稿)
2025-08-15 17:51 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 n1 1 2 i 元素序號(hào) i+1 n1 n an ai+2 ?算法評(píng)價(jià) ?設(shè) Qi是刪除第 i個(gè)元素的概率，則在長(zhǎng)度為 n的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的平均次數(shù)為： ????niide inQE1)(? ? ? ?nOnTninnEnQnidei????????? 1 21)(11則若認(rèn)為故在 順序表中插入或刪除 一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng) n很大時(shí)， 效率很低 ?順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn) ?優(yōu)點(diǎn) ?邏輯相鄰，物理相鄰 ?可隨機(jī)存取任一元素 ?存儲(chǔ)空間使用緊湊 ?缺點(diǎn) ?插入、刪除操作需要移動(dòng)大量的元素 ?預(yù)先分配空間需按最大空間分配，利用不充分 ?表容量難以擴(kuò)充 ? 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 特點(diǎn)： ?用一組 任意 的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素 ?利用 指針 實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 ?每個(gè)數(shù)據(jù)元素 ai， 除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息 ?結(jié)點(diǎn) ?數(shù)據(jù)域：元素本身信息 ?指針域：指示直接后繼的存儲(chǔ)位置 數(shù)據(jù)域 指針域 結(jié)點(diǎn) ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H 例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 43 13 1 NULL 37 7 19 25 數(shù)據(jù)域 指針域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU 存儲(chǔ)地址 1 7 13 19 25 31 37 43 31 H 頭指針 ?實(shí)現(xiàn) typedef struct LNode { ElemType data。 struct LNode *next。 }LNode, *LinkList。 LNode *h,*p。 data next p 結(jié)點(diǎn)（ *p） (*p)表示 p所指向的結(jié)點(diǎn) (*p).data?pdata表示 p指向結(jié)點(diǎn)的數(shù)據(jù)域 (*p).next?pnext表示 p指向結(jié)點(diǎn)的指針域 生成一個(gè) LNode型 新結(jié)點(diǎn)： p=(LNode *)malloc(sizeof(LNode))。 系統(tǒng)回收 p結(jié)點(diǎn)： free(p) ?線性鏈表 ?定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫 ~，也叫單鏈表 h a1 a2 頭結(jié)點(diǎn) an ^ …... h 空表 ^ 頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫 ~ 頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空 ?單鏈表的基本運(yùn)算 ?取元素： GetElem_L ? P29 算法 ?時(shí)間復(fù)雜度 T(n) = O(n) Status GetElem_L(LinkList amp。L,int i, ElemType amp。e) { // 算法 // L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。 // 當(dāng)?shù)?i個(gè)元素存在時(shí)，其值賦給 e并返回 OK，否則返回 ERROR p = Lnext。 j = 1。 // 初始化， p指向第一個(gè)結(jié)點(diǎn)， j為計(jì)數(shù)器 while (p amp。amp。 ji) { // 順指針向后查找，直到 p指向第 i個(gè)元素或 p為空 p = pnext。 ++j。 } if ( !p || ji ) return ERROR。 // 第 i個(gè)元素不存在 e = pdata。 // 取第 i個(gè)元素 return OK。 } // GetElem_L 24 Status ListInsert_L(LinkList amp。L, int i, ElemType e) { // 算法 // 在帶頭結(jié)點(diǎn)的單鏈線性表 L的第 i個(gè)元素之前插入元素 e p = L。 j = 0。 while (p amp。amp。 j i1) { p = pnext。 ++j。 } // 尋找第 i1個(gè)結(jié)點(diǎn) if (!p || j i1) return ERROR。 // i小于 1或者大于表長(zhǎng) s = (LinkList)malloc(sizeof(LNode))。 // 生成新結(jié)點(diǎn) sdata = e。 snext = pnext。 // 插入 L中 pnext = s。 return OK。 } // LinstInsert_L p a b x s ?插入：在線性表兩個(gè)數(shù)據(jù)元素 a和 b間插入 x， 已知p指向 a snext=pnext。 pnext=s。 ? P30 算法 ?時(shí)間復(fù)雜度 T(n) = O(n) Status ListDelete_L(LinkList amp。L, int i, ElemType amp。e) { // 在帶頭結(jié)點(diǎn)的單鏈線性表 L中，刪除第 i個(gè)元素，并由 e返回其值 p = L。 j = 0。 while (pnext amp。amp。 j i1) { // 尋找第 i個(gè)結(jié)點(diǎn)，并令 p指向其前趨 p = pnext。 ++j。 } if (!(pnext) || j i1) return ERROR。 // 刪除位置不合理 q = pnext。 pnext = qnext。 // 刪除并釋放結(jié)點(diǎn) e =
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1