數據結構與演算法：線性表——刪除重覆元素

線性表是一種隨機存取的結構，和鏈表不同，鏈表順序存取的結構。但是，線性表是一種順序存儲的結構，而鏈表是鏈式存儲結構。兩者都是線性的，但區別不同。

進入主題：

1.假如有一串數據元素，要求刪除其中的重覆元素。

首先想到的是用兩層迴圈，第一層從第一個元素開始，第二層從第一層元素的下一個元素開始。

就是假如第一層是a_i元素，則第二層就為a_i+1元素。

函數實現：

void Purge1(ElemType A[],int &n){//ElemType表示任意數據類型，以後不再說明//n為線性表的長度

　　int i=0,j;

　　while(i<n){

　　　　j=i+1;

　　　　while(j<n){

　　　　　　if(A[j]==A[i])

　　　　　　　　Deletelist(A,n,j+1);//具體函數實現最後給出

　　　　　　else

　　　　　　　　j++;

　　　　}

　　　　i++;

　　}

}

2.如果這些元素是按遞增排列，且數據量很大的話，使用上面的演算法就會造成時間上的浪費。

那要怎麼優化呢？

函數實現：

void Purge2(int *A, int &n) {
　　int i = 0, k = 0;//k是重覆的次數
　　for (i = 0; i < n - 1; i++)
　　　　if (A[i] != A[i + 1])
　　　　　　A[i-k+1] = A[i + 1];
　　　　else
　　　　　　k++;
　　n = n - k;
}

經過小規模的測試沒有發現問題。若有有問題可以提出。

經過兩函數的分析，可以看出第一個函數使用的是兩層迴圈，而第二個函數只使用了一層迴圈達到了效果。

避免了不必要的時間浪費。

附上Deletelist函數：

void Deletelist(int *A, int &n, int i) {
　　int j;
　　if (i<1 || i>n)//這條可以無視
　　　　cout << "超出範圍！";
　　for (j = i; j < n; j++)
　　　　A[j - 1] = A[j];
　　n--;
}

碎碎念：本人學生，第一次寫隨筆，也不清楚下次會在什麼時候寫。如果有什麼需要改進的地方，請務必提出來，我在此謝過。