一道算法設(shè)計(jì)題的解析

黃詩(shī)佳，熊啟軍

（湖北文理學(xué)院計(jì)算機(jī)工程學(xué)院，襄陽(yáng)441053）

0 引言

在《數(shù)據(jù)結(jié)構(gòu)與算法》中，主要學(xué)習(xí)使用兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)）來(lái)實(shí)現(xiàn)問(wèn)題所涉及數(shù)據(jù)的類型定義、增刪改查等基本操作。線性表是基本的數(shù)據(jù)結(jié)構(gòu)，是學(xué)習(xí)樹、圖、散列表，以及查找和排序等知識(shí)的基礎(chǔ)。學(xué)好線性表則給學(xué)習(xí)其他知識(shí)打下了堅(jiān)實(shí)的基礎(chǔ)。一道算法設(shè)計(jì)題，使用不同的存儲(chǔ)結(jié)構(gòu)，其實(shí)現(xiàn)算法可能不同；即使是使用同一種存儲(chǔ)結(jié)構(gòu)，其實(shí)現(xiàn)算法也可能不同。

1 問(wèn)題描述

待求解的問(wèn)題是這樣的：輸入若干個(gè)正整數(shù)（輸入負(fù)數(shù)或0 結(jié)束），將其中出現(xiàn)次數(shù)大于等于3 的數(shù)據(jù)有序輸出。

這道題主要涉及數(shù)據(jù)的存儲(chǔ)、排序、計(jì)數(shù)、輸出等。

2 順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)

2.1 整型數(shù)組實(shí)現(xiàn)

使用一個(gè)整型數(shù)組作為存儲(chǔ)結(jié)構(gòu)，進(jìn)行數(shù)據(jù)的讀取、排序、計(jì)數(shù)、輸出。其算法描述如下：

（1）聲明一個(gè)整型數(shù)組a[MaxLength]；

（2）輸入若干個(gè)正整數(shù)a[i]，當(dāng)輸入負(fù)數(shù)或0 結(jié)束；計(jì)數(shù)實(shí)際元素的個(gè)數(shù)len；

（3）編寫函數(shù)sort（int a[],int len）實(shí)現(xiàn)遞增排序；

（4）編寫函數(shù)output（int a[],int len）實(shí)現(xiàn)統(tǒng)計(jì)并輸出出現(xiàn)次數(shù)大于等于3 的元素。

在這個(gè)算法中，第四步是最重要的，其實(shí)現(xiàn)算法主要有如下兩種。

2.1.1 順序式計(jì)數(shù)所謂順序式計(jì)數(shù)，即是針對(duì)排序后的序列，對(duì)每個(gè)元素出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)。算法如下：

在該算法之中，i 和j 作為當(dāng)前正在比較的兩元素的下標(biāo)，它們是順序增加的，且a[i]和a[j]是相鄰的兩個(gè)元素；count 則是遞增或回溯的。

當(dāng)然while 循環(huán)的循環(huán)體也可以改寫成下面的形式：

使得i 可能跳躍式的增加，但j 仍然是順序遞增的。

對(duì)于C 語(yǔ)言學(xué)習(xí)者來(lái)說(shuō)，掌握上述方法是基本要求；而數(shù)據(jù)結(jié)構(gòu)的初學(xué)者來(lái)說(shuō)則是最低要求了。

2.1.2 跳躍式計(jì)數(shù)

所謂跳躍式計(jì)數(shù)，即是針對(duì)排序后的序列，第一次拿a[i]（最初i=0）與a[i+2]元素進(jìn)行比較，相等則與a[i+3]比較……、且還需判斷該數(shù)是否已經(jīng)輸出；不等則對(duì)i 或j 進(jìn)行跳躍式賦值，即這里就體現(xiàn)出了兩種跳躍。下面的函數(shù)中flag 起標(biāo)記的作用，即a[i]是否已輸出。具體算法如下：

顯然，跳躍式計(jì)數(shù)的效率更高一些。上述算法，對(duì)于C 語(yǔ)言學(xué)習(xí)者來(lái)說(shuō)則屬于較高要求。

2.2 結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)

將數(shù)據(jù)的值和它出現(xiàn)的次數(shù)組織成結(jié)構(gòu)體，所有元素組織成結(jié)構(gòu)體數(shù)組。若仍使用2.1.1 中的方法進(jìn)行排序和計(jì)數(shù)，則效率很低；若采取邊輸入邊進(jìn)行插入排序、同時(shí)實(shí)現(xiàn)計(jì)數(shù)操作的方式實(shí)現(xiàn)，則可以少用一個(gè)數(shù)組，從而提高存儲(chǔ)空間的使用效率。

2.2.1 結(jié)點(diǎn)數(shù)據(jù)類型定義

2.2.2 算法描述

下面的函數(shù)實(shí)現(xiàn)將x 插入到已排好序的序列之中、同時(shí)完成計(jì)數(shù)。

上述兩種方法3 種方式的解答辦法具有共同的特點(diǎn)：都使用順序存儲(chǔ)結(jié)構(gòu)，空間復(fù)雜度是相同的；時(shí)間復(fù)雜度總體上與使用的排序方法的時(shí)間復(fù)雜度一致，計(jì)數(shù)方法上有順序和跳躍式兩種、后者效率略高。

上述算法對(duì)于數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)者來(lái)說(shuō)則是基本要求。

3 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)

3.1 數(shù)據(jù)類型定義

將數(shù)據(jù)的類型組織成值、次數(shù)、指針三個(gè)數(shù)據(jù)項(xiàng)構(gòu)成結(jié)構(gòu)體，所有數(shù)據(jù)組織成鏈表。每個(gè)結(jié)點(diǎn)的數(shù)據(jù)類型具體描述如下：

其中，data 表示輸入的整型值；count 表示某值出現(xiàn)的次數(shù)；next 表示下一結(jié)點(diǎn)的地址。

3.2 算法描述

功能的實(shí)現(xiàn)由4 個(gè)函數(shù)構(gòu)成，分別是鏈表初始化函數(shù)、集排序計(jì)數(shù)于一體的函數(shù)、輸出結(jié)果函數(shù)、主函數(shù)。具體算法如下。

（1）鏈表初始化函數(shù)

上述函數(shù)的功能是建立一個(gè)含頭結(jié)點(diǎn)的初始化鏈表。

（2）集排序計(jì)數(shù)于一體的函數(shù)

這個(gè)函數(shù)實(shí)現(xiàn)將值為x 的正整數(shù)插入到一個(gè)遞增有序的鏈表之中，同時(shí)實(shí)現(xiàn)計(jì)數(shù)操作。

（3）輸出函數(shù)

（4）主函數(shù)

由于使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，所以排序只能使用直接插入排序，其時(shí)間復(fù)雜度是O（n^2）；在空間復(fù)雜度上，由于無(wú)需考慮數(shù)據(jù)存儲(chǔ)時(shí)初始空間的大小。因此，與順序存儲(chǔ)結(jié)構(gòu)比較，優(yōu)勢(shì)比較明顯。

上述算法對(duì)于數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)者來(lái)說(shuō)則是必備技能。

4 結(jié)語(yǔ)

這道算法設(shè)計(jì)題，能檢驗(yàn)對(duì)線性表中順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)以及操作的理解和應(yīng)用能力。《數(shù)據(jù)結(jié)構(gòu)與算法》是計(jì)算機(jī)專業(yè)的核心基礎(chǔ)課程，是計(jì)算機(jī)程序設(shè)計(jì)的重要理論和實(shí)踐基礎(chǔ)，是研究生考試的必考科目。對(duì)于算法設(shè)計(jì)題，必須要考慮數(shù)據(jù)的類型定義、存儲(chǔ)結(jié)構(gòu)、且必須體現(xiàn)數(shù)據(jù)的完整性，以及算法的時(shí)間和空間復(fù)雜度性能，才能更好地體現(xiàn)該課程的價(jià)值。