当前位置:首页 » 服务存储 » 广义表为什么不能存储树
扩展阅读
webinf下怎么引入js 2023-08-31 21:54:13
堡垒机怎么打开web 2023-08-31 21:54:11

广义表为什么不能存储树

发布时间: 2022-07-24 23:09:47

Ⅰ 广义表和线性表的区别

一、含义不同:

1、线性表,最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。

2、广义表(Lists,又称列表),一种非线性的数据结构,是线性表的一种推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构。

二、用途不同:

1、时间有序表、排序表、和频率有序表都可以看做是线性表的推广。如果按照结点到达结构的时间先后,作为确定结点之间关系的,这样一种线性结构称之为时间有序表。

2、广义表被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中,广义表是一种最基本的数据结构,就连LISP 语言的程序也表示为一系列的广义表。


(1)广义表为什么不能存储树扩展阅读:

由于广义表是对线性表和树的推广,并且具有共享和递归特性的广义表可以和有向图建立对应,因此广义表的大部分运算与这些数据结构上的运算类似。

在此,只讨论广义表的两个特殊的基本运算:取表头head(Ls)和取表尾tail(Ls)。

根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素,它可以是原子,也可以是子表,而其表尾必定是子表。

Ⅱ 二叉树怎样用广义表表示

二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态: (1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)右子树为空的二叉树——(c); (4)左子树为空的二叉树——(d); (5)完全二叉树——(e)注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。 二叉树 (binary tree) 是另一种树型结构,它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 ),并且,二叉树的子树有左右之分,其次序不能任意颠倒 . 二叉树是一种数据结构

Ⅲ 广义表与线性表、树、图的关系

说有关系也没关系说没关系也有关系。他们只是为了解决不同问题而提出的不同结构,可以互相演化但是没有必要演化。

Ⅳ 学了一个学期了,很多地方都不会,广义表是怎么回事啊

这页的可以编译通过了:

#include <stdio.h>
#include <stdlib.h>
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef char elemType;
#endif
/************************************************************************/
/* 以下是关于二叉树操作的11个简单算法 */
/************************************************************************/
struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
};

/* 1.初始化二叉树 */
void initBTree(struct BTreeNode* *bt)
{
*bt = NULL;
return;
}

/* 2.建立二叉树(根据a所指向的二叉树广义表字符串建立) */
void createBTree(struct BTreeNode* *bt, char *a)
{
struct BTreeNode *p;
struct BTreeNode *s[STACK_MAX_SIZE];/* 定义s数组为存储根结点指针的栈使用 */
int top = -1; /* 定义top作为s栈的栈顶指针,初值为-1,表示空栈 */
int k; /* 用k作为处理结点的左子树和右子树,k = 1处理左子树,k = 2处理右子树 */
int i = 0; /* 用i扫描数组a中存储的二叉树广义表字符串,初值为0 */
*bt = NULL; /* 把树根指针置为空,即从空树开始建立二叉树 */
/* 每循环一次处理一个字符,直到扫描到字符串结束符\0为止 */
while(a[i] != '\0'){
switch(a[i]){
case ' ':
break; /* 对空格不作任何处理 */
case '(':
if(top == STACK_MAX_SIZE - 1){
printf("栈空间太小!\n");
exit(1);
}
top++;
s[top] = p;
k = 1;
break;
case ')':
if(top == -1){
printf("二叉树广义表字符串错误!\n");
exit(1);
}
top--;
break;
case ',':
k = 2;
break;
default:
p = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
p->data = a[i];
p->left = p->right = NULL;
if(*bt == NULL){
*bt = p;
}else{
if( k == 1){
s[top]->left = p;
}else{
s[top]->right = p;
}
}
}
i++; /* 为扫描下一个字符修改i值 */
}
return;
}

/* 3.检查二叉树是否为空,为空则返回1,否则返回0 */
int emptyBTree(struct BTreeNode *bt)
{
if(bt == NULL){
return 1;
}else{
return 0;
}
}

/* 4.求二叉树深度 */
int BTreeDepth(struct BTreeNode *bt)
{
if(bt == NULL){
return 0; /* 对于空树,返回0结束递归 */
}else{
int dep1 = BTreeDepth(bt->left); /* 计算左子树的深度 */
int dep2 = BTreeDepth(bt->right); /* 计算右子树的深度 */
if(dep1 > dep2){
return dep1 + 1;
}else{
return dep2 + 1;
}
}
}

/* 5.从二叉树中查找值为x的结点,若存在则返回元素存储位置,否则返回空值 */
elemType *findBTree(struct BTreeNode *bt, elemType x)
{
if(bt == NULL){
return NULL;
}else{
if(bt->data == x){
return &(bt->data);
}else{ /* 分别向左右子树递归查找 */
elemType *p;
if(p = findBTree(bt->left, x)){
return p;
}
if(p = findBTree(bt->right, x)){
return p;
}
return NULL;
}
}
}

/* 6.输出二叉树(前序遍历) */
void printBTree(struct BTreeNode *bt)
{
/* 树为空时结束递归,否则执行如下操作 */
if(bt != NULL){
printf("%c", bt->data); /* 输出根结点的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}

/* 7.清除二叉树,使之变为一棵空树 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}

/* 8.前序遍历 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%c ", bt->data); /* 访问根结点 */
preOrder(bt->left); /* 前序遍历左子树 */
preOrder(bt->right); /* 前序遍历右子树 */
}
return;
}

/* 9.前序遍历 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left); /* 中序遍历左子树 */
printf("%c ", bt->data); /* 访问根结点 */
inOrder(bt->right); /* 中序遍历右子树 */
}
return;
}

/* 10.后序遍历 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left); /* 后序遍历左子树 */
postOrder(bt->right); /* 后序遍历右子树 */
printf("%c ", bt->data); /* 访问根结点 */
}
return;
}

/* 11.按层遍历 */
void levelOrder(struct BTreeNode *bt)
{
struct BTreeNode *p;
struct BTreeNode *q[QUEUE_MAX_SIZE];
int front = 0, rear = 0;
/* 将树根指针进队 */
if(bt != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = bt;
}
while(front != rear){ /* 队列非空 */
front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */
p = q[front];
printf("%c ", p->data);
/* 若结点存在左孩子,则左孩子结点指针进队 */
if(p->left != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->left;
}
/* 若结点存在右孩子,则右孩子结点指针进队 */
if(p->right != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->right;
}
}
return;
}

/************************************************************************/

int main(int argc, char *argv[])
{
struct BTreeNode *bt; /* 指向二叉树根结点的指针 */
char *b; /* 用于存入二叉树广义表的字符串 */
elemType x, *px;
initBTree(&bt);
printf("输入二叉树广义表的字符串:\n");
/* scanf("%s", b); */
b = "a(b(c), d(e(f, g), h(, i)))";
createBTree(&bt, b);
if(bt != NULL)
printf(" %c ", bt->data);
printf("以广义表的形式输出:\n");
printBTree(bt); /* 以广义表的形式输出二叉树 */
printf("\n");
printf("前序:"); /* 前序遍历 */
preOrder(bt);
printf("\n");
printf("中序:"); /* 中序遍历 */
inOrder(bt);
printf("\n");
printf("后序:"); /* 后序遍历 */
postOrder(bt);
printf("\n");
printf("按层:"); /* 按层遍历 */
levelOrder(bt);
printf("\n");
/* 从二叉树中查找一个元素结点 */
printf("输入一个待查找的字符:\n");
scanf(" %c", &x); /* 格式串中的空格跳过空白字符 */
px = findBTree(bt, x);
if(px){
printf("查找成功:%c\n", *px);
}else{
printf("查找失败!\n");
}
printf("二叉树的深度为:");
printf("%d\n", BTreeDepth(bt));
clearBTree(&bt);
return 0;
}

Ⅳ 广义表一般采用链式存储结构,而不采用顺序存储结构,是什么原因

广义表 的元素可以是广义表 顺序存储的话 如果添加或者删除一个元素的话 开销太大吧

Ⅵ 任何广义表都可以用树形结构表示

错误,树结构可以用广义表表示

Ⅶ 如何用广义表建树~

void CreateBiTree(BiTree *T,char *a)
{
BiTree s[10];
int j, k;
BiTree p;
int top=-1;
T=NULL;
printf("输入树共有多少个结点\n");
scanf("%d",&j);
s=(BiTree *)malloc(j*sizeof(BiTNode));
if(!s)
exit(OVERFLOW);
int i=0;
while(a[i]!='\0')
{
switch(a[i])
{
case ' ':
break;
case '(':
if(top==10)
{
printf("空间太小\n");
exit(1);
}
top++;
s[top]=p;
k=1;
break;
case ')':
if(top==-1)
{
printf("二叉树广义表字符串有错\n");
exit(-1);
}
top--;
break;
case ',':
k=2;
break;
default:

p=(BiTree)malloc(sizeof(BiTNode));
if(!p)
exit(OVERFLOW);

p->data=a[i];
p->Lchild=p->Rchild=NULL;
if(T==NULL)
{
T=&p;
}
else
{
if(k==1)
s[top]->Lchild=p;
else
s[top]->Rchild=p;

}
}
i++;
}
}

Ⅷ 广义表的两种存储结构有什么不同

CPU内部
第一层:通用寄存器文件
第二层:指令和数据缓冲栈
第三层:缓存
第四层:主存储器(DRAM)
第五层:在线外部存储(硬盘驱动器)
第六层:离线外部存储(磁带,光盘存储器等)
层次结构,主要体现在内存的存取速度~~~ ~~
①多个内存和使它们并行工作。本质:添加瓶颈的数目份,使它们并行地工作,从而减缓固定的瓶颈。

②多级存储系统,特别是高速缓存技术,该技术是一种影响系统的性能,以减少存储器的带宽,该方案的最佳结构。本质的:瓶颈构件分割成多个管道组件,并增加运行时间的重叠,以增加速度,减缓固定瓶颈。

③设置各种内部缓冲存储器的微处理器,以减少对存储器的访问的压力。增加寄存器的数量在CPU中,也大大缓解了存储器中的压力。精华液:缓冲技术来减缓临时瓶颈。

Ⅸ 数据结构广义表的问题

第一章 数据结构基本概念
1、基本概念:理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。
2、面向对象概念:理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法,我们采用了一种最流行的说法,即Coad与Yourdon 给出的定义:面向对象 = 对象 + 类 + 继承 + 通信。
要点:
·抽象数据类型的封装性
·面向对象系统结构的稳定性
·面向对象方法着眼点在于应用问题所涉及的对象
3、数据结构的抽象层次:理解用对象类表示的各种数据结构
4、算法与算法分析:理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。
要点:·算法与程序的不同之处需要从算法的特性来解释
·算法的正确性是最主要的要求
·算法的可读性是必须考虑的
·程序的程序步数的计算与算法的事前估计
·程序的时间代价是指算法的渐进时间复杂性度量

第二章 数组
1、作为抽象数据类型的数组:数组的定义、数组的按行顺序存储与按列顺序存储
要点:
·数组元素的存放地址计算
2、顺序表:顺序表的定义、搜索、插入与删除
要点:
·顺序表搜索算法、平均比较次数的计算
·插入与删除算法、平均移动次数的计算
3、多项式:多项式的定义
4、字符串:字符串的定义及其操作的实现
要点:
·串重载操作的定义与实现

第三章 链接表
1、单链表:单链表定义、相应操作的实现、单链表的游标类。
要点:
·单链表的两种定义方式(复合方式与嵌套方式)
·单链表的搜索算法与插入、删除算法
·单链表的递归与迭代算法
2、循环链表:单链表与循环链表的异同
3、双向链表:双向链表的搜索、插入与删除算法、链表带表头结点的优点
4、多项式的链接表示

第四章 栈与队列
1、栈:栈的特性、栈的基本运算
要点:
·栈的数组实现、栈的链表实现
·栈满及栈空条件、抽象数据类型中的先决条件与后置条件
2、栈的应用:用后缀表示计算表达式,中缀表示改后缀表示
3、队列:队列的特性、队列的基本运算
要点:
·队列的数组实现:循环队列中队头与队尾指针的表示,队满及队空条件
·队列的链表实现:链式队列中的队头与队尾指针的表示、
4、双向队列:双向队列的插入与删除算法
5、优先级队列:优先级队列的插入与删除算法

第五章 递归与广义表
1、递归:递归的定义、递归的数据结构、递归问题用递归过程求解
要点:·链表是递归的数据结构,可用递归过程求解有关链表的问题
2、递归实现时栈的应用
要点:·递归的分层(树形)表示:递归树
·递归深度(递归树的深度)与递归工作栈的关系
·单向递归与尾递归的迭代实现
3、广义表:广义表定义、广义表长度、广义表深度、广义表表头、广义表表尾
要点:
·用图形表示广义表的存储结构
·广义表的递归算法

第六章 树与森林
1、树:树的定义、树的基本运算
要点:
·树的分层定义是递归的
·树中结点个数与高度的关系
2、二叉树:二叉树定义、二叉树的基本运算
要点:
·二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数
·完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置
·二叉树的前序·中序·后序·层次遍历
·前序
·中序
·后序的线索化二叉树、前驱与后继的查找方法
3、霍夫曼树:霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算
4、树的存储:树的广义表表示、树的双亲表示、树与二叉树的对应关系、树的先根·中根·后根·层次遍历。
5、堆:堆的定义、堆的插入与删除算法
要点:
·形成堆时用到的向下调整算法及形成堆时比较次数的上界估计
·堆插入时用到的向上调整算法

第七章 集合与搜索
1、集合的概念:集合的基本运算、集合的存储表示
要点:
·用位数组表示集合时集合基本运算的实现
·用有序链表表示集合时集合基本运算的实现
2、并查集:并查集定义、并查集的三种基本运算的实现
3、基本搜索方法
要点:
·对一般表的顺序搜索算法(包括有监视哨和没有监视哨)
·对有序顺序表的顺序搜索算法、用判定树(即扩充二叉搜索树)描述搜索,以及平均搜索长度(成功与不成功)的计算。
·对有序顺序表的折半搜索算法、用判定树(即扩充二叉搜索树)描述搜索,以及平均搜索长度(成功与不成功)的计算。
4、二叉搜索树:
要点:
·动态搜索树与静态搜索树的特性
·二叉搜索树的定义、二叉搜索树上的搜索算法、二叉搜索树搜索时的平均搜索长度(成功与不成功)的计算。
·AVL树结点上的平衡因子、AVL树的平衡旋转方法
·高度为h的AVL树上的最少结点个数与最多结点个数
· AVL树的搜索方法、插入与删除方法

第八章 图
1、图:图的定义与图的存储表示
要点:
·邻接矩阵表示(通常是稀疏矩阵)
·邻接表与逆邻接表表示
·邻接多重表(十字链表)表示
2、深度优先遍历与广度优先遍历
要点:
·生成树与生成树林的定义
·深度优先搜索是个递归的过程,而广度优先搜索是个非递归的过程
·为防止重复访问已经访问过的顶点,需要设置一个访问标志数组visited
3、图的连通性
要点:
·深度优先搜索可以遍历一个连通分量上的所有顶点
·对非连通图进行遍历,可以建立一个生成森林
·对强连通图进行遍历,可能建立一个生成森林
·关节点的计算和以最少的边构成重连通图
4、最小生成树
要点:
·对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树
·会画出用Kruskal算法及Prim算法构造最小生成树的过程
5、单源最短路径
要点:
·采用逐步求解的方式求某一顶点到其他顶点的最短路径
·要求每条边的权值必须大于零
6、活动网络
要点:
·拓扑排序、关键路径、关键活动、AOE网
·拓扑排序将一个偏序图转化为一个全序图。
·为实现拓扑排序,要建立一个栈,将所有入度为零的顶点进栈
·关键路径的计算

第九章 排序
1、基本概念:关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序
2、插入排序:
要点:
·当待排序的关键码序列已经基本有序时,用直接插入排序最快
3、选择排序:
要点:
·用直接选择排序在一个待排序区间中选出最小的数据时,与区间第一个数据对调,而不是顺次后移。这导致方法不稳定。
·当在n个数据(n很大)中选出最小的5 ~ 8个数据时,锦标赛排序最快
·锦标赛排序的算法中将待排序的数据个数n补足到2的k次幂2k-1<n≤2k
·在堆排序中将待排序的数据组织成完全二叉树的顺序存储。
4、交换排序:
要点:
·快速排序是一个递归的排序方法
·当待排序关键码序列已经基本有序时,快速排序显着变慢。
5、二路归并排序:
要点:
·归并排序可以递归执行
·归并排序需要较多的附加存储。可以采用一种"推拉法"(参见教科书上习题)实现归并排序,算法的时间复杂度为O (n)、空间复杂度为O(1)
·归并排序对待排序关键码的初始排列不敏感,排序速度较稳定
6、外排序
要点:
·多路平衡归并排序的过程、I/O缓冲区个数的配置
·外排序的时间分析、利用败者树进行多路平衡归并
·利用置换选择方法生成不等长的初始归并段
·最佳归并树的构造及WPL的计算

第十章 索引与散列
1、线性索引:
要点:
·密集索引、稀疏索引、索引表计算
·基于属性查找建立倒排索引、单元式倒排表
2、动态搜索树
要点:
·平衡的m路搜索树的定义、搜索算法
·B树的定义、B树与平衡的m路搜索树的关系
·B树的插入(包括结点分裂)、删除(包括结点调整与合并)方法
·B树中结点个数与高度的关系
·B+树的定义、搜索、插入与删除的方法
3、散列表
要点:
·散列函数的比较
·装填因子 a 与平均搜索长度的关系,平均搜索长度与表长m及表中已有数据对象个数n的关系
·解决地址冲突的(闭散列)线性探查法的运用,平均探查次数的计算
·线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态
·线性探查法中的聚集问题
·解决地址冲突的(闭散列)双散列法的运用,平均探查次数的计算
·双散列法中再散列函数的设计要求与表长m互质,为此m设计为质数较宜
·解决地址冲突的(闭散列)二次散列法的运用,平均探查次数的计算
·注意:二次散列法中装填因子 a 与表长m的设置
·解决地址冲突的(开散列)链地址法的运用,平均探查次数的计算

我们原来也学过数据结构,个人觉得数组,栈与队列 ,递归与广义表,树与

森林(尤其是二叉树),图 ,排序这些比较重要,应该好好看