1.表的合并

顺序表A和B的元素个数分别为m和n，表A升序排列，表B降序排列，连个表中都不存在相同的元素；

1.1最小值法

问题

（1）将两表合并，两表中的元素都储存在表C中；

算法思想

依次取出两表中最小者插入新表中，直到其中一个表的元素都被插入到新表中为止，最后将剩余表中的元素以从小到大的顺序依次追加到新表表尾。

取最小者的方法：升序表中从低索引依次往高索引开始取；降序表中从高索引依次往低索引开始取，取两者中最小值。

代码

void combineSqList(SqList La, SqList Lb, SqList& Lc)
{
    // 初始化Lc
    Lc.length = 0;
    Lc.maxSize = La.maxSize;
    Lc.data = (ElemType*)malloc(sizeof(ElemType) * (La.length + Lb.length));

    int indexLa = 0;    // 指向La的第一个元素
    int indexLb = Lb.length - 1; // 指向Lb的最后一个元素
    while (indexLa < La.length && indexLb >= 0)
    {
        // 表A当前元素较小
        if (La.data[indexLa] < Lb.data[indexLb])
            Lc.data[Lc.length++] = La.data[indexLa++];
        else    // 表B中当前元素最小
            Lc.data[Lc.length++] = Lb.data[indexLb--];
    }
    // 若La中有剩余元素
    while (indexLa < La.length)
    {
        Lc.data[Lc.length++] = La.data[indexLa++];
    }
    // Lb中有剩余元素
    while (indexLb >= 0)
    {
        Lc.data[Lc.length++] = Lb.data[indexLb--];
    }
}

1.2最大值法

问题

（2）表A有m+n个存储空间，将A、B两表合并，所有元素都存储在A中；

算法思想

从A表的表尾开始存放元素。每次从A和B中取出较大的元素插入到A表末尾，重复上述步骤，直到其中一个表中的元素为空，然后将非空表的剩余元素插入到A中。

代码

void combineSqList(SqList& La, SqList Lb)
{
    int curLength = 0;  // 新表的长度
    int indexLa = La.length - 1;// 指向La的最后一个元素
    int indexLb = 0; // 指向Lb的第一个元素
    int LaLength = La.length + Lb.length;
    while (indexLa >= 0 && indexLb < Lb.length)
    {
        // A表当前访问元素最大
        if (La.data[indexLa] > Lb.data[indexLb])
        {
            La.data[LaLength - curLength - 1] = La.data[indexLa];
            curLength++;
            indexLa--;
        }
        else    // 表B中元素最大
        {
            La.data[LaLength - curLength - 1] = Lb.data[indexLb];
            curLength++;
            indexLb++;
        }
    }
    // 若La中有剩余元素
    while (indexLa >= 0)
    {
        La.data[LaLength - curLength - 1] = La.data[indexLa];
        curLength++;
        indexLa--;
    }
    // Lb中有剩余元素
    while (indexLb < Lb.length)
    {
        La.data[LaLength - curLength - 1] = Lb.data[indexLb];
        curLength++;
        indexLb++;
    }
    La.length = La.length + Lb.length;
}

1.3插入排序

问题

（3）表A前r个元素递增有序，而表A中后n-r个元素递减有序，将表A进行升序排列。

算法思想

将L[n-k]到L[n-1] 的元素依次插入到前面的有序序列中。

代码

// k 表示待排序序列的第一个位置（降序序列）
// 注意：k是元素序号，不是数组下标
void insertSort(SqList& L, int k)
{
    int curIndex = k - 1;   // 指向第k个元素
    while (curIndex < L.length)
    {
        ElemType elem = L.data[curIndex];
        int preCurIndex = curIndex - 1; // 指向data[curIndex]的前驱
        // 从前驱结点开始寻找插入位置
        while (preCurIndex >= 0 && L.data[preCurIndex] > elem)
        {
            // 元素后移
            L.data[preCurIndex + 1] = L.data[preCurIndex];
            preCurIndex--;
        }
        // 在前驱元素的后面插入数据
        L.data[preCurIndex + 1] = elem;
        // 指向下一个待插入元素
        curIndex++;
    }
}

2.交集算法

问题

给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解

A\cap B

(共同元素在求解中只出现一次)

分析

两表访问结果为一个非递减序列，那么必然使用较小者法。如果两者相同，则当前访问元素为交集之中的元素。

算法思想

指针indexLa, indexLb分别指向La和Lb的第一个元素，
如果indexLa所指元素小于indexLb所指元素，移动indexLa来访问下一个元素；
反之，则移动indexLb来访问下一个元素；
如果两指针所指元素相等，则发现共有元素，将其保存后再同时移动两个指针；
重复上述步骤，直到一个表的元素都访问完。

代码

// 交集存储在表La中
void intersectionSqList(SqList& La, SqList Lb)
{
    int curLength = 0;  // 交集结果长度
    int indexLa = 0;    //
    int indexLb = 0;    // La, Lb索引
    // 最小值法
    while (indexLa < La.length && indexLb < Lb.length)
    {
        if (La.data[indexLa] < Lb.data[indexLb])
            indexLa++;  // A表小，索引后移
        else if (La.data[indexLa] > Lb.data[indexLb])
            indexLb++;  // B表小，索引后移
        else    // 元素相同
        {
            La.data[curLength] = La.data[indexLa];
            curLength++;    // 更新新表索引
            indexLa++;      // 更新A表索引
            indexLb++;      // 更新B表索引
        }
    }
    La.length = curLength;  // 更新表长
}

补充

若La与Lb不是递增，而是非递减序列，内部存在相同的元素，在元素相同时，判断当前元素与上一个元素是否相同。

else    // 元素相同
{
    if (curLength == 0 || La.data[curLength - 1] != La.data[curLength])
    {
        La.data[curLength] = La.data[indexLa];
        curLength++;    // 更新新表索引
    }
    indexLa++;      // 更新A表索引
    indexLb++;      // 更新B表索引
}

3.差集算法

问题

给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解A-B；

差集：一般地，设A，B是两个集合，由所有属于A且不属于B的元素组成的集合，叫做集合A减集合B(或集合A与集合B之差)。

如：A={1，2，3} ，B={3，4，5} ,A-B={1，2} 。

算法思想

用两个指针indexLa和indexLb分别指向La和Lb的第一个元素；
如果indexLa所指的元素小于indexLb所指元素，当前元素加入差集序列，并将indexLa指向下一个元素；
如果indexLb所指元素小于indexLa所指元素，将指针indexLb指向下一个元素；
如果两个元素相等，则将两个指针同时后移，指向下一个元素；
重复上述步骤，直到其中一个表中元素都被访问完；
若La中仍有待访问元素，将它们加入差集序列。

代码

// 给定两个非空集合A和B，分别用升序顺序表La和Lb存储，
// 设计算法求解A-B；
void exceptSqList(SqList& La, SqList Lb)
{
    int curLength = 0;  // 存储新表的长度
    int indexLa = 0;    // 表La的索引
    int indexLb = 0;    // 表Lb的索引
    while (indexLa < La.length && indexLb < Lb.length)
    {
        // La中当前元素较小
        if (La.data[indexLa] < Lb.data[indexLb])
        {
            // 存入La表头
            La.data[curLength] = La.data[indexLa];
            curLength++;    // 更新新表长度
            indexLa++;      // 指向La下一个元素
        }
        // Lb中当前元素较小
        else if (La.data[indexLa] > Lb.data[indexLb])
        {
            indexLb++;  // 指向Lb的下一个元素
        }
        else    // 若两个元素相同
        {
            indexLa++;  // 指向La下一个元素
            indexLb++;  // 指向Lb的下一个元素
        }
    }
    // 若La还有待访问元素，全部加入差集序列
    while (indexLa < La.length)
    {
        La.data[curLength] = La.data[indexLa];
        curLength++;
        indexLa++;
    }
    // 更新差集表长
    La.length = curLength;
}

4.逆置顺序表

问题

设计算法逆置顺序表L

算法思想

low指针指向最低位元素，high指针指向最高位元素
用low指针从低端开始往高端访问；
high指针从高端开始往低端访问；
同时将对称位置元素互换；
当low≥high时，整个序列将完成逆置。

代码

// 顺序表逆置
void reverseSqList(SqList& L)
{
    int low = 0;
    int high = L.length - 1;
    ElemType tmpElem = 0;
    while (low < high)
    {
        tmpElem = L.data[low];
        L.data[low] = L.data[high];
        L.data[high] = tmpElem;
        low++;
        high--;
    }
}

5.顺序表L循环左移

问题

序列L循环左移r位

算法思想

先将长度为n 的序列L[0 ... n-1] 进行逆置；
再将逆置后的序列L[0 ... n-r-1] 和 L[n-r ... n-1] 分别进行逆置；
获得L循环左移r位后的结果。

代码

void RotateLeftSqList(SqList& L, int r)
{
    // 逆置L
    reverseSqList(L, 0, L.length - 1);
    // 逆置前 n-r 个元素
    reverseSqList(L, 0, L.length - r - 1);
    // 逆置后 r 个元素
    reverseSqList(L, L.length - r, L.length - 1);
}