【正文】 //中找到則將其刪除 } } 43 167。 線性表的類型定義 void celem(sqlist A， sqlist B， sqlist amp。 //依次獲取線性表 A中的元素 ， //存放在 x中 k=LocateElem(B， x)。j++。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 一、 線性表的順序存儲(chǔ) （ 順序表 ） ?定義：把線性表中所有元素按其邏輯順序依次存儲(chǔ)到指定位置開始的連續(xù)空間中。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?ElemType類型的數(shù)組 list[MaxSize]存儲(chǔ)線性表 A= (a1 , a2 , … , ai , ai+1 , … , an) ?元素地址計(jì)算方法 第 i個(gè)元素的存儲(chǔ)位置為： list+(i1)*sizeof(ElemType) ?線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 47 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 49 167。 char name[20]。 char publisher[30]。 }DATATYPE。 或動(dòng)態(tài)申請(qǐng)和釋放內(nèi)存 DATATYPE *pData； pDat=(DATATYPE*)malloc(sizeof(DATATYPE))。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?線性表的順序存儲(chǔ)示例 （圖書資料） 51 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?插入一個(gè)元素算法 int sxbcr(int i,int x,int v[],int *p){ int j,n。 if((i1) || (in+1)) return (0)。j=i。 v[j]=x。 return (1)。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?插入一個(gè)元素圖示 1 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標(biāo) n1 i n 1 2 i 元素序號(hào) i+1 n n+1 54 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標(biāo) n1 i n 1 2 i 元素序號(hào) i+1 n n+1 an1 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?插入算法時(shí)間復(fù)雜度 T(n) Pi是在第 i個(gè)元素之前插入一個(gè)元素的概率，則在長度為 n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為 ： 56 167。 L,const ElemTypeamp。 return。 i = 0。 [0] = item。 } 57 167。 L,const ElemTypeamp。 return。 i。 for(int j = –1。 j) [j+1] = [j]。 ++ 。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?向線性表中的末尾添加一個(gè)元素 void InsertRear(Listamp。 item){ if( = = MaxSize){ printf( “ List overflow!” )。 } [] = item。 } 59 ? ?nii aaaaa ???? , 1,21 ?變成長度為 n1的線性表 ? ?nii aaaaa ???? , 11,21 ??需將第 i+1至第 n共（ ni）個(gè)元素前移 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?刪 除 一 個(gè) 元 素算法 int sxbsc(int i, int v[], int *p) { int j,n。 if((i1) || (in)) return (0)。jn。 *p=n。 } 61 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標(biāo) n1 i n 1 2 i 元素序號(hào) i+1 n n+1 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?刪 除 一 個(gè) 元 素圖示 2 63 ? ? ? ?nOnTninnEnQnidei????????? 1 21)(11則若認(rèn)為 故在順序表中插入或刪除一個(gè)元平均移動(dòng)表的一半元素，當(dāng) n很大時(shí)，效率很低 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?從線性表中刪除等于給定值的元素 1 int Delete(Listamp。 return 0。 i 。 65 167。 return 0。 j。 。 } 66 [例 ] 已知線性表 (ao， a1， … ， an1)按順序存 儲(chǔ)，且每個(gè)元素都是均不相等的 整數(shù)。 167。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) void move(sqlist A){ int i=0,j=,k。 while (i=j) { while ([i]%2==0) i++。 if(ij){ temp=[i]。 A. data[j]=temp。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺 缺點(diǎn) : ? 插入 、 刪除操作需要移動(dòng)大量的元素 ? 預(yù)先分配空間需按最大空間分配 ， 利用不充分 優(yōu)點(diǎn) : ? 邏輯相鄰 ， 物理相鄰 ? 可隨機(jī)存取任一元素 ? 存儲(chǔ)空間使用緊湊 ? 表容量難以擴(kuò)充 69 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?結(jié)點(diǎn) 數(shù)據(jù)域： 元素本身信息 指針域： 指示直接后繼的存儲(chǔ)位置 71 頭指針 31 H 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 73 ?實(shí)現(xiàn) typedef struct node { datatype data。 }LNode,*LinkList。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 74 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))。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 75 h a1 a2 an ^ …... h 空表 ^ 167。 頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空 76 167。j = 1。amp。 j++。 *e = p。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?在帶頭節(jié)點(diǎn)的單鏈表中第 i 個(gè)結(jié)點(diǎn)處插入新元素 x 78 167。j=0。amp。j++。return ERROR。 s data = x。 pnext = s。} 79 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) Status ListDelete_L (LinkList L,int I,ElemType *e){ P = L。 While(pnextamp。ji1){//尋找第 i個(gè)結(jié)點(diǎn) ,并令 p指向其前趨 P = pnext。 } if(!(pnext)||j i1) return ERROR。 pnext = qnext。free(q)。 }//ListDelete_L ?刪除元素 ： 81 167。 pb = Lbnext。 While (pa amp。 pb){ If(padata = pbdata){ pcnext = pa。 pa = panext。pc = pb。} } pcnext = pa?pa:pb。 } 82 ?它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用 ?不需預(yù)先分配空間 ?指針占用額外存儲(chǔ)空間 ?不能隨機(jī)存取，查找速度慢 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) h 空表 h ?循環(huán)鏈表 :表中最后一個(gè)結(jié)點(diǎn)的指針指向頭表 p或 pnext=H結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀 – 特點(diǎn)： 從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn) ， 提高查找效率 84 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) （ double linked list ) prior element next 指向前驅(qū)結(jié)點(diǎn) 數(shù)據(jù) 指向后繼結(jié)點(diǎn) ?結(jié)點(diǎn)定義 typedef struct node{ datatype data。 }DLNode,*DLinkLIst 86 L ?空雙向循環(huán)鏈表 ： ?非空雙向循環(huán)鏈表 ： L A B 167。 167。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?在給定結(jié)點(diǎn) p前插入一個(gè)新結(jié)點(diǎn) 89 ?在給定結(jié)點(diǎn) p前插入一個(gè)新結(jié)點(diǎn) S=(DLinklist)malloc(sizeof(DLNode))。 sprior = pprior。② ppriornext = s。 ④ 167。 pnextprior=pprior。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?刪除給定結(jié)點(diǎn) p 91 ppriornext=pnext。 ?刪除給定結(jié)點(diǎn) p動(dòng)畫演示 167。 pnextprior = pprior。 ?刪除給定結(jié)點(diǎn) p 算法 就這么簡單！ 167。 3 存儲(chǔ)結(jié)構(gòu)的選用 順序與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的選用應(yīng)考慮因素： （ 1）存儲(chǔ)空間 （ 2）運(yùn)算時(shí)間 （ 3）程序設(shè)計(jì)語言 結(jié)點(diǎn)數(shù)據(jù)占用存儲(chǔ)量量結(jié)點(diǎn)數(shù)據(jù)本身占用存儲(chǔ)存儲(chǔ)密度 ?94 習(xí)題與練習(xí) 二 ： 頭結(jié)點(diǎn)、頭指針和開始結(jié)點(diǎn) 鏈表有 。 （分別以順序、鏈?zhǔn)綄?shí)現(xiàn)） 95 習(xí)題與練習(xí) 二 A[MAXSIZE]的前elenum個(gè)分量中，且遞增有序。 。 第三章 棧與隊(duì)列 98 第 三 章 棧 與 隊(duì)列 167。 定義 ?通常稱插入、刪除的這一端（如 表尾 ）為棧頂 (Top)，另一端（表頭）為 棧底(Bottom)。 ?進(jìn)棧 top+1。棧中元素按 a1， a2， a3， … an的次序進(jìn)棧，退棧按后進(jìn)先出的原則進(jìn)行的 ,因此按 an …… a3 a2 a1的次序出棧 棧 （ stack） 100 棧 （ stack） ?棧的主要操作： （ 1）建立一個(gè)空棧 IniStack(amp。s) （ 3） 進(jìn)棧 Push(amp。s,amp。e) 101 進(jìn)棧： top+1。 int top。 棧 （ stack） 一、棧的順序存儲(chǔ) 104 棧 （ stack） ?棧的順序存儲(chǔ) ?棧頂指針 top 指示棧頂元素在順序棧中的 – top=1,?？?，此時(shí)出棧，則下溢（ underflow） – top= MAXSIZE1,棧滿，此時(shí)入棧，則上溢（ overflow） 105 棧 （ stack） ?順序棧進(jìn)、出棧圖示 top=1 1 2 3 4 5 0 ?？? 棧頂指針 top,指向?qū)嶋H棧頂 后的空位置，初值為 1 top 1 2 3 4 5 0 進(jìn)棧 A top 出棧 棧滿 B C D E F 設(shè)數(shù)組維數(shù)為 M top=1,棧空，此時(shí)出棧，則 下溢 （ underflow) top=M1,棧滿，此時(shí)入棧，則 上溢 （ overflow) top top top top top 1 2 3 4 5 0 A B C D E F top top top top top top 棧空 106 Status Push(SqStack *S,datatype e){ If(Stop = MAXSIZE1) /*上溢 */ return ERROR。 Selements[Stop] = e。 } 棧 （ stack） ? 進(jìn)棧算法 107 棧 （ stack） ? 出棧算法 Status Pops (SqStack *S,datatype *e){ If (Stop == 1) /*下溢 */ return ERROR。 *e = Selemen