題目
有一個遞增非空順序表，設計一個算法删除元素重複的結點。例如，[1，1，2，3，3，3，4，4，7，7，7，9，9，9]經過删除後變成[1，2，3，4，7，9]。
分析
畫圖分析：
有如下代碼：
/* 删除順序表中的重複元素 */
/* &list指的是要執行删除重複元素操作的順序表 */
void deleteRe(SqlList &list){
for(int i=0;i<list.length-1;i++){
if(list.a[i]==list.a[i+1]){
for(int m=i+1;m<list.length-1;m++){
list.a[m]=list.a[m+1];
}
list.length--;
}
}
}
但是如果遇到連續超過2個的重複元素，就會出現問題：
原因就在于i++，在每次的a[i]與a[i+1]的比較後都會i++，具體如下：
既然這樣，就想了個辦法，就是将産生的結果再遞歸去删除重複元素一次，代碼如下：
/* 删除順序表中的重複元素 */
/* &list指的是要執行删除重複元素操作的順序表 */
void deleteRe(SqlList &list){
for(int i=0;i<list.length-1;i++){
if(list.a[i]==list.a[i+1]){
for(int m=i+1;m<list.length-1;m++){
list.a[m]=list.a[m+1];
}
list.length--;
}
}
// 将結果連結清單再遞歸處理
for(int i=0;i<list.length-1;i++){
if(list.a[i]==list.a[i+1]){
deleteRe(list);
}
}
}
運作代碼結果如下：
對這個代碼還是不太滿意，再進行分析：
代碼如下所示：
/* 删除順序表中的重複元素 */
/* &list指的是要執行删除重複元素操作的順序表 */
void deleteRe(SqlList &list){
int i=0;// 計數器，用來記錄目前數是數組中的第幾個元素，0表示第一個元素
while(i<list.length-1){// 表示循環，即順序表有多少個元素參與判斷，就循環多少次
if(list.a[i]==list.a[i+1]){// 如果順序表的目前元素與下一個元素的值相等
for(int m=i+1;m<list.length-1;m++){ // 删除a[i+1]，就是将a[i+1]後面的所有元素向前移動一個位置
list.a[m]=list.a[m+1];
}
list.length--; // 同時順序表的長度要減1
}else{// 當a[i]!=a[i+1]時，到順序表的下一個元素，再進行判斷a[i]==a[i+1]
i++;
}
}
}
測試結果如下：
本題的完整代碼如下：
#include <stdio.h>
#include <stdlib.h>
#define maxSize 20
typedef struct SqlList {
int a[maxSize];
int length;
} SqlList;
/* 建立順序表 */
void createList(SqlList &L) {
int tempNo = 1;
int tempData = 0;
do {
printf("請輸入順序表第%d個元素：",tempNo);
scanf("%d",&tempData);
if(tempData!=-1) {
L.a[tempNo-1] = tempData;
L.length = tempNo;
tempNo++;
}
} while(tempNo<=maxSize&&tempData!=-1);
}
/* 列印順序表 */
void printSqlList(SqlList list) {
printf("\n");
for(int i=0; i<list.length; i++) {
printf("%d\t",list.a[i]);
}
printf("\n");
}
/* 删除順序表中的重複元素 */
/* &list指的是要執行删除重複元素操作的順序表 */
void deleteRe(SqlList &list){
int i=0;// 計數器，用來記錄目前數是數組中的第幾個元素，0表示第一個元素
while(i<list.length-1){// 表示循環，即順序表有多少個元素參與判斷，就循環多少次
if(list.a[i]==list.a[i+1]){// 如果順序表的目前元素與下一個元素的值相等
for(int m=i+1;m<list.length-1;m++){ // 删除a[i+1]，就是将a[i+1]後面的所有元素向前移動一個位置
list.a[m]=list.a[m+1];
}
list.length--; // 同時順序表的長度要減1
}else{// 當a[i]!=a[i+1]時，到順序表的下一個元素，再進行判斷a[i]==a[i+1]
i++;
}
}
}
int main() {
SqlList list;// 聲明一個順序表
createList(list); // 建立順序表
printSqlList(list);// 列印建立成功的順序表
deleteRe(list);// 删除順序表中的重複元素
printSqlList(list); // 列印删除重複項的順序表
return 0;
}