广义表的表尾

件综合课程 广义表的应用 图书借阅管理系统

二〇一四 年 六 月

设计

软

广义表的应用

一、问题陈述

由于广义表在结构上较线性表复杂得多，因此，广义表的运算也不如线性表简单。本设计要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度、求逆表等。

本设计用一个主控菜单程序控制，共分为6个子系统。 （1）建立广义表 （2）输出广义表 （3）结点的查找 （4）求广义表表头 （5）求广义表表尾 （6）求广义表的深度

二、需求分析

1.菜单函数

使用数字0-6来选择菜单项，超出此范围时，提示输入错误，并重新输入。运行程序时，先输入一个广义表，回车后，调用各功能函数，则出现功能菜单，输入的一个数字，该数字用sn存储，使用choose（）接受数字输入，该函数的返回值提供给主函数；则主函数使用while循环实现重复选择，以实现不同的广义表菜单功能。

2.主函数

包含的功能函数有：输出广义表、广义表深度、广义表表头、广义表表尾、广义表查找、广义表逆置6个函数。运行程序时，首先执行主函数，根据提示，建立广义表，广义表中的元素应单独输入，每输入一个字符，回车，广义表输入完成时，应再次输入“）”，表示

本课课题： 广义表

教学目的： 掌握广义表的定义，它的链接存储结构，以及求广义表长度、深度的方法和递归算法 教学重点： 广义表的操作及意义 教学难点： 广义表存储结构 教学过程： 一、广义表的定义

广义表是线性表的推广，其表中的元素可以是另一个广义表,或其自身。

对于一个非空的广义表来说，它的第一个元素称为该广义表的表头，除第一个元素外的所有元素构成的表称为该广义表的表尾。

一个表的尝试是指该表中括号嵌套的最大次数。 广义表的定义: ADT GList{

数据对象:D={i=1,2,...,n>=0;ei(-AtomSet或ei(-GList, AtomSet为某个数据对象}

数据关系:R1={|ei-1,ei(-D,2=

操作结果:创建空的广义表L CreateGList(&L,S);

初始条件:S是广义表的书写形式串 操作结果:由S创建广义表L DestroyGlist(&L); 初始条件:广义表L存在 操作结果:销毁广义表L CopyGlist(&T,L); 初始条件:广义表L存在

操作结果:由广义表L复制得到广义表T GListLength(L); 初始条件:广义表L存在

操作结果:求广义表L的长度,即元素个数 GListDepth(L

第5章 数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：

①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120

G. 156 H. 234 I. 276 J. 282 K. 283 L. 288

⑤： A．行与列的上界相同

数据结构(Java)(第三版) 课件

数据结构(Java版)

数据结构(Java)(第三版) 课件

《数据结构(Java版)》 第0章 Java程序设计基础 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 排序 第9章 查找 第10章 综合应用设计

数据结构(Java)(第三版) 课件

第5章 数组和广义表 5.1 数组 5.2 特殊矩阵的压缩存储 5.3 广义表

数据结构(Java)(第三版) 课件

本章学习目标 目的：了解包含子结构的线性结构。 要求：理解多维数组的存储结构，了解 特殊矩阵压缩存储，了解广义表。 重点： 难点：广义表的表示和实现。

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

5.1 数组5.1.1 一维数组5.1.2 多维数组

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

5.1.1 一维数组

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

数组(array)是一种数据

第5章 数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：

①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120

G. 156 H. 234 I. 276 J. 282 K. 283 L. 288

⑤： A．行与列的上界相同

第4章串、数组和广义表

一．填空题

1. 串的数据元素是字符，顺序，链式，即只有当两个串的长度相等，并且各个对应位置的

字符都相等时才相等。

2. 零个字符的串、零；由一个或多个空格字符组成的串、其包含的空格个数 3. 任意个连续的字符组成的子序列 4. 模式匹配，Index(S,T,pos)，S 5. 14 6. 5

7. LOC (A[0][0])+(n*i+j)*k 8. 326 9. 1208

10. 行号，列号，元素

二．单项选择题

题号 答案 题号 答案 1 B 11 B 2 B 12 B 3 B 13 A 4 B 14 LKCID 5 D 15 D 6 C 16 D 7 DB 17 CB 8 C 9 C 10 B 三．算法设计题

1.

#include #define Maxsize 100 typedef struct {

char data[Maxsize]; int length; }Sqstring;

void Strassign(Sqstring *s,char cstr[]) { int i;

for(i=0;cstr[i]!='\\0';i++) s->data[i]=cstr[i];

s

数组和义广表数的组定义数组的顺序表和示现实矩阵的缩存储压义表广的义定广表义存的结储构义表的递广归算法福州大学至诚学院

组的数象抽据类数型定的义ADTrrAya{据数对：D=象a{j 12 j…n| jij 0, .=.,. b -i1,i= 1, 2,., .n,

n>,0称为数组维的数，bi是数第组 i的长度，维i是数j组元的素第 i下维标 a, j 1j2… j∈EnlmSete}据数系关R=:{R1,R,2 ..,.Rn}R i{<a=j1...i..jj.n,aj1. ..ji1...j+>n 0≤jk|≤kb-, 11k≤n且≤≠k, i≤0ijbi≤ -2, a1…jijj… n,aj 1ji…1+…n∈Dj, i=2,. ., n .}州福学大至学院诚

基操作本：In itrArya&(A n,, obudn, 1.., bo.udn)n操作结：若果数维n和各长度合维，法构造相应则的数 A,组并返回KO Dest。roAyrar(yA)&操作结：果毁数销组A。Valeu(A,e&,i ndx1, e... inde,n)x初始条：A件是n维数组e,元素为量变随后， n个是标下。操作结值：果若各下不标界，则 e超赋为

第五章 数组和广义表 一、选择题

1．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．696 2．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ ）。

A. 10 B. 19 C. 28 D. 55

3．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相

同的（ ）。

A．行号 B．列号 C．元素值 D．地址

4．设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。

A．3700 B．

第五章数组与广义表

一．选择题

1．下面的说法不正确的是____________。

A．数组是一种线性结构 B．数组是一种定长的线性表结构

C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和 排序等

D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操 作

分析：数组的主要操作是存取、修改、检索和排序。数组没有插入和修改 错误。答案应选择 C。

2．一维数组 A 采用顺序存储结构，每个元素占用 6 个字节，第 6 个元素 的起始地址为 100，则该数组的首地址是 。

A．64 B．28 C．70 D．90

分析：设数组元素的首地址为 x，则存在关系 x+5*6=100，因此 x 为 70，答 案应选择 C。

3．稀疏矩阵采用压缩存储的目的主要是______________ 。 A．表达变得简单 B．对矩阵元素的存取变得简单

C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销 分析：答案应选择 D。

4．若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对 角线上所有元素)依次存放于一维数组 B［1..(n(n+1))/2］中，

题目部分，(卷面共有95题,608.0分,各大题标有题量和总分)

一、单项选择题(22小题,共44.0分) (2分)[1]

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为 A、 13 B、 33 C、 18 D、 40 (2分)[2]

二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,?,8,列下标j=1,2,?,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A、 A[8,5] B、 A[3,10] C、 A[5,8] D、 A[0,9] (2分)[3]

已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =

A、（a） B、 A C、 a D、（b） E、 b