数据结构习题练习（五）-顺序表六题(C)

数据结构习题练习这里的代码进行了测试，但不排除依然有bug，如果出现bug，麻烦评论提出，谢谢。
题图这么不一致，真是有点不好意思。

题目来自2022王道408的数据结构考研复习指导。
有的题目我改了改，不完全一致。

对长度为n的顺序表，删除其值为x的元素，要求时间复杂度O(n)，空间复杂度O(1)

//返回顺序表新长度
int deleteX(int* nums, int x, int numsSize){
    int k = 0;
    int pos;
    for(pos = 0;    pos + k<numsSize; pos++){
        nums[pos] = nums[pos + k];
        if(nums[pos] == x){
            k++;
            pos--;
            continue;
        }
    } 
    return numsSize - k;
}

删除顺序表中值在[s, t]之间的元素，并对不合理的调用进行出错提示，时间复杂度O(n)，空间复杂度O(1)

//返回顺序表新长度
int deleteBetweenSandT(int* nums, int s, int t, int numsSize){
    if(s >= t || numsSize == 0){
        puts("error call with deleteBetweenSandT");
        return -1; 
    }
    int k = 0;
    int pos;
    for(pos = 0;    pos + k < numsSize; pos++){
        nums[pos] = nums[pos + k];
        if(nums[pos] <= t && nums[pos] >= s){
            k++;
            pos--;
            continue;
        }
    } 
    return numsSize - k;
}

删除有序顺序表中相同的元素，时间复杂度O(n)，空间复杂度O(1)

//返回顺序表新长度
int deleteSame(int* nums, int numsSize){
    int k = 0;
    int pos;
    for(pos = 0;    pos + k<numsSize; pos++){
        nums[pos] = nums[pos + k];
        if(nums[pos] == nums[pos + k + 1]){
            k++;
            pos--;
            continue;
        }
    } 
    return numsSize - k;
}

将两个有序数组合并成新的有序数组，其中，顺序可以是升序也可以是降序

• 之前好像发过类似的题，不过那个只能升序排升序，
• 这个我改了下，数组升序降序都行，用参数控制，合并成升序降序都行。

int* mergeArray(int* nums1, int nums1Size, int* nums2, int nums2Size, int isAscending){
    //isAscending非0时，以升序合并数组，为0时，以降序合并。
    if(isAscending) isAscending = 1;
    else isAscending = -1;
    int pos1, pos2, posResult, nums1Ascending, nums2Ascending;
    pos1 = pos2 = posResult = 0;
    nums1Ascending = nums2Ascending = 1;    //numsAscending为1时表示nums以升序排列，为-1则是降序。
    int* resultArray = malloc(sizeof(int) * (nums1Size + nums2Size));
    if((nums1[0] - nums1[nums1Size - 1]) * isAscending >= 0){
        nums1Ascending = -1;
        pos1 = nums1Size - 1;
    }
    if((nums2[0] - nums2[nums2Size - 2]) * isAscending >= 0) {
        nums2Ascending = -1;
        pos2 = nums2Size - 1;
    }

    for(posResult = 0;  posResult < nums1Size + nums2Size;   posResult++){
        if(pos1 == nums1Size || pos1 == -1){
            for(;   pos2 < nums2Size && pos2 >= 0;    pos2 += nums2Ascending, posResult++)
                resultArray[posResult] = nums2[pos2];
            return resultArray;
        }
        else if(pos2 == nums2Size || pos2 == -1){
            for(;   pos1 < nums1Size && pos1 >= 0;    pos1 += nums1Ascending, posResult++)
                resultArray[posResult] = nums1[pos1];
            return resultArray;
        }
        else if((nums1[pos1] - nums2[pos2]) * isAscending <= 0){
            resultArray[posResult] = nums1[pos1];
            pos1 += nums1Ascending;
        }
        else if((nums1[pos1] - nums2[pos2]) * isAscending > 0){
            resultArray[posResult] = nums2[pos2];
            pos2 += nums2Ascending;
        }
    }
    return resultArray;
}

将数组A[m + n]中前m个位置的元素与后n个元素的交换

• 因为用到了realloc，所以传参的nums数组只能是malloc分配的数组，不能是int nums[]的数组。
• 这段代码感觉还是挺有意思的，不是用新数组来，而是将原来的数组指针向后移动。

int* switchArray(int* nums, int m, int n){
    int pos;
    nums = realloc(nums, (n + m + m) * sizeof(int));
    for(pos = n + m;    pos < n + m + m; pos++){
        nums[pos] = nums[pos - n - m];
    }
    return &nums[m];
}

将数组内元素向左偏移p位

• 即下面的下标转换：
  • 0, 1, 2, 3, 4, ...., n
  • p, p+1, ..., n-1, 0, 1, ... p-1

int* moveLeft(int* nums, int numsSize, int p){
    int pos;
    int* result = malloc(sizeof(int) * numsSize);
    for(pos = 0;    pos < numsSize - p;  pos++){
        result[pos] = nums[p + pos];
    }
    for(;   pos  < numsSize; pos++){
        result[pos] = nums[p - numsSize + pos];
    }
    return result;
}