fbpx
维基百科

广义表

九月 15, 2023

广义表（英語：Generalized List）是一种非线性的数据结构。但如果广义表的每个元素都是原子，它就变成了线性表。广义表广泛地用于人工智能等领域的LISP语言。

广义表一般记作 LS = (a1, a2, ···, an), n是它的长度，ai可以是单个元素(原子)，也可以是广义表(子表)，当广义表非空时，称第一个元素a1为LS的表头，称其余元素组成的表为LS的表尾。注意：表头是元素(可以是原子，也可以是广表)，表尾一定是广义表。[1]E=(a, E)是一个递归的表。D=(( ),(e),(a,(b,c,d)))是多层次的广义表，长度为3，深度为3。例：((a),a)的表头是(a)，表尾是(a)，((a))的表头是(a)，表尾是( )。

头尾链表存储表示 编辑

存储结构 编辑 

// 广义表的头尾链表存储表示 typedef enum {ATOM, LIST} ElemTag; // ATOM==0：原子，LIST==1：子表 typedef struct GLNode {  ElemTag tag;  // 公共部分，用于区分原子结点和表结点  union {  // 原子结点和表结点的联合部分  AtomType atom;  // atom是原子结点的值域，AtomType由用户定义  struct {  struct GLNode *hp, *tp;  } ptr;  // ptr是表结点的指针域，prt.hp和ptr.tp分别指向表头和表尾  } a; } *GList, GLNode; // 广义表类型

基本操作 编辑 

// 广义表的头尾链表存储的基本操作(11个) #include"func5-1.c" void InitGList(GList *L) {  // 创建空的广义表L  *L = NULL; }  void CreateGList(GList *L, SString S) {  // 采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()"  SString sub, hsub, emp;  GList p, q;  StrAssign(emp, "()"); // 空串emp="()"  if (!StrCompare(S, emp)) // S="()"  *L = NULL; // 创建空表  else { // S不是空串  *L = (GList)malloc(sizeof(GLNode));  if (!*L) // 建表结点  exit(OVERFLOW);  if (StrLength(S) == 1) {  // S为单原子，只会出现在递归调用中  (*L)->tag = ATOM;  (*L)->a.atom = S[1]; // 创建单原子广义表  } else { // S为表  (*L)->tag = LIST;  p = *L;  SubString(sub, S, 2, StrLength(S) - 2);  // 脱外层括号(去掉第1个字符和最后1个字符)给串sub  do {  // 重复建n个子表  sever(sub, hsub); // 从sub中分离出表头串hsub  CreateGList(&p->a.ptr.hp, hsub);  q = p;  if (!StrEmpty(sub)) { // 表尾不空  p = (GLNode *)malloc(sizeof(GLNode));  if (!p)  exit(OVERFLOW);  p->tag = LIST;  q->a.ptr.tp = p;  }  } while (!StrEmpty(sub));  q->a.ptr.tp = NULL;  }  } } void DestroyGList(GList *L) {  // 销毁广义表L  GList q1, q2;  if (*L) {  if ((*L)->tag == LIST) { // 删除表结点  q1 = (*L)->a.ptr.hp; // q1指向表头  q2 = (*L)->a.ptr.tp; // q2指向表尾  DestroyGList(&q1); // 销毁表头  DestroyGList(&q2); // 销毁表尾  }  free(*L);  *L = NULL;  } }  void CopyGList(GList *T, GList L) {  // 采用头尾链表存储结构，由广义表L复制得到广义表T  if (!L) // 复制空表  *T = NULL;  else {  *T = (GList)malloc(sizeof(GLNode));  // 建表结点  if (!*T)  exit(OVERFLOW);  (*T)->tag = L->tag;  if (L->tag == ATOM)  (*T)->a.atom = L->a.atom; // 复制单原子  else {  CopyGList(&((*T)->a.ptr.hp), L->a.ptr.hp);  // 递归复制子表  CopyGList(&((*T)->a.ptr.tp), L->a.ptr.tp);  }  } }  int GListLength(GList L) {  /* 返回广义表的长度，即元素个数 */  int len = 0;  while (L) {  L = L->a.ptr.tp;  len++;  }  return len; }  int GListDepth(GList L) {  /* 采用头尾链表存储结构，求广义表L的深度。*/  int max, dep;  GList pp;  if (!L)  return 1; /* 空表深度为1 */  if (L->tag == ATOM)  return 0; /* 原子深度为0，只会出现在递归调用中 */  for (max = 0, pp = L; pp; pp = pp->a.ptr.tp) {  dep = GListDepth(pp->a.ptr.hp); /* 递归求以pp->a.ptr.hp为头指针的子表深度 */  if (dep > max)  max = dep;  }  return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */ }  Status GListEmpty(GList L) {  /* 判定广义表是否为空 */  if (!L)  return TRUE;  else  return FALSE; }  GList GetHead(GList L) {  /* 生成广义表L的表头元素，返回指向这个元素的指针 */  GList h, p;  if (!L) /* 空表无表头 */  return NULL;  p = L->a.ptr.hp; /* p指向L的表头元素 */  CopyGList(&h, p); /* 将表头元素复制给h */  return h; }  GList GetTail(GList L) {  /* 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针 */  GList t;  if (!L) /* 空表无表尾 */  return NULL;  CopyGList(&t, L->a.ptr.tp); /* 将L的表尾拷给t */  return t; }  void InsertFirst_GL(GList *L, GList e) {  /* 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头) */  GList p = (GList)malloc(sizeof(GLNode)); /* 生成新结点 */  if (!p)  exit(OVERFLOW);  p->tag = LIST; /* 结点的类型是表 */  p->a.ptr.hp = e; /* 表头指向e */  p->a.ptr.tp = *L; /* 表尾指向原表L */  *L = p; /* L指向新结点 */ }  void DeleteFirst_GL(GList *L, GList *e) {  // 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值  GList p = *L; // p指向第1个结点  *e = (*L)->a.ptr.hp; // e指向L的表头  *L = (*L)->a.ptr.tp; // L指向原L的表尾  free(p); // 释放第1个结点 }  void Traverse_GL(GList L, void(*v)(AtomType)) {  // 利用递归算法遍历广义表L  if (L) // L不空  if (L->tag == ATOM) // L为单原子  v(L->a.atom);  else { // L为广义表  Traverse_GL(L->a.ptr.hp, v);  // 递归遍历L的表头  Traverse_GL(L->a.ptr.tp, v);  // 递归遍历L的表尾  } }

扩展线性链表存储表示 编辑

存储结构 编辑 

// 广义表的扩展线性链表存储表示 typedef enum {ATOM, LIST} ElemTag; // ATOM==0：原子，LIST==1：子表 typedef struct GLNode1 {  ElemTag tag;  // 公共部分，用于区分原子结点和表结点  union {  // 原子结点和表结点的联合部分  AtomType atom; // 原子结点的值域  struct GLNode1 *hp; // 表结点的表头指针  } a;  struct GLNode1 *tp;  // 相当于线性链表的next，指向下一个元素结点 } *GList1, GLNode1; // 广义表类型GList1是一种扩展的线性链表

基本操作 编辑 

// 广义表的扩展线性链表存储(的基本操作(13个) #include"func5-1.c"  void InitGList(GList1 *L) {  // 创建空的广义表L  *L = NULL; }  void CreateGList(GList1 *L, SString S) {  // 采用扩展线性链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()"  SString emp, sub, hsub;  GList1 p;  StrAssign(emp, "()"); /* 设emp="()" */  *L = (GList1)malloc(sizeof(GLNode1));  if (!*L) /* 建表结点不成功 */  exit(OVERFLOW);  if (!StrCompare(S, emp)) { /* 创建空表 */  (*L)->tag = LIST;  (*L)->a.hp = (*L)->tp = NULL;  } else if (StrLength(S) == 1) { /* 创建单原子广义表 */  (*L)->tag = ATOM;  (*L)->a.atom = S[1];  (*L)->tp = NULL;  } else { /* 创建一般表 */  (*L)->tag = LIST;  (*L)->tp = NULL;  SubString(sub, S, 2, StrLength(S) - 2);  // 脱外层括号(去掉第1个字符和最后1个字符)给串sub  sever(sub, hsub); // 从sub中分离出表头串hsub  CreateGList(&(*L)->a.hp, hsub);  p = (*L)->a.hp;  while (!StrEmpty(sub)) { // 表尾不空，则重复建n个子表  sever(sub, hsub); // 从sub中分离出表头串hsub  CreateGList(&p->tp, hsub);  p = p->tp;  };  } }  void DestroyGList(GList1 *L) {  /* 初始条件：广义表L存在。操作结果：销毁广义表L */  GList1 ph, pt;  if (*L) { /* L不为空表 */  /* 由ph和pt接替L的两个指针 */  if ((*L)->tag) /* 是子表 */  ph = (*L)->a.hp;  else /* 是原子 */  ph = NULL;  pt = (*L)->tp;  DestroyGList(&ph); /* 递归销毁表ph */  DestroyGList(&pt); /* 递归销毁表pt */  free(*L); /* 释放L所指结点 */  *L = NULL; /* 令L为空 */  } }  void CopyGList(GList1 *T, GList1 L) {  /* 初始条件：广义表L存在。操作结果：由广义表L复制得到广义表T */  *T = NULL;  if (L) { /* L不空 */  *T = (GList1)malloc(sizeof(GLNode1));  if (!*T)  exit(OVERFLOW);  (*T)->tag = L->tag; /* 复制枚举变量 */  if (L->tag == ATOM) /* 复制共用体部分 */  (*T)->a.atom = L->a.atom; /* 复制单原子 */  else  CopyGList(&(*T)->a.hp, L->a.hp); /* 复制子表 */  if (L->tp == NULL) /* 到表尾 */  (*T)->tp = L->tp;  else  CopyGList(&(*T)->tp, L->tp); /* 复制子表 */  } }  int GListLength(GList1 L) {  /* 初始条件：广义表L存在。操作结果：求广义表L的长度，即元素个数 */  int len = 0;  GList1 p = L->a.hp; /* p指向第1个元素 */  while (p) {  len++;  p = p->tp;  };  return len; }  int GListDepth(GList1 L) {  /* 初始条件：广义表L存在。操作结果：求广义表L的深度 */  int max, dep;  GList1 pp;  if (L == NULL || L->tag == LIST && !L->a.hp)  return 1; /* 空表深度为1 */  else if (L->tag == ATOM)  return 0; /* 单原子表深度为0，只会出现在递归调用中 */  else /* 求一般表的深度 */  for (max = 0, pp = L->a.hp; pp; pp = pp->tp) {  dep = GListDepth(pp); /* 求以pp为头指针的子表深度 */  if (dep > max)  max = dep;  }  return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */ }  Status GListEmpty(GList1 L) {  /* 初始条件：广义表L存在。操作结果：判定广义表L是否为空 */  if (!L || L->tag == LIST && !L->a.hp)  return OK;  else  return ERROR; }  GList1 GetHead(GList1 L) {  /* 生成广义表L的表头元素，返回指向这个元素的指针 */  GList1 h, p;  if (!L || L->tag == LIST && !L->a.hp) /* 空表无表头 */  return NULL;  p = L->a.hp->tp; /* p指向L的表尾 */  L->a.hp->tp = NULL; /* 截去L的表尾部分 */  CopyGList(&h, L->a.hp); /* 将表头元素复制给h */  L->a.hp->tp = p; /* 恢复L的表尾(保持原L不变) */  return h; }  GList1 GetTail(GList1 L) {  // 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针  GList1 t, p;  if (!L || L->tag == LIST && !L->a.hp) // 空表无表尾  return NULL;  p = L->a.hp; // p指向表头  L->a.hp = p->tp; // 在L中删去表头  CopyGList(&t, L); // 将L的表尾拷给t  L->a.hp = p; // 恢复L的表头(保持原L不变)  return t; }  void InsertFirst_GL(GList1 *L, GList1 e) {  // 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头)  GList1 p = (*L)->a.hp;  (*L)->a.hp = e;  e->tp = p; }  void DeleteFirst_GL(GList1 *L, GList1 *e) {  // 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值  if (*L && (*L)->a.hp) {  *e = (*L)->a.hp;  (*L)->a.hp = (*e)->tp;  (*e)->tp = NULL;  } else  *e = *L; }  void Traverse_GL(GList1 L, void(*v)(AtomType)) {  // 利用递归算法遍历广义表L  GList1 hp;  if (L) { // L不空  if (L->tag == ATOM) { // L为单原子  v(L->a.atom);  hp = NULL;  } else // L为子表  hp = L->a.hp;  Traverse_GL(hp, v);  Traverse_GL(L->tp, v);  } }

参考资料 编辑

  1. ^ 崔巍; 何玉洁; 郁红英. 数据库技术教程(三级). 清华大学出版社. 2005: P59. ISBN 9787302103769. 

九月 15, 2023
广义表, 英語, generalized, list, 是一种非线性的数据结构, 但如果的每个元素都是原子, 它就变成了线性表, 广泛地用于人工智能等领域的lisp语言, 一般记作, n是它的长度, ai可以是单个元素, 原子, 也可以是, 子表, 当非空时, 称第一个元素a1为ls的表头, 称其余元素组成的表为ls的表尾, 注意, 表头是元素, 可以是原子, 也可以是广表, 表尾一定是, 是一个递归的表, 是多层次的, 长度为3, 深度为3, 的表头是, 表尾是, 的表头是, 表尾是, 目录, 头尾链表存储表示,. 广义表 英語 Generalized List 是一种非线性的数据结构 但如果广义表的每个元素都是原子 它就变成了线性表 广义表广泛地用于人工智能等领域的LISP语言 广义表一般记作 LS a1 a2 an n是它的长度 ai可以是单个元素 原子 也可以是广义表 子表 当广义表非空时 称第一个元素a1为LS的表头 称其余元素组成的表为LS的表尾 注意 表头是元素 可以是原子 也可以是广表 表尾一定是广义表 1 E a E 是一个递归的表 D e a b c d 是多层次的广义表 长度为3 深度为3 例 a a 的表头是 a 表尾是 a a 的表头是 a 表尾是 目录 1 头尾链表存储表示 1 1 存储结构 1 2 基本操作 2 扩展线性链表存储表示 2 1 存储结构 2 2 基本操作 3 参考资料头尾链表存储表示 编辑存储结构 编辑 广义表的头尾链表存储表示 typedef enum ATOM LIST ElemTag ATOM 0 原子 LIST 1 子表 typedef struct GLNode ElemTag tag 公共部分 用于区分原子结点和表结点 union 原子结点和表结点的联合部分 AtomType atom atom是原子结点的值域 AtomType由用户定义 struct struct GLNode hp tp ptr ptr是表结点的指针域 prt hp和ptr tp分别指向表头和表尾 a GList GLNode 广义表类型 基本操作 编辑 广义表的头尾链表存储的基本操作 11个 include func5 1 c void InitGList GList L 创建空的广义表L L NULL void CreateGList GList L SString S 采用头尾链表存储结构 由广义表的书写形式串S创建广义表L 设emp SString sub hsub emp GList p q StrAssign emp 空串emp if StrCompare S emp S L NULL 创建空表 else S不是空串 L GList malloc sizeof GLNode if L 建表结点 exit OVERFLOW if StrLength S 1 S为单原子 只会出现在递归调用中 L gt tag ATOM L gt a atom S 1 创建单原子广义表 else S为表 L gt tag LIST p L SubString sub S 2 StrLength S 2 脱外层括号 去掉第1个字符和最后1个字符 给串sub do 重复建n个子表 sever sub hsub 从sub中分离出表头串hsub CreateGList amp p gt a ptr hp hsub q p if StrEmpty sub 表尾不空 p GLNode malloc sizeof GLNode if p exit OVERFLOW p gt tag LIST q gt a ptr tp p while StrEmpty sub q gt a ptr tp NULL void DestroyGList GList L 销毁广义表L GList q1 q2 if L if L gt tag LIST 删除表结点 q1 L gt a ptr hp q1指向表头 q2 L gt a ptr tp q2指向表尾 DestroyGList amp q1 销毁表头 DestroyGList amp q2 销毁表尾 free L L NULL void CopyGList GList T GList L 采用头尾链表存储结构 由广义表L复制得到广义表T if L 复制空表 T NULL else T GList malloc sizeof GLNode 建表结点 if T exit OVERFLOW T gt tag L gt tag if L gt tag ATOM T gt a atom L gt a atom 复制单原子 else CopyGList amp T gt a ptr hp L gt a ptr hp 递归复制子表 CopyGList amp T gt a ptr tp L gt a ptr tp int GListLength GList L 返回广义表的长度 即元素个数 int len 0 while L L L gt a ptr tp len return len int GListDepth GList L 采用头尾链表存储结构 求广义表L的深度 int max dep GList pp if L return 1 空表深度为1 if L gt tag ATOM return 0 原子深度为0 只会出现在递归调用中 for max 0 pp L pp pp pp gt a ptr tp dep GListDepth pp gt a ptr hp 递归求以pp gt a ptr hp为头指针的子表深度 if dep gt max max dep return max 1 非空表的深度是各元素的深度的最大值加1 Status GListEmpty GList L 判定广义表是否为空 if L return TRUE else return FALSE GList GetHead GList L 生成广义表L的表头元素 返回指向这个元素的指针 GList h p if L 空表无表头 return NULL p L gt a ptr hp p指向L的表头元素 CopyGList amp h p 将表头元素复制给h return h GList GetTail GList L 将广义表L的表尾生成为广义表 返回指向这个新广义表的指针 GList t if L 空表无表尾 return NULL CopyGList amp t L gt a ptr tp 将L的表尾拷给t return t void InsertFirst GL GList L GList e 初始条件 广义表存在 操作结果 插入元素e 也可能是子表 作为广义表L的第1元素 表头 GList p GList malloc sizeof GLNode 生成新结点 if p exit OVERFLOW p gt tag LIST 结点的类型是表 p gt a ptr hp e 表头指向e p gt a ptr tp L 表尾指向原表L L p L指向新结点 void DeleteFirst GL GList L GList e 初始条件 广义表L存在 操作结果 删除广义表L的第一元素 并用e返回其值 GList p L p指向第1个结点 e L gt a ptr hp e指向L的表头 L L gt a ptr tp L指向原L的表尾 free p 释放第1个结点 void Traverse GL GList L void v AtomType 利用递归算法遍历广义表L if L L不空 if L gt tag ATOM L为单原子 v L gt a atom else L为广义表 Traverse GL L gt a ptr hp v 递归遍历L的表头 Traverse GL L gt a ptr tp v 递归遍历L的表尾 扩展线性链表存储表示 编辑存储结构 编辑 广义表的扩展线性链表存储表示 typedef enum ATOM LIST ElemTag ATOM 0 原子 LIST 1 子表 typedef struct GLNode1 ElemTag tag 公共部分 用于区分原子结点和表结点 union 原子结点和表结点的联合部分 AtomType atom 原子结点的值域 struct GLNode1 hp 表结点的表头指针 a struct GLNode1 tp 相当于线性链表的next 指向下一个元素结点 GList1 GLNode1 广义表类型GList1是一种扩展的线性链表 基本操作 编辑 广义表的扩展线性链表存储 的基本操作 13个 include func5 1 c void InitGList GList1 L 创建空的广义表L L NULL void CreateGList GList1 L SString S 采用扩展线性链表存储结构 由广义表的书写形式串S创建广义表L 设emp SString emp sub hsub GList1 p StrAssign emp 设emp L GList1 malloc sizeof GLNode1 if L 建表结点不成功 exit OVERFLOW if StrCompare S emp 创建空表 L gt tag LIST L gt a hp L gt tp NULL else if StrLength S 1 创建单原子广义表 L gt tag ATOM L gt a atom S 1 L gt tp NULL else 创建一般表 L gt tag LIST L gt tp NULL SubString sub S 2 StrLength S 2 脱外层括号 去掉第1个字符和最后1个字符 给串sub sever sub hsub 从sub中分离出表头串hsub CreateGList amp L gt a hp hsub p L gt a hp while StrEmpty sub 表尾不空 则重复建n个子表 sever sub hsub 从sub中分离出表头串hsub CreateGList amp p gt tp hsub p p gt tp void DestroyGList GList1 L 初始条件 广义表L存在 操作结果 销毁广义表L GList1 ph pt if L L不为空表 由ph和pt接替L的两个指针 if L gt tag 是子表 ph L gt a hp else 是原子 ph NULL pt L gt tp DestroyGList amp ph 递归销毁表ph DestroyGList amp pt 递归销毁表pt free L 释放L所指结点 L NULL 令L为空 void CopyGList GList1 T GList1 L 初始条件 广义表L存在 操作结果 由广义表L复制得到广义表T T NULL if L L不空 T GList1 malloc sizeof GLNode1 if T exit OVERFLOW T gt tag L gt tag 复制枚举变量 if L gt tag ATOM 复制共用体部分 T gt a atom L gt a atom 复制单原子 else CopyGList amp T gt a hp L gt a hp 复制子表 if L gt tp NULL 到表尾 T gt tp L gt tp else CopyGList amp T gt tp L gt tp 复制子表 int GListLength GList1 L 初始条件 广义表L存在 操作结果 求广义表L的长度 即元素个数 int len 0 GList1 p L gt a hp p指向第1个元素 while p len p p gt tp return len int GListDepth GList1 L 初始条件 广义表L存在 操作结果 求广义表L的深度 int max dep GList1 pp if L NULL L gt tag LIST amp amp L gt a hp return 1 空表深度为1 else if L gt tag ATOM return 0 单原子表深度为0 只会出现在递归调用中 else 求一般表的深度 for max 0 pp L gt a hp pp pp pp gt tp dep GListDepth pp 求以pp为头指针的子表深度 if dep gt max max dep return max 1 非空表的深度是各元素的深度的最大值加1 Status GListEmpty GList1 L 初始条件 广义表L存在 操作结果 判定广义表L是否为空 if L L gt tag LIST amp amp L gt a hp return OK else return ERROR GList1 GetHead GList1 L 生成广义表L的表头元素 返回指向这个元素的指针 GList1 h p if L L gt tag LIST amp amp L gt a hp 空表无表头 return NULL p L gt a hp gt tp p指向L的表尾 L gt a hp gt tp NULL 截去L的表尾部分 CopyGList amp h L gt a hp 将表头元素复制给h L gt a hp gt tp p 恢复L的表尾 保持原L不变 return h GList1 GetTail GList1 L 将广义表L的表尾生成为广义表 返回指向这个新广义表的指针 GList1 t p if L L gt tag LIST amp amp L gt a hp 空表无表尾 return NULL p L gt a hp p指向表头 L gt a hp p gt tp 在L中删去表头 CopyGList amp t L 将L的表尾拷给t L gt a hp p 恢复L的表头 保持原L不变 return t void InsertFirst GL GList1 L GList1 e 初始条件 广义表存在 操作结果 插入元素e 也可能是子表 作为广义表L的第1元素 表头 GList1 p L gt a hp L gt a hp e e gt tp p void DeleteFirst GL GList1 L GList1 e 初始条件 广义表L存在 操作结果 删除广义表L的第一元素 并用e返回其值 if L amp amp L gt a hp e L gt a hp L gt a hp e gt tp e gt tp NULL else e L void Traverse GL GList1 L void v AtomType 利用递归算法遍历广义表L GList1 hp if L L不空 if L gt tag ATOM L为单原子 v L gt a atom hp NULL else L为子表 hp L gt a hp Traverse GL hp v Traverse GL L gt tp v 参考资料 编辑 崔巍 何玉洁 郁红英 数据库技术教程 三级 清华大学出版社 2005 P59 ISBN 9787302103769 使用 accessdate 需要含有 url 帮助 取自 https zh wikipedia org w index php title 广义表 amp oldid 60464910, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。