一道经典顺序表题目的两种解法

如题 自用笔记 如有错误欢迎及时指正

预期最好性能：遍历顺序表需要O(n)时间复杂度，交换元素需要O(1)时间复杂度

解法一：

从前向后遍历顺序表，遇到非零元素就和当前0元素交换，否则无动作继续检查下一个元素。

void Function1(SqList &L){
    int i=0, j=0;
    int temp;       //缓存
    while(i 
解法二：
 
朴素解法
 
设置计数器counter 记录0元素出现的次数（0元素个数）；
 
从前向后遍历顺序表，遇到非0元素将其向前移动，遇到0元素则将计数器+1；
 
遍历结束后将顺序表后面的length-counter到length范围内的元素（一共counter个）置为0；
 
void Function2(SqList &L){       
    int counter = 0;        //计数器 记录0元素出现次数 个数
    int j = 0;
    int i;          //i负责遍历 j负责保存非0元素的移动位置
    for (i = 0; i < L.length;i++){
        if(L.data[i]!=0){       //非0元素向前移动
            L.data[j++] = L.data[i];        
        }else{
            counter++;      //遇到0元素则增1
        }//if
    }//for
    for (i = L.length - counter; i < L.length;i++){     //后面的元素置0
        L.data[i] = 0;
    }//for
}
 
 
 
 
测试 
 
#include
#include
#include
#define InitSize 5

typedef int ElemType;

//动态分配顺序表

typedef struct{
    ElemType *data;
    int length;
    int MaxSize;
} SqList;

//初始化表
bool InitList_Sq(SqList &L){
    L.data = (ElemType *)malloc(InitSize * sizeof(ElemType));
    L.length = 0;
    L.MaxSize = InitSize;
    return true;
}

//建立顺序表
bool CreateList_Sq(SqList &L){          
        InitList_Sq(L);
        if(L.data==NULL){       
            return false;
        }
        int i;
        ElemType A;
        for (i = 0; i < L.MaxSize; i++){
            scanf("%d",&A);
            L.data[i] = A;
            L.length++;
        }
        return true;
}

//输出
inline void PrintList_Sq(SqList L){
    printf(" 顺序表中的元素如下：");
    for (int i = 0; i < L.length; i++){
        printf("%d ",L.data[i]);
    }
    printf("n");
}

int main(){
    SqList List;    

    CreateList_Sq(List);
     printf("顺序表创建后是：n");
     PrintList_Sq(List);
    //Function1(List);
    //Function2(List);
     PrintList_Sq(List);
     printf("以上为处理后的顺序表n");

    return 0;
}