數據結構實用教程c語言版上ppt-資料下載頁

　　

【正文】 ile ((pnext) amp。amp。 (ji1) ) /*查找第 i1個結點 */ { p=pnext。 j++。 } if ((!pnext)||( ji1)) /* pnext為空，刪除結點不存在， ji1時，位置錯 */ { printf(error)。return 0。 } q=pnext。 /*q指向第 i個結點 */ pnext=qnext。 /*改變指針 */ *e=qdata。 /*指針 e帶回所刪結點數據域的值 */ free(q)。 /*釋放 q占用空間 */ return 1。 } ?平均時間復雜度為 O(n) qaiai + 1ai 1p圖 2 . 1 6 刪 除 第 i 個 結 點 時 指 針 變 化 狀 況 例 寫一算法，刪除帶頭結點的單鏈表 L中的重復結點，即實現如圖所示的操作，圖（ a）為初始的單鏈表，圖（ b）為刪除重復結點后的單鏈表。 22L3332L3 b a 例 寫一算法逆置帶頭結點的單鏈表 L，要求逆置后的單鏈表利用 L中的原結點，不可以重新申請結點空間。 void reverse (Linklist *L) { Linklist *p,*q。 /*p為剩余結點形成單鏈表的頭指針， q保存欲插入 L頭的結點的地址 */ p=Lnext。 /*p指向第一個數據結點 */ Lnext=NULL。 /*將原鏈表置為空表 L*/ while (p) { q=p。 p=pnext。 qnext=Lnext。 /*將當前結點插到頭結點的后面 */ Lnext=q。 } } 例 假設有兩個帶頭結點的單鏈表 A、 B，按元素值非遞減有序，編寫算法將A、 B歸并成一個按元素值非遞增有序的鏈表 C，要求鏈表 C利用 A、 B中的原結點空間，不可以重新申請結點。 LinkList *union(LinkList *A,LinkList *B) { LinkList *C, *p,*q,*s。 p=Anext。q=Bnext。 /*p、 q分別指向單鏈表 A、 B的第一個結點 */ C=A。 /*C表的頭結點利用 A表頭結點的空間 */ Cnext=NULL。 while (pamp。amp。q) { if (pdata=qdata) /*從鏈表 A、 B上取出當前 data值較小者暫存到 s中 */ { s=p。 p=pnext。 } else { s=q。 q=qnext。 } snext=Cnext。 /*將 s插入到 C表的頭部 */ Cnext=s。 } if (!q) q=p。 /* 將剩余結點形成的鏈的鏈頭保存到 q中 */ while (q) /* 將剩余結點依次取出暫存到 s中，將 s插入到 C表的頭部 */ { s=q。 q=qnext。 snext=Cnext。 Cnext=s。 } free(B)。 return *C。 } ? 算法的時間復雜度為 O(m+n)。 ?循環鏈表 ?循環鏈表 （ Circular Linked List）是利用鏈表中某些結點的指針域的值為空（ NULL）的特點，將空指針域改存一些更有意義的信息而形成的。 ?在單循環鏈表上的操作基本與單鏈表相同，稍微不同的是 p，將原來運算中的循環結束條件由判斷指針是否為空，變為判斷是否等于頭指針。 ? 空表的條件是 Lnext==L而非 Lnext==NULL。 ? 指針 p到達表尾的條件是 pnext==L而非 pnext==NULL ?將指向頭結點的指針改為指向尾結點的單循環鏈表 ?將指向頭結點的指針改為指向尾結點的單循環鏈表 ＊ 尾結點的指針為 r，頭結點的指針為 rnext，鏈表為空的條件是 rnext==r ＊ 查找開始結點和尾結點的時間都是 O(1) ?將兩個單鏈表 L L2合并成一個單鏈表，即將 L2的第一個結點鏈接到 L1的尾結點上 。 操作步驟如下： p= r1 –next。 /*保存 L1 的頭結點地址 */ r1next=r2nextnext。 /*把 L2鏈到 L1的尾部 */ free(r2next)。 /*釋放 L2的頭結點 */ r2next=p。 /*形成循環鏈表 */ ? 雙鏈表 ?每個結點附加兩個指針域，一個指向后繼結點、一個指向前趨結點。由這種結點組成的鏈表中有兩條方向不同的鏈，因此稱為 雙（向）鏈表 （ Double Linked List） ?雙鏈表的存儲結構用Ｃ語言描述如下： typedef struct DNode { DataType data。 struct DNode *prior,*next。 } DLinkList。 DLinkList *L。 ?雙鏈表的對稱特性 ： ppriornext = p = pnextprior data nextprior圖 2 . 2 2 雙鏈表結點結構帶頭結點的雙循環鏈表 ?雙鏈表上的運算 ?在進行插入、刪除操作時，除了要修改后繼結點的 next域，還需修改前趨結點的 prior域 ?（ 1）插入 ＊ 將 *s插入到 *p的前面，插入過程： ① s=（ DLinkList *） malloc(sizeof(DLinkList))。 ② sdata=x。 ③ sprior=pprior。 ④ snext=p。 ⑤ ppriornext=s。 ⑥ pprior=s。 ＊ 需要注意的是在修改指針的過程中要保證不要斷鏈了 ＊ 算法的時間復雜度為 O(n) x s 圖 2 . 2 4 雙 向 鏈 表 中 插 入 結 點 指 針 變 化 狀 況p?雙鏈表上的運算 （ 2）刪除 ＊ 刪除 *p，操作如下： ① ppriornext=pnext。 ② pnextprior=pprior。 ③ free(p)。 ＊ 算法的時間復雜度為 O(n) 167。 2． 4 順序表和鏈表的比較 ?1 ．邏輯關系的表示 ?2．存儲密度 ?3．存儲分配方式 ?4．存取方法 ?5．插入、刪除操作 ?6．實現語言 第三章 棧和隊列 167。 3． 1 棧 167。 3． 2 隊列 167。 3． 3 棧與隊列的比較 第三章 棧和隊列 167。 3． 1 棧 ? 棧的定義及運算 ? 棧 （ Stack）是運算受限的線性表，限制它的插入和刪除操作僅在表的一端進行。 ? 棧頂 （ Top） ,棧頂元素 ， 棧底（ Bottom),空棧 ,進棧 或 入棧 ，出棧 或 退棧 。 ? 后進先出的線性表（ Last In First Out），簡稱 LIFO表 ?棧的基本運算有五種： （ 1）初始化棧 initStack（ s）：構造了一個空棧 s。 （ 2）判棧空 empty（ s）：若棧 s為空棧，返回值為“真” （ 1），否則返回值為“假”（ 0）。 （ 3）入棧 push（ s， x）：在棧 s的頂部插入一個新元素 x ， x成為新的棧頂元素。 （ 4）出棧 pop（ s）：刪除棧 s的棧頂元素。 （ 5）讀棧頂元素 top（ s）：棧頂元素作為結果返回， 不改變棧的狀態。 ? 順序棧及運算的實現 ?采用順序方式存儲的棧稱為 順序棧 （ Sequential Stack）。 ?順序棧用 C語言描述如下： define MAXSIZE 1024 /*棧可能達到的最大容量 */ typedef int DataType。 typedef struct { DataType data[MAXSIZE]。 int top。 }SeqStack 。 SeqStack *s。 /*定義 s是一個指向順序棧的指針 */ ?棧的操作及棧頂指針變化情況 ?在順序棧上實現五種基本運算的 C函數 ?（ 1）初始化棧 首先建立棧空間，然后初始化棧頂指針。 SeqStack *initSeqStack() { SeqStack *s。 s=(SeqStack*)malloc(sizeof(SeqStack))。 stop= 1。 return s。 } ?（ 2）判棧空 int empty (SeqStack *s) { if (stop== 1) return 1。 else return 0。 } ?在順序棧上實現五種基本運算的 C函數 ?（ 3）入棧 int push (SeqStack *s, DataType x) { if (stop==MAXSIZE1) /*棧滿不能入棧 */ { printf(overflow)。 return 0。 } stop++。 sdata[stop]=x。 return 1。 } ?在順序棧上實現五種基本運算的 C函數 ?（ 4）出棧 void pop (SeqStack *s) /*設棧不空 */ { stop。 } ?（ 5）讀棧頂元素 DataType top (SeqStack *s) /*設棧不空 */ { return (sdata[stop] )。 } ? 鏈棧及運算的實現 ?采用鏈接方式存儲的棧稱為鏈棧（ Linked Stack） ?鏈棧用 C語言描述如下： typedef struct Node { DataType data。 struct Node *next。 } LinkStack。 LinkStack *top 。 /*說明 top為棧頂指針 */ CAt opBD圖 鏈棧圖示? 棧的應用 ? 例 將一個十進制正整數 N轉換成 r進制的數 N N / 8 （整除） N % 8（求余） 1835 229 3 低 229 28 5 28 3 4 3 0 3 高 ?例 算術表達式中括號匹配的檢查 用棧來實現括號匹配檢查的原則是，對表達式從左到右掃描。 （ 1）當遇到左括號時，左括號入棧； （ 2）當遇到右括號時，首先檢查棧是否空，若棧空，則表明該“右括弧”多余；否則比較棧頂左括號是否與當前右括號匹配，若匹配，將棧頂左括號出棧，繼續操作；否則，表明不匹配，停止操作。 （ 3）當表達式全部掃描完畢，若棧為空，說明括號匹配，否則表明“左括弧”有多余的。 ? 棧與遞歸 ?棧的一個重要應用是在程序設計語言中實現遞歸 ?遞歸： 函數、過程或數據結構等對象在其定義的內部直接或間接出現了對自身的引用是一種 遞歸 。 ?遞歸函數： 一個函數在其定義的內部直接調用自身，這個函數就叫做直接遞歸函數。 long fact (int n) { long f。 if (n==0) f=1 。 else