如何通过头指针和尾指针来描述广义表?
时间: 2024-06-21 22:02:14 浏览: 9
在广义表中,一个元素可以是一个原子或者另一个广义表,因此需要使用递归的方式来描述广义表。广义表的存储通常使用头指针和尾指针的方式来表示。其中头指针指向广义表的第一个元素,而尾指针则指向广义表的最后一个元素。
具体地说,当广义表为空时,头指针和尾指针都为NULL。当广义表只有一个元素时,头指针和尾指针都指向该元素。当广义表有多个元素时,头指针指向第一个元素,尾指针指向最后一个元素的表尾部分。
对于一个非空的广义表,我们可以将其表示为一个二元组:(h, t),其中h为头指针,t为尾指针。如果当前元素是原子,则头指针和尾指针都指向该原子;如果当前元素是一个子表,则头指针和尾指针分别指向该子表的头和尾。
例如,下面是一个包含三个元素的广义表:(1, (2, 3), NULL),其中1是原子,(2, 3)是一个子表。这个广义表的头指针为1,尾指针为NULL。子表(2, 3)的头指针为2,尾指针为3。
相关问题
C语言广义表如何创建表头和表尾
创建广义表的表头和表尾需要涉及到链表的概念。表头是广义表的第一个节点,包含指向表尾的指针和指向第一个元素的指针。表尾是指最后一个元素的节点,包含指向下一个元素的指针和指向表头的指针。以下是具体的创建方法:
1. 创建表头节点,包含指向表尾和第一个元素的指针,其中表尾指针为空,第一个元素指针指向NULL。
2. 以链表的方式逐个创建广义表的元素节点,将每个元素节点的指针指向下一个元素节点,直到创建完最后一个元素节点。
3. 创建表尾节点,包含指向表头和下一个元素的指针,其中下一个元素指针指向第一个元素节点。
4. 将表头节点的表尾指针指向表尾节点,完成广义表的创建。
代码示例:
```c
typedef struct node{
int tag; // 节点类型,0表示元素节点,1表示子表节点
union{
int data; // 元素节点的值
struct node *sublist; // 子表节点的指针
} value;
struct node *next; // 指向下一个节点
} GLNode, *GList;
// 创建表头节点和表尾节点
GList createGList() {
GList head = (GList)malloc(sizeof(GLNode));
GList tail = (GList)malloc(sizeof(GLNode));
head->tag = tail->tag = 1;
head->value.sublist = tail->value.sublist = NULL;
head->next = tail;
tail->next = head;
return head;
}
// 创建元素节点
GList createGLNode(int data) {
GList node = (GList)malloc(sizeof(GLNode));
node->tag = 0;
node->value.data = data;
node->next = NULL;
return node;
}
// 将元素节点加入广义表的表尾
void insertGLNode(GList tail, int data) {
GList node = createGLNode(data);
node->next = tail;
GList p = tail->next;
while (p->next != tail) {
p = p->next;
}
p->next = node;
}
// 创建子表节点并逐个加入元素节点
GList createSublist(int *data, int len) {
GList sublist = createGList();
for (int i = 0; i < len; i++) {
insertGLNode(sublist, data[i]);
}
return sublist;
}
// 将子表节点加入广义表的表尾
void insertSublist(GList tail, int *data, int len) {
GList sublist = createSublist(data, len);
sublist->next = tail;
GList p = tail->next;
while (p->next != tail) {
p = p->next;
}
p->next = sublist;
}
```
以上示例代码实现了广义表的创建,可以通过调用`createGList()`、`insertGLNode()`和`insertSublist()`函数来实现。其中,`createGLNode()`用于创建元素节点,`createSublist()`用于创建子表节点并逐个加入元素节点。`insertGLNode()`和`insertSublist()`用于将节点加入广义表的表尾。
广义表取表头表尾_广义表的深度和长度(C语言)详解
广义表是一种数据结构,它可以看做是一个链表的集合,其中每个节点可以是一个单独的元素或者是一个子表。广义表的深度指的是广义表中嵌套的子表的最大层数,而广义表的长度指的是广义表中元素的总个数。
取广义表的表头和表尾可以使用如下的代码:
```C
typedef struct GLNode{
int tag; // 标志域,0表示单元素,1表示子表
union{
char data;
struct GLNode *sublist;
}val;
struct GLNode *next;
}GLNode, *GList;
// 取广义表的表头
int getHead(GList L, char *head){
if(L == NULL || L->tag == 1) return 0; // 空表或者表头为子表,返回0
*head = L->val.data; // 取出表头元素
return 1;
}
// 取广义表的表尾
int getTail(GList L, GList *tail){
if(L == NULL) return 0; // 空表,返回0
*tail = L->next; // 取出表尾指针
return 1;
}
```
其中,广义表使用链表的形式来存储,每个节点中的tag标志域表示节点的类型,0表示单元素,1表示子表。如果节点是单元素,则val域存储该元素的值;如果节点是子表,则val域存储该子表的头指针。
使用上述代码可以方便地取出广义表的表头和表尾,但是需要注意的是,由于广义表中可能嵌套子表,因此取表尾时需要返回一个指向子表的头指针。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)