线性表代码

代码

发布日期: 2020-08-21

更新日期: 2020-08-25

文章字数: 2k

阅读次数:

1.顺序表创建

#define MaxSize 50
typedef struct {          //定义线性表的最大长度
    int data[MaxSize];    //顺序表的元素
    int length;           //顺序表的当前长度
}SqList;                  //顺序表类型定义
SqList L;                 //自行比较整型浮点型等简单数据类型的定义方式

2.顺序表排序（冒泡排序）

void BubbleSort(SqList &L){                 //因为顺序表L将要改变，所以使用引用型。
    for(int i = 0; i< L.length-1;i++){      //i指针指向表头，从0开始，直到顺序表长度减一
        for(int j = L.length-1; j> 1;j--){  //j指针指向表尾，从长度减一开始，直到i指针
            if(L.data[j-1]> L.data[j]){     //如果前一位比后一位大
                int temp = L.data[j-1];     //就把前一位存入临时变量temp中
                L.data[j-1] = L.data[j];    //把j指针的数据赋值给j-1
                L.data[j] = temp;           //再把临时变量中的数据存入j指针中
                                            //最终完成从小到大的排序过程
            }                               //交换数据的三行代码不要省略
        }
    }
}

3.顺序表插入问题（注意插入）：讲元素e插入到顺序表的第i个位置

bool ListInsert(SqList &L, int i, int e){ //因为顺序表L将要改变，所以使用引用型。又定义指针i和元素e
    if(i < 1|| i > L.length + 1)          //验证插入的合法性，只能插入数列的有效位
        return false;
    if(L.length >= MaxSize)               //验证顺序表长度是否超过最大限制
        return false;
    for(int j = L.length; j >= i; j--)    //从最后一位，一次往后移一位，直到要插入的位置
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;                      //把元素e插入第i个位置
    L.length++;                           //最终顺序表长度加1
    return true;
}

4.将元素e插入到递增的顺序表中，并让其仍然有序

bool ListInster(SqList &L, int e){         //顺序表L会改变，所以用引用型。定义整型变量元素e
    int i = 0;                             //初始化指针i，指向顺序表头部
    while(L.data[i] < e && i < L.length){  //从头开始判断顺序表元素与元素e的大小关系，如果指针没有超过
                                           //顺序表长度并且指针所指元素小于元素e
        i++;                               //那么指针i向后移一位
    }
    for(int j = L.length; j > 1; j--){     //定义指针j指向顺序表元素+1的位置，直到i指针的位置停止
        L.data[j] = L.data[j-1];           //依次向后移动
    }
    L.data[i] = e;                         //元素e插入到指针i的位置
    L.length++;                            //顺序表长度加一
    return true;
}

5.顺序表删除

删除顺序表L中第i(1≤i≤L.length)个位置的元素，成功则返回true，并将被删除的元素用引用变量e返回，否则返回false。（这是删除某一位置的元素）

bool ListDelete(SqList &L, int i, int &e){  //顺序表L会发生改变，所以使用引用型
    if(i < 1 || i > L.length){              //判断i位置是否合法
        return false;
    }
    e = L.data[i-1];                        //把要删除的元素赋值给变量e
    for(int j = i; j < L.length, j++){
        L.data[j-1] = L.data[j];            //依次补齐空缺，后一位往前移一位
    }
    L.length--;                             //顺序表长度减一
    return true;
}

删除顺序表L中值为X的元素（这是删除某一值的方式）

bool ListDelete(SqList &L, int X){
    int count = 0;                       //记录有多少个值为X的元素（有可能有相同的元素）
    for(int i = 0; i < L.length; i++){   //从头到尾一次匹配看是否存在元素X
        if(L.data[i] == x){
            count++;                     //有的话计数器就加一
        }else{
            L.data[i-count] = L.data[i]; //没有的话就将后一位依次向前移动，直到再次匹配到或退出
        }
    }
    L.length = L.length - count;         //更新顺序表长度
}

删除顺序表L中所有素数

bool Prime(int num){                     //求素数
    for(int i = 2; i < num; i++){
        if(num % 2 == 0){
            return false;
        }
    }
    return true;
}
void ListDelete(SqList &L, int x){
    int count = 0;                       //计数器
    for(int i = 0; i < L.length; i++){   //从头到尾依次查找
        if(Prime(num)){                  //如果是素数，计数器加一		
            count++;
        }else{
            L.data[i-count] = L.data[i]; //如果没有，则补齐空缺位置
        }
    }
    L.length = L.length - count;         //更新顺序表长度
}

删除顺序表L中最大值（最小值，此处注意与删除奇偶数的区别）

void ListDelete(SqList &L, int x){
    int pos = 0;                              //记录最大值所在位置
    int max = L.data[0];                      //从头开始扫描，把最大的值存入max中
    for(int i = 1; i < L.length; i++){
        if(max < L.data[i]){                  //如果max中的值小于后面的元素
            pos = i;                          //存储最大值的位置
            max = L.data[i];                  //就把比max大的那个值赋予给max
        }
    }
    fot(int j = pos + 1; j < L.length; i++){  //依次把最大值的后一位往前移动，补全空缺
        L.data[j-1] = L.data[j];                
        L.length--;                           //长度减一
    }
}

删除顺序表L中重复的值（表已经有序）

void ListDelete(SqList &L){
    int count = 0;                          //计数器count
    int num = L.data[0];                    //从第一个数开始比较是否有相同的值
    for(int i = 1; i < L.length; i++){      //从头到尾依次扫描
        if(L.data[i] == num){               //如果之后有值与num相等
            count++;                        //计数器加一
        }else{
            num = L.data[i];                //否则，更新num的值
            L.data[i - count] = L.data[i];  //并更新顺序表
        }
    }
    L.length = L.length - count;
}

逆置：将顺序表L中的所有元素逆置过来

void Inversion(SqList &L){
    int low = 0, high = L.length - 1;  //分别两个指针指向首尾
    while(low < high){
        int temp = L.data[low];        //把第一个元素赋值给临时变量temp
        L.data[low] = L.data[high];    //把high的值赋予low
        L.data[high] = temp;           //在把temp中的值赋予给high
        low++;                         //完成一次交换，然后依次交换           
        high--;
    }
}

平台：找出顺序表中最大的平台值（什么是平台值？）

顺序表合并：将两个升序顺序表合并为一个升序的顺序表

i++ 先执行i=0 再进行i=i+1,也就是i会是0,执行完了再变为1
++i 先执行i=i+1,i会是1

SqList Merge(Sqlist L1, Sqlist L2){
    Sqlist L3;
    int i = 0, j = 0, k = 0;
    while(i < L1.length && j < L2.length){  //L1和L2长度要大于0
        if(L1.data[i] < L2.data[j]){        //如果L1的一位比L2的一位小
            L3.data[k++] = L1.data[i++];    //就把L1的一位放入L3中，并且i和k自增1
        }else{                              //如果L1的一位比L2的一位大
            L3.data[k++] = L2.data[j++];    //就把L2的一位放入L3中，并且j和k自增1
        }
    }                                       //当其中一个被放完时，再单独对另一个顺序表操作即可
    while(i < L1.length){
        L3.data[k++] = L1.data[i++];
    }
    while(i < L2.length){
        L3.data[k++] = L2.data[j++];
    }
    L3.length = k;
    return L3;
}

将两个升序顺序表合并为一个升序的顺序表**（只求∩交集）**

SqList Merge(Sqlist L1, Sqlist L2){
    Sqlist L3;
    int i = 0, j = 0, k = 0;
    while(i < L1.length && j < L2.length){  //L1和L2长度要大于0
        if(L1.data[i] < L2.data[j]){        //如果L1的一位比L2的一位小
            i++;                            //i++
        }else if(L1.data[i] > L2.data[j]){  //如果L1的一位比L2的一位大
            j++;                            //j++
        }else{
            L3.data[k++] = L1.data[i++];    //如果L1的一位和L2的一位相等，则放入L3中
            j++;                            //j++
        }
    }                                       
    L3.length = k;
    return L3;
}

将两个升序顺序表合并为一个升序的顺序表**（∪并集，没有重复元素）**

SqList Merge(Sqlist L1, Sqlist L2){
    Sqlist L3;
    int i = 0, j = 0, k = 0;
    while(i < L1.length && j < L2.length){    //L1和L2长度要大于0
        if(L1.data[i] < L2.data[j]){          //如果L1的一位比L2的一位小
            L3.length[k++] = L2.length[i++];  //把L1放入L3，并且i和k自增
        }else if(L1.data[i] > L2.data[j]){    //如果L1的一位比L2的一位大
            L3.length[k++] = L2.length[j++];  //把L2放入L3，并且j和k自增
        }else{
            L3.data[k++] = L1.data[i++];      //如果L1的一位和L2的一位相等，则把L1放入L3中
            j++;                              //j++
        }
    }                                         //当其中一个被放完时，再单独对另一个顺序表操作即可
    while(i < L1.length){
        L3.data[k++] = L1.data[i++];
    }
    while(i < L2.length){
        L3.data[k++] = L2.data[j++];
    }
    L3.length = k;
    return L3;
}