數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容(編輯修改稿)
2025-07-22 07:23 本頁面
【文章內(nèi)容簡介】 限序列。記為：s=’a1a2…an’(n179。0)216。 S為串名，單引號括起來的字符序列是串的值，n為串的長度。216。 子串——主串中任意個連續(xù)字符組成的子序列。216。 位置——字符在序列中的序號為該字符在串中的位置。子串在 主串中的位置以子串的第一個字符在主串中位置來表示。216。 串相等——兩個串的長度相等，且每個對應(yīng)位置的字符都相等。216。 空串——零個字符的串為空串，長度為0，用214。表示。216。 空格串——由一個或多個空格組成的串為空格串。長度為空格字符的個數(shù)。216。 串的基本操作：通常以“串的整體”為操作對象。216。 串賦值 串復(fù)制216。 求子串 判空串216。 串連接 子串定位216。 串比較 串替換216。 求串長 串插入216。 串清空 串刪除211。 串的表示和實現(xiàn)216。 定長順序存儲表示 為每個串變量分配一個固定長度地址連續(xù)的存儲區(qū)。 define MAX 255 unsigned char sstring[MAX+1]。 0號單元存放串的長度。216。 堆分配存儲表示 在程序執(zhí)行過程中，為每個串變量動態(tài)分配（malloc) 一個地址連續(xù)的存儲區(qū)。216。 串的塊鏈存儲表示 define CSIZE 80 //塊的大小 typedef struct Chunk { char ch[CSIZE]。 struct Chunk *next。 }Chunk。 typedef struct { Chunk *head,*tail。 //頭尾指針 int curlen。 //串長度 }Lstring。數(shù) 組173。 數(shù)組的定義– 數(shù)組的性質(zhì)173。 數(shù)組元素數(shù)目固定，一旦定義，維數(shù)和維界就不再改變。173。 數(shù)組元素具有相同的類型。173。 數(shù)據(jù)元素的下標(biāo)關(guān)系具有上下界的約束并且下標(biāo)有序。– 數(shù)組的描述173。 ji=0，…，bi1, i=1,2,…,n, bi是數(shù)組第i維的長度173。 D={aj1j2…jn|n(0)為數(shù)組的維數(shù)，ji是數(shù)組元素的第i維下標(biāo)}173。 n=1表示一維數(shù)組，是線性表。173。 n=2表示二維數(shù)組，以矩陣形式表示，它也可以看成是線性表，其中每個數(shù)據(jù)元素本身又是一個線性表。– 數(shù)組的基本操作173。 初始化數(shù)組173。 銷毀數(shù)組173。 取元素——給定一組下標(biāo)，返回相應(yīng)的數(shù)組元素值。173。 修改元素值（賦值）——給定一組下標(biāo)，修改相應(yīng)的數(shù)組元素的值。173。 數(shù)組的順序表示和實現(xiàn)– 數(shù)組運(yùn)算通常是隨機(jī)訪問與修改，一般不作插入或刪除，故一旦建立數(shù)組，數(shù)據(jù)元素的個數(shù)與元素之間的關(guān)系就不再發(fā)生變動，所以數(shù)組采用順序存儲結(jié)構(gòu)表示。– 存儲單元是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，用一組地址連續(xù)的存儲單元存放數(shù)組元素有次序約定的問題。– 對于數(shù)組，一旦規(guī)定了它的維數(shù)和各維的長度（下標(biāo)的界限），就可分配空間，并根據(jù)給定的一組下標(biāo)求得相應(yīng)數(shù)組元素的存儲位置。– 一維數(shù)組 LOC(ai)=LOC(a0)+i*L– 二維數(shù)組(m*n)173。 行序為主序（a00,a01,…,a0,n1,a10,a11,……am1,n1)LOC(i,j)=LOC(0,0)+(i*n+j)*L173。 列序為主序（a00,a10,…,am1,0),a01,a11,……am1,n1)LOC(i,j)=LOC(0,0)+(j*m+i)*L– 三維數(shù)組(m*n*p)173。 左下標(biāo)（行）為主序（a000,a001,…a00,p1,a010,……am1,n1,p1)LOC(i,j,k)=LOC(0,0,0)+(i*n*p+j*p+k)*L173。 右下標(biāo)（列）為主序– 多維數(shù)組（b1*b2*…*bn) LOC(j1,j2…,jn)=LOC(0,0,…,0)+ (j1*b2*…*bn+j2*b3*…*bn+jn1*bn+jn)*L– 若確定了數(shù)組的各維長度，則bl*…*bn為常數(shù)，數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù)，由于存取數(shù)組中任一元素的時間相等，故此結(jié)構(gòu)為隨機(jī)存儲結(jié)構(gòu)。173。 矩陣的壓縮存儲– 若矩陣階數(shù)很高，且矩陣中有許多值相同的元素或者零元素，為節(jié)省存儲空間，對矩陣進(jìn)行壓縮存儲，即為多個值相同的元只分配一個存儲空間，對零元不分配空間– 假若值相同的元素或者零元素在矩陣中的分布有一定的規(guī)律，這類矩陣為特殊矩陣，否則為稀疏矩陣。特殊矩陣可將非零元壓縮存儲到一維數(shù)組中，并找到每個非零元在一維數(shù)組中的對應(yīng)關(guān)系。– 特殊矩陣N階對稱矩陣—元素關(guān)于主對角線對稱aij=aji 0=i,j=n1只需存儲上三角或下三角元素。存儲元素總個數(shù)為（1+2+…+n)=n*(n+1)/2假設(shè)以行序為主序存儲下三角中的元當(dāng)i=j k=i*(i1)/2+j1當(dāng)ij k=j*(j1)/2+i1173。 上、下三角矩陣 矩陣的下（上）三角（不包括對角線）中的元均為常數(shù)或零的n階矩陣。只需存儲上（下）三角中的元，再外加一個存儲常數(shù)c的存儲空間。 下三角矩陣： 當(dāng)i=j k=i*(i1)/2+j1 當(dāng)ij k=n*(n+1)/2+1173。 對角矩陣 所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中。即除了主對角線上和主對角線鄰近的上、下方以外，其余元素均為零。– 稀疏矩陣173。 在矩陣A（m*n)中，s為非零元素的個數(shù)，t為零元素的個數(shù)，若st，則A為稀疏矩陣。稀疏因子d=t/(m*n)=。173。 由于稀疏矩陣的非零元素分布沒有任何規(guī)律，壓縮存儲除了存儲非零元素值外，還必須同時存儲它的位置。173。 稀疏矩陣的每個非零元素由一個三元組（i，j，aij)唯一確定。173。 稀疏矩陣可由表示非零元的三元組及其矩陣的行列數(shù)唯一確定。173。 三元組的表示– 三元組順序表– 行邏輯鏈接的順序表– 十字鏈表樹和二叉樹167。 樹的定義和基本術(shù)語167。 樹(tree)是n(n=0)個結(jié)點(diǎn)的有限集。在任意一棵非空樹中：
法律信息相關(guān)推薦
鄂ICP備17016276號-1