【正文】 示空表。，不再是簡單數(shù)據(jù)類型，編程時(shí)該如何表示？ 因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。(x)—— 計(jì)算變量x的長度（字節(jié)數(shù)）； malloc(m) — 開辟m字節(jié)長度的地址空間，并返回這段空間的首地址； free(p) —— 釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。7. 鏈表的運(yùn)算效率分析：（1）查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。（2） 插入和刪除 因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為 O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是 O(n)。例：在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為 O（n）8. 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別和優(yōu)缺點(diǎn)？ 順序存儲(chǔ)時(shí)，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高；缺點(diǎn)是插入或刪除元素時(shí)不方便。　　鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間利用率低。◆ 順序表適宜于做查找這樣的靜態(tài)操作；◆ 鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。◆ 若線性表的長度變化不大，且其主要操作是查找，則采用順序表；◆ 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。9. 判斷：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單”，對(duì)嗎？答：對(duì)的。因?yàn)椤?數(shù)組中各元素具有統(tǒng)一的類型；② 數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。10. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、列下標(biāo) 和 元素值 。 11. 寫出右圖所示稀疏矩陣的壓縮存儲(chǔ)形式。解：介紹3種存儲(chǔ)形式。法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：用十字鏈表表示用途：方便稀疏矩陣的加減運(yùn)算方法：每個(gè)非0元素占用5個(gè)域法3：用三元組矩陣表示：稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)存取功能代碼：（a，b，c，…，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。char V[30]。void build() //字母線性表的生成，即建表操作{ int i。 V[0]=39。a39。 for( i=1。 i=n1。 i++ ) V[i]=V[i1]+1。 }void display( ) //字母線性表的顯示，即讀表操作{ int i。 for( i=0。 i=n1。 i++ ) printf( %c, v[i] )。 printf( \n )。}void main(void) //主函數(shù)，字母線性表的生成和輸出{ n=26。 // n是表長，是數(shù)據(jù)元素的個(gè)數(shù)，而不是V的實(shí)際下標(biāo) build( )。 display( )。}第3章 棧和隊(duì)列內(nèi)容提要：◆ 從數(shù)據(jù)結(jié)構(gòu)角度來講，棧和隊(duì)列也是線性表，其操作是線性表操作的子集，屬操作受限的線性表。但從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型?！?棧的定義及操作。棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，該端稱為棧的頂端。 插入元素到棧頂?shù)牟僮鳎Q為入棧。 從棧頂刪除最后一個(gè)元素的操作，稱為出棧。 對(duì)于向上生成的堆棧: 入?？谠E：堆棧指針top “先壓后加” : S[top++]=an+1 出棧口訣：堆棧指針top “先減后彈” : e=S[top]◆ 棧的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實(shí)現(xiàn)棧的操作。 順序棧入棧函數(shù)PUSH（）status Push(ElemType e) { if(topM){上溢} else s[top++]=e。}順序棧出棧函數(shù)POP()status Pop( ){ if(top=L) { 下溢 }else { e=s[top]。 return(e)。} }◆ 隊(duì)列的定義及操作，隊(duì)列的刪除在一端（隊(duì)尾），而插入則在隊(duì)列的另一端（隊(duì)頭）。因此在兩種存儲(chǔ)結(jié)構(gòu)中，都需要隊(duì)頭和隊(duì)尾兩個(gè)指針。隊(duì)列：只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。鏈隊(duì)列結(jié)點(diǎn)類型定義： typedef Struct QNode{ QElemType data。 //元素 Struct QNode *next。 //指向下一結(jié)點(diǎn)的指針 }Qnode , * QueuePtr 。鏈隊(duì)列類型定義： typedef struct { QueuePtr front 。 //隊(duì)首指針 QueuePtr rear 。 //隊(duì)尾指針 } LinkQueue。鏈隊(duì)示意圖：① 空鏈隊(duì)的特征：front=rear② 鏈隊(duì)會(huì)滿嗎？一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足?、? 入隊(duì)（尾部插入）：rearnext=S。 rear=S。 出隊(duì)（頭部刪除）：frontnext=pnext。2. 順序隊(duì)順序隊(duì)類型定義：define QUEUEMAXSIZE 100 //最大隊(duì)列長度 typedef struct { QElemType *base。 //隊(duì)列的基址 int front。 //隊(duì)首指針 int rear。 //隊(duì)尾指針 }SqQueue建隊(duì)核心語句：q . base=(QElemType *)malloc(sizeof (QElemType ）* QUEUE_MAXSIZE。 //分配空間順序隊(duì)示意圖：循環(huán)隊(duì)列：隊(duì)空條件 : front = rear (初始化時(shí)：front = rear )隊(duì)滿條件： front = (rear+1) % N (N=maxsize)隊(duì)列長度（即數(shù)據(jù)元素個(gè)數(shù)）：L=（N＋rear－front）% N 1） 初始化一個(gè)空隊(duì)列Status InitQueue ( SqQueue amp。q ) //初始化空循環(huán)隊(duì)列 q{ q . base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE)。 //分配空間if (!) exit(OVERFLOW)。//內(nèi)存分配失敗，退出程序 ==0。 //置空隊(duì)列 return OK。 } //InitQueue。2） 入隊(duì)操作Status EnQueue(SqQueue amp。q, QElemType e){//向循環(huán)隊(duì)列 q 的隊(duì)尾加入一個(gè)元素 e if ( (+1) % QUEUE_MAXSIZE = = ) return ERROR 。 //隊(duì)滿則上溢，無法再入隊(duì) = ( q . rear + 1 ) % QUEUE_MAXSIZE。 [ ] = e。 //新元素e入隊(duì) return OK。 }// EnQueue。3） 出隊(duì)操作Status DeQueue ( SqQueue amp。q, QElemType amp。e) {//若隊(duì)列不空，刪除循環(huán)隊(duì)列q的隊(duì)頭元素， //由 e 返回其值，并返回OK if ( = = ) return ERROR。//隊(duì)列空 =(+1) % QUEUE_MAXSIZE 。 e = [ ] 。 return OK。 }// DeQueue◆ 鏈隊(duì)列空的條件是首尾指針相等，而循環(huán)隊(duì)列滿的條件的判定，則有隊(duì)尾加1等于隊(duì)頭和設(shè)標(biāo)記兩種方法。補(bǔ)充重點(diǎn)：1. 為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？① 調(diào)用函數(shù)或子程序非它莫屬；② 遞歸運(yùn)算的有力工具；③ 用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；④ 簡化了程序設(shè)計(jì)的問題。 ？它有什么獨(dú)特用途？① 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU芯片中的指令譯碼隊(duì)列）；② 操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）；③ 簡化程序設(shè)計(jì)。3. 什么叫“假溢出” ？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作