【正文】 第1章 緒論 內(nèi)容提要：◆ 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作。數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容：◆ 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。數(shù)據(jù)——所有能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理的符號(hào)的集合。數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義。數(shù)據(jù)對(duì)象——具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)——是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為： Data_Structure=（D, R）數(shù)據(jù)類型——是一個(gè)值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型——由用戶定義的一個(gè)數(shù)學(xué)模型與定義在該模型上的一組操作， 它由基本的數(shù)據(jù)類型構(gòu)成?！?算法的定義及五個(gè)特征。算法——是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉(zhuǎn)換為輸出的計(jì)算步驟。算法的基本特性：輸入、輸出、有窮性、確定性、可行性 ◆ 算法設(shè)計(jì)要求。①正確性、②可讀性、③健壯性、④效率與低存儲(chǔ)量需求◆ 算法分析。時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性學(xué)習(xí)重點(diǎn)：◆ 數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲(chǔ)）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作（運(yùn)算） 。◆ 用計(jì)算語(yǔ)句頻度來估算算法的時(shí)間復(fù)雜度。第2章 線性表內(nèi)容提要：◆ 線性表的邏輯結(jié)構(gòu)定義，對(duì)線性表定義的操作。 線性表的定義：用數(shù)據(jù)元素的有限序列表示◆ 線性表的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)定義：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu): 其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。通過指針來實(shí)現(xiàn)！◆ 線性表的操作在兩種存儲(chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算：修改、插入、刪除、查找、排序1) 修改——通過數(shù)組的下標(biāo)便可訪問某個(gè)特定元素并修改之。 核心語(yǔ)句: V[i]=x。 順序表修改操作的時(shí)間效率是 O(1)2) 插入——在線性表的第i個(gè)位置前插入一個(gè)元素 實(shí)現(xiàn)步驟： ①將第n至第i 位的元素向后移動(dòng)一個(gè)位置； ②將要插入的元素寫到第i個(gè)位置； ③表長(zhǎng)加1。 注意：事先應(yīng)判斷: 插入位置i 是否合法?表是否已滿? 應(yīng)當(dāng)符合條件： 1≤i≤n+1 或 i=[1, n+1] 核心語(yǔ)句：for (j=n。 j=i。 j)a[j+1]=a[ j ]。 a[ i ]=x。 n++。 插入時(shí)的平均移動(dòng)次數(shù)為：n(n+1)/2247。（n+1）＝n/2≈O(n) 3) 刪除——?jiǎng)h除線性表的第i個(gè)位置上的元素 實(shí)現(xiàn)步驟： ①將第i+1 至第n 位的元素向前移動(dòng)一個(gè)位置； ②表長(zhǎng)減1。 注意：事先需要判斷，刪除位置i 是否合法? 應(yīng)當(dāng)符合條件：1≤i≤n 或 i=[1, n] 核心語(yǔ)句：for ( j=i+1。 j=n。 j++ )a[j1]=a[j]。 n。 順序表刪除一元素的時(shí)間效率為:T（n)=(n1)/2 ≈O(n) 順序表插入、刪除算法的平均空間復(fù)雜度為O(1)單鏈表：（1）用單鏈表結(jié)構(gòu)來存放26個(gè)英文字母組成的線性表（a，b，c，…，z）,請(qǐng)寫出C語(yǔ)言程序。includeincludetypedef struct node{char data。 struct node *next。}node。 node *p,*q,*head。 //一般需要3個(gè)指針變量int n 。 // 數(shù)據(jù)元素的個(gè)數(shù)int m=sizeof(node)。 /*結(jié)構(gòu)類型定義好之后，每個(gè)node類型的長(zhǎng)度就固定了， m求一次即可*/void build( ) //字母鏈表的生成。要一個(gè)個(gè)慢慢鏈入{ int i。head=(node*)malloc(m)。 //m=sizeof(node) 前面已求出p=head。for( i=1。 i26。 i++) //因尾結(jié)點(diǎn)要特殊處理，故i≠26{ pdata=i+‘a(chǎn)’1。 // 第一個(gè)結(jié)點(diǎn)值為字符apnext=(node*)malloc(m)。 //為后繼結(jié)點(diǎn)“挖坑”！p=pnext；} //讓指針變量P指向后一個(gè)結(jié)點(diǎn)pdata=i+‘a(chǎn)’1。 //最后一個(gè)元素要單獨(dú)處理pnext=NULL 。 //單鏈表尾結(jié)點(diǎn)的指針域要置空！} } void display() //字母鏈表的輸出{ p=head。 while (p) //當(dāng)指針不空時(shí)循環(huán)（僅限于無頭結(jié)點(diǎn)的情況） { printf(%c,pdata)。 p=pnext。 //讓指針不斷“順藤摸瓜” }}（2） 單鏈表的修改(或讀取）思路：要修改第i個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針p， 然后才能：pdata=new_value 讀取第i個(gè)數(shù)據(jù)元素的核心語(yǔ)句是：Linklist *find(Linklist *head ,int i){ int j=1。 Linklist *p。 P=headnext。 While((p!=NULL)amp。amp。(ji)) { p=pnext。 j++。 }return p。 }3. 單鏈表的插入鏈表插入的核心語(yǔ)句：Step 1：snext=pnext。Step 2：pnext=s ；6. 單鏈表的刪除刪除動(dòng)作的核心語(yǔ)句（要借助輔助指針變量q）：q = pnext。 //首先保存b的指針，靠它才能找到c；pnext=qnext。 //將a、c兩結(jié)點(diǎn)相連，淘汰b結(jié)點(diǎn)；free(q) ； //徹底釋放b結(jié)點(diǎn)空間7. 雙向鏈表的插入操作：設(shè)p已指向第 i 元素，請(qǐng)?jiān)诘?i 元素前插入元素 x：① ai1的后繼從 ai ( 指針是p)變?yōu)?x（指針是s) : snext = p 。 ppriornext = s 。 ② ai 的前驅(qū)從 ai1 ( 指針是pprior)變?yōu)?x ( 指針是s)。 sprior = p prior 。 pprior = s 。 8. 雙向鏈表的刪除操作：設(shè)p指向第 i 個(gè)元素，刪除第 i 個(gè) 元素后繼方向：ai1的后繼由 ai ( 指針p)變?yōu)?ai+1(指針 p next )。 p priornext = pnext 。 前驅(qū)方向：ai+1的前驅(qū)由 ai ( 指針p)變?yōu)閍i1 (指針 p prior )。 pnextprior = p prior 。 ◆ 數(shù)組的邏輯結(jié)構(gòu)定義及存儲(chǔ)數(shù)組： 由一組名字相同、下標(biāo)不同的變量構(gòu)成N維數(shù)組的特點(diǎn)：n個(gè)下標(biāo)，每個(gè)元素受到n個(gè)關(guān)系約束一個(gè)n維數(shù)組可以看成是由若干個(gè)n－1維數(shù)組組成的線性表。存儲(chǔ)：事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存入存儲(chǔ)器中。 在二維數(shù)組中，我們既可以規(guī)定按行存儲(chǔ)，也 可以規(guī)定按列存儲(chǔ)。設(shè)一般的二維數(shù)組是A[c1..d1, c2..d2]，則行優(yōu)先存儲(chǔ)時(shí)的地址公式為：二維數(shù)組列優(yōu)先存儲(chǔ)的通式為：◆ 稀疏矩陣（含特殊矩陣）的存儲(chǔ)及運(yùn)算。 稀疏矩陣：矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）學(xué)習(xí)重點(diǎn)：◆ 線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。在順序存儲(chǔ)結(jié)構(gòu)中，元素存儲(chǔ)的先后位置反映出這種線性關(guān)系，而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，是靠指針來反映這種關(guān)系的?！?順序存儲(chǔ)結(jié)構(gòu)用一維數(shù)組表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。◆ 鏈表操作中應(yīng)注意不要使鏈意外“斷開”。因此，若在某結(jié)點(diǎn)前插入一個(gè)元素，或刪除某元素，必須知道該元素的前驅(qū)結(jié)點(diǎn)的指針?！?掌握通過畫出結(jié)點(diǎn)圖來進(jìn)行鏈表（單鏈表、循環(huán)鏈表等）的生成、插入、刪除、遍歷等操作。◆ 數(shù)組（主要是二維）在以行序/列序?yàn)橹鞯拇鎯?chǔ)中的地址計(jì)算方法?！?稀疏矩陣的三元組表存儲(chǔ)結(jié)構(gòu)?！?稀疏矩陣的十字鏈表存儲(chǔ)方法。補(bǔ)充重點(diǎn)：：數(shù)據(jù)域和指針域(鏈域)，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。 ？ 頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放表長(zhǎng)度等附加信息，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。4. 如何表示空表？（1）無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；（2）有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表