题目

有一个递增非空顺序表，设计一个算法删除元素重复的结点。例如，[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;
}