【正文】 = Selements[Stop+1]。 } 棧 （ stack） ? 進棧算法 107 棧 （ stack） ? 出棧算法 Status Pops (SqStack *S,datatype *e){ If (Stop == 1) /*下溢 */ return ERROR。 Selements[Stop] = e。 棧 （ stack） 一、棧的順序存儲 104 棧 （ stack） ?棧的順序存儲 ?棧頂指針 top 指示棧頂元素在順序棧中的位置 – top=1,棧空，此時出棧，則下溢（ underflow） – top= MAXSIZE1,棧滿，此時入棧，則上溢（ overflow） 105 棧 （ stack） ?順序棧進、出棧圖示 top=1 1 2 3 4 5 0 ?？? 棧頂指針 top,指向?qū)嶋H棧頂 后的空位置，初值為 1 top 1 2 3 4 5 0 進棧 A top 出棧 棧滿 B C D E F 設數(shù)組維數(shù)為 M top=1,?？眨藭r出棧，則 下溢 （ underflow) top=M1,棧滿，此時入棧，則 上溢 （ 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。 int top。e) 101 進棧： top+1。s,amp。s) （ 3） 進棧 Push(amp。棧中元素按 a1， a2， a3， … an的次序進棧，退棧按后進先出的原則進行的 ,因此按 an …… a3 a2 a1的次序出棧 棧 （ stack） 100 棧 （ stack） ?棧的主要操作： （ 1）建立一個空棧 IniStack(amp。 ?進棧 top+1。 定義 ?通常稱插入、刪除的這一端（如 表尾 ）為棧頂 (Top)，另一端（表頭）為 棧底(Bottom)。 第三章 棧與隊列 98 第 三 章 棧 與 隊列 167。 。 （分別以順序、鏈式實現(xiàn)） 95 習題與練習 二 A[MAXSIZE]的前elenum個分量中，且遞增有序。 3 存儲結(jié)構的選用 順序與鏈式存儲結(jié)構的選用應考慮因素： （ 1）存儲空間 （ 2）運算時間 （ 3）程序設計語言 結(jié)點數(shù)據(jù)占用存儲量量結(jié)點數(shù)據(jù)本身占用存儲存儲密度 ?94 習題與練習 二 ： 頭結(jié)點、頭指針和開始結(jié)點 鏈表有 。 ?刪除給定結(jié)點 p 算法 就這么簡單！ 167。 pnextprior = pprior。 ?刪除給定結(jié)點 p動畫演示 167。 線性表的鏈式存儲結(jié)構 ?刪除給定結(jié)點 p 91 ppriornext=pnext。 pnextprior=pprior。 ④ 167。② ppriornext = s。 sprior = pprior。 線性表的鏈式存儲結(jié)構 ?在給定結(jié)點 p前插入一個新結(jié)點 89 ?在給定結(jié)點 p前插入一個新結(jié)點 S=(DLinklist)malloc(sizeof(DLNode))。 167。 }DLNode,*DLinkLIst 86 L ?空雙向循環(huán)鏈表 ： ?非空雙向循環(huán)鏈表 ： L A B 167。 線性表的鏈式存儲結(jié)構 （ double linked list ) prior element next 指向前驅(qū)結(jié)點 數(shù)據(jù) 指向后繼結(jié)點 ?結(jié)點定義 typedef struct node{ datatype data。 線性表的鏈式存儲結(jié)構 h 空表 h ?循環(huán)鏈表 :表中最后一個結(jié)點的指針指向表頭結(jié)點，使鏈表構成環(huán)狀 – 特點： 從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點 ， 提高查找效率 84 167。 } 82 ?它是一種動態(tài)結(jié)構，整個存儲空間為多個鏈表共用 ?不需預先分配空間 ?指針占用額外存儲空間 ?不能隨機存取，查找速度慢 167。} } pcnext = pa?pa:pb。pc = pb。 pa = panext。 pb){ If(padata = pbdata){ pcnext = pa。 While (pa amp。 pb = Lbnext。 }//ListDelete_L ?刪除元素 ： 81 167。free(q)。 pnext = qnext。 } if(!(pnext)||j i1) return ERROR。ji1){//尋找第 i個結(jié)點 ,并令 p指向其前趨 P = pnext。 While(pnextamp。 線性表的鏈式存儲結(jié)構 Status ListDelete_L (LinkList L,int I,ElemType *e){ P = L。} 79 167。 pnext = s。 s data = x。return ERROR。j++。amp。j=0。 線性表的鏈式存儲結(jié)構 ?在帶頭節(jié)點的單鏈表中第 i 個結(jié)點處插入新元素 x 78 167。 *e = pdata。 j++。amp。j = 1。 頭結(jié)點指針域為空表示線性表為空 76 167。 線性表的鏈式存儲結(jié)構 75 h a1 a2 an ^ …... h 空表 ^ 167。 線性表的鏈式存儲結(jié)構 線性表的鏈式存儲結(jié)構 74 data next p 結(jié)點（ *p） ?(*p)表示 p所指向的結(jié)點 ?(*p).data/pdata表示 p指向結(jié)點的數(shù)據(jù)域 ?(*p).next/pnext表示 p指向結(jié)點的指針域 ?生成一個 LNode型新結(jié)點： p=(LNode *)malloc(sizeof(LNode))。 LNode *h,*p。 struct node *next。 線性表的鏈式存儲結(jié)構 43 存儲地址 數(shù)據(jù)域 指針域 ZHOU 43 LI QIAN SUN WANG WU ZHAO ZHENG 1 7 13 19 25 31 37 13 1 NULL 37 7 19 25 ? 定義：結(jié)點中只含一個指針域的鏈表，也叫單鏈表 例 線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 72 LI ZHAO QIAN SUN ZHOU WU ZHENG WANG ^ H 167。 線性表的鏈式存儲結(jié)構 ?單鏈表 (線性鏈表 ) 特點 : 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素 每個數(shù)據(jù)元素 ai，除存儲本身信息外，還需存儲其直接后繼的信息 70 ?單鏈表 (線性鏈表 ) 特點 : 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素 每個數(shù)據(jù)元素 ai，除存儲本身信息外，還需存儲其直接后繼的信息 指針 數(shù)據(jù)域 結(jié)點 167。} } } 68 167。[i]=[j]。 while ([j]%2==0) j。 ElemType temp。 線性表的順序存儲和實現(xiàn) [解 ] 從左向右找到偶數(shù) [i]，從右向左找到奇數(shù) [j]，將兩 者交換；循環(huán)這個過程直到 i大于 j為止 67 167。設計 把所有奇數(shù)移到所有的偶數(shù)前邊的算法 (要求 時間最少，輔助空間最少 )。 return 1。 j++) Llist[j1] = 。} for(int j = i+1。 線性表的順序存儲和實現(xiàn) ?從線性表中刪除等于給定值的元素 2 if(i = = Lsize){ printf( ―Deleted element is not exist!‖ )。 i++) if(Llist[i] = = item) break 。 } for(i = 0。 線性表的順序存儲和實現(xiàn) ?從線性表中刪除等于給定值的元素 1 int Delete(List* L, ElemType item){ if(Lsize = = 0){ printf( ―L is an empty list!‖ )。 線性表的順序存儲和實現(xiàn) ?刪 除 一 個 元 素圖示 2 63 ? ? ? ?nOnTninnEnQnidei????????? 1 21)(11則若認為 故在順序表中插入或刪除一個元平均移動表的一半元素，當 n很大時，效率很低 167。 } 61 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標 n1 i n 1 2 i 元素序號 i+1 n n+1 167。 *p=n。jn。 if((i1) || (in)) return (0)。 線性表的順序存儲和實現(xiàn) ?刪 除 一 個 元 素算法 int sxbsc(int i, int v[], int *p) { int j,n。 } 59 ? ?nii aaaaa ???? , 1,21 ?變成長度為 n1的線性表 ? ?nii aaaaa ???? , 11,21 ??需將第 i+1至第 n共（ ni）個元素前移 167。 } Llist[] = item。 線性表的順序存儲和實現(xiàn) ?向線性表中的末尾添加一個元素 void InsertRear(List* L, ElemType item){ if(Lsize = = MaxSize){ printf( ―List overflow!‖ )。 Lsize ++ 。 j) Llist[j+1] = Llist[j]。 for(j = Lsize –1。 iLsize。 return。 } 57 167。 Llist[0] = item。 i = 0。 return。 線性表的順序存儲和實現(xiàn) ?向線性表中表頭插入一個元素 InsertFront(List* L,const ElemTypeamp。 線性表的順序存儲和實現(xiàn) ?插入一個元素圖示 2 x 55 ? ? ? ?nOnTninnE i snPnii????????????11 2)1(1111則若認為??????11)1(nii inPE i s167。 } } 53 167。 *p=++n。j) v[j]=v[j1]。 else { for(j=n。 n=*p。 線性表的順序存儲和實現(xiàn) )11( ??? ni?插入一個元素 定義： 線性表的插入是指在第 i 個元素之前插入一個新的數(shù)據(jù)元素 x，使長度為 n的線性表 ( a1, a2 , …, a i1, ai, …a n) 變成長度為 n+1的線性表