【趣学C语言和数据结构100例】
问题描述
66.已知递增有序的单链表 A，B，C分别存储了一个集合，设计算法实现 A=AU(B-C)，要求单链表仍然有序。
67.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
68.已知在一维数组 A[m+n]中依次存放两个线性表(a1,a2,a3,…,am)和(b1,b2,b3.…,bn)。编写一个函数,将数组中两个顺序表的位置互换,即将(b1,b2,b3.…,bn)放在(a1,a2,a3,…,am)的前面。
69.给定三个序列 A、B、C，长度均为 n，且均为无重复元素的递增序列，请设计一个时|上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如，数组 A为{1.2.3]，数组 B为{2.3,4]，数组C为{-1,0.2}，则输出 2
70.已知线性表按顺序存储，且每个元素都是不相同的整型元素，设计把所有的奇数移动至偶数前面的算法。
代码分析
66.有序的单链表 A，B，C->A=AU(B-C)
思路：先实现B-C，并保存在B中，然后AUB。
具体分析：传入3个链表，返回链表，对ABC都操作，则函数名为：LiukList 函数名(LiukList &A,LiukList &B,LiukList &C)；
1.先实现B-C，定义pre记录B的p所到的位置，使p和分别指向B和C，两个使用while循环遍历，使他们两个值小的进行移动，到值相等。在相等时，使pre即此刻的p的前一个指向p的下一个，即跳过p,并且释放p,令p更新为现在的pre的下一个。
2.然后AUB,p和q指向A和B的头部开始，定义r作为辅助记录A的前一个，两个使用while循环遍历，如果p的值小，r更新为p，并且使用尾插法将q插入，并且更新r的位置到p,使p向后移动继续比较。如果q的值小，r更新为q，并且使用将q插入，并且更新r的位置到q,使q向后移动继续比较。直到结束，返回链表A。
67.两个有序顺序表->新的有序顺序表
//顺序表的数据结构
typedef struct {DataType *data; // 数据数组int length; // 当前长度int capacity; // 容量
} SeqList;
分析：合并成功返回1，合并失败返回0。输入3个顺序表，AB用来参数，C用来记录合并后的数据。故函数名为：bool 函数名(SeqList A,SeqList B,SeqList C);如果A+B的长度>C的长度，则直接返回false,定义i,j,k,i为访问A，j为访问B，k为访问C,在不到最后时，使A.data[i]和B.data[j]小的存在C中，并且对应的k++和i++。在比较结束后，使i<长度，或j<长度,的把剩下的存入C中。返回1即可。
68.将数组中两个顺序表的位置互换
思路：先整体反转，再b1到bn反转，使a1到am反转。
具体分析：传入一个数组A[],以及n和m,还有数组的大小。先反转0到m+n-1反转,然后0到n-1反转,然后n到m+n-1反转,故一个调用。everse(A,0,m+n-1,m+n); everse(A,0,n-1,n); everse(A,n,m+n-1,m);接下来写 everse函数。输入函数A，以及左右边值，还有大小。故函数名为void everse(DataType A[],int left,int right,int arrsize)，如果左<0 或者 左>右 或者 右>数组大小，即出现失误，则返回return 0。当左<右时，进行左右值的交换，并且令左++，右–，即可完成交换。
69.输出同时存在于这三个序列 A、B、C中的共同元素
分析：传入abc3个数组和数组的大小n,故函数名为void func(int a[],int b[],int c[],int n)，定义i,j,k分别访问3个数组，当3个都<n时开始访问。如果3个的值相等，则输出a中的值，否则查找。先找到3个中最大的数，再<它的后进行++，直到找到3个的值相等时进行输出。
70.线性表把所有的奇数移动至偶数前面
分析：采用双指针，即左右同时，定义一个high和low，初始化为length-1和0。使用temp记录第一个的值，使用while循环遍历，再 low < high情况子下， 找到偶数: high 指针向左移动，直到找到一个奇数。把这个奇数的值给了low的奇数。从low开始，找到奇数: low 指针向右移动，直到找到一个偶数。把这个偶数的值给了high的偶数。重复: 重复步骤 1-3，直到 low 和 high 指针相遇。最后再把之前的temp的值还回去。
代码实现
#include<stdio.h>
int main(){
// 66.已知递增有序的单链表 A，B，C分别存储了一个集合，设计算法实现 A=AU(B-C)，要求单链表仍然有序。
Linklist fun(Linklist &A,Linklist &B,Linklist &C){//B-CLnode *pre=B,*p=B->next,*q=C->next;while(p && q){if(p->data<q->data){pre=p;p=p->next}
