当前位置：文档之家 › 广义表的head和tail运算讲解

广义表的head和tail运算讲解

  • 格式：docx
  • 大小：26.71 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

第5章 数组和广义表

第5章 数组和广义表

5.2 数组的顺序表示和实现
类型特点: 1) 只有引用型操作，没有加工型操作; 2) 数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映像的方式: 1)以行序为主序(低下标优先); 2)以列序为主序(高下标优先);
以“行序为主序”的存储映像
例如：
a0,0 a0,1 a0,2 a1,0 a1,1 a1,2
解决问题的原则:
1) 尽可能少存或不存零值元素;
2) 尽可能减少没有实际意义的运算; 3) 操作方便; 即: 能尽可能快地找到 与下标值 (i, j) 对应的元素; 能尽可能快地找到 同一行或同一列的非零值元;
有两类稀疏矩阵：
1) 特殊矩阵
非零元在矩阵中的分布有一定规则
例如: 三角矩阵 对角矩阵
2) 随机压缩存储方法:
一、三元组顺序表 二、行逻辑链接的顺序表
三、 十字链表
一、三元组顺序表
#define MAXSIZE 12500 typedef struct { int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值 } Triple; // 三元组类型 typedef struct { Triple data[MAXSIZE + 1]; int mu, nu, tu; } TSMatrix; // 稀疏矩阵类型
三、 十字链表
M .c h e a d
^
M .rh e a d
1 13
1 45
^^
2 2 -1
^^
312
^^
3 0 0 5 0 -1 0 0 2 0 0 0
5.4 广义表的类型定义
ADT Glist { 数据对象：D＝{ei | i=1,2,..,n; n≥0; ei∈AtomSet 或 ei∈GList, AtomSet为某个数据对象 } 数据关系： LR＝{<ei-1, ei >| ei-1 ,ei∈D, 2≤i≤n} 基本操作:

数据结构 5数组和广义表A

数据结构 5数组和广义表A
12
1 Status Locate(Array A,va_list ap,int &off) 2{ 3 //若ap指示的各下标值合法，则求出该元素在A中，相对地
址off
4 off=0; 5 for(i=0;i<A.dim;++i) 6 { 7 ind=va_arg(ap,int); 8 if(ind<0||ind>A.bounds[i]) return OVERFLOW; 9 off+=A.constants[i] *ind; 10 } 11 return OK; 12 }
行数 总列数，即 第2维长度 元素个数
ij
补充：计算二维数组元素地址的通式
设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0。
单个元素 长度
二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
6
例1〖软考题〗：一个二维数组A[1..6, 0..7]，每个数组元素
16
5.4
1、定义：
广义表的定义
广义表是线性表的推广，也称为列表（lists） 记为： LS = ( a1 , a2 , ……， an ) 广义表名 表头(Head） 表尾 (Tail) n是表长
在广义表中约定：
① 第一个元素是表头，而其余元素组成的表称为表尾； ② 用小写字母表示原子类型，用大写字母表示列表。
13
1 Status Value(Array A,ElemType &e,…){ 2 //A是n维数组，e为元素变量，随后是n个下标值，若各下
标不超界，则e赋值为所指定的A的元素值，即将指定元素值 读到e变量中。

第五章 数组和广义表

第五章 数组和广义表

第五章数组和广义表一．选择题1．在二维数组A 中引用A[i,j]的时间_________。

A．与i、j的大小有关B．与i、j的大小无关C．与i的大小有关，与j的大小无关D．与i的大小无关，与j的大小有关2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。

A．行号 B．列号 C．元素值 D.地址3．二维数组A 按行顺序存储，其中每个元素占1个存储单元。

若 A[1][1]的存储地址为420， A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。

A．470 B．471 C．472 D. 4734．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。

A．行号 B．列号 C．元素值 D.地址5．下面的说法中，不正确的是________。

A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B．对角矩阵中只须存放的非零元素即可C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储6．对一些特殊矩阵采用压缩存储的目的主要是为了________。

A．表达变得简单 B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销7．若将n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组 B 中，则该对称矩阵在 B 中占用了________个数组元素。

A．n2 B．n*(n-1) C．n*(n+1)／2 D．n*(n-1)8. 稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。

A. 行号B.列号C.元素值D.元素总数9．稀疏矩阵一般的压缩存储方法有两种，即________。

A．二维数组和三维数组 B．三元组和散列C. 三元组和十字链表 D．散列和十字链表10．有一个 10 阶对称矩阵 A，采用压缩存储方式(以行序为主存储，且A[0 Ⅱ0]=1)，则A[8][5]的地址是________。

数据结构答案第4章

数据结构答案第4章
【解答】设稀疏矩阵为m行n列，如果采用二维数组存储，其空间复杂度为Ｏ(m×n)；因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(m×n)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t<<m×n时，采用三元组顺序表存储可获得较好的时、空性能。
⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。
A 90 B 180 C 240 D 540 E 108 F 114 G 54
⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。
【解答】1140
【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。
Head(Tail(Tail(Head(ST))))=奖金
⑵工资表ST的头尾表示法如图4-7所示。7．若在矩阵A中存在一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有马鞍点的算法，并分析最坏情况下的时间复杂度。
⑵因为k和i, j之间是一一对应的关系，k+1是当前非零元素的个数，整除即为其所在行号，取余表示当前行中第几个非零元素，加上前面零元素所在列数就是当前列号，即：

数据结构 习题 第五章 数组和广义表

数据结构 习题 第五章 数组和广义表

第 5 章数组和广义表一、选择题1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

【燕山大学 2001 一、2 （2分）】A. 13B. 33C. 18D. 402. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。

假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。

若按行存储，则A[2，4]的第一个字节的地址是（③）。

若按列存储，则A[5，7]的第一个字节的地址是（④）。

就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。

供选择的答案：【上海海运学院 1998 二、2 （5分）】①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120G. 156 H. 234 I. 276 J. 282 K. 283 L. 288⑤： A．行与列的上界相同 B. 行与列的下界相同C. 行与列的上、下界都相同D. 行的元素个数与列的元素个数相同3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。

A. BA+141B. BA+180C. BA+222D. BA+225【南京理工大学 1997 一、8 （2分）】4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。

【福州大学 1998 一、10 (2分)】A. 808B. 818C. 1010D. 10205. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

数据结构试卷

数据结构试卷

考试答案不得超过此线一、选择题（每小题2分，共20分）1、与线性表的顺序存储不相符的特性是（）。

A.不便于插入和删除B.必须连续的存储空间C.需另外开辟空间保存元素间的关系D.存储容量固定2、下列时间复杂度最好的是( )。

A、O)(log2n B、O)(2nC、O)(n D、O)log(2nn3、在链表中最常用的操作是删除表中最后一个结点和在最后一个结点之后插入元素，则采用（）最节省时间。

A、带头指针的单向循环链表B、带头指针的双向循环链表C、带尾指针的单向循环链表D、双向链表4、设一个栈的输入序列为1、2、3、4，则借助一个栈所得到的输出序列不可能的是（）A、1，2，3，4B、4，3，2，1C、1，3，4，2D、4，1，2，35、一棵左右子树均不空的二叉树在中序线索化后，空的指针域的个数是( )。

A、0B、1C、2D、不确定6、10个顶点的连通图的深度优先生成树的边数为（）。

A、11B、10C、9D、无法确定7、12个结点的平衡二叉树的最大深度为( )。

A、4B、5C、6D、78、设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（）次。

A、9B、8C、7D、69、一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（）A、（14，18，38，46，65，40，20，53，86，74）B、（14，38，18，46，65，20，40，53，86，74）C、（14，18，20，38，40，46，53，65，74，86）考试答案不得超过此线D、（14，86，20，38，40，46，53，65，74，18）10、快速排序方法在（）情况下最不利于发挥其长处。

A、要排序的数据太大B、要排序的数据中含有多个相同值C、要排序的数据已基本有序D、要排序的数据个数为奇数二、填空题（每小题2分，共16分）1、下面程序段中带下划线的语句的执行次数是for(i=0;i<=n;i++)for(j=0;j<=i;j++)x=x+1;2、若串S=‘software’,其非空子串的数目是3、设数组A[1..5,1..6] 的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A[5，5]的地址是。

数据结构word笔记

张东1145105494简介：1、算法+数据结构=程序2、数据结构3、数据、数据元素（基本单位）、数据项（最小单位）4、数据结构在计算机中的映像是存储结构；数据元素在计算机中的映像是结点；数据项在计算机中的映像是数据域；逻辑结构在计算机中的映像是关系。

5、四种存储方式6、抽象数据类型1）按不同特性分类●原子类型●固定聚合类型●可变聚合类型2）基本操作●init 构造●destroy 销毁●get 返回●put 改变●isasc 升序●isdesc 降序●Max 最大●min 最小7、时间复杂度技巧1）对于循环程序（for），最大执行次数即为for的乘积。

简言之，程序有多少for出现，就是n的多少次方2）对于顺序结构，可用“求和取最大值“法则3）对于循环程序（while），一般结果是O(log M N)4）若是一般的赋值语句，时间复杂度必为O(1)5）对于选择结构的程序，一般时间复杂度为O(1)加：自加自减++ ——x=2；y=x++;y=++x;第二章线性表1、表长相当于元素个数2、线性表一般下标是1—n，故当n=0时，表示线性表为空表3、list 表示线性表elem 元素length 表示求长度（线性表）locate 定位（位置）insert 插入（元素之前）delete 删除void 空类型（写程序必写）顺序结构（链表相反）优势：随机存取劣势：在做插入或删除时需要移动大量的元素malloc 分配一个连续空间realloc 将已分配的空间进行重新分配顺序表插入时所需移动的元素次数期望值是n/2删除时所需移动的元素次数期望值是（n-1）/2删除：模板语句：q=&(L.elem[i-1]) 表示顺序表中插入元素或者删除元素的地址加：逻辑运算符：！非&&与（一假即假）||或（一真即真）逻辑值：真（1）假（0）比较运算符：< >= <= == !=若在if或者while后面的括号中出现逻辑表达式或者比较表达式，那么结果只能为真或假。

数据结构复习题

判断：1．线性表的逻辑顺序与存储顺序总是一致的。

F2．顺序存储的线性表可以按序号随机存取。

F3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

F4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

T 6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

T1.单链表中，增加一个头结点的目的是为了（C）。

(A) 使单链表至少有一个结点(B)标识表结点中首结点的位置（C）方便运算的实现(D) 说明单链表是线性表的链式存储2.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

(A) 单链表(B) 仅有头指针的单循环链表(C) 双链表(D) 仅有尾指针的单循环链表3.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（）。

(A) 单链表(B) 顺序表(C) 双链表(D) 单循环链表1. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。

A. 不确定B. n-i+1C. iD. n-i2. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。

A. i-j-1B. i-jC. j-i+1D. 不确定的3. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi 是( )。

A. iB. n-iC. n-i+1D. 不确定4. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 61. 循环队列存储在数组A[0..m]中，则入队时的操作（）。

广义表的定义与实现


⑷ 建立广义表 以广义表字符串S建立广义表。 从前面的讨论可知，非空广义表可分解成表头和表 尾两个部分。建表时，可分别建立（分解为两个子 问题）： 表头有两种情况，为单原子或为列表，当为列表时 与原问题相同； 表尾必为列表，与原问题相同。 设string sever(string& S )函数的功能为: 从广义表字符串S中提取表头串返回，并将S置成表 尾串。

③有深度： 广义表的深度（多少层）定义为广义表书写 形式中括弧的最大重数，因此空表的深度为1， 因为一个"单原子"不是广义表，所以没有"深 度"可言，但可以认为它的深度为0。 如：A，B：1；C：2；D：3； E：无穷大。 ④可递归： 如E。 ⑤可共享： 子表可共享。

5.1.4 广义表的存储结构

if(L->ptr.tp) { cout<<','; printGList(L->ptr.tp,1); } if(k==0) cout<<')'; } else cout<<L->atom; } }
5.2.4 应用
main.cpp

#include "glist.h" int main(){ string S1="((),(e),(a,(b,c,d)))"; string S2="(a,(x,y),((z)))"; string S3="(a,b)"; string S4="()"; GList L; initGList(L); creatGList(L,S2); cout<<getLength(L)<<endl; cout<<getDepth(L)<<endl; printGList(L); }

计算机专业基础综合数据结构(数组和广义表)历年真题试卷汇编4

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编4(总分：60.00，做题时间：90分钟)一、综合题(总题数：13，分数：26.00)1.简述广义表属于线性结构的理由。

【西北大学2000一、5(3分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：广义表是元素为原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一个元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。

从这个意义上说，广义表属于线性结构，只是元素可以是原子，也可以是子表。

)解析：2.数组、广义表与线性表之间有什么样的关系?【西北工业大学1998一、2(4分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：数组是具有相同性质的数据元素的集合，同时每个元素又由唯一下标限定，可以说数组是值和下标偶对的有限集合。

n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n 维数组可以看作其元素是n一1维数组的一个线性表。

而广义表与线性表的关系，见上面21题的解释。

) 解析：3.什么是广义表?请简述广义表和线性表的主要区别。

【北京大学1997二、2(5分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：线性表中的元素可以是各种各样的，但必须具有相同性质，属于同一数据对象。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

广义表的head和tail运算讲解
一、引言
广义表是一种常用的数据结构，它可以包含任意类型的元素，包括其
他广义表。

广义表的h ea d运算和ta il运算是对广义表进行操作的两个
基础运算，本文将对这两个运算进行详细讲解。

二、广义表的定义
广义表是指可以包含各种元素的线性表，其中的元素可以是原子元素（如整数、字符等），也可以是广义表。

广义表由一系列元素组成，用括
号表示，元素之间用逗号隔开。

三、h e a d运算
h e ad运算用于获取广义表的第一个元素。

下面是h ea d运算的示意图：
```
广义表：(a,b,c,d,...)
h e ad运算结果：a
```
四、t a i l运算
t a il运算用于获取广义表除第一个元素外的剩余元素组成的广义表。

下面是t ai l运算的示意图：
```
广义表：(a,b,c,d,...)
t a il运算结果：(b,c,d,...)
```
五、示例与应用
假设有一个广义表`(1,(2,3),(4,(5,6)))`，我们可以通过h ea d运
算和ta il运算来获取广义表中的元素。

-对该广义表进行hea d运算，将返回第一个元素1。

-对该广义表进行ta i l运算，将返回剩余元素组成的广义表`(2,3)`。

广义表的he ad和t ai l运算可以应用于各种场景。

例如，在处理嵌套
列表时，可以通过递归地使用he ad和t ai l运算，来遍历并处理广义表
中的所有元素。

以下是一个示例代码，演示了如何使用he a d和ta il运算来遍历广义表：
```p yt ho n
定义一个函数，用于遍历广义表
d e ft ra ve rs e(ls t):
i f ls t==[]:
r e tu rn
p r in t(ls t.he ad())
t r av er se(l st.t ail())
调用函数进行遍历
l s t=Li st(1,L is t(2,Li st(3,L is t(4,L i st(5)))))
t r av er se(l st)
```
通过以上示例，我们可以清晰地看到广义表的he ad和t ai l运算在遍
历广义表时的作用。

六、总结
本文详细介绍了广义表的he ad和t ai l运算，并给出了示例和应用场景。

he ad运算用于获取广义表的第一个元素，而ta il运算用于获取广义表除第一个元素外的剩余元素组成的广义表。

这两个运算在处理广义表时非常有用，可以通过它们来遍历、处理和操作广义表中的元素。

希望本文对于读者理解和应用广义表的h ea d和t a il运算有所帮助。