【正文】 數(shù)據(jù)結(jié)構(gòu)教程（第 3版）一 第 1章 緒論 算法及其描述 什么是數(shù)據(jù)結(jié)構(gòu) 算法分析 本章小結(jié) 數(shù)據(jù)結(jié)構(gòu)＋算法＝程序 數(shù)據(jù)結(jié)構(gòu)的定義 邏輯結(jié)構(gòu)類型 存儲(chǔ)結(jié)構(gòu)類型 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 什么是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù) ： 是所有能被輸入到計(jì)算機(jī)中 ,且能被計(jì)算機(jī)處理的符號(hào)的集合。它是計(jì)算機(jī)操作的對(duì)象的總稱 ,也是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。 數(shù)據(jù)元素 ：是數(shù)據(jù) (集合 )中的一個(gè)“個(gè)體” ,是數(shù)據(jù)的基本單位。 數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)對(duì)象 ：是具有相同性質(zhì)的若干個(gè)數(shù)據(jù)元素的集合。 例如 ,202102班為一個(gè)學(xué)生數(shù)據(jù)對(duì)象 ,而其中的“張三”是一個(gè)數(shù)據(jù)元素 )。 數(shù)據(jù)結(jié)構(gòu)：是指 數(shù)據(jù) 以及數(shù)據(jù)元素相互之間的 聯(lián)系 。可以看作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。 因此 ,可時(shí)把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)包括如下幾個(gè)方面： (1) 數(shù)據(jù)元素之間的邏輯關(guān)系 ,即數(shù)據(jù)的邏輯結(jié)構(gòu) 。 (2) 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式 ,即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) ,也稱為數(shù)據(jù)的物理結(jié)構(gòu) 。 (3) 施加在該數(shù)據(jù)上的操作 ,即數(shù)據(jù)的運(yùn)算 。 例 有一個(gè)學(xué)生表如表 。 這個(gè)表中的數(shù)據(jù)元素是學(xué)生記錄 ,每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)項(xiàng) (即學(xué)號(hào) 、 姓別 、 性別和班號(hào) )組成 。 學(xué)號(hào) 姓名 性別 班號(hào) 1 張斌 男 9901 8 劉麗 女 9902 34 李英 女 9901 20 陳華 男 9902 12 王奇 男 9901 26 董強(qiáng) 男 9902 5 王萍 女 9901 表 學(xué)生表 該表中的記錄順序反映了數(shù)據(jù)元素之間的邏輯關(guān)系 , 用學(xué)號(hào)標(biāo)識(shí)每個(gè)學(xué)生記錄 ,這種邏輯關(guān)系可以表示為： 1,8,8,34,34,20,20,12,12,26,26,5 其中尖括號(hào) “ ai,ai+1”表示元素 ai和 ai+1之間是相鄰的 ,即 ai在 ai+1之前 ,ai+1在 ai之后 。 數(shù)據(jù) 在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式就是 存儲(chǔ)結(jié)構(gòu) 。 C/C++語言中 ， 通常采用結(jié)構(gòu)體數(shù)組和鏈表兩種方式實(shí)現(xiàn)其存儲(chǔ)結(jié)構(gòu) 。 存放學(xué)生表的結(jié)構(gòu)體數(shù)組 Stud定義為： struct { int no。 /*存儲(chǔ)學(xué)號(hào) */ char name[8]。 /*存儲(chǔ)姓名 */ char sex[2]。 /*存儲(chǔ)性別 */ char class[4]。 /*存儲(chǔ)班號(hào) */ } Stud[7]={{1,“張斌 ” ,“男 ” ,“9901”},… , {5,王萍 ,女 ,9901}}。 結(jié)構(gòu)體數(shù)組 Stud各元素在內(nèi)存中順序存放 ,即第 i(1≤i≤6)個(gè)學(xué)生對(duì)應(yīng)的元素 Stud[i]存放在第 i+1個(gè)學(xué)生對(duì)應(yīng)的元素 Stud[i+1]之前 ,Stud[i+1]正好在 Stud[i]之后。 9901 女 王萍 5 … 9901 男 張斌 1 Stud[0] Stud[6] Stud數(shù)組起始地址 存放學(xué)生表的鏈表的結(jié)點(diǎn)類型 StudType定義為： typedef struct studnode { int no。 /*存儲(chǔ)學(xué)號(hào) */ char name[8]。 /*存儲(chǔ)姓名 */ char sex[2]。 /*存儲(chǔ)性別 */ char class[4]。 /*存儲(chǔ)班號(hào) */ struct studnode *next。 /*存儲(chǔ)指向下一個(gè)學(xué)生的指針 */ } StudType； 鏈表首結(jié)點(diǎn)地址 head 1 張斌 男 9901 8 劉麗 女 9902 34 李英 女 9901 20 陳華 男 9902 12 王奇 男 9901 26 董強(qiáng) 男 9902 5 王萍 女 9901 ∧ 學(xué)生表構(gòu)成的鏈表如右圖所示。其中的 head為第一個(gè)數(shù)據(jù)元素的指針。 學(xué)生表構(gòu)成的鏈表 對(duì)于 “ 學(xué)生表 ” 這種數(shù)據(jù)結(jié)構(gòu) ,可以進(jìn)行一系列的運(yùn)算 ,例如 ,增加一個(gè)學(xué)生記錄 、 刪除一個(gè)學(xué)生記錄 、 查找性別為 “ 女 ” 的學(xué)生記錄 、 查找班號(hào)為“ 9902”的學(xué)生記錄等等 。 從前面介紹的兩種存儲(chǔ)結(jié)構(gòu)看到 ,同樣的運(yùn)算 ,在不同的存儲(chǔ)結(jié)構(gòu)中 ,其實(shí)現(xiàn)過程是不同的 。 例如 ,查找學(xué)號(hào)為 20的學(xué)生的姓名 ： 對(duì)于 Stud數(shù)組 ,可以從 Stud[0]開始比較 ,Stud[0].no不等于 20,再與 Stud[1].no比較 ,… ,直到 Stud[3].no等于20,返回 Stud[3].name。 對(duì)于 head為首結(jié)點(diǎn)指針的鏈表 ,從 head所指結(jié)點(diǎn)開始比較 ,headno不等于 20,從它的 next得到下一個(gè)結(jié)點(diǎn)的地址 ,再與下一個(gè)結(jié)點(diǎn)的 no域比較 ,… ,直到某結(jié)點(diǎn)的no域等于 20,返回其 name域 。 為了更確切地描述一種數(shù)據(jù)結(jié)構(gòu) ,通常采用二元組表示： B=(K,R) 其中 ,B是一種數(shù)據(jù)結(jié)構(gòu) ,它由數(shù)據(jù)元素的集合 K和 K上二元關(guān)系的集合 R所組成。其中： K={ki| 1≤i≤n,n≥0} R={rj| 1≤j≤m,m≥0} 邏輯結(jié)構(gòu)的描述或表示： 其中： ki表示集合 K中的第 i個(gè)結(jié)點(diǎn)或數(shù)據(jù)元素 。 n為 K中結(jié)點(diǎn)的個(gè)數(shù) ,特別地 ,若 n=0,則 K是一個(gè)空集 ,因而 B也就無結(jié)構(gòu)可言 ,有時(shí)也可以認(rèn)為它具有任一結(jié)構(gòu) 。 rj表示集合 R中的第 j個(gè)二元關(guān)系 (后面均簡(jiǎn)稱關(guān)系 )。 m為 R中關(guān)系的個(gè)數(shù) ,特別地 ,若 m=0,則 R是一個(gè)空集 ,表明集合 K中的元結(jié)點(diǎn)間不存在任何關(guān)系 ,彼此是獨(dú)立的 。 序偶 x,y(x,y∈ K) ? x為第一結(jié)點(diǎn) ,y為第二結(jié)點(diǎn) 。 x為 y的 直接前驅(qū)結(jié)點(diǎn) (通常簡(jiǎn)稱 前驅(qū)結(jié)點(diǎn) ) y為 x的 直接后繼結(jié)點(diǎn) (通常簡(jiǎn)稱 后繼結(jié)點(diǎn) )。 若某個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn) ,則稱該結(jié)點(diǎn)為 開始結(jié)點(diǎn) ；若某個(gè)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn) ,則稱該結(jié)點(diǎn)為 終端結(jié)點(diǎn) 。 說明： x,y表示有向關(guān)系， (x,y)表示無向關(guān)系。采用離散數(shù)學(xué)的表示方法。 例如 ,采用二元組表示例 。 學(xué)生表中共有 7個(gè)結(jié)點(diǎn) ,依次用 k1～ k7表示 ,則對(duì)應(yīng)的二元組表示為 B=(K,R),其中： K={k1,k2,k3,k4,k5,k6,k7} R={r} //只有一種關(guān)系 r={k1,k2,k2,k3,k3,k4,k4,k5,k5,k6,k6,k7} 又例如 ,有如下數(shù)據(jù)即一個(gè)矩陣： ????????????????????????119105471281362 對(duì)應(yīng)的二元組表示為 B=(K,R),其中： K={2,6,3,1,8,12,7,4,5,10,9,11} R={r1,r2} 其中 ,r1表示行關(guān)系 ,r2表示列關(guān)系 r1={2,6,6,3,3,1,8,12,12,7,7,4,5,10, 10,9,9,11} r2={2,8,8,5,6,12,12,10,3,7,7,9, 1,4, 4,11} 一個(gè)二維數(shù)組 可以 利用圖形形象地表示邏輯結(jié)構(gòu)。 例如，上述 “ 學(xué)生表 ” 數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。 k1 k2 k3 k4 k5 k6 k7 學(xué)生表數(shù)據(jù)結(jié)構(gòu)圖示 (1) 線性結(jié)構(gòu) 結(jié)點(diǎn)之間關(guān)系： 一對(duì)一 。 特點(diǎn)： 開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都是惟一的 ,除了開始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外 ,其余結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn) ,有且僅有一個(gè)后繼結(jié)點(diǎn) 。 順序表就是典型的線性結(jié)構(gòu) 。 邏輯結(jié)構(gòu)類型 … (2) 樹形結(jié)構(gòu) 結(jié)點(diǎn)之間關(guān)系： 一對(duì)多 。 特點(diǎn)： 開始結(jié)點(diǎn)惟一 ,終端結(jié)點(diǎn)不惟一 。 除終端結(jié)點(diǎn)以外 ,每個(gè)結(jié)點(diǎn)有一個(gè)或多個(gè)后續(xù)結(jié)點(diǎn)；除開始結(jié)點(diǎn)外 ， 每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn) 。 (3) 圖形結(jié)構(gòu) 結(jié)點(diǎn)之間關(guān)系： 多對(duì)多 。 特點(diǎn)： 沒有開始結(jié)點(diǎn)和終端結(jié)點(diǎn) ， 所有結(jié)點(diǎn)都可能有多個(gè)前驅(qū)結(jié)點(diǎn)和多個(gè)后繼結(jié)點(diǎn) 。 (2) 鏈?zhǔn)酱鎯?chǔ)方法 (3) 索引存儲(chǔ)方法 (4) 散列存儲(chǔ)方法 存儲(chǔ)結(jié)構(gòu)類型 (1) 順序存儲(chǔ)方法 (1) 數(shù)據(jù)類型 高級(jí)程序語言中 ,一般須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式 ,明確說明它們所屬的數(shù)據(jù)類型。不同類型的變量 ,其所能取的值的范圍不同 ,所能進(jìn)行的操作不同。 數(shù)據(jù)類型 是一個(gè)值的集合和定義在此集合上的一組操作的總稱。 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 如 C/C++中的 int就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合 (在 16位計(jì)算機(jī)中為－ 32768~32767的全體整數(shù) )和相關(guān)的整數(shù)運(yùn)算 (如＋、－、＊、／等 )。 (2) 抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型 (Abstract Data Type簡(jiǎn)寫為 ADT)指的是用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問題的數(shù)學(xué)模型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算 ,而不考慮計(jì)算機(jī)的具體存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。 抽象數(shù)據(jù)類型 =數(shù)據(jù)元素集合＋抽象運(yùn)算 例如 ,抽象數(shù)據(jù)類型 復(fù)數(shù) 的定義： ADT Complex { 數(shù)據(jù)對(duì)象： D={e1,e2|e1,e2均為實(shí)數(shù) } 數(shù)據(jù)關(guān)系： R1={e1,e2| e1是復(fù)數(shù)的實(shí)數(shù)部分 ,e2 是復(fù)數(shù)的 虛數(shù)部分 } e1＋ e2i 基本操作： AssignComplex(amp。Z,v1,v2)：構(gòu)造復(fù)數(shù) Z。 DestroyComplex(amp。Z):復(fù)數(shù) Z被銷毀 。 GetReal(Z,amp。real):返回復(fù)數(shù) Z的實(shí)部值 。 GetImag(Z,amp。Imag):返回復(fù)數(shù) Z的虛部值 。 Add(z1,z2,amp。sum):返回兩個(gè)復(fù)數(shù) z1,z2的和 。 } ADT Complex 算法及其描述 什么是算法 算法描述 什么是算法 數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系 ,對(duì)應(yīng)的操作有邏輯結(jié)構(gòu)上的操作功能和具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)。 通常把具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)步驟或過程稱為 算法 。 算法的五個(gè)重要的特性 (1) 有窮性 :在有窮步之后結(jié)束。 (2) 確定性 :無二義性。 (3) 可行性 :可通過基本運(yùn)算有限次執(zhí)行來實(shí)現(xiàn)。 (4) 有輸入 (5) 有輸出 例 考慮下列兩段描述： (1) 描述一 void exam1() { n＝ 2。 while (n%2＝＝ 0) n＝ n+2。 printf(%d\n,n)。 } 華中科大考研題 (2) 描述二 void exam2() { y=0。 x=5/y。 printf(“%d,%d\n”,x,y)。 } 這兩段描述均不能滿足算法的特征 ,試問它們違反了哪些特征 ？ 解： (1)算法是一個(gè)死循環(huán) ,違反了算法的有窮性特征 。 (2)算法包含除零錯(cuò)誤 ,違反了算法的可行性特征 。 算法描述 本書中采用 C/C++語言描述算法。 說明： C++語言中提供了一種 引用 運(yùn)算符“ amp?！?引用是個(gè)別名 ,當(dāng)建立引用時(shí) ,程序用另一個(gè)已定義的變量或?qū)ο?(目標(biāo) )的名字初始化它 ,從那時(shí)起 ,引用作為目標(biāo)的別名而使用 ,對(duì)引用的改動(dòng)實(shí)際就是對(duì)目標(biāo)的改動(dòng)。 注意： Turbo C不支持引用類型。 編寫一個(gè)函數(shù) swap1(x,y)，當(dāng)執(zhí)行語句 swap1(a,b)時(shí) ,交換 a和 b的值。 void swap1(int x,int y) { int tmp。