设计并验证一下算法:设顺序表L中的数据元素为整数且非递增有序,删除其值相同的多余元素,即顺序表L中相同的元素只保留一个,并逆置删除后的顺序表L。
(1)根据键盘输入数据建立顺序表L。
(2)输出顺序表L、删除值相同的多余元素后的顺序表L、逆置的顺序表L。
(3)假设顺序表L长度为n,要求以O(n)的时间复杂度完成对值相同多余元素的删除。
实验代码:
#include <stdio.h>
#include <malloc.h>
#define LIST_INIT_SIZE 100
typedef int ElemType;
typedef struct{
ElemType *elem;//存储空间基址
int length; //当前长度
}SqList;
void InitList(SqList *l){ //初始化顺序表
l->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
l->length=0;
}
void CreateList(SqList *l){//创建顺序表
int data,i=0;
scanf("%d",&data);
while(!(data<0)){
l->elem[i++]=data;
l->length++;
scanf("%d",&data);
}
}
void print(SqList list){//打印顺序表
int i=0;
while(i<list.length){
printf("%d ",list.elem[i++]);
}
printf("\n");
}
void distinc(SqList *l){//去除重复元素
int *p,*q,*r=l->length+l->elem;
for(p=l->elem,q=p+1;q<r;q++){
if(*p!=*q){
*(p+1)=*q;
p++;
}else{
l->length--;
}
}
}
void swap(ElemType *a,ElemType *b){//交换两个数
ElemType temp;
temp=*a;
*a=*b;
*b=temp;
}
void reverse(SqList l){//逆置顺序表
int i;
for(i=0;i<l.length/2;i++){
swap(l.elem+i,l.elem+l.length-1-i);
}
}
int main(){
while(1){
SqList L;
InitList(&L);
printf("输入正整数:(负数代表结束输入)\n");
CreateList(&L);
printf("去除重复元素:");
distinc(&L);
print(L);
reverse(L);
printf("反转:");
print(L);
}
return 0;
}
/*
样例输入:
1 2 3 4 4 4 4 4 5 6 7 7 7 8 -1
*/
运行结果: