有序表的合并问题
/顺序表的存储结构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; //为合并后的新表分配一个数组空间
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:26 编辑
指针加减整数的运算是这样进行的：
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 是数组的长度）
页:
[1]