【正文】 — 開辟m字節(jié)長度的地址空間，并返回這段空間的首地址； free(p) —— 釋放指針p所指變量的存儲空間，即徹底刪除一個變量。補充重點：：數(shù)據(jù)域和指針域(鏈域)，除了首元結(jié)點外，任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示。◆ 掌握通過畫出結(jié)點圖來進(jìn)行鏈表（單鏈表、循環(huán)鏈表等）的生成、插入、刪除、遍歷等操作。在順序存儲結(jié)構(gòu)中，元素存儲的先后位置反映出這種線性關(guān)系，而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，是靠指針來反映這種關(guān)系的。 在二維數(shù)組中，我們既可以規(guī)定按行存儲，也 可以規(guī)定按列存儲。 前驅(qū)方向：ai+1的前驅(qū)由 ai ( 指針p)變?yōu)閍i1 (指針 p prior )。 sprior = p prior 。 //首先保存b的指針，靠它才能找到c；pnext=qnext。 j++。 P=headnext。 while (p) //當(dāng)指針不空時循環(huán)（僅限于無頭結(jié)點的情況） { printf(%c,pdata)。 // 第一個結(jié)點值為字符apnext=(node*)malloc(m)。 //m=sizeof(node) 前面已求出p=head。 // 數(shù)據(jù)元素的個數(shù)int m=sizeof(node)。 struct node *next。 j++ )a[j1]=a[j]。 插入時的平均移動次數(shù)為：n(n+1)/2247。 j=i。數(shù)據(jù)結(jié)構(gòu)的基本運算：修改、插入、刪除、查找、排序1) 修改——通過數(shù)組的下標(biāo)便可訪問某個特定元素并修改之。 線性表的定義：用數(shù)據(jù)元素的有限序列表示◆ 線性表的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。①正確性、②可讀性、③健壯性、④效率與低存儲量需求◆ 算法分析。抽象數(shù)據(jù)類型——由用戶定義的一個數(shù)學(xué)模型與定義在該模型上的一組操作， 它由基本的數(shù)據(jù)類型構(gòu)成。數(shù)據(jù)——所有能被計算機識別、存儲和處理的符號的集合。第1章 緒論 內(nèi)容提要：◆ 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，具有完整確定的實際意義?！?算法的定義及五個特征。時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性學(xué)習(xí)重點：◆ 數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作（運算） 。順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。 核心語句: V[i]=x。 j)a[j+1]=a[ j ]。（n+1）＝n/2≈O(n) 3) 刪除——刪除線性表的第i個位置上的元素 實現(xiàn)步驟： ①將第i+1 至第n 位的元素向前移動一個位置； ②表長減1。 n。}node。 /*結(jié)構(gòu)類型定義好之后，每個node類型的長度就固定了， m求一次即可*/void build( ) //字母鏈表的生成。for( i=1。 //為后繼結(jié)點“挖坑”！p=pnext；} //讓指針變量P指向后一個結(jié)點pdata=i+‘a(chǎn)’1。 p=pnext。 While((p!=NULL)amp。 }return p。 //將a、c兩結(jié)點相連，淘汰b結(jié)點；free(q) ； //徹底釋放b結(jié)點空間7. 雙向鏈表的插入操作：設(shè)p已指向第 i 元素，請在第 i 元素前插入元素 x：① ai1的后繼從 ai ( 指針是p)變?yōu)?x（指針是s) : snext = p 。 pprior = s 。 pnextprior = p prior 。設(shè)一般的二維數(shù)組是A[c1..d1, c2..d2]，則行優(yōu)先存儲時的地址公式為：二維數(shù)組列優(yōu)先存儲的通式為：◆ 稀疏矩陣（含特殊矩陣）的存儲及運算?！?順序存儲結(jié)構(gòu)用一維數(shù)組表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機存取的存儲結(jié)構(gòu)?！?數(shù)組（主要是二維）在以行序/列序為主的存儲中的地址計算方法。 ？ 頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的數(shù)據(jù)域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進(jìn)行操作時，可以對空表、非空表的情況以及對首元結(jié)點進(jìn)行統(tǒng)一處理，編程更方便。7. 鏈表的運算效率分析：（1）查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為 O(n)。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便?！? 順序表適宜于做查找這樣的靜態(tài)操作；◆ 鏈表宜于做插入、刪除這樣的動態(tài)操作。③數(shù)組的基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。法1：用線性表表示： （( 1,2,12) ，(1,3,9)， (3,1,3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,7)）法2：用十字鏈表表示用途：方便稀疏矩陣的加減運算方法：每個非0元素占用5個域法3：用三元組矩陣表示：稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能代碼：（a，b，c，…，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。a39。 }void display( ) //字母線性表的顯示，即讀表操作{ int i。 printf( \n )。}第3章 棧和隊列內(nèi)容提要：棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，該端稱為棧的頂端。 順序棧入棧函數(shù)PUSH（）status Push(ElemType e) { if(topM){上溢} else s[top++]=e。因此在兩種存儲結(jié)構(gòu)中，都需要隊頭和隊尾兩個指針。 //指向下一結(jié)點的指針 }Qnode , * QueuePtr 。鏈隊示意圖：① 空鏈隊的特征：front=rear② 鏈隊會滿嗎？一般不會，因為刪除時有free動作。2. 順序隊順序隊類型定義：define QUEUEMAXSIZE 100 //最大隊列長度 typedef struct { QElemType *base。 //分配空間順序隊示意圖：循環(huán)隊列：隊空條件 : front = rear (初始化時：front = rear )隊滿條件： front = (rear+1) % N (N=maxsize)隊列長度（即數(shù)據(jù)元素個數(shù)）：L=（N＋rear－front）% N 1） 初始化一個空隊列Status InitQueue ( SqQueue amp。 //置空隊列 return OK。 //隊滿則上溢，無法再入隊 = ( q . rear + 1 ) % QUEUE_MAXSIZE。3） 出隊操作Status DeQueue ( SqQueue amp。 e = [ ] 。 ？它有什么獨特用途？① 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU芯片中的指令譯碼隊列）；② 操作系統(tǒng)中的作業(yè)調(diào)度（一個CPU執(zhí)行多個作業(yè)）；③ 簡化程序設(shè)計。那么，從循環(huán)隊列中刪除一個元素時，其操作是先 移動隊首位置 ，后 取出元素。第四章 串內(nèi)容提要 求串長：int strlen(char *s)。串有三種機內(nèi)表示方法：模式匹配算法否則，匹配失敗，返回值 0。 while ( i=S[0] amp。 j=1?？沾?Null String)是指長度為零的串；而空白串(Blank String),是指包含一個或多個空白字符‘ ’(空格鍵)的字符串.2. “空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串。每個集合本身又是棵樹，被稱作這個根的子樹 。性質(zhì)2: 深度為k的二叉樹至多有2k1個結(jié)點（k0）。若是完全/滿二叉樹則可以做到唯一復(fù)原。優(yōu)點：①不浪費空間；②插入、刪除方便 ◆ 二叉樹的遍歷。 法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹 討論2：二叉樹如何還原為森林？ 要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值軜浜蜕值拇鎯Ψ绞剑簶溆腥N常用存儲方式：①雙親表示法 ②孩子表示法 ③孩子—兄弟表示法問：樹→二叉樹的“連線—抹線—旋轉(zhuǎn)” 如何由計算機自動實現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。① 先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點；先根遍歷第一棵樹的根結(jié)點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。樹的帶權(quán)路徑長度：（樹中所有葉子結(jié)點的帶權(quán)路徑長度之和）構(gòu)造Huffman樹的基本思想：權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。(4) 重復(fù)(2) 和(3) , 直到 F 只含一棵樹為止。