【正文】 操作stutus EnQueue(LinkQueue amp。Q, QelemType e){p=(QueuePtr)malloc(sizeof(Qnode))。if(!p)exit(OVERFLOW)。pdata=e。 pnext=NULL。 next=p。 =p。 return OK。}(c) 鏈?zhǔn)疥?duì)列的出隊(duì)列操作。status DeQueue (LinkQueue amp。Q, QelemType amp。e) {if(== returnERROR。p=next。 e=pdata。 next=pnext。if(==p)=。 free(p)。return OK。}注意：當(dāng)隊(duì)列中最后一個(gè)元素被刪除后，隊(duì)列尾指針也丟失了，因此需要對(duì)隊(duì)尾指針重新賦值。小結(jié)：主講主要介紹了隊(duì)列的基本概念和基本操作，以及隊(duì)列的基本操作在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。四、作業(yè)布置 見(jiàn)習(xí)題集實(shí)驗(yàn)作業(yè)見(jiàn)實(shí)驗(yàn)指導(dǎo)。單元名稱：第 七 講：串一、教學(xué)目標(biāo) ，并能利用這些基本操作來(lái)實(shí)現(xiàn)串的其它各種操作的方法。二、重點(diǎn)與難點(diǎn)串的存儲(chǔ)結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)。三、教學(xué)內(nèi)容與教學(xué)過(guò)程講授新課 串類型的定義（1）基本概念： 串（string）：由零個(gè)或多個(gè)字符組成的有限序列，也稱字符串。記為： S = ‘a(chǎn)1a2a3……an’ (n≥0) 如：A= ‘BEIJING’， B= ‘JING’ 串的長(zhǎng)度：串中字符的數(shù)目n 。 空串：不含任何字符的串，串長(zhǎng)度為0， 空格串：僅由一個(gè)或多個(gè)空格組成的串，長(zhǎng)度為串中空格字符的個(gè)數(shù)。 如： ‘ ’ ， C= ‘ BEI JING ’ 子串：由串中任意個(gè)連續(xù)的字符組成的子序列。 主串：包含子串的串。如：A= ‘ BEIJING ’ B= ‘ JING ’ 字符在串中的位置：字符在序列中的序號(hào)。 子串在主串中的位置：以子串的第一個(gè)字符在主串中的位置來(lái)表示。 如：A= ‘ BEIJING ’，B= ‘JING ’，B在A中的位置為4。 串相等：當(dāng)且僅當(dāng)兩個(gè)串的值相等。也就是說(shuō)，只有兩個(gè)串的長(zhǎng)度相等 且各個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。（2）串的抽象數(shù)據(jù)類型定義：ADT String { 數(shù)據(jù)對(duì)象：D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 數(shù)據(jù)關(guān)系：R1＝{ ai1, ai | ai1, ai ∈D, i=2,...,n } 基本操作：（見(jiàn)教材P71）} ADT String 通過(guò)基本操作可以實(shí)現(xiàn)更復(fù)雜的操作。如通過(guò)判等、求串長(zhǎng)和求子串等操作可以實(shí)現(xiàn)定位函數(shù)Index。 串的表示和實(shí)現(xiàn) 定長(zhǎng)順序存儲(chǔ)表示用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，類似于線性表的順序存儲(chǔ)結(jié)構(gòu)。所謂定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)，是直接使用定長(zhǎng)的字符數(shù)組來(lái)定義，數(shù)組的上界預(yù)先給出： define MAXSTRLEN 255 // 用戶可在255以內(nèi)定義最大串長(zhǎng) typedef unsigned char SString[MAXSTRLEN + 1]。 // 0號(hào)單元存放串的長(zhǎng)度特點(diǎn)：串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義長(zhǎng)度的串值則被舍去，稱之為“截?cái)唷?。按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為 “字符序列的復(fù)制”（通過(guò)串聯(lián)接和求子串來(lái)講解）。 堆分配存儲(chǔ)表示以一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，存儲(chǔ)空間在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配。 C語(yǔ)言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc()和free( )進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱串值共享的存儲(chǔ)空間為“堆”。C語(yǔ)言中的串以一個(gè)空字符為結(jié)束符，串長(zhǎng)是一個(gè)隱含值。串堆分配存儲(chǔ)表示：typedef struct { char *ch。 // 若是非空串，則按串長(zhǎng)分配存儲(chǔ)區(qū),否則ch為NULL int length。 // 串長(zhǎng)度} HString。這類串操作實(shí)現(xiàn)的算法為：先為新生成的串分配一個(gè)存儲(chǔ)空間，然后進(jìn)行串值的復(fù)制（以串的復(fù)制操作為例）。講解串堆分配的表示與實(shí)現(xiàn) （P76，77） 塊鏈存儲(chǔ)表示 以鏈表存儲(chǔ)串值，除頭指針外還可以附設(shè)一個(gè)尾指針指示鏈表中的最后一個(gè)結(jié)點(diǎn)，并給出當(dāng)前串的長(zhǎng)度。稱如此定義的傳存儲(chǔ)結(jié)構(gòu)為塊鏈結(jié)構(gòu)。define CHUNKSIZE 80 // 可由用戶定義的塊大小 typedef struct Chunk { // 結(jié)點(diǎn)結(jié)構(gòu) char ch[CUNKSIZE]。 struct Chunk *next。 } Chunk。 typedef struct { // 串的鏈表結(jié)構(gòu) Chunk *head, *tail。 // 串的頭和尾指針 int curlen。 // 串的當(dāng)前長(zhǎng)度 } LString。講解塊鏈存儲(chǔ)表示在串處理系統(tǒng)中的應(yīng)用。小結(jié)：總結(jié)本講的主要內(nèi)容四、作業(yè)布置 見(jiàn)習(xí)題集實(shí)驗(yàn)作業(yè)見(jiàn)實(shí)驗(yàn)指導(dǎo)。單元名稱：第九講 數(shù) 組一、教學(xué)目標(biāo) 。二、重點(diǎn)與難點(diǎn)數(shù)組的壓縮存儲(chǔ)。三、教學(xué)內(nèi)容與教學(xué)過(guò)程講授新課 數(shù)組的定義數(shù)組的抽象數(shù)據(jù)類型定義：ADT Array{ 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作：}ADT Array數(shù)組是一種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看成是一般線性表的擴(kuò)充。二維數(shù)組可以看成是線性表的線性表。 舉例對(duì)于數(shù)組的操作一般只有兩類：（與線性表對(duì)比講解）（1）獲得特定位置的元素值；（2）修改特定位置的元素值。 數(shù)組的順序表示和實(shí)現(xiàn)對(duì)于數(shù)組A，一旦給定其維數(shù)n及各維長(zhǎng)度bi（1≤i≤n），則該數(shù)組中元素的個(gè)數(shù)是固定的，不可以對(duì)數(shù)組做插入和刪除操作，不涉及移動(dòng)元素操作，因此對(duì)于數(shù)組而言，采用順序存儲(chǔ)法比較合適。 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)有兩種：一種是按行序存儲(chǔ)，如高級(jí)語(yǔ)言BASIC、COBOL和PASCAL語(yǔ)言都是以行序?yàn)橹鳌Ａ硪环N是按列序存儲(chǔ)，如高級(jí)語(yǔ)言中的FORTRAN語(yǔ)言就是以列序?yàn)橹鳌?以二維數(shù)組為例，假設(shè)每個(gè)元素只占L個(gè)存儲(chǔ)單元，“以行為主”存放數(shù)組，下標(biāo)從0開始，首元素a00的地址為L(zhǎng)oc[0,0] 求任意元素aij的地址 ，可由如下計(jì)算公式得到：Loc[i,j]=Loc[0,0]+b2i+j 其中b2為第二維的長(zhǎng)度。對(duì)于ｎ維數(shù)組我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲(chǔ)地址的計(jì)算公式。 Loc[j1，j2，…jn]=Loc[0，0，…，0]+ 其中=L，ci1=bici， 1i≤n 特殊矩陣的壓縮存儲(chǔ)特殊矩陣壓縮存儲(chǔ)的壓縮原則是：對(duì)有規(guī)律的元素和值相同的元素只分配一個(gè)存儲(chǔ)單元，對(duì)于零元素不分配空間。（1）對(duì)稱矩陣 滿足條件：aij=aji 1≤i，j≤n （2）三角矩陣（3）帶狀矩陣使用一維數(shù)組存儲(chǔ)以上特殊矩陣，通過(guò)示例講解矩陣中元素與一維數(shù)組中元素的對(duì)應(yīng)關(guān)系。 稀疏矩陣稀疏矩陣：指矩陣中大多數(shù)元素為零的矩陣。一般地，當(dāng)非零元素個(gè)數(shù)只占矩陣元素總數(shù)的5或低于這個(gè)百分?jǐn)?shù)時(shí)，我們稱這樣的矩陣為稀疏矩陣。（1）稀疏矩陣的三元組表表示法對(duì)于稀疏矩陣的壓縮存儲(chǔ)要求在存儲(chǔ)非零元素的同時(shí)，還必須存儲(chǔ)該非零元素在矩陣中所處的行號(hào)和列號(hào)。我們將這種存儲(chǔ)方法叫做稀疏矩陣的三元組表示法。 稀疏矩陣的三元組順序存儲(chǔ)表示define MAXSIZE 1000 typedef struct {int i, j。 ElementType e； }Triple。 typedef struct{Triple data[MAXSIZE+1]。 int mu, nu, tu。 }TSMatrix；用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置運(yùn)算矩陣轉(zhuǎn)置：指變換元素的位置，把位于（row，col）位置上的元素?fù)Q到（col ，row）位置上，也就是說(shuō)，把元素的行列互換。用三元組實(shí)現(xiàn)稀疏矩陣轉(zhuǎn)置運(yùn)算的兩種方式重點(diǎn)掌握第一種方式：由轉(zhuǎn)置后的矩陣中元素在三元組中的次序依次在轉(zhuǎn)置前的矩陣中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。通過(guò)程序結(jié)合矩陣進(jìn)行講解。（2）矩陣的行邏輯鏈接的順序表 （了解）（3）十字鏈表表示 （了解）小結(jié)：總結(jié)本講的主要內(nèi)容四、作業(yè)布置見(jiàn)習(xí)題集實(shí)驗(yàn)作業(yè)見(jiàn)實(shí)驗(yàn)指導(dǎo)。