《算法與數據結構》第3章簡單數據結構ppt.ppt

《《算法與數據結構》第3章簡單數據結構ppt.ppt》由會員分享，可在線閱讀，更多相關《《算法與數據結構》第3章簡單數據結構ppt.ppt（175頁珍藏版）》請在裝配圖網上搜索。

1、算法與數據結構 第 3章 簡單數據結構 簡單數據結構 簡單的數據結構 ， 包括順序表 、 鏈表 、 棧 、 隊列和 廣義表 ， 它們和上一章介紹過的數組和串一起都同屬 于 線性結構 。 在線性結構中 ， 數據元素之間的關系是一對一的次 序關系 ， 其邏輯特征為： 存在一個惟一地被稱作 “ 第一個 ” 的數據元素； 存在一個惟一地被稱作 “ 最后一個 ” 的數據元素； 除第一個之外 ， 每個數據元素都只有一個前趨； 除最后一個之外 ， 每個數據元素都只有一個后繼 。 第 3章 簡單數據結構 3.1 順序表 3.2 鏈表 3.3 棧 3.4 隊列 3.5 廣義表 3.1 順序表 3.1.1 線性表

2、的基本概念 3.1.2 線性表的順序存儲結構 順序表 3.1.3 順序表上的基本運算 線性表的基本概念 線性表 （ Linear List） 是一種最簡單最常用的數據結構 。 一個線性表是由 n（ n0） 個相同類型數據元素 （ 結點 ） 組 成的 有限序列 。 表中有且僅有一個第一個結點 ， 它沒有前 趨而只有一個后繼；有且僅有一個最后一個結點 ， 它沒有 后繼而只有一個前趨；其余結點都只有一個前趨和一個后 繼 。 根據結點之間的關系可以排成一個線性序列： （ a1， a2， a3， a4， ， an） 其中： a1為第一個結點 ， an為最后一個結點；對于 i=2 n， ai-1是 ai的

3、前趨 ， ai是 ai-1的后繼； n稱作線性表的 長度 ， n為 0時稱作 空表 。 線性表的例子 線性表中的數據元素 （ 結點 ） 可以是一個數 、 一個符號 、 一頁書 、 一個記錄等 。 下面給出線性表的幾個例子： （ “ A”， “ B”， ， “ Z”） 是一個線性表 ， 稱作字母表 ， 表中 的數據元素都是單個大寫字母字符； （ 3， 7， 9， 12， 66， 87） 是一個線性表 ， 表中的每個數據元素都 是一個整數； 學生成績表也是一個線性表 ， 表中的數據元素為描述一個學生高 考情況的一個記錄 ， 它由姓名 、 準考證號 、 數學 、 語文 、 英語 、 理綜 、 總分七

4、個數據項組成 。 線性表的形式化定義 線性表的形式化定義如下： Linear List=(D,R) 其中： D=ai|ai Do， i=1， 2， ， n， n 0； R=|ai-1,ai Do， i=2， 3， ， n； Do為某個數據對象 。 線性表是一種相當靈活的數據結構 ， 其長度可根 據需要增減 ， 即對數據元素不僅可以訪問 ， 還可 進行插入和刪除 。 線性表的基本運算 置空表 setnull(L)：將線性表 L置為空表 。 求長度 length(L)：計算線性表 L中數據元素的個數 。 取元素 get(L,i)：取出線性表 L中第 i個數據元素； 要求 ilength(L)。 取

5、前趨 prior(L,x)：取出線性表 L中值為 x的元素的 前趨元素；要求 x的位序大于 1。 取后繼 next(L,x)：取出線性表 L中值為 x的元素的 后繼元素；要求 x的位序小于 length(L)。 定位序 locate(L,x)：確定元素 x在線性表 L中的位置 ， 并給出位置序號；若 L中無 x返回 0。 線性表的基本運算（續(xù)） 插入 insert(L,x,i)：在線性表 L中第 i個位置上插入值為 x的新 元素 ， 使表長增 1；要求 1ilength(L)+1。 刪除 delete(L,i)：刪除線性表 L中的第 i個元素 ， 使表長減 1； 要求 1ilength(L)。

6、 利用這些基本運算 ， 可以實現線性表的其它較復雜運算 ， 如線性表的分拆 、 合并 、 逆置等 。 在實際應用中 ， 當線性表作為一個運算對象時 ， 所需的運 算種類不一定相同 ， 不同的運算將構成不同的抽象數據類 型 。 這里所給出的運算是定義在邏輯結構上的抽象運算 ， 而運 算的實現要依賴于所采用的存儲結構 。 3.1 順序表 3.1.1 線性表的基本概念 3.1.2 線性表的順序存儲結構 順序表 3.1.3 順序表上的基本運算 線性表的順序存儲結構 順序表 順序表 （ sequential list） 是用一組 地址連續(xù) 的存儲單 元依次存放線性表中的各個數據元素 ， 是一種最簡單 最

7、自然的線性表存儲方法 。 這組地址連續(xù)的存儲空間的大小依線性表中的數據 元素個數而定 ， 線性表中第一個元素存放在這組空間 的開始處 ， 第二個元素緊跟著存放在第一個元素之 后 ， ， 余類推 。 顯然 ， 順序表中相鄰的數據元素在計算機內的存儲 位置也相鄰； 換句話說 ， 順序表以數據元素在計算機內的 物理位 置相鄰 來表示數據元素在線性表中的邏輯相鄰關系 。 線性表的存儲地址計算公式 由于線性表中的數據元素具有相同的類型 ， 所以可 以很容易地確定順序表中每個數據元素在存儲空間中 與起始單元的相對位置； 假定線性表中每個數據元素需要占用 c個存儲單元 ， loc(a1)是第一個數據元素的存

8、儲地址 （ 也稱作基地 址 ） ， 則第 i個數據元素的存儲地址可由下式確定： loc(ai)=loc(a1)+(i-1)*c 其中： 1ilength(L)+ 1。 顯然 ， 順序表是一種可隨機存取的數據結構 。 線性表的順序存儲結構示意圖 順序表的順序存儲結構（續(xù)） 由于在高級程序設計語言中的一維數組 （ 或向量 ） 在計算機內分配的是一片連續(xù)的存儲單元 ， 所以可借 助一維數組為順序表開辟存儲空間存儲表中的數據元 素 。 考慮到線性表因插入 、 刪除運算長度可變 ， 數組的 容量要足夠大 （ 可設為 MAXSIZE， 其值依實際問題而 定 ） ， 并設一指示器變量 last指向表中的最后

9、一個元 素位置 。 為了討論方便 ， 我們假定元素是從數組下標為 1的位 置開始存放 ， 即 last=0時為空表 。 順序表的類型描述 #define MAXSIZE 500 typedef struct elemtyPe dataMAXSIZE; int last; sequenlist; 即把順序表類型 sequenlist描述為一個結構體 ， 域 data數組存放表中的數據元素 ， 域 last存放表長 ， datalast存放表中最后一個元素 。 elemtype為表中數據元素的類型 ， 對于不同的實際問 題可以為不同的具體類型 ， 如整型 int、 實型 float、 字符型 ch

10、ar、 雙精度實型 double、 或其它結構類型等 。 3.1 順序表 3.1.1 線性表的基本概念 3.1.2 線性表的順序存儲結構 順序表 3.1.3 順序表上的基本運算 順序表上的基本運算 在定義了線性表的順序存儲結構之后 ， 就可以討論 各種基本運算的實現問題了 。 順序表上的許多運算是很容易實現的 。 例如： 置空表就是使表長為 0， 即 (*L).last=0； 求表長就是讀出 last域的值 ， 即 (*L).last； 取元素就是按位序取出 data 域中相應元素 ， 即 (*L).datai；取前趨就是將元素 x的位序前一個元素取出 ， 即 (*L).datalocate(

11、L,x)-1； 取后繼即取出 (*L).datalocate(L,x)+1的值等 。 這里只討論定位序 、 插入和刪除運算的實現算法 。 1. 定位序 locate(L,x) 定位序即按值查找 ， 確定元素 x在順序表 L中的位置 。 最簡單的方法是從第一個元素起和 x比較 ， 直到找到 一個值為 x的數據元素返回它的位置序號 （ 即數組下 標 ） ， 或者找遍表中所有元素均無值為 x的元素時返 回 0。 其算法描述如下： int locate(L,x) sequenlist *L; elemtyPe x; int i=1; while(ilast) 定位序 （續(xù)） if(iL-last) r

12、eturn 0; /*未找到值為 x的元素返回 0*/ else return i; /*找到值為 x的元素返回它的位序 i*/ /*locate*/ 該算法的主要時間花費在于查找比較的循環(huán) 。 當 a1=x時一次比較成功 ， 當 an=x時 n次比較成功 ， 在 x 分 布位置等概率的情況下平均比較次數為 (n+1)/2；查找 不成功時的比較次數為 n+1。 所以算法的時間復雜度 為 O(n)。 2. 插入 insert(L,x,i) 插入運算 是指在順序表 L的第 i個元素之前加入一個 新元素 x。 插入的結果使 x 在順序表中第 i個元素位置 上 ， 使順序表的長度由 n變?yōu)?n+1。

13、插入新元素 x后 ， 部分數據元素間的邏輯關系發(fā)生了 改變 ， 要求物理存儲位置也要相應變化 。 除非 i=n+1， 否則必須將位序為 i,i+1, ,n的數據元 素向后移動一個元素位置 ， 空出第 i個位置插入新元 素 x；在 i=n+1時直接將新元素 x插入表尾 。 在順序表中插入新元素 x的過程 插入運算的算法描述 void insert(L,x,i) sequenlist *L; elemtype x; int i; int j; if(i(L-last+1) printf(“插入位置不正確 n”); else if(L-last=MAXSIZE) printf(“表已滿 ， 發(fā)生上溢

14、 n”); else for(j=L-last;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-last=L-last+1; /*insert*/ 插入運算算法的時間復雜度 算法中的數據元素移動是從第 n個元素到第 i個元素 依次后移的 。 算法中的主要時間開銷在于后移元素的 for循環(huán) ， 循環(huán)執(zhí)行 n-i+1次 。 當 i=n+1時不需移動元素是最 好情況 ， 當 i=1時需移動元素 n次是最壞情況 ， 在插 入位置等概率分布時的平均移動次數為 n/2。 所以算法最好情況下的時間復雜度為 O(1)， 在最壞 情況下的時間復雜度為 O(n)， 在平均情況下的時

15、間 復雜度也是 O(n)。 3.刪除 delete(L,i) 刪除運算是把順序表中第 i個元素刪掉 ， 使順序表的 長度由 n變?yōu)?n-1， 其部分元素的邏輯關系和存儲位置 也發(fā)生相應變化 ， 即 由 （ a1,a2, ,ai-1,ai,ai+1, ,an） 變成為 （ a1,a2, ,ai-1,ai+1, ,an） 。 除非 i=n時直接刪除 ， 否則需要從第 i+1元素到第 n元 素依次前移一個元素位置 。 在順序表中刪除第 i個元素過程 刪除運算的算法描述 void delete(L,i) sequenlist *L; int i; int j; if(iL-last) printf(“

16、刪除位置不正確 n”); else for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last=L-last-1; /*delete*/ 刪除運算算法的時間復雜度 由刪除過程可以看出 ， 通過元素 ai+1到 an的依次前移 就達到了刪除 ai的目的 。 該算法的時間開銷也主要是在元素的移動 。 當 i=n時最好不需移動 ， 當 i=1時最壞需移動 n-1次 ， 在等概率的情況下需平均移動元素 (n-1)/2次 。 其時 間復雜度在最好 、 最壞和平均的情況下分別為 O(1)， O(n)和 O(n)。 舉例 刪除順序表中的重復元素 一個順序表中可能含有一些值相同

17、的重復元素 ， 題目 要求對于值相同的重復元素只保留位序最小的一個而 刪除其它多余的元素 。 如 （ 5， 2， 2， 3， 5， 2） 經刪除重復元素后變?yōu)?（ 5， 2， 3） 算法思路 ：從順序表中第一個元素起 ， 逐個檢查它后 面是否有值相同的其它元素 ， 若有便刪除之；直到表 中所有元素都已無重復元素為止 。 為此 ， 算法中需設 兩重循環(huán) ， 外層控制清除的趟數 ， 內層控制每趟的檢 查范圍 。 刪除順序表中的重復元素的算法描述 void Purge(L) sequenlist *L; int i,j,k; i=1; while(ilast) j=i+1; while(jlast)

18、 if(L-dataj=L-datai) for(k=j+1;klast;k+) L-datak-1=L-datak; L-last=L-last-1; else j+; i+; /*Purge*/ 舉例 有序表的合并 順序表 A和 B的元素均按由小到大的升序排列 ， 編 寫算法將它們合并成為順序表 C， 要求 C中元素也是 從小到大的升序排列 。 算法思路 ：依次掃描 A和 B中元素 ， 比較當前兩個 元素值 ， 將較小的元素賦給 C， 直到其中一個順序 表掃描完畢 ， 然后將另一個順序表中剩余元素賦給 C即可 。 有序表的合并的算法描述 void merge(C,A,B) sequenli

19、st *C,*A,*B; int i,j,k; i=1;j=1;k=1; while(ilast else C-datak+=B-dataj+; While(ilast) C-datak+=A-datai+; While(jlast) C-datak+=B-dataj+; C-last=k-1; /*merge*/ 第 3章 簡單數據結構 3.1 順序表 3.2 鏈表 3.3 棧 3.4 隊列 3.5 廣義表 3.2 鏈表 順序表的特點是 ， 邏輯關系上相鄰的兩個元素在物理位置上 也相鄰 。 這一特點使得順序表有如下兩個優(yōu)點： 無需為表示數據元素之間的關系而額外增加存儲空間； 可以隨機存取表中

20、任一數據元素 ， 元素存儲位置可以用一個簡單 、 直觀的公式表示 。 這一特點也造成了這種存儲結構的兩個缺點： 插入和刪除運算必須移動大量 （ 幾乎一半 ） 數據元素 ， 效率較低； 必須預先分配存儲空間 ， 造成空間利用率低 ， 且表的容量難以擴充 。 本節(jié)介紹線性表的另一種存儲結構 鏈式存儲結構 。 它不 要求邏輯上相鄰的元素在物理位置上也相鄰 ， 為表示元素之 間的關系要增加額外存儲空間 ， 也不能隨機存取數據元素； 但是它沒有順序存儲結構所具有的缺點 。 3.2 鏈表 3.2.1 線性表的鏈式存儲結構 鏈表 3.2.2 單鏈表上的基本運算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線

21、性表應用舉例 一元多項式相加問題 線性表的鏈式存儲結構 鏈表 線性表的 鏈式存儲結構 ， 是用一組任意的存儲單元 （ 這組存 儲單元的地址可以連續(xù) ， 也可以不連續(xù) ） 來存放線性表中的各 個數據元素的 。 為了表示出每個數據元素與其后繼之間的關系 ， 對每個元素 除了存儲元素本身的信息外 ， 還需存儲指示該元素的后繼元素 的地址；這兩部分信息組成一個結點 。 存放數據元素信息的域 data稱作 數據域 ， 存放后繼元素地址信 息的域 next稱作 指針域 或 鏈域 。 一個線性表的 n個元素通過每 個結點的指針域拉成一條 “ 鏈子 ” ， 所以稱之 鏈表 （ Linked List） 。 由

22、于這種鏈表中每個結點只含有一個指向后繼的指針 ， 所以稱作 線性鏈表 或 單鏈表 （ Single Linked List） 。 單鏈表存儲舉例 對于線性表 （ mon,tue,wed,thu,fri,sat,sun） ， 其單鏈 表存儲示意圖如下圖 。 單鏈表 由于單鏈表中每個結點的存儲地址是放在其前趨結 點的指針域中 ， 因此整個鏈表的存取必須從第一個 結點開始；需設立頭指針指示鏈表中的第一個結點 。 這樣就可以由頭指針找到第一個結點 ， 再由第一個 結點的指針域找到第二個結點 ， ， 依次順著指 針域找到每個結點 。 此外 ， 在鏈表中最后一個結點沒有后繼 ， 該結點的 指針域為空 ，

23、用 NULL或 表示空指針域 。 單鏈表（續(xù)） 對于單鏈表 ， 我們并不關心各個結點的實際存儲位 置 ， 而關心的是結點間的邏輯次序關系 ， 故可將單 鏈表 （ mon,tue,wed,thu,fri,sat,sun） 的畫成如下圖 。 其中用箭頭表示的指針域中的指針 。 由上圖可以很 清楚地看出 ， 線性表的鏈式存儲結構是通過鏈指針 來表示數據元素之間的邏輯關系的 ， 是非順序存儲 結構 。 整個單鏈表可由頭指針惟一確定 ， 所以常用 頭指針名來命名一個單鏈表 ， 如稱表 H則意味著該單 鏈表的頭指針為 H。 單鏈表的 類型 描述 typedef struct node elemtype d

24、ata; struct node *next; LinkList; LinkList *H,*P; 需要說明的是 ， 定義 LinkList與 struct node為相同類 型不同的類型標識符 （ 名字 ） ， 是為了用它說明單鏈表類型 ， 這種方法有利于提高程序或算法的可讀性 。 另外 ， 指針變量所指向的結點地址并不是在程序中顯式給 出 ， 而是在程序的執(zhí)行過程中用標準函數 malloc根據需要 動態(tài)生成的 。 單鏈表結點空間的申請與釋放 malloc函數的返回值類型在 ANSI C版本中是 void *類型 ， 所以動態(tài)生成的結點類型必須強制轉換為指向該結點的指針類 型 。 具體方法為

25、 P=(LinkList*)malloc(sizeof(LinkList); 它獲得一個單鏈表類型結點 ， 結點地址在指針變量 P。 如下圖 當要釋放結點空間時可用標準函數 free完成 ， 即 free(P); 它釋放指針 P所指結點空間給內存 。 對結點中兩個域的訪問 ， 只能通過指向該結點的指針進行 ， 如 P-data和 P-next 或者 (*P).data和 (*P).next 3.2 鏈表 3.2.1 線性表的鏈式存儲結構 鏈表 3.2.2 單鏈表上的基本運算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線性表應用舉例 一元多項式相加問題 單鏈表上的基本運算 為了方便運算 ， 使

26、單鏈表的空表和非空表的處理一 致 ， 通常在單鏈表的第一個結點前增加一個頭結點 。 頭結點的數據類型和其它結點一致 ， 它的數據域無 定義 ， 指針域中存放第一個數據結點的地址 ， 空表 時指針域為空 。 空表和非空表的圖形表示如下： 若無特殊說明 ， 本章算法均采用帶頭結點的單鏈表 。 1.建立單鏈表 在單鏈表中每個元素的存儲空間是在需要時才申請 ， 其邏輯 關系靠指針來表示 ， 所以在建立單鏈表的過程中更多關心的 是指針的鏈接 。 一開始先申請并生成頭結點 ， 然后每讀入一個數據元素申請 一個結點 ， 填入數據后插入表尾 ， 為此要設一個尾指針 r。 具體的算法描述如下： LinkList

27、 *CreateLinkList() char ch; int x; LinkList *head; /*head為頭結點指針 */ LinkList *r,*P; head=(LinkList *)malloc(sizeof(LinkList); head-next=NULL; 建立單鏈表（續(xù)） r=head; /*尾指針初始化 */ ch=getchar(); while(ch!=*) /*“*”為輸入數據結束符號 */ scanf(“%d”, P=(LinkList *)malloc(sizeof(LinkList); P-data=x; P-next=NULL; r-next=P; r

28、=r-next; ch=getchar(); return head; /*CreateLinkList*/ 該算法的時間復雜度為 O(n)。 單鏈表建立過程示例 線性表 （ 25， 45， 18， 76， 29） 的單鏈表動態(tài)建立過程如下 圖： 2.求表長 只要設一個移動指針掃描整個單鏈表 ， 就可以統(tǒng)計出元素個 數即表長 。 其算法描述如下： int LengthLinkList(L) LinkList *L; LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表長 */ /*LengthLink

29、List*/ 該算法掃描整個單鏈表 ， 時間復雜度為 O(n)。 3.元素的查找方法一 單鏈表上元素的查找分 按值查找 和按序號查找。 按值查找 的方法是，從第一個結點起判斷當前結點的值是否 等于給定值，若找到返回該結點地址，否則繼續(xù)下一個結點； 若整個表中未找到返回 NULL。算法描述如下： LinkList *LocateLinkList(L,x) LinkList *L; elemtyPe x; LinkList *P; P=L-next; while(P!=NULL) return P; /*返回找到的結點位置或 NULL*/ /*LocateLinkList*/ 元素的查找方法二 按

30、序號查找 的方法是，從第一個結點起做 i次指針傳遞返回該 結點地址，若找不到 i次已到表尾則返回 NULL， 算法描述如下： LinkList *GetLinkList(L,i) LinkList *L; int i; LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P; else return NULL; /*GetLinkList*/ 這兩個算法的時間復雜度在最壞情況下和等概率平均情況下都 為 O(n)。 4.插入 在單鏈表中插入元素只需修改有關結點的指針域內容 ， 不需 象順序表那樣移動

31、元素 。 插入運算有 前插 和 后插 兩種：設 P指向單鏈表中某結點 ， S指 向待插入的新結點 ， 把 *S插入到 *P的前面稱作 前插 ， 而把 *S 插入 *P的后面稱作 后插 。 后插操作的命令如下 ， 且操作次序不能交換 。 S-next=P-next; P-next=S; 后插的示意圖如下圖： 插入（續(xù)） 前插需要 *P的前趨 *q， 然后再完成在 *q之后插入 *S的后插； 這就需要從第一個結點開始查找 *P的前趨 *q， 使得時間開銷 由后插的 O(1)上升到 O(n)。 能不能也用 O(1)的時間開銷完成 前插呢 ？ 回答是肯定的 。 我們只要先把 *S插入到 *P的后面 ，

32、 然后再將 P-data與 S-data互相交換即可；這樣既能滿足邏輯 關系 ， 也能使得時間開銷為 O(1)。 其操作過程為 S-next=P-next; P-next=S; x=P-data; P-data=S-data; S-data=x; 插入算法描述 在單鏈表 L中第 i個位置上插入值為 x的元素的算法描述： LinkList *insertLinkList(L,x,i) LinkList *L; elemtyPe x; int i; LinkList *P,*S; P=getLinkList(L,i-1);/*查找第 i-1個結點 */ if(P=NULL) Printf(“第 i

33、-1個元素不存在 ， 參數 i有錯 n”); else S=(LinkList *)malloc(sizeof(LinkList); S-data=x; S-next=P-next; P-next=S; /*insertLinkList*/ 該算法的時間復雜度為 O(n)。 5.刪除 設 P為指向單鏈表中某結點的指針 ， 刪除 P所指結點即 *P的操 作示意圖如下圖 。 由示意圖可見 ， 要刪除 *P先要找到 *P的前趨結點 *q， 然后完 成指針的變化操作即可 。 顯然要找到 *P的前趨得有 O(n)的時間開銷 。 在找到 *q的前提 下 ， 刪除 *P的操作可由下列語句實現： q-next

34、=P-next; free (P); 刪除（續(xù)） 若要刪除 P所指結點的后繼結點 （ 假設存在 ） ， 時間開銷 為 O(1),直接完成刪除即可： S=P-next; P-next=S-next; free S; 要刪除單鏈表 L中的第 i個結點 ， 關鍵是先找出第 i-1個結 點 （ 即前趨結點 ） ， 然后完成刪除并釋放被刪結點空間的 工作 。 刪除單鏈表 L中的第 i個結點算法 LinkList *deleteLinkList(L,i) LinkList *L; int i; LinkList *P,*S; P=getLinkList(L,i-1);/*查找第 i-1個結點 */ if(

35、P=NULL) Printf(“第 i-1個元素不存在 ， 參數 i 有錯 n”); else S=P-next; P-next=S-next; free (S); *deleteLinkList*/ 該算法的時間復雜度為 O(n)。 舉例 將單鏈表 H逆置 所謂 逆置 是指結點間的關系相反 ， 即前趨變后繼而后繼變前 趨 。 如圖 (a)的單鏈表逆置后成為圖 (b)的單鏈表 。 算法思路 ：依次從原鏈表中取出每個結點 ， 每次都把它作為 第一個結點插入到新鏈表中去 。 為此要借用兩個指針變量 P和 q， P用來指向原鏈表中的當前第一個結點 ， q用來指向從原表 取出的每一個結點并利用它插入到

36、新鏈表中去 ， 當 P為空時完 成逆置 。 將單鏈表 H逆置的算法描述 void reverse(H) LinkList *H; LinkList *P,*q; P=H-next; H-next=NULL; while(P!=NULL) q=P; P=P-next; q-next=H-next; H-next=q; *reverse*/ 該算法沒有開辟新的存儲空間 ， 對鏈表順序掃描一遍就完成 了逆置 ， 時間開銷為 O(n)。 3.2 鏈表 3.2.1 線性表的鏈式存儲結構 鏈表 3.2.2 單鏈表上的基本運算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線性表應用舉例 一元多項式相加問題

37、循環(huán)鏈表 循環(huán)鏈表 （ Circular Linked List） 是鏈式存 儲結構的另一種形式 ， 其特點是表中最后一個結點的 指針域指向頭結點 ， 使整個鏈表構成一個環(huán) ， 可以從 表中任一結點出發(fā)訪問遍所有結點 （ 即遍歷 ） 。 單循環(huán)鏈表的空表和非空表兩種狀態(tài)如下圖所示： 單循環(huán)鏈表上的基本運算與單鏈表基本一致 ， 差別 僅在于對最后一個結點的循環(huán)處理上；單鏈表是判斷 指針是否為空 （ NULL） ， 而單循環(huán)鏈表是判斷指針是 否指向頭結點 。 求循環(huán)鏈表的表長算法描述 int Lengthcircularlist(L) LinkList *L; LinkList *P; int j

38、=0; P=L; While(P-next!=L) /*與求單鏈表表長差別僅在于把 NULL換為頭指針 L*/ P=P-next; j+; return j; /*Lengthcircularlist*/ 循環(huán)鏈表（續(xù)） 有時對鏈表常做的操作是在表尾和表頭進行 。 為了找尾結點必須從頭結點開始掃描全部結點 ， 時 間開銷為 O(n)；而找頭結點僅 O(1)時間 。 改進的方法是不設頭指針而設尾指針 。 這樣找到頭 結點和尾結點都只需要 O(1)的時間 ， 頭結點為 (*(*r).next).next而尾結點為 r， 對于在鏈表的頭尾 操作的應用十分方便 。 帶尾指針的循環(huán)鏈表 如下圖所示： 雙

39、向鏈表 在單循環(huán)鏈表中 ， 雖然可以從任一已知結點出發(fā)找到其 前趨結點 ， 但需耗時 O(n)， 原因在于每個結點只有一個 指向后繼的指針域 。 如果希望能夠快速確定任一結點的前趨 ， 就必須付出空 間代價 ， 即增加一個指針域存儲其前趨信息 ， 這樣每個 結點就有兩個方向不同的鏈 ， 稱之為 雙向鏈表 （ double linked list） 。 如果讓每條鏈都構成一個環(huán) ， 則稱為 雙向循環(huán)鏈表 （ double circular linked list） 。 雙向鏈表的使用往往做成雙循環(huán)鏈表 ， 和單循環(huán)鏈表類 似 ， 也是由頭指針標識 ， 也可以增加頭結點方便運算 。 雙向鏈表的結點

40、定義和類型 typedef struct dupnode elemtype data; struct dupnode *prior,*next; dulinklist; dulinklist *H; 雙向鏈表是一種對稱結構 ， 每個結點都既有指向其前趨 的指針 ， 也有指向其后繼的指針；每個結點的地址既放 在其后繼結點的前趨域中 ， 也放在其前趨結點的后繼域 中 。 即有 P-next-prior=P=P-prior-next 雙向鏈表示意圖 雙向鏈表插入運算 與單鏈表相比雙向鏈表的運算要方便得多 。 然而由于要 涉及多指針域的運算 ， 對于某些運算要注意運算的先后 順序 。 在 *P之前插入

41、 *S的步驟為： P-prior-next=s; S-prior=P-prior; S-next=P; P-prior=S; 盡管上面的指針操作順序不是惟一的 ， 但是也不能任意 次序 ， 必須保證操作 在操作 之前完成 ， 否則 *P的前 趨域的信息就丟掉了 ， 導致不能正確地插入 *S。 雙向鏈表插入運算的示意圖 雙向鏈表的刪除運算 刪除 P所指結點 （ 即 *P） 的操作步驟為： P-prior-next=P-next; P-next-prior=P-prior; free (P); 在雙向鏈表中刪除一個結點的運算如下圖所示： 3.2 鏈表 3.2.1 線性表的鏈式存儲結構 鏈表 3.2

42、.2 單鏈表上的基本運算 3.2.3 循環(huán)鏈表和雙向鏈表 3.2.4 線性表應用舉例 一元多項式相加問題 一元多項式 一個一元多項式可以表示為 P(x)=a0+a1x+a2x2+ +anxn 其中： a0,a1,a2, ,an這 n+1個系數惟一確定了多項式 ， 而 每一項的指數隱含在系數 ai的序號中 ， 所以一元多項式 可以由線性表 （ a0,a1, ,an） 來表示 。 設 A=(a0,a1, ,an )， B=(b0,b1, ,bm)， 則多項式加法就是 求 A+B=C。 其中： C=(a0+b0,a1+b1, ,am+bm,am+1, ,an) 或 C=（ a0+b0,a1+b1,

43、， an+bn,bn+1, ,bm） 。 一元多項式在計算機中的表示 如何在計算機中表示描述多項式的線性表呢 ？ 我們首先考 慮用順序表 （ 即順序存儲結構 ） 。 如果只存儲系數讓指數隱含在系數序號中 ， 則會浪費存儲 空間 ， 如 T(x)=3+5x200+7x1000的線性表長度為 1001， 而其中僅 有三個非零元素 ， 故應當避免 。 解決的辦法是對每一非零項用 （ 系數 ， 指數 ） 二元組 ， T(x) 只需存儲 （ 3， 0） ， （ 5， 200） 和 （ 7， 1000） 三個有序對 ， 顯然對高階稀疏多項式這種方法較好 。 順序存儲便于訪問 ， 但插入刪除需大量移動元素

44、， 所以對 只需求多項式的值無需修改系數和指數值的情況下 ， 采用順 序表結構較好 。 一元多項式的數據類型定義 如果是多項式的運算問題如相加和相乘等 ， 考慮到 會產生新的項和系數為零項減少這兩種情況 ， 宜考 慮采用鏈式存儲結構即單鏈表實現 。 其數據類型可如下定義： typedef struct linknode float coef; int exp; struct linknode *next; polynomial; 多項式的鏈式存儲表示示例 假設使用頭結點 ， 前述的 T(X)= 3+5x200+7x1000可表示 為如下圖所示的結構： 多項式相加算法的思路 不產生新結點而利用原

45、有結點空間 ， 設兩個指針變 量 p和 q分別指向 A和 B兩個多項式單鏈表的第一個結 點 ， 依次比較兩指針所指結點的指數項 。 若指數相等系數相加 ， 和不為零修改 *p的系數項并 刪除 *q， 和為零刪除 *p和 *q； 若指數不等 ， p-expexp時 *p為和多項式中的一 項 ， p-expq-exp時把 *q插在 *p之前 （ *q為和多項 式中的一項 ） ； 所有操作之后要相應移動指針 。 直到其中一個鏈空 ， 把另一個鏈剩下的結點插在 *p之后 。 多項式相加算法的描述 void polyadd(A,B) polynomial *A,*B; polynomial *p,*q,

46、*s,*r; float x; p=A-next; q=B-next; s=A; while(p!=NULL) q-next=p; /*把 p接在 q所指結點后 */ s-next=q; /*把 q接入結果鏈 */ s=q; q=r; else if(p-expexp) s=p; p=p-next; 多項式相加算法的描述（續(xù)） else x=p-coef+q-coef; if(x!=0) p-coef=x; s=p; else s-next=p-next; free(p); p=s-next; r=q; q=q-next; free(r); if(q!=NULL) s-next=q; /*把

47、q鏈剩余結點鏈入結果鏈 */ free(B); /* polyadd*/ 該算法的比較次數與 A、 B兩個多項式的長度 m和 n有關 ， 算法 的時間復雜度為 O(m+n)。 第 3章 簡單數據結構 3.1 順序表 3.2 鏈表 3.3 棧 3.4 隊列 3.5 廣義表 3.3 棧 3.3.1 棧的概念及運算 3.3.2 順序棧及運算實現 3.3.3 鏈棧及運算實現 3.3.4 棧的應用舉例 遞歸的實現 棧的概念 棧 （ stack） 是操作受限的線性表 ， 限定對元素 的插入和刪除運算只能在表的一端進行 。 通常把進行插入和刪除操作的這一端稱作 棧頂 （ top） ， 另一端稱作 棧底 （

48、bottom） ； 把棧的插入元素操作稱作 進棧 、 入棧 或 壓入 ； 棧的刪除元素操作稱作 退棧 、 出棧 或 彈出 ； 當棧中沒有元素時稱作 空棧 。 棧的概念（續(xù)） 由棧的定義可知 ， 每一次 入棧 的 元素都在原棧頂元素之上成為新 的棧頂元素 ， 每一次 出棧 的元素 總是當前棧頂元素使次棧頂元素 成為新的棧頂元素 ， 即最后進棧 的元素總是最先出棧 。 所以棧也 稱作 后進先出 （ Last In First Out） 表 ， 簡稱 LIFO表 。 如右圖 所示 ， 元素是以 a1,a2, ,an-1,an 的次序進棧 ， 出棧的次序則是 an,an-1, ,a2,a1。 棧的基本

49、運算 置空棧 setnull(s)：將棧 S設置成空棧 ， 即不管棧的原來 狀態(tài)如何一律置為空棧； 判?？?empty(s)：返回一個布爾值 ， 當棧 S為空時返回 1， 否則返回 0； 進棧 push(s,x)：該操作把元素 X壓入棧 S中 ， 成為新的棧 頂元素； 出棧 pop(s)：該操作從棧頂彈出棧頂元素并返回 ， 棧 S為空 時返回 NULL； 讀棧頂元素 gettop(s)：該操作返回棧 S的棧頂元素 ， 當棧 S為空時返回 NULL；它與 pop(s)的差別僅在于沒有彈出棧頂 元素 ， 棧 S 的狀態(tài)沒有改變 ， 只是讀棧頂元素的值并返回 。 3.3 棧 3.3.1 棧的概念及運

50、算 3.3.2 順序棧及運算實現 3.3.3 鏈棧及運算實現 3.3.4 棧的應用舉例 遞歸的實現 順序棧 利用順序存儲結構實現的棧稱作 順序棧 （ sequential stack） 。 類似于順序表 ， 棧中的數據元素用一個預設的足夠長度的 一維數組來存放 ， 棧底位置可以設在數組的任一端點 ， 而 棧頂是隨著插入和刪除運算而變化的 ， 用 top指針指示當前 棧頂的位置 。 順序棧的類型描述如下： #define MAXSIZE 100 typedef struct elemtype dataMAXSIZE; int top; seqstack; seqstack *s; 順序棧（續(xù)）

51、通常把 0下標端設為棧底 ， 這樣棧空時棧頂指針 top=-1， 棧 滿時棧頂指針 top= MAXSIZE-1； 入棧 時棧頂指針加 1（ 即 s-top+） ， 然后數據元素進棧； 出棧 時在讀出棧頂數據元素后棧頂指針減 1， 即 s-top-。 在棧滿時做入棧操作會產生空間不足的情況 ， 簡稱 上溢 （ overflow） ； 而在?？諘r做出棧操作會產生無元素可出的情況 ， 簡稱 下 溢 （ underflow） 。 上溢和下溢兩種情況均應該避免 ， 而?？赵趹弥型ǔＷ?為算法 （ 或程序 ） 的控制轉移條件 。 棧頂指針與數據元素之間的關系 順序棧的基本運算 空棧操作 置空棧算法 v

52、oid setnull(seqstack *s) /*不論棧 S狀態(tài)如何 ， 都置 top為 -1*/ s-top=-1; 判棧空算法 int empty(seqstack *s) /*依 top值 ， 在空棧時返回 1， 否則返回 0*/ if(s-top=-1) return 1; else return 0; 順序棧的基本運算 進棧 進棧算法 int push(seqstack *s,elemtype x) /*把元素 x壓入棧 s中 */ if(s-top=MAXSIZE-1) return 0; /*棧上溢進棧不成功返回 0標志 */ else s-top+; /*棧頂指針加 1*/

53、 s-datas-top=x; /*元素 x進棧 */ return 1; /*進棧成功返回 1標志 */ 順序棧的基本運算 出棧 出棧算法 elemtype pop(seqstack *s) if(s-top=-1) return NULL; else s-top-; /*棧頂指針減 1*/ return s-datas-top+1; /*返回原棧頂元素的值 */ 順序棧的基本運算 讀棧頂元素 讀棧頂元素算法 elemtype gettop(seqstack *s) /*讀棧頂元素并返回其值 */ if(s-top=-1) return NULL; /*棧空無元素返回 NULL*/ else

54、 return s-datas-top; /*否則返回棧頂元素值 */ 兩棧共享 在一個應用程序中需要使用多個棧的時候 ， 為了提高空間 的使用效率 ， 減少預分配空間過多造成的浪費 ， 又能降低 發(fā)生棧上溢而產生錯誤中斷的可能性 ， 可以讓多個棧共享 存儲空間 。 例如兩棧共享一維數組空間 ， 可按 “ 底設兩端 、 相向而動 、 迎面增長 ” 的方式組織 共享棧 ， 如下圖所示 。 僅當兩個棧頂相遇才會發(fā)生上溢 ， 棧頂可以越過中間點 ， 顯然比各用一半空間發(fā)生上溢的概率要小得多 。 兩棧共享的數據類型定義 兩棧共享的數據類型可如下定義： typedef struct elemtype s

55、tackm; /*m為數組長度 ， 可依具體問題而定 */ int top2; /* top0和 top1分別為兩棧的棧頂指針 */ sharedstack; 兩棧共享的基本運算 置空棧 置空棧算法 void setnull(sharedstack *s) s-top0=-1; /*0號?？諡?-1*/ s-top1=m; /*1號棧空為 m*/ 兩棧共享的基本運算 進棧 進棧算法 int push(sharedstack *s,int i,elemtype x) /* i=0,1為兩棧的編號 ， 算法把元素 x壓入棧 si 中 */ if(i1|s-top0+1=s-top1) return

56、 0; else if(i=0) s-stack+s-top0=x; else s-stack-s-top1=x; return 1; 兩棧共享的基本運算 出棧 出棧算法 elemtype pop(sharedstack *s,int i) /*彈出 i號棧的棧頂元素 */ if(i1) return NULL; /*參數出錯無法彈出 */ else if(i=0) if (s-top0=-1) return NULL; /*0號棧無法彈出 */ else return s-stacks-top0-; else if(s-top1=m) return NULL; /*1號棧無法彈出 */ el

57、se return s-stacks-top1+; 3.3 棧 3.3.1 棧的概念及運算 3.3.2 順序棧及運算實現 3.3.3 鏈棧及運算實現 3.3.4 棧的應用舉例 遞歸的實現 鏈棧的基本概念 利用鏈式存儲結構實現的棧稱作 鏈棧 （ link stack） 。 鏈棧中的每個數據元素用一個結點表 示 ， 其結構形式與單鏈表完全相同 。 鏈棧從本質上講就是單鏈表 ， 無非是 限制了插入和刪除運算只能在鏈頭進 行 ， 所以可以說鏈棧就是限制插入和 刪除運算只能在鏈頭進行的單鏈表 。 由于在鏈頭運算 ， 所以不用象單鏈表 那樣附加頭結點 ， 更方便運算 ， 如右 圖所示 。 鏈棧的類型定義

58、鏈棧的類型定義如下： typedef struct node elemtype data; struct node *next; linkstack; linkstack *top; /*棧頂指針 ， 即鏈頭指針 */ 鏈棧的基本運算 空棧操作 置空棧算法 void setnull(linkstack *top) top=NULL; /*只要置 top為空即可 */ 判?？账惴?int empty(linkstack *top) /*?？辗祷?1否則返回 0*/ if(top=NULL) return 1; else return 0; 鏈棧的基本運算 進棧 進棧算法 void push(li

59、nkstack *top,elemtype x) /*注意：鏈棧不會發(fā)生上溢 ！ */ linkstack *p; p=(linkstack*)malloc(sizeof(linkstack); p-data=x; p-next=top; top=p; 鏈棧的基本運算 出棧 出棧算法 elemtype pop(linkstack *top) linkstack *p; elemtype x; if(top=NULL) return NULL; /*棧為空無元素彈出 */ else p=top; /*保存棧頂指針于 P中 */ x=top-data; top=top-next; free (p)

60、; return x; /*返回彈出元素的值 */ 鏈棧的基本運算 讀棧頂元素 讀棧頂元素算法 elemtype gettop(linkstack *top) if(top=NULL) return NULL; /*若棧為空返回空 */ else return top-data; /*否則返回棧頂元素的值 */ 3.3 棧 3.3.1 棧的概念及運算 3.3.2 順序棧及運算實現 3.3.3 鏈棧及運算實現 3.3.4 棧的應用舉例 遞歸的實現 棧的應用 棧在計算機學科有著許多重要的應用 。 例如： 把十進制整數轉換為二進制整數的方法是 “ 除 2取余 ， 逆序排列 ” ， 利用棧來記下每次余

61、數最后輸出棧中內容 即可； 在語言翻譯中要把十進制表達式的中綴形式先轉換成后 綴形式 ， 然后把后綴表達式翻譯成為一條條運算指令 ， 在后續(xù)課程 編譯原理 中大家會看到都得使用棧結構 來完成； 在算法設計中的需要回溯處理的問題如迷宮問題 、 二叉 樹的遍歷 、 圖的遍歷等非遞歸算法的設計需要借助棧來 完成 ， 把遞歸過程轉換為非遞歸過程也需要借助棧結構； 還有語言翻譯中的函數調用 ， 過程調用 ， 遞歸子程序處 理等等都離不開棧的應用 。 棧的應用舉例 遞歸的實現 遞歸 是算法和程序設計中的一個重要概念 ， 也是算法和程 序設計的一種重要方法和手段 。 在高級程序設計語言中有過程 、 函數和子

62、程序等程序模塊 的概念 ， 這些程序模塊是架構結構化程序的基本單位 。 當這些模塊直接或間接地在程序中調用了自身 ， 就稱作 遞 歸程序模塊 ； 直接調用自身的稱為 直接遞歸 ， 間接調用自身的稱為 間接遞歸 。 遞歸的概念對于程序模塊而存在 ， 即遞歸過程 、 遞歸函數 、 遞歸子程序等 ， 其前提是問題定義的遞歸特性和數據結構的 遞歸特性 。 而問題定義的遞歸特性主要靠我們在對求解問題本 身的分析和理解的過程中去發(fā)現 。 棧的應用舉例 遞歸的實現 (續(xù) ) 在 C語言中 ， 當一個函數體內出現了自身的函數名 （ 即直接調用自身 ） ， 就稱該函數為 直接遞歸函數 ； 當一個函數通過調用其它

63、函數來調用了自身 ， 如 函數 A調用函數 B， 函數 B調用函數 C， 函數 C又調用 了函數 A， 這種情況下稱函數為 間接遞歸函數 （ A、 B、 C都是間接遞歸函數 ） 。 遞歸的實現 求階乘 階乘函數可遞歸定義如下： 必須注意 ， 遞歸定義不能是無限循環(huán)地定義 ！ 任何遞歸定 義必須同時滿足如下兩個條件： 被定義項在定義中的應用 （ 即作為定義項的出現 ） 應 具有更小的 “ 尺度 ” ； 被定義項在最小 “ 尺度 ” 上的定義不是遞歸的 。 例如上述的階乘函數定義中 ， 被定義項 n！ 在定義中的應用 (n-1)!具有比原來 n更小的 “ 尺度 ” n-1；同時 n！ 在最小 “

64、尺度 ” 為 0上的定義由自然數 1直接定義不是遞歸的 。 這兩 個條件實際上構成了遞歸程序設計的基本原則 。 此外 ， 通常把反映條件 的部分 （ 即遞歸結束條件 ） 寫在 遞歸程序模塊的開頭處 。 遞歸的實現 求階乘 (續(xù) ) 許多實際問題是可以遞歸定義的 ， 對于這些問題 很容易寫出它們的遞歸求解算法 。 計算階乘函數的遞歸算法如下： int fact(int n) if(n=0) return 1; else return n*fact(n-1); 遞歸的實現 求階乘 (續(xù) ) 遞歸函數的運行引起遞歸調用 。 例如 ， fact(4)的執(zhí)行中遞歸函數出現的調用 返回 過程如下圖所示：

65、fact(4) fact(3) fact(2) fact(1) fact(0) 1 1 2 6 24 函數 調用與返回 返回值 函數的調用與返回 通常 ， 當一個函數調用另一個函數時 ， 在執(zhí)行被調 用函數前系統(tǒng)要預先做三件事情： 將所有的實參和函數返回地址等信息傳遞給被調用函數； 為被調用函數的局部變量分配存儲空間 將控制轉移到被調用函數的入口處 。 而在從被調用函數返回調用函數之前 ， 系統(tǒng)也需要 做如下三件事情： 保存被調用函數的計算結果； 釋放為被調用函數局部變量分配的數據空間； 按返回地址將控制轉移給調用函數 。 函數的嵌套調用 當多個函數構成嵌套調用時 ， 系統(tǒng)按照先調用后 返回的

66、原則進行工作 。 這種信息的傳遞和控制轉移符合后進先出的原則 ， 使用棧來實現是非常自然的 。 系統(tǒng)將整個程序運行期間所需要的存儲空間都利 用一個工作棧來管理 ， 每當調用 （ 或執(zhí)行 ） 一個函 數時 ， 就為它在棧頂分配一個存儲區(qū)； 每當退出 （ 或執(zhí)行完 ） 一個函數時 ， 就釋放為它 所分配的存儲區(qū)； 當前工作的函數的數據區(qū)總在工作棧的當前棧頂 位置 。 函數的嵌套調用時棧變化過程 函數嵌套調用時工作棧的變化情況如下圖 ， 其中的 1和 2表 示返回地址 ， 是程序中的語句標號 。 遞歸函數的執(zhí)行過程 遞歸函數的執(zhí)行過程類似于嵌套調用時的情況 ， 只不過是在直接遞歸時的調用函數和被調用函數是 同一個函數罷了 。 例如前述的 fact函數 ， 從遞歸調用開始 ， 每遞歸 調用深入一層 ， 就在工作棧的棧頂為所有形參局部 變量和返回地址開辟空間保存 ， 每退出一層遞歸就 從棧頂釋放為本層開辟的空間并返回調用層 。 由于是同一個函數 ， 其返回地址應為同一語句位 置設為 r。 遞歸調用 fact(4)的工作棧變量情況 遞歸的實現小結 利用遞歸算法 （ 函數 、 過程 、 子程序等 ）