[院校資料]第二章-線性表(編輯修改稿)
2024-11-12 23:56 本頁面
【文章內(nèi)容簡介】 式表示 :可以用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素 。 存儲單元即可以是連續(xù)的 ，也可以是不連續(xù)的 ， 甚至是零散分布在內(nèi)存中的任意位置上的 。 鏈表中結(jié)點的邏輯次序和物理次序不一定相同 。 為了能正確表示結(jié)點間的邏輯關(guān)系 ， 在存儲每個結(jié)點值的同時 ， 還必須存儲指示其后繼結(jié)點的地址 （ 或位置 ） 信息 ? 例 : 線性表 (趙，錢，孫，李，周，伍，張，王 )的鏈?zhǔn)奖硎? 線性鏈表 數(shù)據(jù)域 指針域李 43錢 13孫 1王 NULL伍 37趙 7張 19周 251 13 19 25 31 37 43 7 頭指針： 31(趙的地址 ) 存儲地址 : 錢 孫 李 周 趙 伍 張 王 H 鏈表相關(guān)的名稱 ? 數(shù)據(jù)域 、 指針域 ? 結(jié)點 、 頭結(jié)點 ? 指針 (鏈 ) ? 鏈表 、 單鏈表 (線性鏈表 ) a1 a2 a3 L ai an typedef struct Lnode{ ElemType data。 struct Lnode *next。 }Lnode, *Linklist。 線性表的單鏈表存儲結(jié)構(gòu) Status GetElem_L(LinkList L, int i, ElemType amp。e) { //L為帶頭結(jié)點的單鏈表的頭指針 。當(dāng)?shù)?i個元素 //存在時，其值賦給 e并返回 OK, 否則返回 ERROR. LinkList p。 int j。 p = Lnext。 j = 1。 while (p amp。amp。 ji){ p = pnext。 ++j。 } if(!p || ji) return ERROR。 e = pdata。 return OK。 } 線性表的單鏈表存儲結(jié)構(gòu) ? 插入結(jié)點 :指針 p所指的結(jié)點后插入 指針 s所指的結(jié)點 ? snext = pnext。 pnext = s。 snext=pnext a1 a3 a2 p s 插入前： a2 a1 a3 p s pnext=s 插入后： 線性表的單鏈表存儲結(jié)構(gòu) ?插入結(jié)點：在帶頭結(jié)點的單鏈表第 i個結(jié)點前插入元素 e Status ListInsert_L(LinkList amp。L, int i, ElemType e) { LinkList s,p。 int j。 p = L。 j = 0。 while( p amp。amp。 ji1 ){ p=pnext。 ++j } if(!p||ji1) return ERROR。 s = (Lnode *)malloc(sizeof(Lnode))。 if(!s) return OVERFLOW。 sdata = e。 snext = pnext。 pnext = s。 return OK。 } 線性表的單鏈表存儲結(jié)構(gòu) ? 刪除結(jié)點：刪除指針 p所指的結(jié)點后的結(jié)點 ? pnext = pnext next。 a1 a3 a2 p 刪除前： 刪除后： a1 a3 a2 p pnext = pnext next s s=pnext 釋放結(jié)點后： a1 a3 p free(s) 線性表的單鏈表存儲結(jié)構(gòu) ?刪除結(jié)點 :刪除第 i個元素，并由 e返回其值 Status ListDelete_L(LinkList L, int i, ElemType amp。e) { LinkList s,p。 int j。 p = L。 j = 0。 while(pnext amp。amp。 ji1){p=pnext。++j} if(!(pnext)||ji1) return ERROR。 s = pnext。 pnext = snext。 e = sdata。 free(s)。 return OK。 } 線性表的單鏈表存儲結(jié)構(gòu) ? 建立單鏈表 :逆位序輸入 n個元素 ,建立帶表頭結(jié)點的單鏈表 L void CreateList_L( LinkList amp。L , int n ) { L = (LinkList)malloc(sizeof(LNode)) 。 Lnext = null 。 for( int i = n 。 I 0 。 i ) { p = (LinkList)malloc(sizeof(LNode))。 scanf(amp。pdata) 。 pnext = Lnext 。 //插入表頭 Lnext = p 。 } } 線性表的單鏈表存儲結(jié)構(gòu) ? 建立單鏈表 : 按位序輸入 n個元素 ,建立帶表頭結(jié)點的單鏈表 L void CreateList_L( LinkList amp。L , int n ) { L = (LinkList)malloc(sizeof(LNode)) 。 Lnext = NULL 。 ListNode *r = NULL 。 for( int i = 0 。 i n 。 i++ ) { p = (LinkList)malloc(sizeof(LNode))。 scanf(amp。pdata) 。 if( Lnext == null ) { Lnext = p 。 } else { rnext = p 。 } r = p 。 } if ( r != NULL ) rnext = NULL 。 } 線性表的單鏈表存儲結(jié)構(gòu) ? 例：合并兩個有序鏈表 void MergeList(LinkListamp。La,LinkListamp。 Lb,LinkListamp。 lc) { ListNode* pa = Lanext 。 ListNode* pb = Lbnext 。 while( pa amp。amp。 pb ) { if ( padata = pbdat
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1