1.创建一个顺序表

// 本程序为顺序表模版
#include <iostream>
#define MAX_SIZE 100 //确定顺序表总的空间大小为100
typedef int ElemType;
typedef struct sqlist
{
   
    ElemType list[MAX_SIZE];
    int length; //记录表长
}sqlist;

void print_list(sqlist a)
{
   
    for (int i=0; i<a.length; i++) {
   
        printf("%d->",a.list[i]);
    }
}
int main() {
   
    sqlist a;
    a.length=0; //初始化单链表表长为7
    for(int i=0;i<=6;i++)
    {
   
        a.list[i]=i+1;
        a.length++;
    }     //定义一个 1，2，3，4，5，6，7的顺序表

    printf("检查顺序表的第一个元素：%d\n当前顺序表的表长为：%d\n",a.list[0],a.length);
    printf("--------打印读入链表-----------\n");
    print_list(a);printf("\n");
    printf("-----------------------------\n");
    return 1;
}

2.从顺序表中删除第i个元素

void delete_i(sqlist &a,int x)
{
   
    for(int i=x;i<a.length;i++)
    {
   
        a.list[i-1]=a.list[i];
    }
    a.list[a.length-1]=0;//清空最后一个值的数据
    a.length--;
}

3.在第i个元素前插入e

void insert_i(sqlist &a,int x,int e)
{
   
    for(int i=a.length;i>=x;i--)
    {
   
        a.list[i]=a.list[i-1];
    }
    a.list[x-1]=e;
    a.length++;
}

4.从顺序表中删除最小元素，空出的位置由最后一个元素填补

void delete_min(sqlist &a)
{
   
    int min=100000;
    int flag=0;
    for(int i=0;i<a.length;i++)
    {
   
        if(a.list[i]<min)
        {
   
            min=a.list[i];
            flag=i;
        }
    }
    a.list[flag]=a.list[a.length-1];
    a.length--;
}

5.在无序顺序表中删除值在s和t之间的所有元素

void deleteElem(sqlist &a,int s,int t)
{
   
    int curlength=0;//指向表头的指针，同时也记录着新表的长度
    for(int i=0;i<a.length;i++)
    {
   
        if(a.list[i]<s||a.list[i]>t)
        {
   
            a.list[curlength++]=a.list[i];
        }
    }
    a.length=curlength;
}

6.在非递减顺序表中删除值在区间[s,t]的所有元素

从前后找到第一个s，从后往前找到最后一个t，将t后面加入到第一个s前面

//在无序顺序表中删除s和t之间的所有元素
void delete_st(sqlist &a,int s,int t)
{
   
    int first_s=0;
    int last_t=0;
    int curlength1=0; //记录s前新表长度
    int curlength2=0; //记录t后新表长度

    for(int i=0;i<a.length;i++)
    {
   

        if(a.list[i]>=s)
        {
   
            first_s=i;
            break;
        }else curlength1++;

    }

    for(int j=a.length-1;j>=0;j--)
    {
   
        if(a.list[j]<=t)
        {
   
            last_t=j;
            break;
        }else curlength2++;
    }
    for(int i=first_s,j=last_t+1;j<a.length;j++,i++)
    {
   
        a.list[i]=a.list[j];
    }
    a.length=curlength1+curlength2;
    printf("length=%d\n",a.length);
}

7.删除非递减顺序表中的重复元素

思想:新表表尾和旧表元素不同时，加入新表

void delete_repeat(sqlist &a)
{
   
    int curlength=0;
    for(int i=1;i<a.length;i++)
    {
   
        if(a.list[curlength]!=a.list[i])
        {
   
            a.list[++curlength]=a.list[i];
        }
    }
    a.length=curlength+1; //长度=下标+1
}

从第8题开始，存储方式改为动态存储

8.顺序表A和B的元素个数分别为m和n，表A升序，表B降序排序，两个表中都不在相同的元素

关于动态存储顺序表

typedef int ElemType;
typedef struct SqList
{
   
    ElemType *PList;
    int length;
    int listSize;
}SqList;

8.1 将两表合并，两表中的元素存储到表C中(c表保持升序)

void combine(sqList &a,sqlist &b,sqlist &c)
{
   
    c.length=a.length+b.length;
    c.list=(ElemType *)malloc(sizeof(ElemType)*c.length);
    int curlength=0;
    int index_a=0; //指向a第一个元素的指针
    int index_b=b.length-1; //指向b最后一个元素的指针
    while(index_a<a.length&&index_b>=0)
    {
   
        if(a.list[index_a]<b.list[index_b])
        {
   
            //把a加入c
            c.list[curlength++]=a.list[index_a];
            index_a++;
        }else{
   
            //把b加入c
            c.list[curlength++]=b.list[index_b];
            index_b--;
        }
    }
    //把a或b中的剩余元素加入c中
    while(index_a<a.length)
    {
   
        c.list[curlength++]=a.list[index_a];
        index_a++;
    }
    while(index_b>=0)
    {
   
        c.list[curlength++]=b.list[index_b];
        index_b--;
    }
}

8.2 表A前r个元素递增有序，而表A中后n-r个元素递减有序，将表A进行升序排序

一直以最后一个元素为目标，依次的插入进前面的递增序列。不断更新最后一个元素。

void combine_a(sqList &a ,int k)
{
   
            for(int i=0;i<a.length-1;i++)
            {
   
                if(a.list[a.length-1]<=a.list[i])
                {
   
                    int temp=a.list[a.length-1];
                    for(int j=a.length-1;j>i;j--)//包括i在内的所有元素后移
                    {
   
                        a.list[j]=a.list[j-1];
                    }
                    a.list[i]=temp;
                }
            }
}

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

解析:

分别设置两个指针指向两个集合开头，若集合A开头元素小于B集合开头元素，则说明B集合的其他元素都大于A，故A后移一位，反之B后移一位，每当相等的时候，加入交集，同时A和B同时后移一位，直到其中一个表为空时，退出循环。在a表中存储交集

设计样例:
A:1 2 5 7 9 15
B:0 4 5 7 8 9

输出：应为 5 7 9
代码如下:

void jiaoji(sqList &a,sqlist &b)
{
   
    int curlength=0;
    int index_a=0;
    int index_b=0;
    while (index_a<a.length||index_b<b.length) {
   
        if(a.list[index_a]<b.list[index_b])
        {
   
            index_a++;
        }
        else if(a.list[index_a]==b.list[index_b])
        {
   
            a.list[curlength++]=a.list[index_a];
            index_a++;
            index_b++;
        }else{
   
            index_b++;
        }

    }
    a.length=curlength;
}

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

解析:

每次将A小于的元素加入进差集当中
设计样例:
A:1 2 5 7 9 15
B:0 4 5 7 8 9

输出：应为 1 2 15
代码如下:

void chaji(sqList &a,sqlist &b)
{
   
    int curlength=0;
    int index_a=0;
    int index_b=0;
    while (index_a<a.length||index_b<b.length) {
   
        if(a.list[index_a]<b.list[index_b])
        {
   
            a.list[curlength++]=a.list[index_a++];
        }
        else if(a.list[index_a]==b.list[index_b])
        {
   
            index_a++;
            index_b++;
        }else{
   
            index_b++;
        }

    }

    while (index_a<a.length) {
    //如果b短，将a中剩余的元素加入
        a.list[curlength++]=a.list[index_a++];
    }
    a.length=curlength;

}

11.设计算法算法逆置顺序表

void reverse(sqList &a)
{
   
    int low=0;
    int high=a.length-1;
    while (low<high) {
   
        int temp=a.list[low];
        a.list[low++]=a.list[high];
        a.list[high--]=temp;
    }
}

12.将序列L循环左移动

解析:使用三次逆置

void r_reverse(sqList &a,int low,int high)
{
   
    while (low<high) {
   
        int temp=a.list[low];
        a.list[low++]=a.list[high];
        a.list[high--]=temp;
    }
}
void ROL(sqList &a,int r)
{
   
    r_reverse(a,0,r-1);
    r_reverse(a,r,a.length-1);
    r_reverse(a, 0,a.length-1);
}