[数组和广义表](6)题集_2

这章节的题目难度超出我的想象,我尽力把所有题目的题解整理出来,却卡到了离散数学上,我是废物

18、试设计一个算法,将数组An中的元素A[0]至A[n-1]循环右移k位,并要求只要一个元素大小的附加存储,元素移动或交换次数为O(n)

这题解法很多,我一开始也是想着如滚动数组一样的思维,从第i个分量起,循环右移k位,顶掉(j+k)%n,但是在某种特殊情况下,这种算法是不可行的

后来请教了大佬,得出以下思路:

img

先看下一个nums数组右移3位后,思路如下:

  • 先将前numSzie-k反转,再将后k位反转
  • 最后再整体反转

我们来证明下这算法的正确型,假设nums=[1,2,3,4,5,6],图解如下:

img

时间复杂度为O(n),空间上也只用了常量级别的两个指针,为O(1)

代码实现如下所示:

#define _CRT_SECURE_NO_WARNINGS

#define OK 1
#define ERRROR -1
typedef int Status;
#include<stdio.h>
#include<stdlib.h>

Status PrintNums(int*, int);
int main()
{
    int nums[6] = { 1,2,3,4,5,6 };
    int numsSize = 6;
    int k = 0;
    printf("请输入循环右移次数:");
    scanf("%d", &k);
    if (k % numsSize == 0)
    {
        PrintNums(nums, numsSize);
        return OK;
    }

    //反转前numSize-k位
    for (int i = 0, j = numsSize - (k % numsSize)-1; i < j; i++, j--)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    //反转后k位
    for (int i = k - 1, j = numsSize - 10; i < j; i++, j--)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    for (int i = 0, j = numsSize - 1; i < j; i++, j--)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    PrintNums(nums, numsSize);
    return OK;
}
Status PrintNums(int* nums, int numsSize)
{
    int i = 0;
    while (i < numsSize)
    {
        printf("%d", nums[i]);
        i++;
    }
    return OK;
}

19、若矩阵A(m*n)中的某个元素a(i,j)是第i行中的最小值,同时又是第j列中的最大值,则称此元素为该矩阵中的一个马鞍点,假设以二维数组存储矩阵A(m*n),试编写出求矩阵中所有马鞍点的算法,并分析算法在最坏情况下的时间复杂度

这题怎么说呢,我想了很久,想优化算法, 但是都想不出来,最坏情况下可达到m*n,一个矩阵里可能会有多个马鞍点,这些马鞍点的值必定相等,但是值想等的值不一定是马鞍点,所以要将每个元素全部判断一遍。

若优化的话反而代码会异常乱。

img

#define _CRT_SECURE_NO_WARNINGS
#define MAXMATRIXCOL 5
#define MAXMATRIXROW 5
#define ERROR -1
#define OK 0
#define TRUE 1
#define FALSE 0
typedef int Bool;
typedef int Status;

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct Coor
{
    int x, y;
    int Elem;
}Coor;

typedef struct CoorA
{
    Coor A[MAXMATRIXCOL * MAXMATRIXROW];
    int tu;
};

Status PrintMatrix(int** Matrix);
Status InputMatrix(int** Matrix);
Bool MaxColElem(int** Matrix, int col, int row);
Status MinAndMax(int** Matrix, CoorA *A);
Status PrintMinAndMax(CoorA A);
int main()
{
    CoorA A;
    
    /*创建*/
    int** Matrix = (int**)malloc(sizeof(int*) * MAXMATRIXROW);
    for (int i = 0; i < MAXMATRIXROW; i++)
    {
        *(Matrix + i) = (int*)malloc(sizeof(int) * MAXMATRIXCOL);
        if (!(Matrix + i))
            exit(ERROR);
        memset(*(Matrix + i), 0, sizeof(int) * MAXMATRIXCOL);
    }


    InputMatrix(Matrix);
    PrintMatrix(Matrix);

    MinAndMax(Matrix, &A);
    PrintMinAndMax(A);
    return 0;
}

Status PrintMatrix(int** Matrix)
{
    for (int i = 0; i < MAXMATRIXROW; i++)
    {
        for (int j = 0; j < MAXMATRIXCOL; j++)
        {
            printf("%d ", *(*(Matrix + i) + j));
        }
        printf("\n");
    }
    return OK;
}

Status InputMatrix(int** Matrix)
{
    for (int i = 0; i < MAXMATRIXROW; i++)
    {
        for (int j = 0; j < MAXMATRIXCOL; j++)
        {
            printf("请输入Matrix[%d][%d]:", i, j);
            scanf("%d", Matrix[i] + j);
        }
    }
    return OK;
}

Bool MaxColElem(int** Matrix, int col, int row)
{
    for (int i = (col + 1) % MAXMATRIXCOL; i != col; i=(i+1)%MAXMATRIXCOL)
    {
        if (Matrix[row][i] > Matrix[row][col])
            return FALSE;
    }
    return TRUE;
}

Bool MinRowElem(int** Matrix ,int col, int row)
{
    for (int i = (row + 1) % MAXMATRIXROW; i != row; i = (i + 1) % MAXMATRIXROW)
    {
        if (Matrix[i][col] < Matrix[row][col])
            return FALSE;
    }
    return TRUE;
}

Status MinAndMax(int** Matrix,CoorA* A)
{
    int p = 0;
    (*A).tu = 0;
    for (int i = 0; i < MAXMATRIXROW; i++)
    {
        for (int j = 0; j < MAXMATRIXCOL; j++)
        {
            if (MinRowElem(Matrix, i, j) && MaxColElem(Matrix, i, j))
            {
                (*A).A[p].x = i;
                (*A).A[p].y = j;
                (*A).A[p].Elem = Matrix[i][j];
                p++;
                (*A).tu++;
            }
        }
    }
    return OK;
}
Status PrintMinAndMax(CoorA A)
{
    for (int i = 0; i < A.tu; i++)
    {
        printf("%d,%d,%d\n", A.A[i].x, A.A[i].y, A.A[i].Elem);
    }
    return OK;
}

21、假设稀疏矩阵A和B均以三元组顺序表作为存储结构,试写出矩阵相加的算法,另设三元组表C存放结果矩阵。

这题四星的难度可能就是考虑输入三元组为无序的情况下,那么在输入三元组的时候我们需要进行一个排序,算法如下所示:

#define _CRT_SECURE_NO_WARNINGS

#define MAXMATRIXSIZE 12500
#define ERROR -1
#define OK 1;
#include<stdio.h>
#include<stdlib.h>

typedef int Status;
typedef int ElemType;
typedef struct
{
    int x, y;
    ElemType e;
}Elem;

typedef struct
{
    Elem data[MAXMATRIXSIZE];
    int mu, nu, tu;
}TSMatrix;

Status CreateTSMatrix(TSMatrix*);
Status PrintTSMatrix(TSMatrix T);
Status Add_toTSMatrix(TSMatrix A, TSMatrix B, TSMatrix* C);
int main()
{

    TSMatrix A, B, C;
    printf("Please Create TSMatrix A\n");
    CreateTSMatrix(&A);
    printf("Please Create TSMatrix B\n");
    CreateTSMatrix(&B);
    Add_toTSMatrix(A, B, &C);
    
    system("pause");
    return OK;
}


/*创建矩阵*/
Status CreateTSMatrix(TSMatrix* T)
{
    printf("Please input Matrix 'row、col and non-Zeros: ");
    scanf("%d,%d,%d", &T->mu, &T->nu, &T->tu);
    if (T->mu * T->nu > MAXMATRIXSIZE || T->tu > T->mu * T->nu)
        return ERROR;

    int row, col, elem, total = -1;
    for (int i = 0; i < T->tu; i++)
    {
        printf("Input Row、Col and Elem:");
        scanf("%d,%d,%d", &row, &col, &elem);
        if (i == 0)
        {
            T->data[i].x = row; T->data[i].y = col; T->data[i].e = elem;
            total++;
        }
        else
        {
            int i = total;
            for (; i >= 0; i--)
                if (T->data[i].x <= row)
                    break;

            for (; T->data[i].x == row && T->data[i].y > col; i--);

                for (int j = total; j > i; j--)
                {
                    T->data[j + 1].x = T->data[j].x;
                    T->data[j + 1].y = T->data[j].y;
                    T->data[j + 1].e = T->data[j].e;
                }
                T->data[i+1].e = elem;
                T->data[i+1].x = row;
                T->data[i+1].y = col;
                total++;
        }
    }
    PrintTSMatrix(*T);
    return OK;
}

Status Add_toTSMatrix(TSMatrix A, TSMatrix B,TSMatrix *C)
{
    if (A.mu != B.mu || A.nu != B.nu)
    {
        printf("两矩阵不能相加");
        exit(ERROR);
    }
    C->mu = A.mu; C->nu = A.nu; C->tu;
    int pa = 0, pb = 0, pc = 0;

    while(pa<A.tu&&pb<B.tu)
    {
        if (A.data[pa].x == B.data[pb].x)//行相等
        {
            if (A.data[pa].y == B.data[pb].y)
            {
                if (A.data[pa].e + B.data[pb].e != 0)
                {
                    C->data[pc].x = A.data[pa].x;
                    C->data[pc].y = A.data[pa].y;
                    C->data[pc].e = A.data[pa].e + B.data[pb].e;
                    pc++;
                }
                pa++; pb++;
            }
            else if (A.data[pa].y < B.data[pb].y)
            {
                C->data[pc].x = A.data[pa].x; C->data[pc].y = A.data[pa].y; C->data[pc].e = A.data[pa].e;
                pc++; pa++;
            }
            else
            {
                C->data[pc].x = B.data[pb].x; C->data[pc].y = B.data[pb].y; C->data[pc].e = B.data[pb].e;
                pc++; pb++;
            }
        }
        else if (A.data[pa].x < B.data[pb].x)//A行要小于B行
        {
            C->data[pc].x = A.data[pa].x; C->data[pc].y = A.data[pa].y; C->data[pc].e = A.data[pa].e;
            pc++; pa++;
        }
        else//大于
        {
            C->data[pc].x = B.data[pb].x; C->data[pc].y = B.data[pb].y; C->data[pc].e = B.data[pb].e;
            pc++; pb++;
        }
    }
    C->tu = pc;
    printf("\n相加后为:\n");
    PrintTSMatrix(*C);
    return OK;
}

Status PrintTSMatrix(TSMatrix T)
{
    for (int i = 0; i < T.tu; i++)
    {
        printf("%d,%d,%d\n", T.data[i].x, T.data[i].y, T.data[i].e);
    }
    return OK;
}

对应上述代码,结合矩阵相加特性,主要要考虑的是以下几点:

  • A和B需要是按行顺序存储(若用户不是按行输入,则需要考虑排序问题 )
  • A的行和列与B的行和列想等的时候,进行相加

    • 若A的行和B的行相等,而列不等的时候,则列小的在前面
  • 若行不等的时候,则行小的在前面

相加算法的时间复杂度为O(B.tu+A.tu)

22、假设稀疏矩阵A和B均以三元组顺序表作为存储结构,试写出满足以下条件的矩阵相加的算法:假设三元组A的空间足够大,将矩阵B加到矩阵A上,不增加A和B之外的附加空间,要求达到O(m+n)的时间复杂度

这题和上题类同,A的空间足够大,则可以将A的元素复制到尾部,腾出空间来对A和B进行相加处理,利用上一题的归并思想,移动指针来进行操作,不考虑复制和清除操作,时间复杂度可以达到O(m+n),代码如下所示:

Status AddTsmatrix(TSMatrix* A, TSMatrix* B)
{
//以行数为主序用归并法进行合并,行列相同的即相加,移动B指针
    if (A->mu != B->mu && A->nu != B->nu)
        return ERROR;
    DrawMatrix(A);
    int pa = MATRIXMAXSIZE - A->tu;
    int pb = 0, pc = 0;
    while (pa < MATRIXMAXSIZE && pb < B->tu)
    {

        if (A->Data[pa].x == B->Data[pb].x)
        {
            if (A->Data[pa].y == B->Data[pb].y)
            {
                if (A->Data[pa].e + B->Data[pb].e != 0)
                {
                    A->Data[pc].x = A->Data[pa].x;
                    A->Data[pc].y = A->Data[pa].y;
                    A->Data[pc].e = A->Data[pa].e + B->Data[pb].e;
                    pa++; pc++; pb++;
                }
            }
            else if (A->Data[pa].y < B->Data[pb].y)
            {
                A->Data[pc].x = A->Data[pa].x;
                A->Data[pc].y = A->Data[pa].y;
                A->Data[pc].e = A->Data[pa].e;
                pa++; pc++;
            }
            else
            {
                A->Data[pc].x = B->Data[pb].x;
                A->Data[pc].y = B->Data[pb].y;
                A->Data[pc].e = B->Data[pb].e;
                pb++; pc++;
            }
        }
        else if (A->Data[pa].x < B->Data[pb].x)
        {
            A->Data[pc].x = A->Data[pa].x;
            A->Data[pc].y = A->Data[pa].y;
            A->Data[pc].e = A->Data[pa].e;
            pa++; pc++;
        }
        else
        {
            A->Data[pc].x = B->Data[pb].x;
            A->Data[pc].y = B->Data[pb].y;
            A->Data[pc].e = B->Data[pb].e;
            pb++; pc++;
        }
    }
    if (pb < B->tu)
    {
        while (pb < B->tu)
        {
            A->Data[pc].x = B->Data[pb].x;
            A->Data[pc].y = B->Data[pb].y;
            A->Data[pc].e = B->Data[pb].e;
            pc++, pb++;
        }
    }
    else
    {
        while (pa < MATRIXMAXSIZE)
        {
            A->Data[pc].x = A->Data[pa].x;
            A->Data[pc].y = A->Data[pa].y;
            A->Data[pc].e = A->Data[pa].e;
            pc++, pa++;
        }
    }
    CleanMatrix(A);
    A->tu = pc;
    return OK;
}
Status DrawMatrix(TSMatrix* A)
{
    for (int i = 0, j = MATRIXMAXSIZE - A->tu; i < A->tu; i++,j++)//将矩阵A复制一份到尾端,让前端提供足够的空间出来
    {
        A->Data[j] = A->Data[i];
    }
    return OK;
}
Status CleanMatrix(TSMatrix* A)
{
    for (int i = MATRIXMAXSIZE - A->tu; i < MATRIXMAXSIZE; i++)
    {
        A->Data[i].e = 0;
        A->Data[i].x = 0;
        A->Data[i].y = 0;
    }
    return OK;
}//清除复制的空间

23、三元组顺序表的一种变型是,从三元组顺序表中去掉行下标域得到二元组顺序表,另设一个行起始向量,其每个分量是二元组顺序表的一个下标值,指示该行中第一个非零元素在二元组顺序表中的起始位置,试编写一个算法,由矩阵元素的下标值i,j求矩阵元素,试讨论这种方法和三元组顺序表相比有什么优缺点

这题我们在学习的时候学习过行逻辑链接的顺序表,和这题的知识点对应,我们只需要从rpos(行向量表)中查询与给定行在三元组中对应的位置和它下一个非零元的起始位置,在这个范围内查找是否有与j相等的值,若有,则返回它的元素值,若没有,则表示该下标对应的为零元素

测试代码如下所示:

#define _CRT_SECURE_NO_WARNINGS
#define MATRIXMAXSIZE 12500
#define OK 1
#define ERROR -1

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int Status;
typedef struct
{
    int y, elem;
}Triple;
typedef struct
{
    Triple data[MATRIXMAXSIZE];
    int* rpos;
    int mu, nu, tu;
}RLSMatrix;

Status CreateRLSMatrix(RLSMatrix* T);//创建
Status FoundElem(RLSMatrix* T, int i, int j);
int main()
{
    int i, j;
    RLSMatrix T;
    CreateRLSMatrix(&T);
    printf("请输入要查询的i和j:"); 
    scanf("%d,%d", &i, &j);
    FoundElem(&T, i, j);
    system("pause");
    return 0;
}

Status CreateRLSMatrix(RLSMatrix* T)
{
    printf("请输入矩阵的行、列、非零元个数:");
    scanf("%d,%d,%d", &T->mu, &T->nu, &T->tu);

    if (T->mu * T->nu > MATRIXMAXSIZE || T->tu > T->mu * T->nu)
        return ERROR;
    
    T->rpos = (int*)malloc(sizeof(int) * T->mu);

    memset(T->rpos, -1, sizeof(int) * T->mu);

    int i = 0;
    int row = 0, col, elem, rowp = -1;
    int total = 0;

    while (i < T->tu)
    {
        printf("请输入行、列、和元素值:");
        scanf("%d,%d,%d", &row, &col, &elem);
        if (rowp != row) T->rpos[row] = total;
        rowp = row;
        T->data[i].y = col;
        T->data[i].elem = elem;
        total++;
        i++;
    }

    for (int i = 0; i < T->mu; i++)
    {
        if (T->rpos[i] != -1)
        printf("%d,%d\n", i, T->rpos[i]);
    }
    return OK;
}
Status FoundElem(RLSMatrix* T, int i, int j)
//给定i和j的坐标值,输出对应的元素值
{
    int k;
    if (i >= T->mu || j >= T->nu)//给定下标越界
        return ERROR;
    if (T->rpos[i] + 1)//当给定下标在行逻辑中有元素的话
    {
        for (k = i + 1; k < T->mu && T->rpos[k] == -1; k++);//计算下一个在行逻辑中有元素的值
    }
    else
    {
        printf("该下标位置为0元素\n");
        return ERROR;
    }
    for (int p = T->rpos[i]; p < T->rpos[k]; p++)
    {
        if (T->data[p].y == j)//在这个范围内查询是否满足于j相等的值
        {
            printf("该位置非零元为:%d", T->data[p].elem);
            return OK;
        }
    }
    printf("该下标位置为0元素\n");
    return ERROR;
}

24、三元组顺序表的另一种变型是,不存在矩阵元素的行、列下标,而存非零元在矩阵中以行为主序时排列的顺序号,及在LOC(0,0)=1,l=1时,按LOC公式计算出的值,试写一算法,由矩阵元素的下标值i,j求元素的值

这题就是求出给定下标对应的元素之前有多少个元素,然后将这个值存入一个一维数组中即可,对应知识点是给定一个起始地址,用给定的下标计算该元素的位置

测试代码如下:

#define _CRT_SECURE_NO_WARNINGS


#define MAXMATRIXSIZE 1250
#define ERROR -1
#define OK 0
typedef int Status;
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
    int* Data;
    int* DataLoc;
    int mu, nu, tu;//行、列、非零元个数
}LMatrix;


Status InitLMatrix(LMatrix* T);//初始化三元组变种
Status LoactionElem(LMatrix* T, int i, int j);
int main()
{
    LMatrix T;
    InitLMatrix(&T);
    int i, j;
    printf("请输入i,j:");
    scanf("%d,%d", &i, &j);
    LoactionElem(&T, i, j);

    system("pause");
    return 0;
}
Status InitLMatrix(LMatrix *T)
{
    printf("Please input row、col and ElemNumber:");
    scanf("%d,%d,%d", &T->mu, &T->nu, &T->tu);
    if (T->mu * T->nu > MAXMATRIXSIZE || T->tu > T->mu * T->nu)
        return ERROR;
    

    T->Data = (int*)malloc(sizeof(int) * T->tu);
    T->DataLoc = (int*)malloc(sizeof(int) * T->tu);
    memset(T->DataLoc, -1, sizeof(int) * T->tu);


    int i = 0, row, col, val;
    while (i < T->tu)
    {
        printf("Please input row、col、val:");
        scanf("%d,%d,%d", &row, &col, &val);
        if (row > T->mu || col > T->nu)
            return ERROR;
        T->DataLoc[i] = row * T->nu + col;
        T->Data[i] = val;

        i++;
    }

    return OK;
}
Status LoactionElem(LMatrix* T, int i, int j)
{
    int Loc = i * T->nu + j, val = 0;
    for (int i = 0; i < T->tu; i++)
        if (T->DataLoc[i] == Loc) {
            val = T->Data[i]; break;
        }

    printf("该下标元素值为:%d", val);
    return OK;
}

25、若将稀疏矩阵A的非零元素以行序为主序的顺序存于一位数组V中,并用二维数组B表示A中的相应元素是否为零元素(以0和1分别表示零元素和非零元素),例如:

img

试写一算法:实现在上述表示法中实现矩阵的相加的运算,并分析你的算法的时间复杂度

这题算法也就是移动指针来进行加减运算,若两个矩阵中同行同列的值都为1的话,就代表可以运算,按行读取也就是V中存放的顺序是逐行存放的,我们将B加A的结果存放到C中的话,测试代码如下所示:

#define _CRT_SECURE_NO_WARNINGS

typedef int Status;
#define ERROR -1
#define OK 0;
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
    int** B;//二维数组,存放0和1
    int* V;//一纬数组,存放非零元素
    int mu, nu, tu;//行列和值
}TSMatrix;

Status CreateTSMatrix(TSMatrix* T);//创建一个三元组变种
Status Add_toTSMatrix(TSMatrix* C, TSMatrix, TSMatrix);//相加
Status PrintTSMatrix(TSMatrix T);
int main()
{
    TSMatrix A, B, C;
    printf("请创建A:\n");
    CreateTSMatrix(&A);
    PrintTSMatrix(A);
    printf("请创建B:\n");
    CreateTSMatrix(&B);
    PrintTSMatrix(B);

    //算法
    printf("\n");
    Add_toTSMatrix(&C, A, B);
    PrintTSMatrix(C);

    system("pause");
    return 0;
}
Status CreateTSMatrix(TSMatrix* T)
{
    printf("请输入矩阵的行、列、非零元个数:");
    scanf("%d,%d,%d", &T->mu, &T->nu, &T->tu);
    if (T->tu > T->mu * T->nu)
        return ERROR;
    T->V = (int*)malloc(sizeof(int) * T->tu);
    T->B = (int**)malloc(sizeof(int) * T->mu);

    for (int k = 0; k < T->mu; k++)
    {
        *(T->B + k) = (int*)malloc(sizeof(int) * T->nu);
        memset(*(T->B+k), 0, sizeof(int) * T->nu);
    }
    int i = 0 ,row, col,elem;
    while (i < T->tu)
    {
        printf("请输入矩阵的行、列和值:");
        scanf("%d,%d,%d", &row, &col, &elem);
        if (row > T->mu || col > T->nu)
            return ERROR;
        *(*(T->B + row) + col) = elem;
        i++;
    }
    int p = 0;
    for (int i = 0; i < T->mu; i++)
    {
        for (int j = 0; j < T->nu; j++)
        {
            if (*(*(T->B + i) + j) != 0)
            {
                T->V[p] = *(*(T->B + i) + j);
                *(*(T->B + i) + j) = 1;
                p++;
            }
        }
    }

    return OK;
}
Status PrintTSMatrix(TSMatrix T)
{

    for (int i = 0; i < T.mu; i++)
    {
        for (int j = 0; j < T.nu; j++)
        {
            printf("%d", *(*(T.B + i) + j));
        }
        printf("\n");
    }

    printf("\n");
    for (int i = 0; i < T.tu; i++)
    {
        printf("%d ", T.V[i]);
    }

    return OK;
}
Status Add_toTSMatrix(TSMatrix* C, TSMatrix A, TSMatrix B)
{
    if (A.mu != B.mu || A.nu != B.nu)
        return ERROR;

    int pa = 0, pb = 0, pc = 0;
    C->B = (int**)malloc(sizeof(int*) * A.mu);
    for (int k = 0; k < A.nu; k++)
    {
        *(C->B + k) = (int*)malloc(sizeof(int) * A.nu);
        memset(*(C->B + k), 0, sizeof(int) * A.nu);
    }
    C->V = (int*)malloc(sizeof(int) * (A.tu + B.tu));
    for (int i = 0; i < A.mu; i++)
    {
        for (int j = 0; j < B.nu; j++)
        {
            if (B.B[i][j]&& A.B[i][j])
            {
                C->B[i][j] = 1;
                C->V[pc] = A.V[pa] + B.V[pb];
                pc++; pa++; pb++;
            }
            else if (B.B[i][j])
            {
                C->B[i][j] = 1;
                C->V[pc] = B.V[pb];
                pc++; pb++;
            }
            else if (A.B[i][j])
            {
                C->B[i][j] = 1;
                C->V[pc] = A.V[pa];
                pc++; pa++;
            }
        }
    }
    C->tu = pc;
    C->mu = A.mu;
    C->nu = B.nu;
    return OK;
}

26到27题是对应十字链表的操作,具体点击之前的学习笔记观看思路,这里就不再做叙述,代码如下:

#define _CRT_SECURE_NO_WARNINGS

#define MAXMATRIXSIZE 12500
#define OK 1
#define ERROR 0

typedef int Status;

#include<stdio.h>
#include<stdlib.h>
typedef struct OList
{
    int x, y;
    int e;
    struct OList* right, * down;
}OLNode, * OLink;

typedef struct
{
    OLink* rhead, * chead;//指针数组
    int mu, nu, tu;//行、列、非零元个数
}CrossList;

Status CreateTSMatrix_OL(CrossList* T);//创建十字链表
Status PrintRowMatrix(CrossList T);//按行打印十字链表(可用于检测)
Status Add_toTSMatrix(CrossList* A, CrossList* B);//两矩阵按十字链表形式进行相加操作
Status PrintColMatrix(CrossList T);//按列打印(可用于检测)
int main()
{
    CrossList A,B;
    printf("请输入十字链表A:");
    CreateTSMatrix_OL(&A);
    printf("请输入十字链表B:");
    CreateTSMatrix_OL(&B);

    printf("两矩阵相加后:\n");
    Add_toTSMatrix(&A, &B);//相加

    system("pause");
    return 0;
}
Status CreateTSMatrix_OL(CrossList* T)
{
    printf("请输入矩阵的行数、列数、非零元个数:");
    scanf("%d,%d,%d", &T->mu, &T->nu, &T->tu);
    if (T->tu > T->mu * T->nu)
        return ERROR;
    T->rhead = (OLink*)malloc(sizeof(OLink) * T->mu);
    T->chead = (OLink*)malloc(sizeof(OLink) * T->nu);
    if (!T->rhead || !T->chead)
        return ERROR;

    for (int i = 0; i < T->mu; i++) T->rhead[i] = NULL;//将指针全部赋空

    for (int i = 0; i < T->nu; i++) T->chead[i] = NULL;

    int i = 0, row, col, val;
    while (i < T->tu)
    {
        printf("请输入矩阵的行、列、非零元值");
        scanf("%d,%d,%d", &row, &col, &val);
        
        if (row >= T->mu || row < 0 || col >= T->nu || col < 0)
            return ERROR;
        
        OLink s = (OLink)malloc(sizeof(OLNode));
        s->x = row;s->y = col; s->e = val;
        
        if (T->rhead[row] == NULL || T->rhead[row]->y > s->y)
        {
            s->right = T->rhead[row];
            T->rhead[row] = s;
        }
        else
        {
            OLink p = T->rhead[row], p1 = p;
            while (p != NULL && p->y < s->y) { p1 = p; p = p->right; };
                p1->right = s;
                s->right = p;
        }
        if (T->chead[col] == NULL || T->chead[col]->x > s->x)
        {
            s->down = T->chead[col];
            T->chead[col] = s;
        }
        else
        {
            OLink p = T->chead[col], p1 = p;
            while (p != NULL && p->x < s->x) { p1 = p; p = p->down; };
                p1->down = s;
                s->down = p;
        }
        i++;
    }
    PrintRowMatrix(*T);
    printf("\n");
    PrintColMatrix(*T);
    return OK;
}
Status PrintRowMatrix(CrossList T)//按行打印
{
    for (int i = 0; i < T.mu; i++)
    {
        OLink p = T.rhead[i];
        printf("第%d行:", i);
        while (p)
        {
            printf("%d,%d,%d   ", p->x, p->y, p->e);
            p = p->right;
        }
        printf("\n");
    }
    return OK;
}

Status Add_toTSMatrix(CrossList* A,CrossList *B)
{
    if (A->mu != B->mu || A->nu != B->nu)
        return ERROR;

    //拿B遍历A

    for (int i = 0; i < B->mu; i++)
    {
        OLink p = B->rhead[i];
        while(p!=NULL)
        {
            OLink node = (OLink)malloc(sizeof(OLNode));
            OLink AR = A->rhead[i]; OLink AD = A->chead[p->y];
            node->x = p->x; node->y = p->y; node->e = p->e; node->down = NULL; node->right = NULL;
            
            if (!AR || AR->y > node->y)//A中行无此结点
            {
                node->right = A->rhead[i];//插入后需要在列中插入
                A->rhead[i] = node;
                if (!AD || AD->x > node->x)
                {
                    node->down = A->chead[p->y];
                    A->chead[p->y] = node;
                }
                else
                {
                    OLink ADr = NULL;
                    while (AD)
                    {
                        if (AD->x > node->x)
                            break;
                        ADr = AD;
                        AD = AD->down;
                    }
                    node->down = AD;
                    ADr->down = node;
                }
                A->tu++;
            }
            else
            {
                OLink ARr = NULL;
                while (AR)
                {
                    if (AR->y >= p->y)
                        break;
                    ARr = AR;
                    AR = AR->right;
                }
                if (AR && AR->y == node->y)
                {
                    if (AR->e + node->e != 0)
                    {
                        AR->e = AR->e + node->e;
                    }
                    else//等于0的情况需要删除结点
                    {
                        //删除需要考虑是否在头端
                        if (ARr == NULL)//删除在头端
                        {
                            A->rhead[i] = A->rhead[i]->right;
                        }
                        else
                        {
                            ARr->right = AR->right;
                        }
                        /*删除在行中的结点后还需要删除在列中的结点*/
                        OLink ADr = NULL;
                        while (AD)
                        {
                            if (AD->x == node->x)
                                break;
                            ADr = AD;
                            AD = AD->down;
                        }
                        if (ADr == NULL)
                        {
                            A->chead[p->y] = A->chead[p->y]->down;
                            free(AD); AD = NULL;
                        }
                        else
                        {
                            ADr->down = AD->down;
                            free(AD); AD = NULL;
                        }
                        A->tu--;
                    }
                }
                else
                {
                    ARr->right = node;
                    node->right = AR;
                    if (!AD || AD->x > p->x)
                    {
                        node->down = A->chead[p->y];
                        A->chead[p->y] = node;
                    }
                    else
                    {
                        OLink ADr = NULL;
                        while (AD)
                        {
                            if (AD->x > node->x)
                                break;
                            ADr = AD;
                            AD = AD->down;
                        }
                        ADr->down = node;
                        node->down = AD;

                    }
                    A->tu++;
                }
            }
            node = NULL;
            p = p->right;
        }
    }
    PrintRowMatrix(*A);
    printf("\n");
    PrintColMatrix(*A);
    return OK;
}
Status PrintColMatrix(CrossList A)
{
    for (int i = 0; i < A.nu; i++)
    {
        OLink p = A.chead[i];
        printf("第%d列:", i);
        while (p)
        {
            printf("%d,%d,%d   ", p->x, p->y, p->e);
            p = p->down;
        }
        printf("\n");
    }
    return OK;
}

30、试按表头、表尾的分析方法重写求广义表的深度的递归算法

复习一下,广义表的递归算法通常会出现以下两种情况:

  • 为子表,深度+1
  • 为原字,深度+0

上述两种情况同时也是递归函数的出口,我们利用表头表的特性,可不断先取出表头进行判断,再传入表尾进行新一轮判断。

递归定义如下:

img

我查阅了很多博客和资料,都是下列算法,并没有关于GetHead和GetTail操作的详细,若按题目理解,应该就是对表头和表尾的操作,但是取表头和取表尾来进行求深度的话,暂时还没有好的办法,算法如下所示:

int DepthGList(GList L)
{
    int max = 0, dep = 0;
    if (L && L->tag == LIST)
    dep = DepthGList(L->hp) + 1;
    if (dep > max)max = dep;
    if (L && L->tp != NULL)
        dep = DepthGList(L->tp);
    if (dep > max)max = dep;
    return max;
}

31、按线性扩展结构编写复制广义表的算法

这题在补充笔记中有详细介绍,我们来复习一下,复制广义表L需要走过L的每一个结点,会出现以下情况:

  • 当L为空表的时候,将T置为空表
  • 当L为原子的时候,将T复制为原子结点,并且复制原子值
  • 当L为子表的时候,将T置为子表,并且传入表头进行复制
  • 当表头复制结束后,对表尾进行复制

算法如下所示:

Status CopyGList(GList* T, GList* L)
{
    if ((*L) == NULL)//为空时,将T置为空
    {
        (*T) = NULL;
        return OK;
    }
    (*T) = (GList)malloc(sizeof(GLNode));
    (*T)->tag = (*L)->tag;//复制标志域
    if ((*L)->tag == ATOM)
        (*T)->data = (*L)->data;//为原子
    else
        CopyGList(&(*T)->hp, &(*L)->hp);//为子表
    //if ((*L)->tp)//复制表尾
        CopyGList(&(*T)->tp, &(*L)->tp);
    //else
        //(*T)->tp = (*L)->tp;//表为赋空
//注释的代码可不要
    return OK;
}

32、试编写判别两个广义表相等的递归算法(由于本人习惯线性扩展操作,则这题用线性扩展结构来记录,在结尾会附上大佬博客全部答案的链表)

两广义表相等需要满足以下条件:

  • 两表全为空
  • 两表全部为空

    • 两表标志域相等

      • 为ATOM且data域相等

        • 判断表尾
      • 为LIST

        • 判断表头

          • 表头相等情况下判断表尾
  • 否则全为FALSE

代码如下所示:

Bool GListCompare(GList T, GList L)
{
    if (!L && !T)//全为空相等
        return TRUE;
    if (L && T)//若全部为空,则出现以下情况
    {
        if (L->tag == T->tag)//标志相同
        {
            if (L->tag == ATOM && L->data == T->data)//若是原子结点,则判断它的Data域是否相等
            {
                if (GListCompare(T->tp, L->tp))//若相等的情况,再传入表尾进行判断
                    return TRUE;//若表尾相等,则返回TRUE
            }
            else if (L->tag == LIST)//若是子表情况
            {
                if (GListCompare(T->hp, L->hp))//则传入表头进行判断
                {
                    if (GListCompare(T->tp, L->tp))//若表头相等,再传入表尾进行判断
                        return TRUE;//最后返回TRUE
                }
            }
        }
    }
    //其余情况,返回FALSE
    return FALSE;
}

33、试编写递归算法,输出广义表中所以的原子项以及所在层次

这题其实就是遍历广义表的一个变型而已,只需要在参数哪儿加一个层次就好,从0开始,遇到子表则参数+1,遇到原子输出参数值与原子值即可,代码如下所示:

void visit(GList L,int n)
{
    if (L != NULL && L->tag == ATOM)
    {
        printf("第%d层:%c", n,L->data);
    }
    else if (L != NULL && L->hp != NULL)
    {
        visit(L->hp, n + 1);
    }

    if (L != NULL && L->tp != NULL)
    {
        visit(L->tp, n);
    }
}

34、试编写递归算法,逆转广义表中的数据元素

例如将广义表(a,((b,c),( )),(((d),e),f))

逆置为:((f,(e,(d))),(( ),(c,d)),a)

这题的难度为五星,我想了很久还是没想到合适的解法,最终卑微的看了答案,我卡在的点在如何转换两结点的位置,但是却忽视了指针(域)最重要的特性,我一直用顺序表的思维,把地址看作值来处理,但是没有想到递归可回到上一个场景进行处理,代码如下,对这题我会做详细的图解和程序跟踪,以便理解:

我们来看看问题的归纳,逆置广义表,就是逆置每一层次的表头和表尾,则我们可以将问题分解为:逆置最下层的表头和表尾,同时,若广义表只有一个结点或为空表的时候,则不需要逆置

  • 逆置操作的前提:表头与表尾为均不能为空

代码如下所示:

Status InverseGList(GList* L)
{
    GList head, tail;
    head = *L;
    tail = (*L)->tp;//存入表尾的地址

    if (head->tag == LIST && head->hp != NULL)//为子表与不为空
        InverseGList(&(*L)->hp);
    if (tail)//若表尾不为空
    {
        InverseGList(&(*L)->tp);
        *L = (*L)->tp;//这步妙,指针的特性,
        tail->tp = head;//不需要起其他变量,直接调换位置
        head->tp = NULL;
    }
}

我们来跟着代码走一遍:

img

img

img

img

img

img

img

通过演示,我们已经确定了算法的正确性,恕我愚笨,不能想到其他解法,只能参考大佬的答案进行记录,在这题最难的点就是如何逐步将问题缩小并且控制两个方向的结点连接,我们需要注意的是指针的特性和函数传参还有递归的特性

代码的研读很有帮助,在的时候记录了表头和表尾,回溯的时候再从最后面开始调换位置,问题缩小到了两个结点直接的互换。并且通过传参为址的特性,直接将表尾与上层子表所连接。

35、假设广义表按如下形式的字符串表示(a1,a2,a3,...,an) n>=0其中a1或为单字母的表示的原子,或为广义表:n=0时,为只含空格字符的空表( )

  • 试着按头尾链模式编写,按照读入的一个广义表字符串建立其存储结构的递归算法

头尾链和线性扩展两种结构在之前都有记录,在创建的时候会出现( )空表,原子,以及子表的三种情况,我们以表头和表尾的分析方法,将问题缩小到:取出逗号前的作为表头,如果为一个字符的话就是原子结点,如果不为原子的话,就为子表,然后传入其表头,重复之前操作,表头创建完毕后,若字符串还未为空,则创建表尾,则递归算法如下所示:

Status CreateGList(GList* L, String S)
//采用头尾链表存储结构,由广义表的书写形式串S创建广义表L,设emp="( )"
{
    String sub, hstr,emp=" ";
    GList p = (*L), q = NULL;
    if (StrCompare(S, emp))
    {
        (*L) = NULL;
    }
    else
    {
        if (!((*L) = (GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);//建立表结点
        if (StrLength(S) == 1) {
            (*L)->sign = ATOM;
            (*L)->data = S;//创建单原子广义表
        }
        else
        {
            (*L)->sign = LIST;
            SubString(sub, S, 2, StrLength(S) - 2);//脱外层括号
            do {//重复建立n个子表
                sever(sub, hstr);//从sub中分离表头和表尾
                CreateGList(&p->hp, hstr);
                q = p;
                if (!StrEmpty(sub))
                {
                    if (!(p = (GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);
                    p->sign = LIST;
                    q->tp = p;
                }
            } while (!StrEmpty(sub));
            q->tp = NULL;
        }
        return OK;
    }
}

void sever(String str, String hstr)
//将非空串str分割成两部分:hsub为第一个','之前的子串,str为之后的子串
{
    int n = StrLength(str);
    int i = 0, k = 0;//k记尚未配对的左括号个数
    String ch;
    do {//搜索最外层的第一个逗号
        i++;
        SubString(&ch, str, i - 1, 2);
        if (ch[0] == '(')
            k++;
        else if (ch[0] == ')')
            k--;
    } while (i < n && (ch[0] != ',' || k != 0));
    if (i < n)
    {
        SubString(hstr, str, 1, i - 1);//截取,前面的子串存入hstr
        SubString(str, str, i + 1, n - i);//截取,后面的子串存入hstr
    }
    else
    {
        StrCopy(hstr, str);
        ClearString(str);
    }
}

以上创建操作若有疑惑,书上有详细讲解,或点击此连接

36、试按上题描述的格式输出广义表的递归算法:

解读下题意,就是根据广义表的存储结构输出广义表的书写形式串,我们可以知道,每次传入表头,代表新一层的广义表,则需要添加括号,若传入表尾,代表同一层的广义表,则需要添加逗号。代码如下所示

//线性扩展表
void PrintGlist(GList L)
{
    if (!L || L->tag == LIST && L->hp == NULL)//为空表情况
        printf("( )");//直接输出
    else if (L && L->tag == ATOM)//为原子情况,输出原子元素
        printf("%c", L->data);
    else
    {
        printf("(");//只有当为子表的时候,传入表头才需要添加括号
        PrintGlist(L->hp);
        printf(")");
    }
    if (L && L->tp) {//判断表尾是否为空,添加表尾的时候需要添加,号
        printf(",");
        PrintGlist(L->tp);
    }
}
//线性扩展测试通过

//头尾链式
void GList_PrintList(GList A)//按标准形式输出广义表
{

    if (!A)
        printf("( )");
    else
        if (!A->tag) printf("%d", A->data);
        else
        {
            printf("(");
            GList_PrintList(A->ptr.hp);
            if (A->ptr.tp)
            {
                printf(",");
                GList_PrintList(A->ptr.tp);
            }
            printf(")");
        }
}

37、试编写递归算法,删除广义表中所有值等于x的原子项

这题可利用34题的思路来实现结点之间的连接,只有当Tag域为ATOM的时候,才会对结点进行操作,若为子表,则传入表头,再传入表尾即可,代码如下所示:

Status DeleteElemGList(GList* L, char x)
{
    if ((*L) && (*L)->tag == ATOM)
    {
        if ((*L)->data == x)
        {
            GList p = (*L);
            *L = (*L)->tp;
            free(p);
            DeleteElemGList(&(*L), x);//如果相等,则连接表尾后传入进去
        }
        else
        {
            DeleteElemGList(&(*L)->tp, x);//如果不想等,则搜索表尾
        }
    }
    else if ((*L) && (*L)->tag == LIST && (*L)->hp)//为子表则分两个方向探寻
    {
        DeleteElemGList(&(*L)->hp, x);
        DeleteElemGList(&(*L)->tp, x);
    }
}

38、试编写算法,依次从左至右输出广义表中第l层的原子项

例如:广义表(a,(b,c,d))中,第一层的原子为a,第二层的原子为b,c,d,这题我们只需要在遍历节点上稍做修改就好,从左到有就是先表头再表尾,算法如下所示:

void visit(GList L, int n, int x)
{
    if (L != NULL && L->tag == ATOM)
    {
        if (n == x)
        printf("第%d层:%c", x,L->data);
    }
    else if (L != NULL && L->hp != NULL)
    {
        visit(L->hp, n + 1, x);
    }
    if (L->tp)
        visit(L->tp, n, x);
}

至此,从10.7到11.12,35天的时间才搞定这一章,总结下来,复合型数据结构与递归,分治的知识点还是似懂非懂的状态,还是题目太少,第20题、28、29三道题,我未找到满意的答案与分析,自己也想不出来,暂时搁置。

由于本文记录的均为自己的思路,并不适用于所有人,则这里放上大佬的题解链接,内容详细:点击此处

第20题考验的是对数组的操作,但是我卡在了如何降幂输出,第28、29题我并未想到有何方式测试,仅算法在百度文库上有记载。

本文链接:

https://nullcode.fun/37.html
1 + 5 =
快来做第一个评论的人吧~