|
|
好同学们，大家好，今天呢，我们来为大家讲解一下我们数据结构当中数组和广义表的内容。那么数组呢？它也是一种线性表，和我们之前讲过的栈队列串一样，那么它都是线性表。那么数组呢，是由类型相同的数据元素构成的，有序集合每个元素呢，称为数据数组元素。每个元素受n个线性关系的约束，每个元素呢，在n个线性关系中的序号I1I2一直到in称为该元素的下标，
可以通过该下标来访问该数据元素。因为数组中的每个元素呢，处于n个关系中，所以称该数组呢，为n为数组，我们数组呢，可以看作是广线性等的推广。它的特点呢，是结构中的元素，本身可以是具有某种结构的数据，但属于了同一数据类型。也就是说，数组的定义呢？数组是由有限个数据元素的集合，数组的所有数据元素呢？
具有相同属性，每个数组元素名呢？由数组名和下标组成。每一组有定义的下标值，都有一个与该下标对应的数组元素。指。数组呢，一旦被定义其为数了和为界了，就不再改变，因此呢，除了初始化和销毁之外，数组呢，就只有两种操作。一种呢，是给定一组下标存取相应的数据元素。
第二种呢，是给定一组下标修改相应数据元素中的某个数据项的值数组呢，不能进行插入和删除的运算。比如说我们看一下这样一个数组amn。我们可以呢，将数组a看成长度为m的线性表b。等于b1b2一直到bm，其中呢，每个元素BI。是长度为n的线性表，也就是说数组中的第I行。BI呢等于AI 1 AI 2。一直到ain。这是我们的每个元素BI，是一个长度为n的线性表。
也就是说。我们的每个数据元素di呢，是长度为n的线性表，也就说数组a中的di行。b=AI 1 AI 2。一直到了。ain.它是一个行向量形式的线性表。我们也可以呢，将数组a看成长度为n的线性表CC=c 1c二，一直到CN。其中呢，每个数据元素cic j是长度为m的线性表，也就是说数组中的DJ列CJ。等于a1 ga 2g一直到amg。
比如说数组元素CG呢，是一个。长度为m的线性表数组中的DJ列，那么这个时候呢，我们就把数据我们就把这样一个。ag.amn它当中这样一个看成是这样一个长度n的线性表ccg呢？就是这样一个列向量形式的线性表。也就是说，在C语言中，一个二维数组呢？可以定义为其分量类型为一维数组类型的一维数组类型。同样的一个N维数组类型呢，可以定义为其数组元素为n- 1维数组类型的一维数组类型。数组一旦被定义，
它的围住了和违建了，就不再改变。因此，除了结构的初始化和销毁之外。数组呢，只有存取元素和修改元素的操作，那么数组呢，只有两个操作，一个呢，是修改元素值，一个呢，是存取元素。接下来我们看一下数组的顺序存储和表示。由于数组呢，一般不做插入或删除操作，
也就是说一旦建立了数组。结构中的数据元素，个数和元素之间的关系就不再发生变动，因此呢，我们采取顺序存储结构呢，表示数组呢比较合适。由于存储单元呢，是一维的结构，而数组呢，可可能是多维的结构，则用一组连续单元连续存储单元存放数组。和数据元素呢，就有次序约定的问题数组呢，有两种顺序存储方式，一种呢是行优先。
将数据元素呢按行排列，一种呢是列优先，将数组元素呢按列向量排列。也就是说，对应的二维数组呢，有两种存储方式，一种呢是以行序为主序的存储方式，一种呢是以列序为主序的存储方式。那么由此呢，对于数组一旦规定了其维数和个维的长度，就可为它分配存储空间。那么，只要给出一组下标，便可求得相应数组元素的存储位置。那么，
我们来看一下。我们可以呢，把二维数组呢a看成三个元素，构成a0a1a2。其中呢a0。它可以表示a零零a零一a零二a零三a1呢？可以表示a一零a一一a一二a一三a2呢？可以表示a二零a二一a二二a二三。那么，我们可以把数组a呢看成这三个元素的构成，看成了是它以行向以行序为主序的方式呢？进行构成的这样一个部分。AI叫做它的航名，每个数据元素AI包含有四个元素的一维数组组成。我们数组二维数组amn呢，
按行优先存储在内存中，且每个元素呢，占第一个存储单元，那么我们要求AI。g的地址呢，就直接可以用location aig=location a零零+I×n+g×d。来进行表示就其中呢？我们表示。第一呢？是每个数据元素占的存储单元n和g是它n和g。I和g是它的下标。I和g是它的下标。那么。location aig就等于location a零零+I×n，加g×d。
那么就求得了aig的存储地址。接下来我们看一下矩阵的压缩存储。矩阵呢，是许多科学和工程计算问题中研究的数学对象。矩阵用二维数组来表示了是比较。适合的方式，但是呢，在数值分析中常出现一些基数很高的矩阵，或者同时呢，在矩阵中有许多值相同的元素或者零元素。有时呢，为了节约存储空间，可以对这类矩阵呢进行压缩存储。所谓压缩存储呢，是指为多个值相同的元素呢。
只分配一个存储空间，对零元呢？不分配存储空间，若值相同的。元素或磷元素在矩阵中的分布有一定的规律，我们则称此类矩阵呢，为特殊矩阵。特殊矩阵主要包括了对称矩阵，三角矩阵和对角矩阵等，那么我们下面呢？主要来讲一下这三种矩阵对称矩阵。三角矩阵和对角矩阵。我们压缩的含义呢，是为多个值相同的元素呢，只分配一个存储空间零元素呢，
不分配空间或者少分配存储空间。特殊矩阵呢，是元素值相同或零元素分布有一定规律的矩阵，稀疏矩阵呢，是元素值相同或零元素分配没有规律的矩阵。特殊矩阵的压缩存储呢，实际上是将二维数组的数据元素呢压缩到一维数组上，那么我们来看一下，比如说在一个n阶方程中，若数据元素呢满足以下性质。aij=aji零小于ij小于等于n- 1，则称n呢，为对称矩阵，也就是说对称矩阵呢，它的含义呢？
就是aig=aji那么称为对称矩阵，那么这个时候呢，我们比如说看下。它下面的这样一个部分主对角，主对角线下面的这样一些部分呢，比如说。找到一五。一八。三零二。七零六一那么找到这些数字了，再加上主对角线的上的上的元素，那么我们就可以了找到整个。矩阵的这样一个形式，那么比如说对称矩阵呢？在k0 k=0 k等于一二三一直到。
二分之n乘n减n加一减一，这样一些数据元素当中，在该该下三角组成中第I行呢，恰有I加一个元素。元素总数呢，为二分之n，乘n加一，那么为了便于访问对称矩阵a中的元素。必须在aij和sk sak中找一个对应关系k等于二分之I。乘I+1+g。那么，这是当I小于大于等于g的时候的这样一个情况。并且呢。k等于二分之g加g乘g加一加I，这是当I小于g的时候的情况。
在对角矩阵中呢，那么什么是对角矩阵中呢？在对角矩阵中所有的。非零元素集中在一组对角线。为中心的带状区域中计，除了主对角线和主对角线相邻，两侧若干条对角线上的元素之外。其余元素呢，皆为零，比如说这样一个矩阵。a0a零一a一零a一一a一二a二一a二二a二三那么一直到后面的an- 1 an- 2。an- 1。n- 1。那么这个时候呢，是一个对角矩阵。
那么，需要存储的元素个数呢？为3 n- 2，那么就是AK=1=2=3，一直到了3 n- 3。3 n- 3 n- 3，那么需要存储的元素个数呢？为3 n- 2。接下来我们再看一下系数矩阵，系数矩阵呢m中中共有s个非零元素，那么。若s呢？远小于。矩阵元素的总数则称m为稀疏矩阵啊，比如说这样一个矩阵当中，
我们的。零元素呢，那么比较多，那么s呢，非零元素个数呢，远小于矩阵元素的个数，那么这样呢，我们称之为稀疏矩阵。接下来我们看一下三元组顺序表，三元组顺序表呢？井号define map size 100 type define struct in tig element type v。triple type pp struct triple data marks+inter MU nu tu triple table。那么，这是啊，定义一个结构体类型的这样一个名称，
那么再定义一个结构体类型的名称，那么用三元组顺序表呢来进行表示。另外呢，还有识字链表，识字链表呢，它有行号，列号，还有这样一个value非零值，还有右指针指向本行中的下一个列节点的地址。还有down向下指针，指向本页中下一个节点的地址。我们来看一下特殊组件的压缩存储，那么刚才我们讲过了，由我们的三角矩阵。对角矩阵，
对称矩阵，那么我们首先来看一下对称矩阵，若n阶矩阵呢？a满足aig=aji。那么则称n呢？为n阶对称矩阵，那么对于对称矩阵呢？我们可以为每一对对称圆分配一个存储空间。可以将n二个圆呢压缩成n个n10。n- 1÷2的圆的空间中，那么我们可以以行序为主序呢？存储下三角中的圆那么对称矩阵的压缩存储呢？它存储地址的计算公式呢？是location aij=location a零零。加上二分之I乘I减一，
加上g减一，那乘以l，这是它的这样一个存储地址，这样一个。查找这些找查。去查询的这样一个查看的这样一个部分，那么三角矩阵是什么呢？三角矩阵包括下三角矩阵。和上三角矩阵指的是矩阵的下三角和指的指的是矩阵的上三角和下三角中元素呢，均为常数零常数c。或零的这n阶矩阵对于三角矩阵除了和对称矩阵一样是存储其上下三角中的圆之外。再加一个存储长度c的存储空间。对角矩阵呢。是所有非零圆都集中在以主对角线为中心的带状区域中，即除了主对角线和直接连在对角线上的上下若干条，
对角圆的线的圆之外，其余的圆皆为零。对于对焦矩阵，也可以按照某个原则以行为主序，或者以对角线的顺序呢，将其压缩存储到一维数组上。那么，以常规方法呢？即以二位数组表示了高阶系数矩阵产生什么问题？比如说零值元素呢？占了很大的空间，计算中需要很多零值的运算用，除法还是判别除数是否为零？那么，我们要解决问题的原则呢？
是尽可能减少不存或者说不存不存零值元素。尽可能减少没有意义的运算，那么操作方便，也就是说能尽快的找到与下标值ig对应的元素，能够尽快的找到同一行或者同一列的非零元素。那么，常用的系数组件的存储方法呢？有顺序存储，链接存储和散列存储顺序存储呢？有三元组表示，法行逻辑连接的顺序表带辅助航向的二元组表示法以及伪定值表示法。链接存储了，有带行向量指针的单列表示法行列表示法，也就是多列表示法，首先我们来看一下三元素表示法，
刚才我们讲过了这样一个部分，我们来看一下。用一个线性表呢来表示稀疏矩阵线性表的每个节点呢，对应稀疏矩阵的一个非零元素，其中每其中包括三个域。分别为，该元素的行下标，列下标和值节点间的先后顺序呢？按取间的行优先。顺序排列那么跳过零元素，将线性表呢？按顺序的方法存储在连续的存储空间中，那么我们来看一下，比如说第I第一行第一列，那么它的值是三。
第二行第三列，它的值是负一。第五行第四列。它的值呢？是二那么系数矩阵呢？共有零个n个非零元，且并且行下标列下标的与值一样都占一个存储单元。则三元组呢，它这个方这个方法呢，需要三个存储单元，接下来我们看一下链接存储。在行向量指针的链单列表示，法将矩阵的每一行的非零元素呢链接成一个单列表，每个节点呢包括三个域列下标非零元素是指针。复设一个行指针向量呢，
作为m个单链表表头，指针向量，比如说我们第一个表头指针，那么指向的这样一个。它的这样一个列下标是三。列下标是列下标是三列，下标是一非零元素呢是三。那么，还有它的五第五个。e下边是七。竖直了。是七列车标是五数字是七，还有我们这样一个第四列，它的列车标是四。它的值呢？
是二那所需的存储量呢？是3 n+m，那么是nm个单链表的表头指针向量那么用类似方法呢？可以组织成带列指针向量的单面表示法。好吧，我们还有行列表是吧？就是我们十字链表将行将带行指针的向量的单量表表示法呢和带列向量指定向量的单量表示法。结合在一起来存储稀疏矩阵，每个节点呢，包括五个字段，行下标，列下标值，行指针和列指针。以及我们的多链表表示，法将十字链表呢进一步扩充，
将每条链呢都采用循环的双链表表示，并且每个节点呢，包括七个字段，行下标，列下标，指左右，指左行，指的右行，指的上列，指针和下列指针。接下来我们看一下广义表，广义表呢，又称为列表，它是线性表的一个推广。广义表。
是有n个元素。a1，a2，a3一直到an的有限序列，其中呢AI是原子项，或者呢，又是一个广义表。比如说lsa 1，a2，z3一直到an ls呢，是广义表的名字n为它的长度，若AI是广义表，那么则称为它为ls的子表。为了区分原子和广义表书写时呢，我们用大写字母呢表示，
广义表用小写字母呢表示原子。那么，我们来看一下这些结论。广义表的元素呢，可以是子表，而子表的元素呢，还可以是子表，由此呢，广义表是一个多层次的结构。比如说我们这里的。d=ABC。三个元素。那么b呢？它当中呢？还有一个e。
那么c呢？它当中包含了a以及了。bcd.那么a呢？那么它是一个没有这样一个。它是这样一个一个空的，这样一个部分，一个一个括号里空的，这样一个值的，这样一个部分一呢，把它们包含了。b呢，当中包含了ec呢，当中包含了a和bcd这样一一个一个组合组合的这样一个括号当中的这样一个组成的部分。广义表呢，
可以为其他表所共享，比如说广义表ABC为d的词表在d中呢，可以不必列出词表的值，而通过词表的名称来引用。并且呢，广义表呢，具有递归性。那么，我们称a1是ls的表头。其余元素呢，组成的表a2a一直到an是ls的唯一表尾，由表头和表尾的定义可知，任何一个非空广义表呢，其表头可能是广义表，也可能是。
不是广义表，而是表尾了一定。试管仪表。比如说get head b=egethellb等于这样一个空的，这样一个部分。get,get headb.等于age the TD=BC。那么，由于BC呢？为非空广义表，那么继续分解呢？可以得到。get het t bc=bgethettl，BC=cge thet tlc=cge thet tlc等于。
空表的这样一个部分，那么有那么任何一个非空表，一表了其表头，可能是广义表，也可能不是广义表，那么其表物理呢？一定是广义表。那么，大家注意了，广义表一个空表了和广义表了，当中有括号了，那么是不一样的。比如说a这样一个括号a呢，是一个空表，它的长度为零。
b呢，只有一个原子eb的长度为1 c=a。括号bcd列表c的长度为二两个元素呢，分别为原子a和子表bcd。d=abcd的长度为三三个元素呢，都是列表代入子表值，那么得到AB呢？是这样一个。表示的这样一个运用部分，一=a一，它是一个递归表，长度为二一呢，相当于一个无限长无限的这样一个列表。一=a括号a括号a这样一个部这样应用的这样一个部分。那么，
我们来看一下广义表的结构特点。广义表中的数据元素呢？具有相对次序。广义表的长度呢？定义为最外层包含元素的个数。广义表的深度呢？定义为所含括弧的重述。那么，广义表的深度，原子的深度为零。空表的深度呢为一。广义表呢？可以共享广义表可以是一个递归的表，递归的表的深度是无穷值，长度是有限值，
那么这里呢？大家就要注意广义表的长度。定义为最外层包含元素的个数，广义表的深度定义为所含括弧的重数，原子的深度为零。它的深度呢，为一原子的深度为零。那么另外呢，除了空表的表头指针为空外，对于任何非空列表，其表头指针呢，均指向一个表结点。且该节点中的HP e呢？指向表头节点或为原子节点或为表节点tpe呢？指向列表表尾，
除非表尾为空则指针为空，否则b为表节点。那么我们呢，要分清列表，中原子和子表所在的层次，并且呢，要知道最高层的表节点个数呢，即为表列表的长度。那么，它的优点呢？是给列表的运算带来方便，比如说求列表的长度和深度，求表头表尾，那么它的缺点呢？是表节点个数多和列表中的括弧对数不匹配。
也比较多的占用了存储空间。接下来我们看一下广义表的存储结构。由于广义表中的数据元素呢，可以具有不同的结构或者是原子，或者是广义表，因此呢，我们难以用顺序存储。结构表示。通常采用链式存储结构，每个数据元素呢，可以用一个节点表示，广义表中有两种数据元素原子呢，或者广义表因此呢。需要用两种结构的节点，一种是表节点，
另一种呢是原子节点。比如说我们的表结点，比如说我们的a是一个这样一个括号空的，这样一个部分括号的，这样一个部分b呢等于e。c呢等于abcdd呢等于abce呢等于ae，这样一个属，这样一个嵌套的，这样一个递归的，这样一个广义表。呃，接下来我们看一下广义表呢，与线性表的区别。线性表呢a1a2一直到an它是n个元素的有限级，每个元素的类型呢是相同的。
元素之间的位置呢，是一维的线性的，而广义表呢ls=a 1a二一直到an其中每个元素呢，既可以是原子，也可以呢是子表。那么称de为表头d2到dn呢？为表尾那么广义表呢？n表示，广义表的长度括号层数呢？表示，广义表的深度。比如说我们来看一下，比如说线性表当中每个元素呢，它的类型是相同的，而在广义表中呢，
每个元素可以是原子，也可以是子表。那么，它这样一个结论是，结论呢，是存储结构呢，线性表，它有我们的顺序表和链表。这样一个存储方式，广义表呢，有我们的链式结构。那么，以及我们的长度与深度，长度呢？就是我们网页表的。
这样一个最外层的这样一个元素的这样一个数，这样一个。这个这个数目的元素个数的这样一个部分，它的深度呢就是我们。网易表的。括号当括号的这样一个最大乘数，比如说我们来看一下由广义表的长度呢定义为最外层包含元素的个数，广义表的深度呢定义为所包含括号的括弧的重重数。广义表的表头与表尾以及呢？广义表的嵌套性与递归性，那么这样一些应用的部分。好同学们，今天呢，我们给大家讲了一下关于我们数组，我们的数组与广义表的这样一些结构。
啊，我们来回顾一下我们多维数组呢，可以看成是线性表的推广，其特点呢，是结构中的元素本身，所以是具有某种结构的数据，但属于同一。数据类型，一个N维数组呢，实际上是n个线性表的组合，每一维呢都是一个线性表。数组呢，一般采用顺序存储结构，所以说存储多维数组时呢，应将其确定转换为一个一维结构按行和列的转换呢。
来进行进行存储，那么科学和工程计算中的矩阵呢？通常用二维数组来表示，为了节约存储空间，那么对几种常见的矩阵形式，比如说对称矩阵。三角矩阵和对角矩阵呢？在存储时呢？可以进行压缩存储，那么就多积为多个相同值值，多个值相同的圆呢？只分配一个存储空间。对零元呢，不分配求助空间，而我们的广义表呢，
是另一种线性表的推广形式。表中的元素呢，可以是原子的单个元素。也可以呢，是一个子表，所以线性表呢，可以看成呢，是广义表的这样一个特殊情况，广义表的结构呢，比较灵活，在某种前提下呢，可以兼容线性表数，组数，有像图了等各种常用的数据结构。广义表的常用操作呢？
有取表头和表尾，广义表呢？通常采用链式存储结构，头尾链表的存储结构和扩展线性链表的这样一个存储结构。那么大家呢，要掌握我们数组和广义表这两种数据结构的特点。掌握数据存储时地址的这样一个计算方法，以及呢几种特殊矩阵，比如说三角矩阵，对角矩阵以及呢对称矩阵，它的压缩生成方法，并且呢，了解。广义表的这样一个链式存储结构好，同学们今天的课呢，
我们就讲到这里好，大家下去之后呢，再看一下这些部分进行一个了解和掌握好，谢谢大家。
|
|
|Archiver|手机版|小黑屋|5432考试网
( 蜀ICP备2022024372号|
川公网安备51152402000101号 )|网站地图
发表于 2024-4-15 09:16:59