數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識要點-wenkub.com
2025-06-19 17:05 本頁面
【正文】 j++) if(a[j]a[k]){K=j。 i++) {k=i1。具體步驟是：(1) 在未排序的文件中找出關(guān)鍵字值最小的記錄，然后把這個記錄與第一個位置上的記錄對換，使得關(guān)鍵字值最小的記錄定位；(2) 在余下的記錄中找出關(guān)鍵字值最小的記錄，并把它與第二個位置上的記錄進(jìn)行對調(diào)，使關(guān)鍵字值次小的記錄在已排序的序列中定位；(3) 依次類推，一直到所有的記錄逐個在排序的序列中定位簡單選擇排序算法Bibblesort(R){ Int a[n]。j) if(a[j]a[j1]) {temp=a[j]。 for (i=1。依次類推，一直到所有記錄都有序為止。} } a[j+1] = temp。//把當(dāng)前待排序的首元素保存起來 for (j=i1。 int i, j, temp。設(shè)有一個包含n個記錄{R(1), R(2), …, R(n)}的源文件。該方法是提取關(guān)鍵字中取值較均勻的數(shù)字位作為哈希地址的方法。構(gòu)造方法： ? 直接定址法是以關(guān)鍵字k本身或關(guān)鍵字加上某個數(shù)值常量c作為哈希地址的方法。? if (R[mid].keyk) /*繼續(xù)在R[low..mid1]中查找*/? high=mid1。若不相等,再根據(jù)k與該中間結(jié)點關(guān)鍵字的比較大小確定下一步查找哪個子表,這樣遞歸進(jìn)行下去,直到找到滿足條件的結(jié)點或者該線性表中沒有這樣的結(jié)點。 }以有序表表示靜態(tài)查找表時，Search函數(shù)可用折半查找來實現(xiàn)。amp。上面構(gòu)造的哈夫曼樹對應(yīng)的哈夫曼編碼如下：1：000 3：001 5：01 7：1第八章查找順序查找：是一種最簡單的查找方法。給定權(quán)值w=(1,3,5,7)來構(gòu)造一棵哈夫曼樹給定一組葉結(jié)點權(quán)值，所構(gòu)造的哈夫曼樹樹的形狀可能不同，但帶權(quán)路徑長度值是相同的，一定是最小的。Lk其中Wk為第k個葉結(jié)點的權(quán)值，Lk為第k個葉結(jié)點的路徑長度。由二叉樹的先序序列和后序序列不能唯一地確定該二叉樹。若二叉樹為空,則其高度為0；否則,其高度等于左子樹與右子樹中的最大高度加l。 DispBiTNode(Trchild)。voidDispBiTNode(BiTree T){ if (T != NULL) { printf(%c, Tdata)。bt=NULL。bt=(BiTNode *)malloc(sizeof(BiTNode))。(1)創(chuàng)建二叉樹CreateBTNode(*b,*str)：根據(jù)二叉樹括號表示法的字符串*str生成對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 /*遞歸調(diào)用的結(jié)束條件*/PostOrder(btlchild)。 /*中序遞歸遍歷bt的左子樹*/ Visit(bt)。 /*先序遞歸遍歷bt的左子樹*/PreOrder(btrchild)。（DLR）先序遍歷二叉樹的過程是：(1) 訪問根結(jié)點；(2) 先序遍歷左子樹；(3) 先序遍歷右子樹。/*左右孩子指針域*/}BiTNode, *BiTree。二叉鏈表也可以帶頭結(jié)點的方式存放，如圖(b)所示。如圖所示(a)為一棵完全二叉樹，(b)不是完全二叉樹。i/2 或235。性質(zhì)2 深度為k(k≥1)的二叉樹至多有2k－1個結(jié)點。它或為空樹(n＝0)，或為非空樹；對于非空樹有：(1) 有一個特定的稱之為根的結(jié)點； (2) 根結(jié)點以外的其余結(jié)點分別由兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成。注意,下面的先根遍歷和后根遍歷算法都是遞歸的。②樹中所有結(jié)點可以有零個或多個后繼結(jié)點。性質(zhì)3 高度為h的m次樹至多有個結(jié)點。森林的概念與樹的概念十分相近,因為只要把樹的根結(jié)點刪去就成了森林。結(jié)點的層次從樹根開始定義,根結(jié)點為第1層,它的孩子結(jié)點為第2層,以此類推,一個結(jié)點所在的層次為其雙親結(jié)點所在的層次加1。4. 孩子結(jié)點、雙親結(jié)點和兄弟結(jié)點：在一棵樹中,每個結(jié)點的后繼,被稱作該結(jié)點的孩子結(jié)點(或子女結(jié)點)。2. 分支結(jié)點與葉結(jié)點：度不為零的結(jié)點稱為非終端結(jié)點,又叫分支結(jié)點。（4）括號表示法。這是樹的最基本的表示,使用一棵倒置的樹表示樹結(jié)構(gòu),非常直觀和形象（2）文氏圖表示法。因此，可以采用單鏈表方式來存儲串值，串的這種鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈串。（10）子串定位StrIndex（s，t，pos）：從主串s的第pos個字符起定位串s中是否存在和串t值相等的子串，若存在，則返回子串t在主串s中第一次出現(xiàn)的位置，否則，返回函數(shù)值0。（5）求串長StrLen（s）：返回s串的元素個數(shù)，即s串的長度。從鏈隊的結(jié)構(gòu)可看出，進(jìn)隊的基本操作步驟為(設(shè)進(jìn)隊結(jié)點的地址為x)：Rearnext=x；xnext=NULL；Rear=x；第四章串串結(jié)構(gòu)的形式化定義為：String=(D，R)其中，D={ ai︱ai∈character，i=1，2…n，n≥0}，R={ a i1 ai︱a i1，ai∈D，i=1，2，…n } 串的基本運算有：（1）初始化ClearString（s）：初始化串s。DELQUEUE(queue，r，f，out)/* 在queue隊列中退出一個元素到out，f和r分別是隊首和隊尾的標(biāo)志 */{ if(f==r) { printf(隊空)。ADDQUEUE(queue，r，f，in)/* 在queue隊列中進(jìn)一個元素in，f和r分別是隊首和隊尾的標(biāo)志 */{ if(r==n) { printf(隊滿)。3. 出棧操作鏈棧出棧操作的含義是：從鏈棧中彈出棧頂結(jié)點并返回該結(jié)點中的元素值。 } 調(diào)用此函數(shù)之前，在主調(diào)函數(shù)中(例如main(?))說明一個指針變量后，先為它申請分配一個結(jié)點，然后調(diào)用初始化函數(shù)。 structLsnode *next。int top。帶頭結(jié)點的單向循環(huán)鏈表和雙向循環(huán)鏈表如下圖第三章棧和隊列棧是限定只能在表尾進(jìn)行插入和刪除的線性表，并將表尾稱為棧頂，表頭稱為棧底。 qnextprior=p。 sprior=p。 /*指向前驅(qū)結(jié)點*/ structDNode *next。 向單鏈表中的指定位置插入一個元素ntInsertElem_Loc(LinkList *l
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1