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