说明

• 本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
• 请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
• 由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。

2.27 假设两个元素依值递增有序排列的线性表A和B

分别表示两个集合，
且同一表中可能存在值相同的元素，
现要求构成一个线性表C，
利用A表空间存放表C，
其元素为A和B中元素的交集，
且表C中的元素也依值递增有序排列，
要求新生成的表C中的元素值各不相同。
试对线性表编写求C的算法。

解1

不应该先删除表A和表B中多余的值相同的元素，
应采用“下标平行移动，一次扫描完成”的策略，
只要进一步考虑，和表B中结点值相同的表A的结点值，
是否和表C中当前最后一个结点的值相同，
如果算法成功，是不需要对表C中的元素执行去重操作的：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10#define MAX_TEST_LENGTH 8
#define MAX_TEST_ELEM 5
typedef int ElemType;
typedef struct{ElemType *elem; // 存储空间基址int length; // 当前长度int listsize; // 当前分配的存储容量
} SqList; // 顺序表类型
typedef struct LNode{ElemType data;struct LNode *next;
} LNode, *LinkList; // 线性链表类型Status InitList_Sq(SqList *pL){// 构造一个空的线性表(*pL).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!(*pL).elem) exit(OVERFLOW); // 存储分配失败(*pL).length = 0; // 空表长度为0(*pL).listsize = LIST_INIT_SIZE; // 初始存储容量return OK;
}// InitList_SqStatus ListInsert_Sq(SqList *pL, int i, ElemType e){// 在顺序线性表L中第i个位置之前插入新的元素e// i的合法值范围：[1,ListLength_Sq(L)+1]if(i<1 || i>((*pL).length+1)) return ERROR; // i值不合法if((*pL).length>=(*pL).listsize){ // 当前存储空间已满，增加分配ElemType *newbase = (ElemType *)realloc((*pL).elem,((*pL).listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase) exit(OVERFLOW); // 存储分配失败(*pL).elem = newbase; // 新基址(*pL).listsize += LISTINCREMENT; // 增加存储容量}ElemType *p = NULL;ElemType *q = &((*pL).elem[i-1]); // q为插入位置for(p=&((*pL).elem[(*pL).length-1]);p>=q;--p) *(p+1) = *p; // 插入位置及之后的元素右移*q = e; // 插入e++((*pL).length); // 表长增1return OK;
}// ListInsert_SqStatus FreeList_Sq(SqList *pL){// 释放线性表if(NULL!=(*pL).elem){free((*pL).elem);return OK;}else{return ERROR;}
}// FreeList_Sqint InsertOrderSqList(SqList *pL,int x){//把x插入递增有序表pL中，并返回插入的位置（数组下标）int i;if((*pL).length+1>(*pL).listsize) return OVERFLOW;(*pL).length++;for(i=(*pL).length-1;(*pL).elem[i]>x&&i>=0;i--)(*pL).elem[i+1]=(*pL).elem[i];(*pL).elem[i+1]=x;return i+1;
}//InsertOrderSqList int cmp(const void *x,const void *y){// qsort函数需要调用的比较函数ElemType *a=(ElemType *)x; ElemType *b=(ElemType *)y;return (*a-*b);
}void display_list(SqList L){int i;for(i=1;i<=L.length;i++){printf("[%d]=%d\t",i-1,L.elem[i-1]);if(i%7==0) putchar('\n');}
}void intersect_sqlist(SqList *pA,SqList B,SqList **ppC){//未去重且元素递增排列的线性表A和B中元素交集合并存入无重复元素的C中，//C利用A的空间存储，且仍保持有序//因为线性表是顺序存储的，而为了利用A空间，C又不能拷贝A中元素//所以，C只能作为A的一个别名，传入的pC必须为SqList类型的空指针ElemType b_cur_same_v;int i,j,k,d,c_len,a_next_n_c,b_cur_idx,b_next_diff_idx;i=j=k=c_len=b_cur_idx=a_next_n_c=0;while(i<pA->length&&b_cur_idx<=B.length){//两表探索的边界有差异//首先每次大循环需要对A进行前期去重k=i;for(j=i+1;(j<pA->length)&&(pA->elem[j]==pA->elem[i]);j++);if(j>i+1){d=j-i-1; //d只能在这个局部使用while(j<pA->length) pA->elem[++k]=pA->elem[j++];pA->length -= d;}if(i==0){b_cur_same_v=B.elem[b_cur_idx];b_next_diff_idx=b_cur_idx+1;while(b_next_diff_idx<B.length&&B.elem[b_next_diff_idx]==b_cur_same_v) b_next_diff_idx++;b_cur_idx=b_next_diff_idx;}while(b_cur_idx<B.length&&b_cur_same_v<pA->elem[i]){b_cur_same_v=B.elem[b_cur_idx];b_next_diff_idx=b_cur_idx+1;while(b_next_diff_idx<B.length&&B.elem[b_next_diff_idx]==b_cur_same_v) b_next_diff_idx++;b_cur_idx=b_next_diff_idx;}	if(b_cur_same_v==pA->elem[i]){for(j=i;j<pA->length;j++) pA->elem[j-a_next_n_c]=pA->elem[j];pA->length-=a_next_n_c;i=i-a_next_n_c+1; //下标回退并且加1a_next_n_c=0;c_len++;}else{a_next_n_c++;i++;}}pA->length=c_len;(*ppC)=pA;
}void sorted_list_to_set(SqList *pL){//在顺序线性表中去除重复元素，成为集合int i,j,k,d;for(i=0;i<pL->length;i++){k=i;for(j=i+1;(j<pL->length)&&(pL->elem[j]==pL->elem[i]);j++);if(j>i+1){d=j-i-1;while(j<pL->length){pL->elem[++k]=pL->elem[j++];}pL->length -= d;}}
}Status create_sorted_sqlists(SqList *pA, SqList *pB){int i;//int A[22]={1,4,5,5,5,5,5,5,5,5,5,10,10,10,10,10,11,11,16,18,18,18};//int B[28]={0,0,0,0,0,5,5,5,5,5,5,9,9,9,9,9,9,9,11,11,11,11,11,11,17,17,17,17};//A先超限表示已遍历完，B先超限还有一个没考察完//int A[4]={13,13,13,13};//int B[10]={4,4,7,11,11,11,13,13,13,13};//int A[10]={4,4,7,11,11,11,13,13,13,13};//int B[4]={13,13,13,13};int A[10]={4,4,4,4,5,5,5,5,5,5};int B[6]={5,10,10,13,17,17};for(i=0;i<10;i++){pA->elem[i] = A[i];}pA->length=10;printf("\nA:\n");display_list(*pA);for(i=0;i<6;i++){pB->elem[i] = B[i];}pB->length=6;printf("\nB:\n");display_list(*pB);return OK;
}Status rand_create_sorted_sqlists(SqList *pA, SqList *pB){int dupli_rand_count,dupli_rand_num;time_t t;int count;srand((unsigned)time(&t)); //初始化随机数发生器count = rand()%MAX_TEST_LENGTH;while(count--){dupli_rand_count=rand()%10;dupli_rand_num=rand()%MAX_TEST_ELEM;while(dupli_rand_count--){if(OK!=ListInsert_Sq(pA,1+rand()%((*pA).length+1),dupli_rand_num))return ERROR; // 随机找一个合法位置插入新随机元素}}qsort((*pA).elem,(*pA).length,sizeof(ElemType),cmp);printf("\nA:\n");display_list(*pA);count = rand()%MAX_TEST_LENGTH;while(count--){dupli_rand_count=rand()%10;dupli_rand_num=rand()%MAX_TEST_ELEM;while(dupli_rand_count--){if(OK!=ListInsert_Sq(pB,1+rand()%((*pB).length+1),dupli_rand_num))return ERROR; // 随机找一个合法位置插入新随机元素}}qsort((*pB).elem,(*pB).length,sizeof(ElemType),cmp);printf("\nB:\n");display_list(*pB);return OK;
}int main(){SqList La,Lb;SqList *pC; //由于题目指出需要利用A空间存结果，所以直接让指针指向，相对于La不需初始化和销毁if(OK!=InitList_Sq(&La)) return ERROR;if(OK!=InitList_Sq(&Lb)) return ERROR;//if(OK!=create_sorted_sqlists(&La,&Lb)) return ERROR;if(OK!=rand_create_sorted_sqlists(&La,&Lb)) return ERROR;intersect_sqlist(&La,Lb,&pC);printf("\nC:\n");display_list(*pC); //pC作为一个别名，只有这么一点用if(OK==FreeList_Sq(&La))printf("\nFree SqList A success!\n");if(OK==FreeList_Sq(&Lb))printf("\nFree SqList B success!\n");return 0;
}

算法粗略思想如下：
首先有去重地定位A中最新元素
此后查找B中元素
若B下标对应当前值和A最新去重值不同
假设B的现阶段值是连续重复的
还要记录B当前值后在B中往后继续比较寻找到下一个不同值的下标
如果B的这些可能重复且还没有移动到下一个的值比A最新去重值小
那就让B的最新下标增加到其下一个值的最初位置
此时A的下标可以不变
B的每次下标移动都需记录对应新初值且寻找下一个不同的
相当于B有一个值记录和一个不同值的新下标记录
直到B的移动到其值记录大于等于A的最新去重值如果是大于即不相等则B后面更大且不等
得知A的最新去重值不属于交集
此时本应该立即将A中后缀全移动一个位置覆盖前面成为新表
其实不然
可以让A的前期去重下标移动不仅记录目前首个已确定非交集元素下标
还需继续往后重复以上步骤直到发现新的元素相等的情况
这样才能以最新相等的交集元素为首
将其后缀全部替代非交集的那一部分
这个替代过程的关键是只能将A的用来记录交集个数的最新表长加一
也就是不管后面还有什么整个搬动替代只能让交集个数加一
由于pA的原表长用来同步去重和遍历
还需要增加一个变量专门记录pC将会得到的交集个数以结束之后赋予它所指向的表A
为了验证这个算法的缺陷，经历了足够但还不充分的测试

解2

其实该算法并没有上面想象的那么复杂：

void sqlist_intersect(SqList *pA,SqList B,SqList **ppC){//求元素递增排列的线性表A和B的元素的交集并存回A中int i,j,k;i=j=0;k=-1;while(i<pA->length&&j<B.length){if(pA->elem[i]<B.elem[j]) i++;else if(pA->elem[i]>B.elem[j]) j++;else{if((k>-1&&pA->elem[i]!=pA->elem[k])||k==-1)pA->elem[++k]=pA->elem[i];i++;j++;}}pA->length=k+1;(*ppC)=pA;
}