[已解决]有序表的合并问题

1094570635

/顺序表的存储结构
typedef struct{
    ElemType *elem;
    int length;
}SqList;

//已知顺序有序表 LA 和 LB 的元素按值非递减排列
//归并 LA 和 LB 得到新的顺序有序表 LC, LC 的元素也按值非递减排列
void MergeList_Sq (SqList LA, SqList LB, SqList &LC){
    int m = LA.length, n = LB. length;
    LC.length = m + n;      //新表长度为待合并两表的长度之和

    LC.elem = new ElemType[LC.length];      //为合并后的新表分配一个数组空间
    pc = LC.elem;     //指针 pc 指向新表的第1个元素

    //指针 pa 和 pb 的初值分别指向两个表的第1个元素
    pa = LA.elem;
    pb = LB.elem;

    pa_last = LA.elem + m - 1;    //指针 pa_last 指向 LA 的最后一个元素
    pb_last = LB.elem + n - l;    //指针 pb_last 指向 LB 的最后一个元素

    while((pa <= pa_last) && (pb <= pb_last)){     // LA 和 LB 均未到达表尾
        if(*pa <= *pb) *pc++ = *pa++;     //依次“摘取”两表中值较小的结点插入到 LC 的最后
        else *pc++ = *pb++;
    }

    while(pa <= pa_last) *pc++ = *pa++;    //LB已到达表尾，依次将 LA 的剩余元素插入 LC 的最后
    while(pb <= pb_last) *pc++ = *pb++;    //LA已到达表尾，依次将 LB 的剩余元素插入 LC 的最后

这个代码
如何理解 pa_last = LA.elem + m - 1，我知道p_last是一个指针，指向数组最后一个元素，LA.elem是数组的首地址，为什么首地址后面+ LA.length-1就可以得到最后一个地址。

最佳答案

月排行榜 / 总排行榜

dolly_yos2

2022-10-31 19:25:33

指针加减整数的运算是这样进行的：

When an expression J that has integral type is added to or subtracted from an expression P of pointer type, the result has the type of P.
-- If P evaluates to a null pointer value and J evaluates to 0, the result is a null pointer value.
-- Otherwise, if P points to an array element i of an array object x with n elements(9.3.4.5), the expressions P + J and J + P (where J has the value j) point to the (possibly-hypothetical) array element i + j of x if 0 ≤ i + j ≤ n and the expression P - J points to the (possibly-hypothetical) array element i - j of x if 0 ≤ i - j ≤ n.
-- Otherwise, the behavior is undefined.

这里对应的是第二种情况，也就是当 LA.elem 是数组的首地址，指向数组的第0个元素时，其加上 LA.length-1 后指向的是数组的第 LA.length-1 个元素，也就是最后一个元素（其中 LA.length 是数组的长度）

跳转到最佳答案楼层

dolly_yos2

指针加减整数的运算是这样进行的：

When an expression J that has integral type is added to or subtracted from an expression P of pointer type, the result has the type of P.
-- If P evaluates to a null pointer value and J evaluates to 0, the result is a null pointer value.
-- Otherwise, if P points to an array element i of an array object x with n elements(9.3.4.5), the expressions P + J and J + P (where J has the value j) point to the (possibly-hypothetical) array element i + j of x if 0 ≤ i + j ≤ n and the expression P - J points to the (possibly-hypothetical) array element i - j of x if 0 ≤ i - j ≤ n.
-- Otherwise, the behavior is undefined.

这里对应的是第二种情况，也就是当 LA.elem 是数组的首地址，指向数组的第0个元素时，其加上 LA.length-1 后指向的是数组的第 LA.length-1 个元素，也就是最后一个元素（其中 LA.length 是数组的长度）