数据结构顺序线性表操作集合

ゝ一世哀愁。 2022-02-21 00:39 367阅读 0赞

# 线性表有顺序表和链式表，下面是顺序表各操作实现 #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int dataType;
    #define MAXSIZE 50
    
    typedef struct { 
        dataType data[MAXSIZE];
        int last; //值等于数组中最后一个元素的下标，可指示数组长度
    } SqList;
    
    //初始化一个线性表
    SqList *initSqList()
    { 
        SqList *L;
        int n, i;
    
        L = (SqList *)malloc(sizeof(SqList));
        printf("请输入存储的元素个数：");
        scanf("%d", &n);
        L->last = n - 1;
    
        printf("请依次输入要存储的元素：");
        for (i = 0; i < n; i++) { 
            int element;
            scanf("%d", &element);
            L->data[i] = element;
        }
    
        return L;
    }
    
    //向表位置i处插入一个类型为dataType的元素x
    int insertSqList(SqList *L, int i, dataType x)
    { 
        int j;
    
        if (L->last == MAXSIZE - 1) { 
            printf("表满！\n");
            return -1;
        }
        if (i < 1 || i > L->last + 1) { 
            printf("位置错误！\n");
            return -1;
        }
        for (j = L->last; j >= i - 1; j--)
            L->data[j + 1] = L->data[j];
    
        L->data[i - 1] = x;
        L->last++;
    
        return 1;
    }
    
    //删除表中第i个元素
    int deleteSqList(SqList *L, int i)
    { 
        int j;
    
        if (i < 1 || i > L->last + 1) { 
            printf("不存在第i个元素！\n");
            return -1;
        }
        for (j = i; j <= L->last; j++)
            L->data[j - 1] = L->data[j];
    
        L->last--;
    
        return 1;
    }
    
    //查找表中值为x的元素；若存在，则返回存储位置
    int LocationSqList(SqList *L, dataType x)
    { 
        int i = 0;
    
        while (i <= L->last && L->data[i] != x)
            i++;
        if (i > L->last)
            return -1;
        else
            return i;
    }
    
    //输出表中元素个数
    void lengthSqList(SqList *L) {  printf("表中元素个数为：%d\n", L->last + 1); }
    //打印表中元素
    int printSqList(SqList *L)
    { 
        if (L->last == -1) { 
            printf("表中元素为空！");
            return -1;
        }
        else { 
            int i;
    
            printf("表中元素为: ");
            for (i = 0; i <= L->last; i++)
                printf("%d ", L->data[i]);
            printf("\n");
            return 1;
        }
    }
    
    //将表置空
    void clearSqList(SqList *L)
    { 
        if (L->last + 1 >= 1)
            L->last = -1;
        printf("顺序表已被清空！\n");
    }
    
    //销毁顺序表
    void destroySqList(SqList *L)
    { 
        if (!L)
            printf("顺序表不存在！\n");
        else { 
            free(L);
            printf("顺序表已被销毁！\n");
        }
    }
    
    /* * 以表中元素L->data[0]（a1）为界将表中元素划分为两部分,a1前的元素都小于a1， * a1后的元素都大于a1，从a1后的元素向后遍历表，若当前元素大于a1，则不移动； * 否则将当前元素前面的元素全部后移 */
    void partition(SqList *L)
    { 
        int i, j;
        dataType x, y;
    
        x = L->data[0];
        for (i = 1; i <= L->last; i++)
            //若当前元素小于x，将当前元素前面的元素全部后移
            if (L->data[i] < x) { 
                y = L->data[i];
                for (j = i - 1; j >= 0; j--)
                    L->data[j + 1] = L->data[j];
                L->data[0] = y;
            }
    }
    
    //有升序排列表A、B，将两表合并为表C（升序）
    void merge(SqList *A, SqList *B, SqList *C)
    { 
        int i, j, k;
    
        i = j = k = 0;
        while (i <= A->last && j <= B->last) { 
            if (A->data[i] < B->data[j])
                C->data[k++] = A->data[i++];
            else
                C->data[k++] = B->data[j++];
        }
        while (i <= A->last)
            C->data[k++] = A->data[i++];
        while (j <= B->last)
            C->data[k++] = B->data[j++];
    
        C->last = k - 1;
    }
    
    /* * 有表A、B，AS、BS分别为其除去最大共同前缀的子表 * 例：A = (x, x, j, c, n, u),B = (x, x, j, k, n, u) * 最大共同前缀：x, x, j * AS：c, n, u * BS：k, n, u * * AS = BS = 空表，相等； * AS != BS != 空表 * 或 AS = 空表&&BS != 空表 * 或 AS != 空表 && BS != 空表， * 但AS[0] < BS[0],则AS < BS，否则AS > BS * AS = BS，返回0 * AS > BS，返回1 * AS < BS，返回-1 */
    int compareAS_BS(SqList *A, SqList *B)
    { 
        int i = 0, j;
        int ms = 0, ns = 0;
        dataType AS[MAXSIZE], BS[MAXSIZE];
    
        while (A->data[i] == B->data[i])
            i++;
        for (j = i; j <= A->last; j++) { 
            AS[j - i] = A->data[i];
            ms++; // AS长度
        }
        for (j = i; j <= B->last; j++) { 
            BS[j - i] = B->data[i];
            ns++; // BS长度
        }
    
        if (ms == ns && ms == 0)
            printf("AS = BS\n");
        else if ((ms == 0 && ns > 0) || (ms > 0 && ns > 0 && AS[0] < BS[0]))
            printf("AS < BS\n");
        else
            printf("AS > BS\n");
    }
    int main()
    { 
        SqList *L;
        L = initSqList(); //初始化表L
    
        printSqList(L);
        lengthSqList(L);
    
        insertSqList(L, 3, 100);
        deleteSqList(L, 1);
        printSqList(L);
    
        partition(L);
        printSqList(L);
    
        clearSqList(L);
        printf("%p\n", L);
        destroySqList(L);
    
        return 0;
    }
    
    // int main()
    //{ 
    // SqList *L, *A, *B;
    //
    // L = initSqList();//初始化表L
    // int index = LocationSqList(L, 100);
    // if (index != -1)
    // printf("%d\n", index);
    // else printf("元素不存在！\n");
    //
    // partition(L);
    // printSqList(L);
    // clearSqList(L);
    //
    // A = initSqList();
    // printSqList(A);
    //
    // B = initSqList();
    // printSqList(B);
    //
    // compareAS_BS(A, B);
    //
    // merge(A, B, L);
    // printSqList(L);
    //
    // return 0;
    //}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220221/e37527232aff4cb896306fb82389e399.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220221/03dffe3334e94dfea40852837b16bb56.png