數(shù)據(jù)結(jié)構(gòu)課件線性表(編輯修改稿)
2025-08-17 21:19 本頁面
【文章內(nèi)容簡介】 。 return OK。 } 遞減插入 Status DeOrderInsert_Sq(SqList amp。La, ElemType x) { int i, j。 if ( = ) return OVERFLOW。 i=。 while (i=0 amp。amp。 [i]x) i。 //不同之處 for (j=。 ji。j) [j+1] = [j]。 [i+1]= x。 ++。 return OK。 } 4. 順序表的分析 1）優(yōu)點 ? 順序表的結(jié)構(gòu)簡單 ? 順序表的存儲效率高，是緊湊結(jié)構(gòu) ? 順序表是一個隨機存儲結(jié)構(gòu)（直接存取結(jié)構(gòu)） 2）缺點 ? 在順序表中進行插入和刪除操作時，需要移動數(shù)據(jù)元素，算法效率較低。 ? 對長度變化較大的線性表，或者要預(yù)先分配較大空間或者要經(jīng)常擴充線性表，給操作帶來不方便。 ? 原因：數(shù)組的靜態(tài)特性造成 作業(yè) ? 編寫程序，建立并顯示一個有 10個數(shù)據(jù)元素的順序線性表。 ? 實現(xiàn)順序線性表的插入、查找、刪除等 算法。 順序表之整體概念： elem 0 1 length1 listsize length 數(shù)組下標(biāo) 內(nèi)存狀態(tài) 變量 操作算法 listsize1 初始化操作 插入操作 刪除操作 查找操作 排序操作 . . . . . . . . . . . . . . . 空閑 表區(qū) elem 順序表之整體概念： 順序表有下列缺點： （ 1）插入、刪除操作時需要移動大量元素， 效率較低； （ 2）最大表長難以估計，太大了浪費空間， 太小了容易溢出。 因此，在插入和刪除操作是經(jīng)常性操作的應(yīng)用場合 選用順序存儲結(jié)構(gòu)不太合適，此時可以選用鏈?zhǔn)酱鎯Y(jié) 構(gòu)，數(shù)據(jù)元素之間的邏輯關(guān)系由結(jié)點中的指針來指示。 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 1. 線性鏈表 ? 特點：在內(nèi)存中用一組任意的存儲單元來存儲線性表的數(shù)據(jù)元素，用每個數(shù)據(jù)元素所帶的指針來確定其后繼元素的存儲位置。這兩部分信息組成數(shù)據(jù)元素的存儲映像，稱作 結(jié)點 。 ? 結(jié)點 ：數(shù)據(jù)域 + 指針域（鏈域） ? 鏈?zhǔn)酱鎯Y(jié)構(gòu)： n個結(jié)點鏈接成一個鏈表 ? 線性鏈表（單鏈表）：鏈表的每個結(jié)點只包含一個指針域。 data next 單鏈表 (Singly Linked List) ? first 頭指針 ? last 尾指針 ? ^ 指針為空 ? 單鏈表由頭指針唯一確定，因此常用頭指針的名字來命名。如表 first. 單鏈表的存儲映像 1）線性鏈表的描述 p28 typedef struct LNode{ ElemType data。 Struct LNode *next。 } LNode, *LinkList。 LinkList L。 //L是 LinkList類型的變量， 表示單鏈表的頭指針 2）術(shù)語 ? 頭指針：指向鏈表中第一個結(jié)點 ? 第一個數(shù)據(jù)元素結(jié)點（開始結(jié)點） ? 頭結(jié)點：有時在單鏈表的第一個數(shù)據(jù)元素結(jié)點之前附設(shè)一個結(jié)點，稱之頭結(jié)點。 ?說明：頭結(jié)點的 next域指向鏈表中的第一個數(shù)據(jù)元素結(jié)點。 ?對于頭結(jié)點數(shù)據(jù)域的處理： ，則在該處存放鏈表長度信息。 3）帶頭結(jié)點的單鏈表示意圖 p28圖 ? 由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以對鏈表第一個位置的操作同其他位置一樣，無須特殊處理。 ? 無論鏈表是否為空，其頭指針是指向頭結(jié)點的非空指針，因此對空表與非空表的處理也就統(tǒng)一了，簡化了鏈表操作的實現(xiàn)。 非空表 空表 2. 基本操作 1）取元素 p29 算法 2）插入元素 p30 算法 3）刪除元素 p30 算法 4）建立鏈表 p30~p31 算法 5）有序鏈表的合并 p31 算法 6）查找（按值查找） 7）求長度 8）集合的并運算 取元素（按序號查找） p29 算法 從鏈表的頭指針出發(fā)，順鏈域 next逐個結(jié)點往下搜索，直至找到第 i個結(jié)點為止（ j=i) Status GetElem_L(LinkList L, int i,ElemType amp。e) { LinkList p。 p=Lnext。 int j=1。 while (p amp。amp。 ji) { p=pnext。 ++j。 } if (!p || ji) return ERROR。 e=pdata。 return OK。 } 插入元素 p30 算法 在第 i個元素之前插入，先找到第 i1個結(jié)點 Status ListInsert_L(LinkList amp。L,int i,ElemType e) { LinkList p,s。 p=L。 int j=0。 while (p amp。amp。 ji1) { p=pnext。 ++j。}//插入點，前一指針 if (!p || j i1) return ERROR。 s = (LinkList) malloc( sizeof (LNode))。 sdata = e。 snext = pnext。 pnext = s。 return OK。} … e s Pnext=s … (2) (3) p snext=pnext a (1) b 在帶表頭結(jié)點的單鏈表 第一個結(jié)點前插入新結(jié)點 newnode→ next = p→ next。 if ( p→ next ==NULL ) last = newnode。 p→ next = newnode。 刪除元素 p30 算法 Status ListDelete_L(LinkList amp。L, int i, ElemType amp。e) { LinkList p,q。 p=L。 int j=0。 while (pnext amp。amp。 ji1) { p=pnext。 ++j。} if (!(pnext) || j i1) return ERROR。 q=p
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1