一道算法設計題的解析

黃詩佳，熊啟軍

（湖北文理學院計算機工程學院，襄陽441053）

0 引言

在《數據結構與算法》中，主要學習使用兩種存儲結構（順序存儲和鏈式存儲）來實現問題所涉及數據的類型定義、增刪改查等基本操作。線性表是基本的數據結構，是學習樹、圖、散列表，以及查找和排序等知識的基礎。學好線性表則給學習其他知識打下了堅實的基礎。一道算法設計題，使用不同的存儲結構，其實現算法可能不同；即使是使用同一種存儲結構，其實現算法也可能不同。

1 問題描述

待求解的問題是這樣的：輸入若干個正整數（輸入負數或0 結束），將其中出現次數大于等于3 的數據有序輸出。

這道題主要涉及數據的存儲、排序、計數、輸出等。

2 順序存儲結構實現

2.1 整型數組實現

使用一個整型數組作為存儲結構，進行數據的讀取、排序、計數、輸出。其算法描述如下：

（1）聲明一個整型數組a[MaxLength]；

（2）輸入若干個正整數a[i]，當輸入負數或0 結束；計數實際元素的個數len；

（3）編寫函數sort（int a[],int len）實現遞增排序；

（4）編寫函數output（int a[],int len）實現統計并輸出出現次數大于等于3 的元素。

在這個算法中，第四步是最重要的，其實現算法主要有如下兩種。

2.1.1 順序式計數所謂順序式計數，即是針對排序后的序列，對每個元素出現的次數進行統計。算法如下：

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

當然while 循環的循環體也可以改寫成下面的形式：

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

對于C 語言學習者來說，掌握上述方法是基本要求；而數據結構的初學者來說則是最低要求了。

2.1.2 跳躍式計數

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

顯然，跳躍式計數的效率更高一些。上述算法，對于C 語言學習者來說則屬于較高要求。

2.2 結構體數組實現

將數據的值和它出現的次數組織成結構體，所有元素組織成結構體數組。若仍使用2.1.1 中的方法進行排序和計數，則效率很低；若采取邊輸入邊進行插入排序、同時實現計數操作的方式實現，則可以少用一個數組，從而提高存儲空間的使用效率。

2.2.1 結點數據類型定義

2.2.2 算法描述

下面的函數實現將x 插入到已排好序的序列之中、同時完成計數。

上述兩種方法3 種方式的解答辦法具有共同的特點：都使用順序存儲結構，空間復雜度是相同的；時間復雜度總體上與使用的排序方法的時間復雜度一致，計數方法上有順序和跳躍式兩種、后者效率略高。

上述算法對于數據結構學習者來說則是基本要求。

3 鏈式存儲結構實現

3.1 數據類型定義

將數據的類型組織成值、次數、指針三個數據項構成結構體，所有數據組織成鏈表。每個結點的數據類型具體描述如下：

其中，data 表示輸入的整型值；count 表示某值出現的次數；next 表示下一結點的地址。

3.2 算法描述

功能的實現由4 個函數構成，分別是鏈表初始化函數、集排序計數于一體的函數、輸出結果函數、主函數。具體算法如下。

（1）鏈表初始化函數

上述函數的功能是建立一個含頭結點的初始化鏈表。

（2）集排序計數于一體的函數

這個函數實現將值為x 的正整數插入到一個遞增有序的鏈表之中，同時實現計數操作。

（3）輸出函數

（4）主函數

由于使用鏈式存儲結構，所以排序只能使用直接插入排序，其時間復雜度是O（n^2）；在空間復雜度上，由于無需考慮數據存儲時初始空間的大小。因此，與順序存儲結構比較，優勢比較明顯。

上述算法對于數據結構學習者來說則是必備技能。

4 結語

這道算法設計題，能檢驗對線性表中順序存儲、鏈式存儲以及操作的理解和應用能力。《數據結構與算法》是計算機專業的核心基礎課程，是計算機程序設計的重要理論和實踐基礎，是研究生考試的必考科目。對于算法設計題，必須要考慮數據的類型定義、存儲結構、且必須體現數據的完整性，以及算法的時間和空間復雜度性能，才能更好地體現該課程的價值。