數(shù)據(jù)結(jié)構(gòu)課件線性表-預(yù)覽頁
【正文】 1) C語言中 動(dòng) 態(tài)分配描述 p22 define LIST_INIT_SIZE 100 define LISTINCREMENT 10 typedef struct { ElemType *elem。 SqList L。 if (!) exit(OVERFLOW)。 } ② 插入 p24算法 Status ListInsert_sq(SqList amp。 = newbase。 ② 插入 p24算法 函數(shù) realloc的格式及功能 格式： void *realloc(void *p,unsigned size) 功能：將 p所指向的已分配內(nèi)存區(qū)域的大小 改為 size。 for (p=amp。 *q=e。L,int i,ElemType amp。 e=*p。++p) *(p1)=*p。 ? 插入： ?最壞： i=1，移動(dòng)次數(shù)為 n ?最好 : i=表長 +1，移動(dòng)次數(shù)為 0 ?平均：等概率情況下，平均移動(dòng)次數(shù) n/2 課本式子 25 ? 刪除： ?最壞： i=1，移動(dòng)次數(shù)為 n1 ?最好 : i=表長，移動(dòng)次數(shù)為 0 ?平均：等概率情況下，平均移動(dòng)次數(shù) (n1)/2 課本式子 26 查找 p25~p26算法 int LocateElem_Sq(SqList L, ElemType e) { i=1。 if (i=) return i。 while (i= amp。 else return 0。 while (i= amp。 } while (i=) [k++]=[i++]。Lc) { pa=。 if (!) exit(OVERFLOW)。amp。 while (pb=pb_last) *pc++=*pb++。 if (!) exit(OVERFLOW)。 in。in。La, ElemType x) { int i=0。 [i]x) i++。//元素的后移 [i]= x。La, ElemType x) { int i, j。amp。j) [j+1] = [j]。 } 4. 順序表的分析 1）優(yōu)點(diǎn) ? 順序表的結(jié)構(gòu)簡單 ? 順序表的存儲(chǔ)效率高，是緊湊結(jié)構(gòu) ? 順序表是一個(gè)隨機(jī)存儲(chǔ)結(jié)構(gòu)（直接存取結(jié)構(gòu)） 2）缺點(diǎn) ? 在順序表中進(jìn)行插入和刪除操作時(shí)，需要移動(dòng)數(shù)據(jù)元素，算法效率較低。 順序表之整體概念： elem 0 1 length1 listsize length 數(shù)組下標(biāo) 內(nèi)存狀態(tài) 變量 操作算法 listsize1 初始化操作 插入操作 刪除操作 查找操作 排序操作 . . . . . . . . . . . . . . . 空閑 表區(qū) elem 順序表之整體概念： 順序表有下列缺點(diǎn)： （ 1）插入、刪除操作時(shí)需要移動(dòng)大量元素， 效率較低； （ 2）最大表長難以估計(jì)，太大了浪費(fèi)空間， 太小了容易溢出。 ? 結(jié)點(diǎn) ：數(shù)據(jù)域 + 指針域（鏈域） ? 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表 ? 線性鏈表（單鏈表）：鏈表的每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域。 } LNode, *LinkList。 ?對(duì)于頭結(jié)點(diǎn)數(shù)據(jù)域的處理： ，則在該處存放鏈表長度信息。e) { LinkList p。amp。 e=pdata。 p=L。 ji1) { p=pnext。 sdata = e。} … e s Pnext=s … (2) (3) p snext=pnext a (1) b 在帶表頭結(jié)點(diǎn)的單鏈表 第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn) newnode→ next = p→ next。L, int i, ElemType amp。 while (pnext amp。} if (!(pnext) || j i1) return ERROR。 free(q)。 delete q。L, int n) { LinkList p。i0。 pnext = Lnext。Lc) { LinkList pa,pb,pc。//La頭結(jié)點(diǎn)作為 Lc頭結(jié)點(diǎn) while (pa amp。 pa=panext。} } pcnext=pa?pa:pb。 p=Lnext。 pdata != x) {p= pnext。 } else { printf (i=%d\n,i)。 p=Lnext。} return(j)。La,LinkList Lb) { LinkList p,q,first。//對(duì) Lb中的每一個(gè)元素 while (p) { x=pdata。amp。 qnext = Lanext。 在循環(huán)鏈表中沒有 NULL 為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。 pnext = Lbnext。 pnext=Lbnext。 free(Lb)。 L= (LinkList)malloc(sizeof(LNode))。 pdata=x。 p=Lnext。 } printf(L\n)。 p→ next = p。 }DuLNode, *DuLinkList。 (2) current→ next = p。 雙向循環(huán)鏈表的刪除算法 (刪除 current) 3）基本操作： 雙向循環(huán)鏈表的建立 void CrtList_DuL(DuLinkList amp。 L next=L。 pnextprior =p。 Lprior =p。 while (p!=L){ printf(%d,pdata)。 ? 系數(shù) a0, a1, a2, …, an ? 指數(shù) 0, 1, 2, …, n。 int expn。若未變成 0，則將結(jié)果加到結(jié)果多項(xiàng)式
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1