【正文】 、 最壞和平均的情況下分別為 O(1)，O(n)和 O(n)。 ?如 （ 5， 2， 2， 3， 5， 2） 經(jīng)刪除重復元素后變?yōu)? （ 5， 2， 3） ?算法思路 ：從順序表中第一個元素起 ， 逐個檢查它后面是否有值相同的其它元素 ， 若有便刪除之；直到表中所有元素都已無重復元素為止 。 刪除順序表中的重復元素的算法描述 void Purge(L) sequenlist *L。 i=1。 while(j=Llast) if(Ldata[j]==Ldata[i]) {for(k=j+1。k++) Ldata[k1]=Ldata[k]。} else j++。} }/*Purge*/ 舉例 —有序表的合并 ?順序表 A和 B的元素均按由小到大的升序排列 ， 編寫算法將它們合并成為順序表 C， 要求 C中元素也是從小到大的升序排列 。 有序表的合并的算法描述 void merge(C,A,B) sequenlist *C,*A,*B。 i=1。k=1。amp。 else Cdata[k++]=Bdata[j++]。 While(jBlast) Cdata[k++]=Bdata[j++]。 }/*merge*/ 第 3章 簡單數(shù)據(jù)結構 順序表 鏈表 棧 隊列 廣義表 鏈表 ?順序表的特點是 ， 邏輯關系上相鄰的兩個元素在物理位置上也相鄰 。 ?這一特點也造成了這種存儲結構的兩個缺點： ?插入和刪除運算必須移動大量 （ 幾乎一半 ） 數(shù)據(jù)元素 ， 效率較低； ?必須預先分配存儲空間 ， 造成空間利用率低 ， 且表的容量難以擴充 。 它不要求邏輯上相鄰的元素在物理位置上也相鄰 ， 為表示元素之間的關系要增加額外存儲空間 ， 也不能隨機存取數(shù)據(jù)元素；但是它沒有順序存儲結構所具有的缺點 。 ?為了表示出每個數(shù)據(jù)元素與其后繼之間的關系 ， 對每個元素除了存儲元素本身的信息外 ， 還需存儲指示該元素的后繼元素的地址；這兩部分信息組成一個結點 。 一個線性表的 n個元素通過每個結點的指針域拉成一條 “ 鏈子 ” ， 所以稱之 鏈表 （ Linked List） 。 單鏈表存儲舉例 ?對于線性表 （ mon,tue,wed,thu,fri,sat,sun） ， 其單鏈表存儲示意圖如下圖 。 ?這樣就可以由頭指針找到第一個結點 ， 再由第一個結點的指針域找到第二個結點 ， …… ， 依次順著指針域找到每個結點 。 單鏈表（續(xù)） ?對于單鏈表 ， 我們并不關心各個結點的實際存儲位置 ， 而關心的是結點間的邏輯次序關系 ， 故可將單鏈表 （ mon,tue,wed,thu,fri,sat,sun） 的畫成如下圖 。 由上圖可以很清楚地看出 ， 線性表的鏈式存儲結構是通過鏈指針來表示數(shù)據(jù)元素之間的邏輯關系的 ， 是非順序存儲結構 。 單鏈表的 類型 描述 typedef struct node {elemtype data。 }LinkList。 ?需要說明的是 ， 定義 LinkList與 struct node為相同類型不同的類型標識符 （ 名字 ） ， 是為了用它說明單鏈表類型 ，這種方法有利于提高程序或算法的可讀性 。 單鏈表結點空間的申請與釋放 ?malloc函數(shù)的返回值類型在 ANSI C版本中是 void *類型 ，所以動態(tài)生成的結點類型必須強制轉換為指向該結點的指針類型 。 ?它獲得一個單鏈表類型結點 ， 結點地址在指針變量 P。 ?它釋放指針 P所指結點空間給內(nèi)存 。頭結點的數(shù)據(jù)類型和其它結點一致 ， 它的數(shù)據(jù)域無定義 ， 指針域中存放第一個數(shù)據(jù)結點的地址 ， 空表時指針域為空 。 ?在單鏈表中每個元素的存儲空間是在需要時才申請 ， 其邏輯關系靠指針來表示 ， 所以在建立單鏈表的過程中更多關心的是指針的鏈接 。 ?具體的算法描述如下： LinkList *CreateLinkList() {char ch。 LinkList *head。 head=(LinkList *)malloc(sizeof(LinkList))。 建立單鏈表（續(xù)） r=head。 while(ch!=’*’) /*“*”為輸入數(shù)據(jù)結束符號 */ {scanf(“%d”,amp。 P=(LinkList *)malloc(sizeof(LinkList))。 Pnext=NULL。 r=rnext。} return head。 單鏈表建立過程示例 ?線性表 （ 25， 45， 18， 76， 29） 的單鏈表動態(tài)建立過程如下圖： ?只要設一個移動指針掃描整個單鏈表 ， 就可以統(tǒng)計出元素個數(shù)即表長 。 {LinkList *P=L。 While(Pnext!=NULL) {P=Pnext。} return j。 ?單鏈表上元素的查找分 按值查找 和按序號查找。算法描述如下： LinkList *LocateLinkList(L,x) LinkList *L。 {LinkList *P。 while((P!=NULL)amp。(Pdata!=x)) P=Pnext。 /*返回找到的結點位置或 NULL*/ }/*LocateLinkList*/ 元素的查找方法二 ?按序號查找 的方法是，從第一個結點起做 i次指針傳遞返回該結點地址，若找不到 i次已到表尾則返回 NULL， 算法描述如下： LinkList *GetLinkList(L,i) LinkList *L。 {LinkList *P。 P=L。amp。 j++。 else return NULL。 ?在單鏈表中插入元素只需修改有關結點的指針域內(nèi)容 ， 不需象順序表那樣移動元素 。 ?后插操作的命令如下 ， 且操作次序不能交換 。 ② Pnext=S。 能不能也用 O(1)的時間開銷完成前插呢 ？ 回答是肯定的 。 ?其操作過程為 ① Snext=Pnext。 ③ x=Pdata。 ⑤ Sdata=x。 elemtyPe x。 {LinkList *P,*S。/*查找第 i1個結點 */ if(P==NULL) Printf(“第 i1個元素不存在 ， 參數(shù) i有錯 \n”)。 Sdata=x。 Pnext=S。 ?設 P為指向單鏈表中某結點的指針 ， 刪除 P所指結點即 *P的操作示意圖如下圖 。 ?顯然要找到 *P的前趨得有 O(n)的時間開銷 。 free (P)。 Pnext=Snext。 ? 要刪除單鏈表 L中的第 i個結點 ， 關鍵是先找出第 i1個結點 （ 即前趨結點 ） ， 然后完成刪除并釋放被刪結點空間的工作 。 int i。 P=getLinkList(L,i1)。 else {S=Pnext。 free (S)。 舉例 ——將單鏈表 H逆置 ?所謂 逆置 是指結點間的關系相反 ， 即前趨變后繼而后繼變前趨 。 ?算法思路 ：依次從原鏈表中取出每個結點 ， 每次都把它作為第一個結點插入到新鏈表中去 。 將單鏈表 H逆置的算法描述 void reverse(H) LinkList *H。 P=Hnext。 while(P!=NULL) {q=P。 qnext=Hnext。} }*reverse*/ ?該算法沒有開辟新的存儲空間 ， 對鏈表順序掃描一遍就完成了逆置 ， 時間開銷為 O(n)。 ?單循環(huán)鏈表的空表和非空表兩種狀態(tài)如下圖所示： ?單循環(huán)鏈表上的基本運算與單鏈表基本一致 ， 差別僅在于對最后一個結點的循環(huán)處理上；單鏈表是判斷指針是否為空 （ NULL） ， 而單循環(huán)鏈表是判斷指針是否指向頭結點 。 {LinkList *P。 P=L。 j++。 }/*Lengthcircularlist*/ 循環(huán)鏈表（續(xù)） ?有時對鏈表常做的操作是在表尾和表頭進行 。 ?改進的方法是不設頭指針而設尾指針 。 ?帶尾指針的循環(huán)鏈表 如下圖所示： 雙向鏈表 ?在單循環(huán)鏈表中 ， 雖然可以從任一已知結點出發(fā)找到其前趨結點 ， 但需耗時 O(n)， 原因在于每個結點只有一個指向后繼的指針域 。 ?如果讓每條鏈都構成一個環(huán) ， 則稱為 雙向循環(huán)鏈表（ double circular linked list） 。 雙向鏈表的結點定義和類型 typedef struct dupnode {elemtype data。 }dulinklist。 ?雙向鏈表是一種對稱結構 ， 每個結點都既有指向其前趨的指針 ， 也有指向其后繼的指針；每個結點的地址既放在其后繼結點的前趨域中 ， 也放在其前趨結點的后繼域中 。 然而由于要涉及多指針域的運算 ， 對于某些運算要注意運算的先后順序 。 ② Sprior=Pprior。 ④ Pprior=S。 雙向鏈表插入運算的示意圖 ① ② ③ ④ 雙向鏈表的刪除運算 ?刪除 P所指結點 （ 即 *P） 的操作步驟為： ① Ppriornext=Pnext。 ③ free (P)。 ?設 A=(a0,a1,… ,an )， B=(b0,b1,… ,bm)， 則多項式加法就是求 A+B=C。 一元多項式在計算機中的表示 ?如何在計算機中表示描述多項式的線性表呢 ？ 我們首先考慮用順序表 （ 即順序存儲結構 ） 。 ?解決的辦法是對每一非零項用 （ 系數(shù) ， 指數(shù) ） 二元組 ， T(x)只需存儲 （ 3， 0） ， （ 5， 200） 和 （ 7， 1000） 三個有序對 ，顯然對高階稀疏多項式這種方法較好 。 一元多項式的數(shù)據(jù)類型定義 ?如果是多項式的運算問題如相加和相乘等 ， 考慮到會產(chǎn)生新的項和系數(shù)為零項減少這兩種情況 ， 宜考慮采用鏈式存儲結構即單鏈表實現(xiàn) 。 int exp。 }polynomial。 ?若指數(shù)相等系數(shù)相加 ， 和不為零修改 *p的系數(shù)項并刪除 *q， 和為零刪除 *p和 *q； ?若指數(shù)不等 ， pexpqexp時 *p為和多項式中的一項 ， pexpqexp時把 *q插在 *p之前 （ *q為和多項式中的一項 ） ； ?所有操作之后要相應移動指針 。 多項式相加算法的描述 void polyadd(A,B) polynomial *A,*B。 float x。 q=Bnext。 while((p!=NULL)amp。(q!=NULL)) if((pexp)(qexp)) {r=qnext。 /*把 p接在 q所指結點后 */ snext=q。 q=r。 p=pnext。 if(x!=0) {pcoef=x。 } else {snext=pnext。} p=snext。 q=qnext。} if(q!=NULL) snext=q。 }/* polyadd*/ ?該算法的比較次數(shù)與 A、 B兩個多項式的長度 m和 n有關 ， 算法的時間復雜度為 O(m+n)。 ?通常把進行插入和刪除操作的這一端稱作 棧頂（ top） ， 另一端稱作 棧底 （ bottom） ； ?把棧的插入元素操作稱作 進棧 、 入棧 或 壓入 ； ?棧的刪除元素操作稱作 退棧 、 出棧 或 彈出 ； ?當棧中沒有元素時稱作 空棧 。 所以棧也稱作 后進先出 （ Last In First Out） 表 ， 簡稱 LIFO表 。 棧的基本運算 ?置空棧 setnull(s)：將棧 S設置成空棧 ， 即不管棧的原來狀態(tài)如何一律置為空棧； ?判?？?empty(s)：返回一個布爾值 ， 當棧 S為空時返回 1，否則返回 0； ?進棧 push(s,x)：該操作把元素 X壓入棧 S中 ， 成為新的棧頂元素； ?出棧 po