数据结构习题练习(五)-顺序表六题(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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注