2.2—线性表的顺序表示

顺序表的实现和基本操作

#include <iostream>
#include <stdio.h>
using namespace std;

// 取地址符的意义:https://blog.csdn.net/u011723466/article/details/27109249
// 没有取地址符,就变化不了实际的值。所以 PrintfList 直接 SqList L。
// 要改变 L ,当 元素 = e, 这时写 f(SqList &L, ElemType e){}
// 要改变 L,当 元素 = e,更改为 x,并读取x,这时写 f(SqList &L, ElemType &e){}
#define MaxSize 50

typedef int ElemType;

// 静态分配,长度就是 MaxSize
typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

// 动态分配,长度见下方的调用
#define InitSize 100    // 表长度的初始定义
typedef struct {
    ElemType *data;
    int MaxSize_1, length;
}SeqList;

// e 插入到 L 中的第 i 个位置
bool ListInsert(SqList &L, int i, ElemType e){
    if(i < 1 || i > L.length + 1){// 判断 i 的范围是否有效
        //!!! 之所以可以在 length + 1插入,是因为:
        //尾部插入一个,顺序表仍然符合:连续性
        printf("插入的位置超出范围!\n");
        return false;
    }    
        
    if(L.length >= MaxSize){// 储存空间已满,不能插入
        printf("存储空间满!\n");
        return false;
    }        
        
    for(int j = L.length; j >= i; j--){    // i 元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;        //位置 i 放入e
    L.length++;            // 线性表长度加1
    
    return true;
}

// 删除 L 中的 第 i 个元素
bool ListDelete(SqList &L, int i, ElemType &e){
    if(i < 1 || i > L.length){
        return false;
    }

    e = L.data[i-1];        // 被删除元素赋给e
    // 因为data是数组,所以 i-1
    for(int j = i; j < L.length; j++){
        L.data[j-1] = L.data[j];    // 元素前移,当前等于后方的元素
    }

    L.length --;    //表长度减1
    return true;
}

// 查找 L 中值为 e 的第一个元素
int LocateElem(SqList L, ElemType e){
    for(int i = 0; i < L.length; i ++){
        if(L.data[i] == e){
            return i+1; // 返回位序为 i + 1
        }
    }
    return 0;
}

void PrintfList(SqList L){
    for(int i = 0; i < L.length; i++){
        printf("%4d\n", L.data[i]);
    }
    printf("\n");
}


int main(void){
    SqList L;
    ElemType del;

    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 3;
    L.data[3] = 4;
    L.length = 5;

    if(ListInsert(L, 2, 10)){
        printf("插入成功!\n");
        PrintfList(L);
    }else{
        printf("插入失败!\n");
    }

    if(ListDelete(L, 2, del)){
        printf("删除成功!\n");
        printf("删除的元素为: %d\n", del);
        PrintfList(L);
    }else{
        printf("删除失败!\n");
    }

    int ret = LocateElem(L, 3);
    if(ret){
        printf("查找成功!\n");
        printf("元素位置为:%d\n", ret);
        PrintfList(L);
    }else{
        printf("查找失败!\n");
    }

    return 0;
}

课后代码题

2.2.3-1

#include <iostream>
#include <stdio.h>
using namespace std;

#define MaxSize 50

typedef int ElemType;

// 静态分配,长度就是 MaxSize
typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

bool Del_Min(SqList &L, ElemType &e){
    // e 为元素值
    if(L.length == 0){
        printf("顺序表为空!\n");
        return false;
    }

    e = L.data[0];
    int e_i = 0;    // 次序码
    for(int i = 0; i < L.length; i++){
        if(L.data[i] < e){
            e = L.data[i];
            e_i = i;
        }
    }

    L.data[e_i] = L.data[e_i + 1];
    L.length --;
    
    return true;
}

void PrintfList(SqList L){
    for(int i = 0; i < L.length; i++){
        printf("%4d\n", L.data[i]);
    }
    printf("\n");
}

int main(void){
    SqList L;
    ElemType del;

    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 3;
    L.data[3] = 4;
    L.data[4] = -5;
    L.length = 5;

    int ret = Del_Min(L, del);
    if(ret){
        printf("删除的最小元素为:%d\n", del);
        PrintfList(L);
    }else{
        printf("操作失败!\n");
    }
    return 0;
}

2.2.3-2

/**
 * 翻转线性表,空间复杂度为1
 */
#include <iostream>
#include <stdio.h>
using namespace std;
#define MaxSize 50
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

void PrintfList(SqList L){
    for(int i = 0; i < L.length; i++){
        printf("%4d", L.data[i]);
    }
    printf("\n");
}

void ReverseList(SqList &L){

    // 自己实现,空间复杂度为 L 的长度,其实没必要
    // SqList L2 = L;
    // for(int i = 0; i < L.length / 2; i++){
    //     L.data[i] = L.data[L.length - i -1];
    // }

    // for(int j = 0; j < L2.length / 2; j++){
    //     L.data[L.length - j -1] = L2.data[j];
    // }
    
    // 答案写法,提前记录再放到后面,只用一个缓冲区
    ElemType temp; 
    for(int i = 0; i < L.length / 2; i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length - i -1];
        L.data[L.length - i -1] = temp;
    }
    
}

int main(void){
    SqList L;
    ElemType del;

    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 3;
    L.data[3] = 4;
    L.data[4] = 5;
    L.length = 5;

    PrintfList(L);
    ReverseList(L);
    PrintfList(L);

    return 0;
}

2.2.3-3

/**
 * 删除线性表中所有值为 x 的数据元素。时间复杂度O(n),空间复杂度O(1)
 */
#include <iostream>
#include <stdio.h>
using namespace std;

#define MaxSize 50
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

void PrintfList(SqList L){
    for(int i = 0; i < L.length; i++){
        printf("%4d", L.data[i]);
    }
    printf("\n");
}

void Delete_Elem_x(SqList &L, ElemType e){

    // 方法1, 不等于 e 的元素放入新数组
    int k = 0; //不相同元素的个数
    for(int i = 0; i < L.length; i++){
        if(L.data[i] != e){
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
    
    // 方法2
    // int k = 0; // 相同元素个数
    // for(int i = 0; i < L.length; i++){
    //     if(L.data[i] == e){
    //         k ++;
    //     }else {
    //         L.data[i - k] = L.data[i]; // 元素前移
    //     }
    // }
    // L.length = L.length - k;
}


int main(void){
    SqList L;
    ElemType del;

    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 2;
    L.data[3] = 4;
    L.data[4] = 5;
    L.length = 5;

    PrintfList(L);
    Delete_Elem_x(L, 2);
    PrintfList(L);

    return 0;
}

2.2.3-4,5

/**
 * 删除线性表中所有值为 s 到 t 的数据元素。
 */
#include <iostream>
#include <stdio.h>
using namespace std;

#define MaxSize 50
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

void PrintfList(SqList L){
    for(int i = 0; i < L.length; i++){
        printf("%4d", L.data[i]);
    }
    printf("\n");
}

bool Delete_between(SqList &L, ElemType s, ElemType t){
    
    // 我的做法
    if(!(s < t) && L.length == 0){
        return false;
    }
    int k = 0;
    for(int i = 0; i < L.length; i++){
        if(L.data[i] < s || L.data[i] > t){
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
    return true;
}

int main(void){
    SqList L;
    ElemType del;

    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 2;
    L.data[3] = 4;
    L.data[4] = 5;
    L.length = 5;

    PrintfList(L);
    Delete_between(L, 2, 4);
    PrintfList(L);

    return 0;
}

2.2.3-6

/**
 * 删除线性表中重复的数据元素。
 */
#include <iostream>
#include <stdio.h>
using namespace std;

#define MaxSize 50
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

void PrintfList(SqList L){
    for(int i = 0; i < L.length; i++){
        printf("%4d", L.data[i]);
    }
    printf("\n");
}

bool Delete_repetition(SqList &L){

    if(L.length == 0){
        return false;
    }

    int k = 0;
    for(int i = 0; i < L.length; i ++){
        if(L.data[i] != L.data[i + 1]){
            L.data[k] = L.data[i];
            k++;
            // 高级写法 L.data[k++] = L.data[i];
        }
    }

    L.length = k; // 虽然 K 起始于 0,表示下标,通常总长度要k+1,但最后执行了++
    return true;
}

int main(void){
    SqList L;
    ElemType del;

    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 2;
    L.data[3] = 2;
    L.data[4] = 5;
    L.data[5] = 5;
    L.length = 6;

    PrintfList(L);
    Delete_repetition(L);
    PrintfList(L);

    return 0;
}

2.2.3-7

/**
 * 两个有序顺序表合并成一个顺序表。
 */
#include <iostream>
#include <stdio.h>
using namespace std;

#define MaxSize 50
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

void PrintfList(SqList L){
    for(int i = 0; i < L.length; i++){
        printf("%4d", L.data[i]);
    }
    printf("\n");
}

// 标准答案,经典算法,应该记住。两个有序表连接成新的有序表
bool Connect_List2(SqList &L1, SqList &L2, SqList &LBig){
    if(L1.length + L2.length > LBig.length){
        return false;
    }

    int i = 0, j = 0, s = 0;
    while(i < L1.length && j < L2.length){
        if(L1.data[i] < L2.data[j]){
            LBig.data[s++] = L1.data[i++];
        }else{
            LBig.data[s++] = L2.data[j++];
        }
    }

    while(i < L1.length){
        LBig.data[s++] = L1.data[i++];
    }

    while(j < L2.length){
        LBig.data[s++] = L2.data[j++];
    }

    LBig.length = s;

    return true;
}

bool Connect_List(SqList &L1, SqList &L2, SqList &LBig){
    // 第一个答案,错误,没有考虑到“有序”,不能简单做连接工作
    // for(int i = 0; i < L1.length; i++){
    //     LBig.data[i] = L1.data[i];
    // }

    // for(int j = 0; j < L2.length; j++){
    //     LBig.data[L1.length + j] = L2.data[j];
    // }

    // 改良版,外层循环,再内层循环,将小的存入新表
    int t = 0; // L2表的次序码
    int s = 0; // 总表的次序码
    for(int i = 0; i < L1.length; i++){
        while(t < L2.length){
            if(L1.data[i] <= L2.data[t]){
                LBig.data[s++] = L1.data[i];
                break; // 取到 L1 中的值,必须要break L2的 while
            }
            else{
                LBig.data[s++] = L2.data[t];
                t++;
            }
        }
    }

    if(t < L2.length){ // 防止 L1 循环完,L2 直接 break, 使 L2 中的值丢失。
        for(int j = t; j < L2.length; j++){ // 取 break 之后的 t, L2.data[t] ~ L2.data[L2.length]
            LBig.data[s++] = L2.data[j];
        }
    }

    // 简化流行的写法,while直接做判断和循环,见标准答案
    // int j = t;
    // while(t < L2.length){
    //     LBig.data[s++] = L2.data[j++];
    // }

    LBig.length = s;

    return true;
}



int main(void){
    SqList L1;
    SqList L2;
    SqList LBig;
    ElemType del;

    L1.data[0] = 1;
    L1.data[1] = 3;
    L1.data[2] = 5;
    L1.length = 3;

    L2.data[0] = 2;
    L2.data[1] = 4;
    L2.data[2] = 6;
    L2.data[3] = 8;
    L2.length = 4;

    LBig.length = 7;

    PrintfList(L1);
    PrintfList(L2);
    PrintfList(LBig);

    Connect_List(L1, L2, LBig);

    PrintfList(L1);
    PrintfList(L2);
    PrintfList(LBig);

    return 0;
}

2.2.3-8

/**
 * 数组中两个线性表,编写函数实现两个线性表位置调换
 */
#include <iostream>
#include <stdio.h>

using namespace std;

#define MaxSize 50
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

void PrintfList(SqList L){
    for (int i = 0; i < L.length; i++){
        printf("%4d\n", L.data[i]);
    }
    printf("\n");
}

int main(void){
    SqList L;
    ElemType del;

    L.data[0] = 1;
    L.data[1] = 3;
    L.data[2] = 5;
    L.length = 3;
    
    PrintfList(L);

    return 0;
}

2.2.3-9

/**
 * 数组中两个线性表,编写函数实现两个线性表位置调换
 */
#include <iostream>
#include <stdio.h>

using namespace std;

#define MaxSize 50
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList;

void PrintfList(SqList L){
    for (int i = 0; i < L.length; i++){
        printf("%4d\n", L.data[i]);
    }
    printf("\n");
}

// 经典算法,折半查找
int Binary_Search(SqList L, ElemType x){

    int low = 0, high = L.length - 1, mid;

    while (low <= high){
        mid = (low + high) / 2;

        if (L.data[mid] == x){
            return mid;
        } else if(x < L.data[mid]){
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

int SearchExchangeInsert(SqList &L, ElemType x){
    int low = 0, high = L.length, mid;

    while (low <= high){
        mid = (low + high) / 2;

        if (L.data[mid] == x){
            int temp = L.data[mid];
            L.data[mid] = L.data[mid + 1];
            L.data[mid + 1] = temp;
            return 1; // 替换操作

        } else if (x < L.data[mid]){
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    
    //全部折半完无匹配
    if (low > high){
        // low 即最后一次折半所在的地方
        for(int i = L.length; i > low - 1; i--){
            L.data[i] = L.data[i - 1];
        }
        printf("%d,%d,%d\n", mid, low, high);
        L.data[high + 1] = x;
        L.length++;

        return 2; // 插入操作
    }

    return -1;
}

int main(void){
    SqList L;
    ElemType del;

    L.data[0] = 11;
    L.data[1] = 22;
    L.data[2] = 33;
    L.data[3] = 35;
    L.data[4] = 55;
    L.data[5] = 66;
    L.data[6] = 77;
    L.length = 7;
    
    PrintfList(L);
    printf("%d\n", SearchExchangeInsert(L, 34)); 
    PrintfList(L);

    return 0;
}

本文链接:https://ariser.cn/index.php/archives/100/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!