[院校資料]第二章-線性表-文庫吧在線文庫
【正文】 int listsize。 } Status ListInsert_Sq(Sqlistamp。([i1])。 } Status ListDelete_Sq(Sqlistamp。p=q。 存儲單元即可以是連續(xù)的 ，也可以是不連續(xù)的 ， 甚至是零散分布在內(nèi)存中的任意位置上的 。 int j。 e = pdata。 j = 0。 snext = pnext。 j = 0。 free(s)。 scanf(amp。 for( int i = 0 。 } if ( r != NULL ) rnext = NULL 。 pb ) { if ( padata = pbdata ) { pcnext = pa 。 //釋放頭結(jié)點 } } ? 循環(huán)鏈表的特點 :表中的最后一個結(jié)點的指針域指向頭結(jié)點 , 整個鏈表形成一個環(huán) 。 循環(huán)鏈表 ? 鏈表初始化： Status InitList( LinkListamp。 e ) { link p 。 } 循環(huán)鏈表 int LocateElem( LinkList L , ElemType e , int (*pare) (ElemType,ElemType ) ) { int i = 1 。 循環(huán)鏈表 ? 插入操作 void ListInsert(LinkList L, int i, ElemType e ) { link p , y 。 sdata=e。 // 排除空表的情況 if(i1||iLn) return ERROR 。 e = pdata 。 j=0。 prior data next 結(jié)點： 雙向鏈表 a1 a3 a2 p s 插入前： p s 插入后： a1 a2 a3 ?插入結(jié)點：指針 p所指的結(jié)點前插入 指針 s所指的結(jié)點 ? sprior=pprior。 // 構(gòu)造數(shù)據(jù)為 e的結(jié)點 s sprior = pprior。 // 在 L中確定第 i個元素的位置指針 p if (!(p=GetElemP_DuL(L,i))) return ERROR。 一元多項式的表示及加法 ADT Polynomial { 數(shù)據(jù)對象：略 數(shù)據(jù)關(guān)系：略 基本操作： CreatePolyn( amp。Pb) 操作結(jié)果：完成多項式的相乘運算 ,即 Pa=PaxPb,并銷毀一元多項式 Pb } ADT Polynomial 。 hb=GetHead(pb) 。 qa=NextPos(pa,qa)。 qa=NextPos(pa,ha) 。 FreeNode(hb) 。 qb=NextPos(pb,hb) 。 ha=qa } else { DelFirst(ha,qa) 。amp。 typedef LinkList polynomial 。Pb) 操作結(jié)果：完成多項式的加法運算 ,即 Pa=Pa+Pb,并銷毀一元多項式 Pb SubtractPolyn(amp。 free(p)。 return OK。 雙向鏈表 ?插入結(jié)點程序 Status ListInsert_DuL(DuLinklist L, int i, ElemType e) { DuLinklist s,p。 typedef struct DuLnode{ ElemType data。 j = 0 。j++) q = qnext 。 Ln++。 for(j=1。 while(pare(pdata,e)==0){p=pnext 。 for(j=1。 Llast = head 。 } Lnode, *Link 。 pc=pb。 lc) { ListNode* pa = Lanext 。pdata) 。 } } 線性表的單鏈表存儲結(jié)構(gòu) ? 建立單鏈表 : 按位序輸入 n個元素 ,建立帶表頭結(jié)點的單鏈表 L void CreateList_L( LinkList amp。 Lnext = null 。++j} if(!(pnext)||ji1) return ERROR。 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。 ++j } if(!p||ji1) return ERROR。 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。amp。 }Lnode, *Linklist。 } ListInsert的時間復(fù)雜度： ? 插入一個元素所需平均移動次數(shù) : n+1 Eis = ∑ 1/(n+1) ( n – i + 1) 則 i=1 n+1 n Eis = 1/(n+1) ∑ ( n – i + 1) = 1/(n+1) ∑ i i=1 i=1 = 1/(n+1) * n(n+1)/2 = n/2 ? 時間復(fù)雜度為 O(n) 。([i1])。 p) *(p+1)=*p。 // 存儲分配失敗 if(!newbase) exit(OVERFLOW)。 if (!) return
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1