数据结构与算法·第5章【数组和广义表】

这篇具有很好参考价值的文章主要介绍了数据结构与算法·第5章【数组和广义表】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数组

基本操作

InitArray(&A, n, bound1, ..., boundn)

DestroyArray(&A)

Value(A, &e, index1, ..., indexn)

Assign(&A, e, index1, ..., indexn)

数组的顺序表示

两种顺序映象的方式:

  1. 以行序为主序(低下标优先);
  2. 以列序为主序(高下标优先)。

数据结构与算法·第5章【数组和广义表】

n n n维数组:LOC(x1, x2, ..., xn) = LOC(0, 0, ..., 0) + [(x1 × b1 + x2) × b2 + x3] × b3 + ... + xn

数据类型定义

#include <stdarg.h> // 标准头文件,提供宏 va_start、va_arg 和 va_end,用于存取变长参数表

#define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为 8

typedef struct {
    ElemType *base;  // 数组元素地址,由 InitArray 分配
    int dim;         // 数组维数
    int *bounds;     // 数组维界基址,由 InitArray 分配
    int *constants;  // 数组映像函数常量基址,由 InitArray 分配
} Array;

其中:

Status InitArray(Array& A, int dim, ...) {
    // 若维数 dim 不合法,则返回 ERROR
    if (dim < 1 || dim > MAX_ARRAY_DIM) {
        return ERROR;
    }
    A.dim = dim;
    A.bounds = (int*)malloc(dim * sizeof(int));
    if (!A.bounds) {
        exit(OVERFLOW);
    }
    // 存储各维长度,并计算元素总数 elemtotal
    int elemtotal = 1;
    va_list ap;  // 定义 va_list 类型变量 ap,用于存放变长参数表信息的数组
    va_start(ap, dim);  // 初始化 ap 数组
    for (int i = 0; i < dim; ++i) {
        A.bounds[i] = va_arg(ap, int);
        if (A.bounds[i] < 0) {
            return UNDERFLOW;
        }
        elemtotal *= A.bounds[i];
    }
    va_end(ap);  // 结束 ap 数组

    A.base = (ElemType*)malloc(elemtotal * sizeof(ElemType));
    if (!A.base) {
        exit(OVERFLOW);
    }
    // 求映像函数的常数 ci,并存入 A.constants[i-1],i=1,...,dim
    A.constants = (int*)malloc(dim * sizeof(int));
    if (!A.constants) {
        exit(OVERFLOW);
    }
    A.constants[dim - 1] = 1;
    // L=1,指针的增减以元素的大小为单位
    for (int i = dim - 2; i >= 0; --i) {
        A.constants[i] = A.bounds[i + 1] * A.constants[i + 1];
    }
    return OK;  // 返回 OK
}

A.bounds是每一维可以放多少元素:a[A.bounds[0]][A.bounds[1]][A.bounds[2]]……
A.constants是指向每一维开始的元素的指针(因为是顺序存放,所以没有在计算机中没有明显的维数的区分,需要自己计算出指向每一维第一个元素的指针)

关于va_list的解释

/**
 * 在数组 A 中定位指定下标的元素,并计算出该元素的相对地址。
 * 
 * @param A     要定位的多维数组
 * @param ap    指示要定位的下标列表的可变参数
 * @param off   返回该元素在数组 A 中的相对地址
 * @return      如果下标合法,返回 OK;否则返回 OVREFLOW
 */
Status Locate(Array A, va_list ap, int& off) {
    // 初始化偏移量为 0
    off = 0;
    // 循环遍历所有维度
    for (int i = 0; i < A.dim; ++i) {
        // 获取当前维度的下标值
        int ind = va_arg(ap, int);  
        // 检查下标值是否超出边界
        if (ind < 0 || ind >= A.bounds[i]) {
            return OVREFLOW;
        }
        // 计算该维度下标对应的偏移量,并累加到总偏移量中
        off += A.constants[i] * ind;
    }
    // 如果下标合法,则返回 OK
    return OK;
}

矩阵的压缩存储

数据结构与算法·第5章【数组和广义表】

#define MAXSIZE 12500

typedef union {
    Triple data[MAXSIZE + 1]; // 用于存储稀疏矩阵中的非零元素
    int mu, nu, tu; // 分别表示稀疏矩阵的行数、列数和非零元素个数
} TSMatrix; // 稀疏矩阵类型

有2类稀疏矩阵:

  • 非零元在矩阵中的分布有一定规则
    例如: 三角矩阵, 对角矩阵
  • 随机稀疏矩阵
    非零元在矩阵中随机出现

随机稀疏矩阵的压缩存储方法:

  • 三元组顺序表

这个结构体一般用于表示稀疏矩阵中的非零元素。对于一个 m 行 n 列的稀疏矩阵,如果其非零元素个数为 k,则可以用一个长度为 k 的 Triple 数组来存储这些非零元素。

#define MAXSIZE 12500

typedef struct {
    int i, j; // 该非零元的行下标和列下标
    ElemType e; // 该非零元的值
} Triple; // 三元组类型
  • 行逻辑联接的顺序表
  • 十字链表

求转置矩阵

三元组作转置

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
    T.mu = M.nu;
    T.nu = M.mu;
    T.tu = M.tu;
    if (T.tu) {
        int col, t, p;
        int num[MAXSIZE + 1] = {0}; // 列计数器,用于记录每列非零元素的个数
        int cpot[MAXSIZE + 1] = {0}; // 行指针数组,用于记录每列第一个非零元素在转置矩阵中的位置
        // 统计每列非零元素的个数
        for (col = 1; col <= M.nu; ++col) {
            num[col] = 0;
        }
        for (t = 1; t <= M.tu; ++t) {
            ++num[M.data[t].j];
        }
        // 计算每列第一个非零元素在转置矩阵中的位置
        cpot[1] = 1;
        for (col = 2; col <= M.nu; ++col) {
            cpot[col] = cpot[col - 1] + num[col - 1];
        }
        // 执行转置操作
        for (p = 1; p <= M.tu; ++p) {
            col = M.data[p].j;
            int q = cpot[col]; // 该元素在转置矩阵中的位置
            T.data[q].i = M.data[p].j;
            T.data[q].j = M.data[p].i;
            T.data[q].e = M.data[p].e;
            ++cpot[col]; // 该列的行指针加1
        }
    }
    return OK;
} // FastTransposeSMatrix

行逻辑连接的顺序表

#define MAXMN 500

typedef struct {
    Triple data[MAXSIZE + 1]; // 非零元三元组表
    int rpos[MAXRC + 1]; // 各行第一个非零元的位置表
    int mu, nu, tu;  // 矩阵的行数、列数和非零元个数            
} RLSMatrix; // 行逻辑链接顺序表类型
ElemType value(RLSMatrix M, int r, int c) {
    int p = M.rpos[r];
    while (M.data[p].i == r && M.data[p].j < c) {
        p++;
    }
    if (M.data[p].i == r && M.data[p].j == c) {
        return M.data[p].e;
    } else {
        return 0;
    }
} // value

矩阵乘法:

// 稀疏矩阵相乘
Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {
    // 如果两个稀疏矩阵的列数不等,则无法相乘,返回错误状态
    if (M.nu != N.mu) {
        return ERROR;
    }
    // 计算结果矩阵Q的行数,列数以及非零元素个数
    Q.mu = M.mu;
    Q.nu = N.nu;
    Q.tu = 0;
    // 如果M、N之间存在非零元素,则进行矩阵相乘的处理
    if (M.tu * N.tu != 0) {
        // 遍历M的每一行
        for (int arow = 1; arow <= M.mu; ++arow) {
            // M矩阵中第arow行在三元组表中的起始位置
            int mp = M.rpos[arow];
            // 遍历N的每一列
            for (int bcol = 1; bcol <= N.nu; ++bcol) {
                // 初始化N矩阵中第bcol列在三元组表中的起始位置
                int np = N.rpos[bcol];
                // 累加M矩阵第arow行和N矩阵第bcol列的乘积
                ElemType temp = 0;
                while (mp < M.tu && np < N.tu) {
                    // 如果M矩阵和N矩阵中的当前位置元素在同一列,则累加乘积
                    if (M.data[mp].j == N.data[np].i) {
                        temp += M.data[mp].e * N.data[np].e;
                        mp++;
                        np++;
                    } else if (M.data[mp].j < N.data[np].i) {
                        mp++;
                    } else {
                        np++;
                    }
                } // while
                // 如果累加的乘积不为0,则添加到结果矩阵Q中
                if (temp != 0) {
                    Q.tu++;
                    // 将非零元素添加到Q三元组表的末尾
                    Q.data[Q.tu].i = arow;
                    Q.data[Q.tu].j = bcol;
                    Q.data[Q.tu].e = temp;
                }
            } // for bcol
        } // for arow
    } // if
    return OK;
} // MultSMatrix

十字链表

数据结构与算法·第5章【数组和广义表】

结构体定义

typedef struct OLNode {
    int i, j;       // 该非零元的行和列下标 
    ElemType e;     // 该非零元的值 
    struct OLNode *right, *down;   // 该非零元所在行表和列表的后继指针 
} OLNode, *OLink;

typedef struct {
    OLink *rhead, *chead;   // 行和列链表头,指向 rhead 与 chead 数组
                            // 指针向量基址由 CreateSMatrix 函数分配
    int mu, nu, tu;         // 稀疏矩阵的行数、列数和非零元个数      
} CrossList;

广义表

数据结构与算法·第5章【数组和广义表】
结构特点:

  • 广义表的长度定义为最外层包含元素个数;
  • 广义表的深度定义为所含括弧的重数;
    注意:“原子”的深度为 0 ;“空表”的深度为 1

数据结构与算法·第5章【数组和广义表】
表头要去掉一次括号,表尾直接拿并且包含原来的括号

广义表的存储结构

表头、表尾法

数据结构与算法·第5章【数组和广义表】
其中,NIL表示空表
数据结构与算法·第5章【数组和广义表】
还是好好看看吧

子表表示

数据结构与算法·第5章【数组和广义表】
数据结构与算法·第5章【数组和广义表】

注意其中0|x后面是0|y,而不是跟着表尾,这个时候是把表后面的元素拿出来,所以它和表头表尾表示法的区别就在这,它拿后面的子表也要去掉最外面的括号

搭配这个例子才比较好理解一些

求深度

int GlistDepth(Glist L) {
    // 返回指针L所指的广义表的深度
    int max = 0;
    Glist pp;
    int dep;
    if(!L) return 1;
    if(L->tag==ATOM) return 0;
    for (pp = L; pp; pp = pp->ptr.tp) {
        dep = GlistDepth(pp->ptr.hp);
        if (dep > max) {
            max = dep;
        }
    }
    return max + 1;
} // GlistDepth

遇到求深度的一些填空题,可能要自己画一下了,不是用眼睛能看出来的

比如:广义表 {{1,2},{3,{4,5}}} 中,子表 {1,2} 和 {3,{4,5}} 位于同层,此广义表中包含 3 层括号,因此深度为 3。

  1. ((1,2),(3,(4,5)))
  2. ((1,2),(3,(4,5)))
  3. ((1,2),(3,(4,5)))

习题

计算地址

数据结构与算法·第5章【数组和广义表】
数据结构与算法·第5章【数组和广义表】
注意按行和按列计算
数据结构与算法·第5章【数组和广义表】
(1)100 (2)776 (3)1784 (4)4416

a3125—— 3×3×5×8+1×5×8+2×8+5
高维的系数乘以低维所包含的元素数

5.19 马鞍点

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

void saddle(int a[m][n]) {
    int flag = 0, min, col;
    for (int i = 0; i < m; ++i) {
        min = a[i][0];
        for (int j = 0; j < n; ++j) {
            if (a[i][j] < min) {
                min = a[i][j];
                col = j;
            }
        }
        int flag1 = 1;
        for (int k = 0; k < m; ++k) {
            if (min < a[k][col]){
                flag1 = 0;
                break;
            }
        }
        if (flag1) {
            printf("%d行%d列是马鞍点,值为%d\n", i, col, min);
            flag = 1;
        }

    }
    if (!flag) {
        printf("无马鞍点\n");
    }
}

时间复杂度: O ( m 2 + m ∗ n ) O(m^2+m*n) O(m2+mn)文章来源地址https://www.toymoban.com/news/detail-474051.html

到了这里,关于数据结构与算法·第5章【数组和广义表】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构【数组、串、广义表】

    一、数组 1.概念:线性表是通过数组实现的,数组是线性表的推广,数组只有存取元素和修改元素的操作(除了初始化和销毁); 2.数组的存储结构:一个数组的所有元素在内存中占用一段连续的存储空间(顺序存储); 以行为主顺序优先存储; 以列为主顺序优先存储。

    2024年02月15日
    浏览(40)
  • 数据结构--串、数组、广义表

    也叫字符串 抽象类型定义 存储结构(顺序表较为常用) 顺序存储结构 为了方便一些操作,通常串的数组的第一个位置不放元素,而是从ch【1】开始存放元素 链式存储结构 如果一个结点的数据域只放一个字符,那么会导致存储密度异常的底,解决这个问题:在数据域放更多的

    2024年02月15日
    浏览(38)
  • 数据结构—数组和广义表

    4.2数组 数组: 按一定格式排列起来的,具有 相同类型 的数据元素的集合。 **一维数组:**若线性表中的数据元素为非结果的简单元素,则称为一维数组。 **一维数组的逻辑结构:**线性结构,定长的线性表。 **声明格式:**数据类型 变量名称 [长度] ; 例如:int num[5] = {0,1

    2024年02月15日
    浏览(45)
  • 数据结构之串|数组|广义表

    总结:

    2024年01月16日
    浏览(43)
  • 12-数据结构-数组、矩阵、广义表

    目录 数组、矩阵、广义表   一、数组         二.矩阵 三、广义表         这一章节理解基本概念即可。数组要看清其实下标是多少,并且二维数组,存取数据,要先看清楚是按照行存还是按列存,按行则是正常一行一行的去读写,按列则是,从左至右,一列一列的弄。

    2024年02月13日
    浏览(36)
  • 数据结构之数组、矩阵和广义表

      数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法,为提高利用

    2024年01月22日
    浏览(44)
  • C语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作

    本篇实验代码非本人写,代码源自外部,经调试解决了部分warning和error后在本地vs上可以正常运行,如有运行失败可换至vs 未来会重构实现该两个实验 内容要求: 1、初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立哈夫曼树 2、建立编码

    2024年02月13日
    浏览(53)
  • 【数据结构】——多维数组、矩阵以及广义表的相关习题

    1、数组通常具有的两种基本操作是()。 A、查找和修改 B、查找和索引 C、索引和修改 D、建立和删除 解析: (A) 基本操作是查找和修改,其中每个元素都可以通过其索引来访问,这是从数组的第一个元素开始计算的。除了访问和修改数组元素之外,还可以执行其他一些操

    2024年02月04日
    浏览(36)
  • 数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)

    目录 二叉树的定义 二叉树具体的五种基本形态 1.空树 2.只有一个节点 3.有左子树,但右子树为空 4.有右子树,但左子树为空  5.左右两子树都不为空 特殊二叉树 斜二叉树 满二叉树  完全二叉树 二叉树的几个重要性质 初识二叉树的几个操作函数  二叉树T: 一个有穷的节点

    2024年02月03日
    浏览(60)
  • 数据结构--》数组和广义表:从基础到应用的全面剖析

            数据结构为我们提供了组织和处理数据的基本工具。而在这个广袤的数据结构领域中,数组和广义表是两个不可或缺的重要概念。它们作为线性结构的代表,在算法与应用中扮演着重要的角色。         无论你是初学者还是进阶者,本文将为你提供简单易懂、

    2024年02月08日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包